Известно что для списков на каждый элемент приходится по одному или двум дополнительных указателей.
Т.е. на 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 эффективны только для векторов.
Здравствуйте, c-smile, Вы писали:
CS>То что список как структура данных имеет свои уникальные свойства — понятно и никем не оспаривается. CS>Конечно же есть *алгоритмы* для которых требуются такие уникальные свойства.
Есть еще одна штука большинство алгоритмов на списках легко обобщаются на деревья и более сложные структуры
данных. Те же B-Tree T-Tree тоже во многом списки.
CS>Проблема в том что неинтрузивные списки как коллекции не эффективны. А с интрузивными списками концепция итераторов как-то не вяжется.
Есть вполне эффективные реализации списков.
CS>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
Угу итераторы уже всеми кому не лень критикуются и в общем по делу. Всякие ranges, enums и т. п. лучше.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, Ikemefula, Вы писали:
I>>В листе точно так же.
FR>В нормальных кошерных списках не так. FR>Явовские и шарповские коллеции не списки а недоразумения
В этих языках нет указателей, поэтому, наверное, такая "хитрая"
замена...
T>List нужен когда необходимо часто вставлять и удалять элементы. У вектора эта операция будет приводить T>в среднем к копированию половины вектора при каждой операции, что может оказаться гораздо медленнее.
это вы все проблемы std::vector, здесь основной недостаток, что std::vector, хочет вызывать операцию копирования для каждого своего элемента. Это долго, т.к. непозволяет массово копировать элементы. std::vector слишком абстрактный — содан для любых типов элементов. Если хранимый элемент "простой", т.е. ему достаточно просто скопировать свою занимаемую память, то для очень больших массивов данных std::vector неэффективен.
Я сделал свои вектора, которые ненастолько "абстрактны" как std, но зато позволяют копировать свое содержимое как memmove: сдвигаем область памяти на размер ячейки умноженный на длину "хвоста" вправо, что-то вроде: "memmove( base + (insert_pos)*size_item, base + (insert_pos+1)*size_item, (len-insert_pos)*size_item );"
Операция memcpy/memmove очень быстра, даже несколько гигабайт копируются за микросекунды. Вставка в прозвольное положение для такого вектора примерно как в std::list.
Здравствуйте, shrecher, Вы писали:
S>Операция memcpy/memmove очень быстра, даже несколько гигабайт копируются за микросекунды. Вставка в прозвольное положение для такого вектора примерно как в std::list.
Чуть чуть попадаем в swap и микросекунды превращаются в десятки секунд
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, shrecher, Вы писали:
S>>Операция memcpy/memmove очень быстра, даже несколько гигабайт копируются за микросекунды. Вставка в прозвольное положение для такого вектора примерно как в std::list.
FR>Чуть чуть попадаем в swap и микросекунды превращаются в десятки секунд
Все лучше чем с list который вообще может при *каждом* обращении к элементу в swap ходить.
Здравствуйте, shrecher, Вы писали:
S>Здравствуйте, tripol, Вы писали:
S>Операция memcpy/memmove очень быстра, даже несколько гигабайт копируются за микросекунды. Вставка в прозвольное положение для такого вектора примерно как в std::list.
Хочу несколько поправить. Два гигабайта в двухканальном режиме дают минимальное время
2(объем данных) / 19.2Гб/c * 2(двухканальный режим) / 2(операция чтения + записи) = 0.1секунды
При 100 операциях понадобится времени около 5 секунд, при тысяче — 50 секунд и т.д.
FR>>Чуть чуть попадаем в swap и микросекунды превращаются в десятки секунд
CS>Все лучше чем с list который вообще может при *каждом* обращении к элементу в swap ходить.
В данном случае (копировании гигабайт при простой вставке) хуже, list в худшем случае поднимет пару страничек
и вполне уложится в микросекунды, а контейнер с memmove еще пару минут погоняет диск
Ну и правильный аллокатор для любых случаев ухода в swap сделает list лучше чем массив.
S>это вы все проблемы std::vector, здесь основной недостаток, что std::vector, хочет вызывать операцию копирования для каждого своего элемента. Это долго, т.к. непозволяет массово копировать элементы. std::vector слишком абстрактный — содан для любых типов элементов. Если хранимый элемент "простой", т.е. ему достаточно просто скопировать свою занимаемую память, то для очень больших массивов данных std::vector неэффективен.
S>Я сделал свои вектора, которые ненастолько "абстрактны" как std, но зато позволяют копировать свое содержимое как memmove: сдвигаем область памяти на размер ячейки умноженный на длину "хвоста" вправо, что-то вроде: "memmove( base + (insert_pos)*size_item, base + (insert_pos+1)*size_item, (len-insert_pos)*size_item );"
S>Операция memcpy/memmove очень быстра, даже несколько гигабайт копируются за микросекунды. Вставка в прозвольное положение для такого вектора примерно как в std::list.
Боюсь , заблуждаетесь. POD типы могут копирироваться не медленее memmove (разве что на экстра битом компиляторе может быть разница.) Дизайн вектора не тянет за собой дополнительных расходов, только при неправильном использовании.
CS>Проблема в том что неинтрузивные списки как коллекции не эффективны.
А конкретно? уточните.
CS> А с интрузивными списками концепция итераторов как-то не вяжется.
С чего бы это ?
CS>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
iterators — как раз, абстракция которая наиболее эффективна. Эфективнее может быть только инкупсуляция перебора элементоа внутрь контейнера
Здравствуйте, tripol, Вы писали:
T>В этих языках нет указателей, поэтому, наверное, такая "хитрая" T>замена...
Если очень хочется, то в .Net есть LinkedList
Здравствуйте, c-smile, Вы писали:
CS> Зачем нужны эти list<>?
Т.е. зачем нужны неинтрузивные списки?
Потому что они применимы абсолютно к любому типу (например, int, string, указатели). Поэтому если тебе просто нужен список — берешь std::list и не паришься.
Интрузивные контейнеры — это оптимизация (в данном случае — по памяти).
Которая, естественно, небесплатна: ты платишь значительным ухудшением дизайна класса и заодно сужаешь возможности по его использованию. Например, твой класс не может быть членом одновременно нескольких интрузивных списков, если ты, конечно, не предусмотришь next1, next2 и т.д.
И которая, когда преждевременная, сам знаешь куда должна идти.
CS>А нафига тогда эта вселенская абстракция по имени iterator?
а итераторы никакого отношения к интрузивности/неинтрузивности контейнеров не имеют, это ортогональная концепция.
Равно как и диапазоны (ranges).
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, c-smile, Вы писали:
FR>>>Чуть чуть попадаем в swap и микросекунды превращаются в десятки секунд
CS>>Все лучше чем с list который вообще может при *каждом* обращении к элементу в swap ходить.
FR>В данном случае (копировании гигабайт при простой вставке) хуже, list в худшем случае поднимет пару страничек FR>и вполне уложится в микросекунды, а контейнер с memmove еще пару минут погоняет диск
Давай начнем с того что коллекции размером с гигабайт это уже будет "переход колличества в качество" —
требуют принципиально других и структур данных и алгоритмов.
Т.е. ни о какой дилемме vector<> vs. list<> тут вообще речи нет.
Здравствуйте, c-smile, Вы писали:
CS>Давай начнем с того что коллекции размером с гигабайт это уже будет "переход колличества в качество" — CS>требуют принципиально других и структур данных и алгоритмов. CS>Т.е. ни о какой дилемме vector<> vs. list<> тут вообще речи нет.
Это да, но при этом почти наверняка будут использоваться деревья, то есть родня списков.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, Ikemefula, Вы писали:
I>>Граждане сиплюсники !
I>>Указывайте пожалуйста что речь о С++.
FR>Наоборот гражданам явщикам и нетчикам надо указывать что они называют списком убогий массив с ограничениями
На самом деле это в С++ какое-то неправильное название. List — это общее название набора неких значений. А вот Linked list — конкретная структура данных. Почему в STL doubly-linked list назвали просто list для меня загадка.
Здравствуйте, _DAle_, Вы писали:
_DA>На самом деле это в С++ какое-то неправильное название. List — это общее название набора неких значений. А вот Linked list — конкретная структура данных. Почему в STL doubly-linked list назвали просто list для меня загадка.
Первым языком программирования использующим списки был Lisp в нем они были именно линейными связными, так что C++ как и функциональные языки идет в русле традиции, а всякие новомодные языки в количестве двух штук ее нарушают
Здравствуйте, c-smile, Вы писали:
CS> Зачем нужны эти list<>?
Удаление/добавление за O(1) при имеющемся итераторе, splice за O(1) (не везде), отсутствие инвалидации других итераторов после удаления/вставки... Как это ни странно звучит, но как раз list иногда используют вместо vector для экономии памяти. Так как вектор может выделить примерно в два раза больше памяти, чем нужно, при расширении.
CS>Если реально итерируемыми контейнерами являются vector<> и list<>, list<> уходит в небытие — остается vector<>.
Вообще еще и deque есть, который тоже иногда используется.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, c-smile, Вы писали:
CS>>Проблема в том что неинтрузивные списки как коллекции не эффективны. M>А конкретно? уточните.
Давай рассмотрим практическую задачу.
Ну скажем устройство DOM элемента в HTML.
namespace dom
{
class node { ... }
class element: public node
{
collection<node*> children; /* все дети */
collection<node*> visuals; /* отображаемые дети */
}
}
Если collection это list<> то на каждый элемент в children и visuals создается
дополнительно list item в размере 3х указателей.
В случае когда collection<> это vector<> то на каждый элемент имеем один указатель — элемент массива.
CS>> А с интрузивными списками концепция итераторов как-то не вяжется. M>С чего бы это ?
В случае интрузивного списка node вверху будет выглядеть как:
class node
{
node* next; //
node* prev; // children list
node* visual_next; //
node* visual_prev; // visuals list
}
Я честно говоря затрудняюсь представить generic механизм интрузивных списков допускающий
one element — N lists комбинации.
CS>>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
M>iterators — как раз, абстракция которая наиболее эффективна. Эфективнее может быть только инкупсуляция перебора элементоа внутрь контейнера
В случае моего примера:
Итерация по элементам в случае vector<> это итерация по массиву + 1 переход по указателю.
Итерация по элементам в list<> это 2 перехода по указателям.
Т.е. с точки зрения архитектуры процессоров перебор vector<> эффективнее перебора list<>.
Т.е. для итерирования вектор наиболее подходит — для него эта коцепция является "родной".
Для остальных типов коллекций итератор это вельми дорогая и как правило нетривиальная штука.
Маленькое уточнение , вы не ошиблись , может так ?
class node
{
node* next; //
node* prev; // children list current
node* visual_next; //
node* visual_prev; // visuals list current
node* children_head; // children list subnodes head
node* visual_head; // visuals list subnodes head
}
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, tripol, Вы писали:
FR>>>В NET указатели есть. T>>В "unsafe code" правда.
K>А где указатели есть в safe code?
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, tripol, Вы писали:
FR>>>В NET указатели есть. T>>В "unsafe code" правда.
K>А где указатели есть в safe code?
Малость не понял вопрос.
Хрен его знает. В C++ понятия safe code нет, и оно ему не нужно.
Здравствуйте, c-smile, Вы писали:
CS>То что список как структура данных имеет свои уникальные свойства — понятно и никем не оспаривается. CS>Конечно же есть *алгоритмы* для которых требуются такие уникальные свойства. CS>Проблема в том что неинтрузивные списки как коллекции не эффективны. А с интрузивными списками концепция итераторов как-то не вяжется. CS>Тогда вся концепция итераторов как обобщения выглядит весьма ограниченной — фактически iterators эффективны только для векторов.
Ну, так может дело не в списках, а в iterators С++?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Ikemefula, Вы писали:
I>А что можно предложить взамен ?
Более простые итераторы которые позволяют только перебрать элементы по порядку. Как я понимаю аналогичную фичу в В назвали диапазонами. А в дотнете она известна под идиотским императивным (но тем не менее вполне приемлемым) интерфейсом IEnumerabl<T>.
I>Итератор это всего лишь отделение обхода от структуры.
Итераторы С++ излишне переусложнены.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Ikemefula, Вы писали:
I>>А что можно предложить взамен ?
VD>Более простые итераторы которые позволяют только перебрать элементы по порядку. Как я понимаю аналогичную фичу в В назвали диапазонами. А в дотнете она известна под идиотским императивным (но тем не менее вполне приемлемым) интерфейсом IEnumerabl<T>.
I>>Итератор это всего лишь отделение обхода от структуры.
VD>Итераторы С++ излишне переусложнены.
Для пользователя идентично работе с указателями. Для Random итератора
доступны все операторы, которые применимы к указателю, в том числе
адресная арифметика. Для Forward итератора: ++, * и еще может какие.
Что бы этого достичь, конечно нужно больше кода.
Не вижу сложности в их использовании.
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, tripol, Вы писали:
K>>>А где указатели есть в safe code? T>>http://msdn.microsoft.com/en-us/library/t2yzs44b.aspx CC>Статья там называется "Unsafe Code and Pointers (C# Programming Guide)"
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, minorlogic, Вы писали:
M>>Здравствуйте, c-smile, Вы писали:
CS>>>Проблема в том что неинтрузивные списки как коллекции не эффективны. M>>А конкретно? уточните.
CS>Давай рассмотрим практическую задачу. CS>Ну скажем устройство DOM элемента в HTML.
CS>
CS>namespace dom
CS>{
CS> class node { ... }
CS> class element: public node
CS> {
CS> collection<node*> children; /* все дети */
CS> collection<node*> visuals; /* отображаемые дети */
CS> }
CS>}
CS>
CS>Если collection это list<> то на каждый элемент в children и visuals создается CS>дополнительно list item в размере 3х указателей. CS>В случае когда collection<> это vector<> то на каждый элемент имеем один указатель — элемент массива.
Ты не совсем прав. vector резервирует память для амортизации push_back, т.е. на самом деле у тебя будет 1.5-2 кратный перерасход памяти в худшем случае. Т.е. быстродействие покупается ценой расхода памяти.
