[c++] Как я могу эффективно выбрать контейнер стандартной библиотеки в C ++ 11?


1 Answers

Мне нравится ответ Маттиу, но я собираюсь переформулировать блок-схему следующим образом:

Когда НЕ использовать std :: vector

По умолчанию, если вам нужен контейнер с материалом, используйте std::vector . Таким образом, каждый другой контейнер оправдан, предоставляя некоторую функциональность, альтернативную std::vector .

Конструкторы

std::vector требует, чтобы его содержимое было конструктивным, поскольку оно должно быть в состоянии перемешать элементы вокруг. Это не страшное бремя для размещения на содержании (обратите внимание, что конструкторы по умолчанию не требуются , благодаря emplace и т. Д.). Однако большинство других контейнеров не требуют какого-либо конкретного конструктора (опять же, благодаря emplace ). Поэтому, если у вас есть объект, где вы абсолютно не можете реализовать конструктор перемещения, вам придется выбрать что-то еще.

std::deque будет общей заменой, имеющей многие свойства std::vector , но вы можете вставлять только в обоих концах deque. Вставки в середине требуют перемещения. В std::list не содержится никаких требований к его содержимому.

Потребности

std::vector<bool> is ... not. Ну, это стандарт. Но это не vector в обычном смысле, так как операции, которые обычно разрешают std::vector , запрещены. И это, безусловно , не содержит bool s .

Поэтому, если вам требуется реальное vector поведение из контейнера bool s, вы не получите его из std::vector<bool> . Таким образом, вам придется сделать это с помощью std::deque<bool> .

поиск

Если вам нужно найти элементы в контейнере, а тег поиска не может быть просто индексом, вам может потребоваться отказаться от std::vector в пользу set и map . Обратите внимание на ключевое слово « may »; сортируемый std::vector иногда является разумной альтернативой. Или карта flat_set/map , которая реализует отсортированный std::vector .

В настоящее время существует четыре варианта, каждый из которых имеет свои собственные потребности.

  • Используйте map если тег поиска - это не то же самое, что и элемент, который вы ищете. В противном случае используйте set .
  • Используйте unordered когда у вас много элементов в контейнере, и производительность поиска абсолютно должна быть O(1) , а не O(logn) .
  • Используйте multi если вам нужно несколько элементов, чтобы иметь один и тот же тег поиска.

заказ

Если вам нужен контейнер предметов, который нужно сортировать на основе конкретной операции сравнения, вы можете использовать set . Или multi_set если вам нужно, чтобы несколько элементов имели одинаковое значение.

Или вы можете использовать отсортированный std::vector , но вам придется сортировать его.

стабильность

Когда итераторы и ссылки являются недействительными, иногда вызывает беспокойство. Если вам нужен список элементов, так что у вас есть итераторы / указатели на эти элементы в разных местах, тогда подход std::vector к аннулированию может оказаться неприемлемым. Любая операция вставки может привести к аннулированию, в зависимости от текущего размера и емкости.

std::list предлагает твердую гарантию: итератор и связанные с ним ссылки / указатели становятся недействительными, когда сам элемент удаляется из контейнера. std::forward_list есть, если память вызывает серьезную озабоченность.

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

Эффективность вставки

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

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

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

Следует отметить, что благодаря семантике перемещения производительность std::vector вставки может быть не такой плохой, как раньше. В некоторых реализациях реализована форма перемещения семантического элемента перемещения (так называемая «swaptimization»), но теперь, когда перемещение является частью языка, оно предусмотрено стандартом.

Нет динамических распределений

std::array - прекрасный контейнер, если вы хотите наименьшее количество динамических распределений. Это всего лишь оболочка вокруг C-массива; это означает, что его размер должен быть известен во время компиляции . Если вы можете с этим жить, используйте std::array .

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

Question

Там есть хорошо известное изображение (чит-лист) под названием «C ++ Container choice». Это блок-схема, чтобы выбрать лучший контейнер для желаемого использования.

Кто-нибудь знает, есть ли уже версия C ++ 11?

Это предыдущий:




Вот быстрый поворот, хотя, вероятно, ему нужна работа

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Вы можете заметить, что это дико отличается от версии C ++ 03, в первую очередь из-за того, что мне действительно не нравятся связанные узлы. Контейнеры с связанными узлами обычно могут бить по производительности не связанным контейнером, за исключением нескольких редких ситуаций. Если вы не знаете, что такое ситуации, и у вас есть доступ к boost, не используйте контейнеры связанных узлов. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). В этом списке основное внимание уделяется контейнерам с малой и средней стороны, потому что (A) составляет 99,99% от того, что мы имеем в коде, и (B) Большое количество элементов требует специальных алгоритмов, а не разных контейнеров.




Related