Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
Т.е. на list<int> в 10 элементов требует памяти 120 байт.
Тогда как для vector<int> 40 байт.
В реальных задачах элементы могут участвовать в нескольких списках одновременно что усугубляет проблему потребления памяти в списках.
Я тут проанализирвал все свои проекты — на примерно 45 vector<>/hash_map<> коллекций приходится один случай использования l2element<> ( интрузивный список ).
У вектора можно спросить size, его можно эффективно отсортировать. С вектором можно использовать ranges. И прочие радости жизни.
Философические вопросы:
Зачем нужны эти list<>?
Допуская что в некоторых случаях list<> могут быть полезны зададимся вопросом:
А нафига тогда эта вселенская абстракция по имени iterator?
Если реально итерируемыми контейнерами являются vector<> и list<>, list<> уходит в небытие — остается vector<>.
А для него есть очень эффективные и удобные ranges. А для всех остальных случаев перебора можно использовать абстракцию stream<T>.
Здравствуйте, c-smile, Вы писали:
CS>Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
CS>Т.е. на list<int> в 10 элементов требует памяти 120 байт. CS>Тогда как для vector<int> 40 байт.
Ну список не обязательно реализовывать канонически, штуки типа http://en.wikipedia.org/wiki/VList по потреблению памяти близки к вектору.
Здравствуйте, c-smile, Вы писали:
CS>Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
CS> Зачем нужны эти list<>?
CS>Допуская что в некоторых случаях list<> могут быть полезны зададимся вопросом:
CS> А нафига тогда эта вселенская абстракция по имени iterator?
CS>Если реально итерируемыми контейнерами являются vector<> и list<>, list<> уходит в небытие — остается vector<>. CS>А для него есть очень эффективные и удобные ranges. А для всех остальных случаев перебора можно использовать абстракцию stream<T>.
List нужен когда необходимо часто вставлять и удалять элементы. У вектора эта операция будет приводить
в среднем к копированию половины вектора при каждой операции, что может оказаться гораздо медленнее.
iterator используется для одинаковой работы с контейнерами существующими алгоритмами.
По большому счету с помощью stream нельзя запомнить позицию и вернуться к ней.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, c-smile, Вы писали:
CS>>Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
CS>>Т.е. на list<int> в 10 элементов требует памяти 120 байт. CS>>Тогда как для vector<int> 40 байт.
FR>Ну список не обязательно реализовывать канонически, штуки типа http://en.wikipedia.org/wiki/VList по потреблению памяти близки к вектору.
Ну дык в .NET List<> это вообще vector<>. Там еще добавляется требование минимизации кол-ва указателей — меньше работы GC.
Собственно я об этом и вопрошаю — на кой они сдались эти списки когда есть гораздо более эффективные конструкции?
Единственный practical use case для списков это интрузивные списки. А для них итерация это do ... while(pel = pel->next); — т.е. next есть свойство самого элемента ибо коллекции как таковой нет.
CS>Ну дык в .NET List<> это вообще vector<>. Там еще добавляется требование минимизации кол-ва указателей — меньше работы GC.
CS>Собственно я об этом и вопрошаю — на кой они сдались эти списки когда есть гораздо более эффективные конструкции? CS>Единственный practical use case для списков это интрузивные списки. А для них итерация это do ... while(pel = pel->next); — т.е. next есть свойство самого элемента ибо коллекции как таковой нет.
Ну еще есть во всяком случае в C++ такое свойство что итераторы на список не умирают при изменении списка, чего не
скажешь об итераторах на вектор.
А так тоже правило от Александреску "используй по умолчанию vector" в целом верно, но всегда могут найтись задачи для которых
лучше подходит list.
Здравствуйте, c-smile, Вы писали:
CS>Вот такие вот мои мысли. Обсудим?
У вектора есть одно неприятное свойство — он не дает строгой гарантии безопасности при возникновении исключений, а только базовую(вставка элемента в контейнер). Там где нужно обеспечить строгую гарантию будут накладные расходы достаточно большие(полное копирование вектора и своп)
Здравствуйте, c-smile, Вы писали:
CS>Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
CS>Т.е. на list<int> в 10 элементов требует памяти 120 байт. CS>Тогда как для vector<int> 40 байт.
CS>В реальных задачах элементы могут участвовать в нескольких списках одновременно что усугубляет проблему потребления памяти в списках. CS>Я тут проанализирвал все свои проекты — на примерно 45 vector<>/hash_map<> коллекций приходится один случай использования l2element<> ( интрузивный список ).
CS>У вектора можно спросить size, его можно эффективно отсортировать. С вектором можно использовать ranges. И прочие радости жизни.
CS>Философические вопросы:
CS> Зачем нужны эти list<>?
CS>Допуская что в некоторых случаях list<> могут быть полезны зададимся вопросом:
CS> А нафига тогда эта вселенская абстракция по имени iterator?
CS>Если реально итерируемыми контейнерами являются vector<> и list<>, list<> уходит в небытие — остается vector<>. CS>А для него есть очень эффективные и удобные ranges. А для всех остальных случаев перебора можно использовать абстракцию stream<T>.
CS>Вот такие вот мои мысли. Обсудим?
В списках хорошо хранить объекты работающие с ресурсами ОС или железа. Например, рекордсеты БД, у которых деструктор закрывает соединение и т.п.
Здравствуйте, Centaur, Вы писали:
C>Здравствуйте, c-smile, Вы писали:
CS>> Зачем нужны эти list<>?
C>Списки не инвалидируют итераторы/указатели/ссылки при вставке и удалении элементов. Списки можно splice’ить.
То что список как структура данных имеет свои уникальные свойства — понятно и никем не оспаривается.
Конечно же есть *алгоритмы* для которых требуются такие уникальные свойства.
Проблема в том что неинтрузивные списки как коллекции не эффективны. А с интрузивными списками концепция итераторов как-то не вяжется.
Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
Здравствуйте, tripol, Вы писали:
T>List нужен когда необходимо часто вставлять и удалять элементы. У вектора эта операция будет приводить T>в среднем к копированию половины вектора при каждой операции, что может оказаться гораздо медленнее.
Здравствуйте, c-smile, Вы писали:
CS>Ну дык в .NET List<> это вообще vector<>. Там еще добавляется требование минимизации кол-ва указателей — меньше работы GC.
CS>Собственно я об этом и вопрошаю — на кой они сдались эти списки когда есть гораздо более эффективные конструкции?
У списков есть большое преимущество — алгоритмическая сложность некоторых операций.
Кроме того, у списков есть большой недостаток — алгоритмическая сложность некоторых операций.
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, tripol, Вы писали:
T>>List нужен когда необходимо часто вставлять и удалять элементы. У вектора эта операция будет приводить T>>в среднем к копированию половины вектора при каждой операции, что может оказаться гораздо медленнее.
I>В листе точно так же.
Здравствуйте, tripol, Вы писали:
T>>>List нужен когда необходимо часто вставлять и удалять элементы. У вектора эта операция будет приводить T>>>в среднем к копированию половины вектора при каждой операции, что может оказаться гораздо медленнее.
I>>В листе точно так же.
T>Вы про C++-шный std::list<> ?
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, Centaur, Вы писали:
C>>Здравствуйте, c-smile, Вы писали:
CS>>> Зачем нужны эти list<>?
C>>Списки не инвалидируют итераторы/указатели/ссылки при вставке и удалении элементов. Списки можно splice’ить.
CS>То что список как структура данных имеет свои уникальные свойства — понятно и никем не оспаривается. CS>Конечно же есть *алгоритмы* для которых требуются такие уникальные свойства. CS>Проблема в том что неинтрузивные списки как коллекции не эффективны. А с интрузивными списками концепция итераторов как-то не вяжется. CS>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
Ну вообще то концепция итераторов не ограничивается списком и вектором. Итераторы эффективны там где нужно делать обход сложной структуры данных.
Например, сбалансированного дерева.
Здравствуйте, c-smile, Вы писали:
CS>Проблема в том что неинтрузивные списки как коллекции не эффективны. А с интрузивными списками концепция итераторов как-то не вяжется.
А что можно предложить взамен ?
Итератор это всего лишь отделение обхода от структуры.
CS>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
