Преимущества slist над вектором?

Question

Что мне нужно - это просто динамически растущий массив. Мне не нужен произвольный доступ, и я всегда вставляю его в конец и читаю его от начала до конца.

slist кажется первым выбором, потому что он обеспечивает только то, что мне нужно. Однако я не могу сказать, какую выгоду я получаю, используя слайст вместо вектора. Кроме того, несколько материалов, которые я прочитал о STL, говорят: «векторы, как правило, наиболее эффективны во времени для доступа к элементам и добавления или удаления элементов с конца последовательности». Поэтому мой вопрос: для моих нужд, слэст действительно лучший выбор, чем вектор? Заранее спасибо.

Answer 1

Для начала slist является нестандартным.

Для вашего выбора связанный список будет медленнее, чем вектор, рассчитывать на него. Есть две причины, способствующие этому:

1. Прежде всего, местонахождение кеша; векторы хранят свои элементы линейно в ОЗУ, что облегчает кэширование и предварительную выборку.
2. Во-вторых, добавление к связанному списку включает динамические распределения, которые добавляют большие накладные расходы. Напротив, векторы большую часть времени делают не необходимо выделить память.

Однако, std::deque, вероятно, будет еще быстрее. In-depth performance analysis показал, что, несмотря на предвзятое отношение, std::deque почти всегда превосходит std::vector в производительности (если не требуется никакого произвольного доступа) из-за его улучшенной (выделенной) стратегии распределения памяти.

Answer 2

Да, если вы всегда читаете начало до конца, slist (связанный список) звучит как путь. Возможным исключением является то, что вы будете одновременно добавлять большое количество элементов в конец. Тогда вектор может быть лучше, если вы используете резерв соответствующим образом.

Конечно, профиль, чтобы быть уверенным, что это лучше для вашего приложения.

Answer 3

Я предполагаю, что вы имеете в виду std :: list by "slist". Векторы хороши, когда вам нужен быстрый, случайный доступ к последовательности элементов, с гарантированной непрерывной памятью и быстрым последовательным чтением (IOW, от начала до конца). Списки хороши, когда вам нужна быстрая (постоянная) вставка или удаление элементов в начале или конце последовательности, но не заботятся о производительности произвольного доступа или последовательного чтения.

Причина разницы в том, как они реализованы. Векторы реализуются внутри как массив элементов, которые необходимо перераспределить, когда его размер/емкость достигается при добавлении элемента. Списки реализуются как дважды связанный список, что может привести к пропуску кэша для последовательного чтения. Для списков случайного доступа для списков также требуется сканирование с первого (или последнего) элемента в списке до тех пор, пока он не найдет объект, который вы запрашиваете.

Answer 4

Мэтт Аустерн (автор «Generic Programming and STL» и общий гуру C++) является сильным сторонником одноуровневых списков для включения в предстоящий стандарт C++; см. его презентацию в http://www.accu-usa.org/Slides/SinglyLinkedLists.ppt и его длинную статью в http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2543.htm для более подробной информации, включая обсуждение компромиссов, которые могут помочь вам в выборе этой структуры данных. (Обратите внимание, что в настоящее время предлагается имя forward_list, хотя slist - это то, как это традиционно называлось в SGI STL & других популярных библиотеках).

Answer 5

Я буду второй (или, может быть, третий ...) мнение, что std::vector или std::deque выполнит эту работу. Единственное, что я добавлю, это несколько дополнительных факторов, которые должны определять решение между std::vector<T> и std::list<T>. Они имеют много общего с характеристиками T и с какими алгоритмами вы планируете использовать.

Первый - память наверху. Std::list является контейнером на основе узлов, поэтому, если T является примитивным типом или относительно небольшим пользовательским типом, тогда накладные расходы на память связи на узле могут быть незначительными - считайте, что std::list<int>, вероятно, будет использовать хранилище не менее 3 * sizeof(int) для каждый элемент, тогда как std::vector будет использовать только хранилище sizeof(int) с небольшими заголовками заголовка. Std::deque похож на std::vector, но имеет небольшие накладные расходы, которые линейны до N.

Следующая проблема - стоимость строительства копии. Если T(T const&) вообще стоит дорого, то избегайте std::vector<T>, так как это приводит к появлению множества копий при увеличении размера вектора. Здесь std::deque<T> является победителем и std::list<T> также является соперником.

Последним вопросом, который обычно определяет решение о типе контейнера, является то, могут ли ваши алгоритмы работать с ограничениями аннулирования итератора std::vector и std::deque. Если вы будете много манипулировать элементами контейнера (например, сортировать, вставлять посередине или перетасовывать), тогда вам может понадобиться наклоняться в сторону std::list, поскольку для управления порядком требуется немного больше, чем сброс нескольких указателей привязки.

Answer 6

Звучит неплохо для std :: deque для меня. Он обладает преимуществами памяти, такими как смежное выделение памяти для каждой «плиты» (полезно для кэшей ЦП), никаких накладных расходов для каждого элемента, такого как std :: list, и ему не нужно перераспределять весь набор как std :: vector делает. Подробнее о std::deque here