Когда вообще используется этот List?

Question

[Junior007]

Пытаюсь понять преимущества структуры std::list, вроде как написано, что она способна быстро выполнять вставку в середину, но протестив на Ideone: ideone.com/oFQeXE
List - Явный аутсайдер. Жрет кучу памяти, заполняется в разы медленней вектора, так еще и саму вставку выполняет долго.

Vector - 0.2 sec (полное выполнение за: 0.42)
List - 0.11 sec (2.44)

Когда же тогда он применяется?

Answer 1

[Vitaly]

Ваш эксперимент далёк от идеала. Сделайте примерно 1000 одинаковых экспериментов и возьмите среднее + если мы измеряете время вставки, то ненадо учитывать время заполнения контейнера. Надо вызвать resize у вектора и листа, заполнить их (не push_back'ом), а потом измерить время вставки, и так примерно 1000 раз, каждый раз с новым вектором и листом. И время замерять, после того как вы получили итератор на нужное место в листе, а не до. Т.е. только время вставки.
Про оптимизации пока умолчим.

Применяется лист в зависимости от данных и используемых алгоритмов. Где актуальны приемущества листа (читайте документацию, какие), там и применяется. + еще надо уметь пользоваться контейнерами (а то потом начнется про то что, например, вектор работает медленно и памяти много жрет или что в листе долгий доступ по индексу).

PS Время так можно замерять: en.cppreference.com/w/cpp/chrono

Comments

[Vitaly]

Ринат Велиахмедов: Можно, но тогда код заполнения не такой универсальный получится, т.к у листа такого метода нет, как я помню.

[Vitaly]

Ринат Велиахмедов: Эм... У нас с вами разные версси доков похоже. В моей версии метода reserve у листа нет, да и он лишен смысла, если подумать, т.к. для стедешного листа это не актуально совсем по понятным причинам. Другое дело QList, мб вы с ним спутали?

Answer 2

[Rou1997]

У меня ни тот, ни другой не применяется, я использую System.Collections.Generic.List, TList или QList, еще NewStringUTF, а старье "раритет" не нужен когда у меня все равно в проекте задействовано что-то более современное и удобное, а единственное преимущество STL-"раритетов" для меня кроссплатформенность и независимость от библиотек, тогда из этих 2 для меня лучше std::vector т.к. поддерживает оператор [], а вообще крайне редко такое требуется, и я все это могу объяснить своими практическими задачами на работе, а у вас преимущества похоже просто "из пальца высосаны", так что вопрос не имеет смысла, объясните зачем вам такое быстродействие?

Comments

[Junior007]

Хм, я верно понял, что Вы библиотеки для C# приводите?)

[Rou1997]

Junior007: Нет, неверно, C# это вам не C++ чтобы у него столько библиотек или классов было, первый класс для C#, второй для Delphi и C++ Builder, третий для C++ для Qt, четвертый для C++ для JNI и - внезапно - для arm ассемблера!

Answer 3

[Алексей Гриченко]

У вас получился тест на линейное заполнение контейнера. Одна вставка в середину на результаты не повлияет и разницы между list и vector вы не увидите. Попробуйте вставлять элементы в начало контейнера - картинка будет совсем другой.

Comments

[Junior007]

Нет, я закомментировал сначала участки кода, которые производят вставку, получалось так:
List (заполнение) ~ 2.00 sec
List (Вставка) ~ 2.11 sec

Vector (З) ~ 0.4 sec
Vector (В) ~ 0.6 sec

[Алексей Гриченко]

Ну у вас и получилось, что вставка в список в два раза быстрее (0.1 против 0.2). Хотя правильнее делать многократную вставку и сравнивать среднее время. Примерно как описано ниже.