Здравствуйте, 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
}
