Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Универсальный список  (Прочитано 7186 раз)
0 Пользователей и 1 Гость смотрят эту тему.
eugrita
Помогающий

ru
Offline Offline

« : 03-12-2009 09:51 » 

При проектировании списка его элементом обычно является некая структура данных с полями, S1.
А далее определяется вспомогательная структура с членом-ссылкой на структуру данных
struct S2 {
  struct S1 el;
  S2 * next;
               };
(c разновидностями для 2-направленных списков)
Можно ли как-то может за счет шаблонов или typedef или еще как добиться
более универсального определения структуры S2 чтобы она не зависела от видов полей S1 ?
Отдельно вопрос для С и отдельно для С++
Записан
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 03-12-2009 10:05 » 

В C++ можно почти полностью, что и иллюстрирует та же библиотека STL. Единственное, поскольку помещение в список в случае хранения по значению требует копирования элементов, то реализация шаблонного списка неизбежно налагает требования на способ копирования элементов (скажем, std::auto_ptr-ы в std::vector складывать - плохая идея).

Другой подход - чистый ОО, когда в список можно положить данные любого типа, наследованного от некоторого базового класса. Такой подход иллюстрируют, например, Java и .NET. Теоретически, ничто не мешает в C++ сделать так же. Хотя вариант трудоёмкий и полный недостатоков.

На C, как мне кажется, можно пойти таким путём: каким-либо единым образом передавать информацию о размере структуры S1. Т.е., примерно так, как это делает, скажем, Microsoft для поддержки разных версий одного типа структуры: в обязательном заголовке структуры есть поле size, которое для каждой конкретной структуры заполняется с помощью sizeof, что позволяет работать с разными структурами, учитывая их размер.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 03-12-2009 10:05 » 

eugrita, для C++ существует STL. Правда, для каждого типа S1 надо будет объявить новый тип S2.

Код:
#include <list>

typedef struct _my_struct_t
{
} my_struct_t;

typedef std::list<my_struct_t> my_struct_list_t;

Для C шаблоны не применимы, но задачу можно решить макросами.
Мой любимый пример - списки в ядре Linux. См. файл include/linux/list.h в исходниках ядра.
« Последнее редактирование: 03-12-2009 10:07 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #3 : 03-12-2009 10:08 » 

Конечно можно:

1. Как уже упомянуто в вопросе - шаблон (так уже собственно организованы STL списки)

2. Можно сделать список жёстко заданного типа, например, CMyListObject, который содержит поля-указатели CMyListObject *Prev; CMyListObject *Next; и является родительским классом для всех производных типов, которые могут быть организованы в список. Можно использовать множественное наследование.

Лично я предпочитаю первый вариант.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
eugrita
Помогающий

ru
Offline Offline

« Ответ #4 : 03-12-2009 11:13 » 

Прочел все ответы. Может что недопонял, но даже в STL такой код
struct S1 {
 ...
               };
list< S1 >sp;
ничуть не приближает к ответу на заданный вопрос
так как предполагает определение жесткого типа перед вызовом конструктора list из STL
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #5 : 03-12-2009 11:40 » 

eugrita, а как ты собираешься наставлять компутер на путь истинный, не создав своего типа ? Как ты себе это представляешь ? Улыбаюсь
Записан

eugrita
Помогающий

ru
Offline Offline

« Ответ #6 : 03-12-2009 12:39 » 

это то понятно.непонятно другое.
можно наверно  сделать класс и наследуемые - это как из тяжелой пушки по воробьям
Меня интересует вопрос , возможно ли и какими средствами, чтобы структура данных в списке
была любая, в том числе и разного sizeof  и при этом список не переписывался. Конечно можно при каждом пользовании впихивать новую структуру -элемент данных. Но тогда заодно придется переписывать метод ввода в нее add.
Может как-то за счет перегрузки (или класса с перегруженными методами)?

Прим. Наверное этот вопрос при наличии STL почти не имеет смысла ведь создание списка делается 1 оператором а вот как без STL, ручками?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #7 : 03-12-2009 12:42 » 

макрос
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 03-12-2009 13:54 » 

А какова, собственно, цель? Если нужно сделать список как единственный тип, способный хранить "что угодно", то это решение само по себе плохо поддерживается C/C++.

Проблемы начинаются уже с того момента, что в C/C++ памятью управляет программист. В отличие от высокоуровневых языков со счётчиками ссылок и сборщиком мусора, типа Java, Python или Lisp.

Соответственно, без счётчиков ссылок уже не так просто помещать абы что в списки: требуется копировать данные или помещать указатели. С указателями возникает проблема контроля времени жизни объекта, а с самими объектами - проблема копирования, которая в условиях жёсткой типизации и ручного управления памятью не имеет (насколько я знаю) универсальных решений.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 03-12-2009 14:26 » 

eugrita, для всякой всячины в едином списке тебе все равно потребуется общая заглушка: базовый класс класс или структура в начале каждого объекта (в которой будет информация о типе объекта). И хранить в списке придется указатели, а не сами объекты.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
eugrita
Помогающий

ru
Offline Offline

« Ответ #10 : 03-12-2009 19:43 » 

Cпасибо. примерно понятно
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines