В каком сценарии я использую определенный контейнер STL?

Question

Я читал о контейнерах STL в моей книге по C ++, в частности, о STL и его контейнерах. Теперь я понимаю, что у каждого из них есть свои специфические свойства, и я близок к тому, чтобы запомнить их все ... Но я пока не понимаю, в каком сценарии используется каждый из них.

Какое объяснение? Пример кода гораздо предпочтительнее.

Answer 1

Этот шпаргалка содержит довольно хорошее резюме различных контейнеров.

См. Блок-схему внизу в качестве руководства для использования в различных сценариях использования:

_{Создано Дэвидом Муром и по лицензии CC BY-SA 3.0}

Answer 2

Вот блок-схема, вдохновленная созданной мной версией Дэвида Мура (см. Выше), которая соответствует (в основном) новому стандарту (C ++ 11). Это только мое личное взятие на него, это не бесспорный, но я полагал, что это могло бы быть полезным для этой дискуссии:

Answer 3

Простой ответ: используйте std::vector для всего, если только у вас нет реальной причины поступить иначе.

Когда вы обнаружите случай, когда вы думаете: «Ну и дела, std::vector здесь не очень хорошо работает из-за X», переходите к принципу X.

Answer 4

Посмотрите на Эффективный STL Скотта Мейерса. Хорошо объяснить, как использовать STL.

Если вы хотите сохранить определенное / неопределенное количество объектов и никогда не будете удалять их, тогда вам нужен вектор. Это замена по умолчанию для массива C, и он работает как один, но не переполняется. Вы также можете заранее установить его размер с помощью Reserve ().

Если вы хотите хранить неопределенное количество объектов, но вы будете добавлять и удалять их, то вам, вероятно, нужен список ... потому что вы можете удалить элемент, не перемещая следующие элементы - в отличие от вектора. Однако он занимает больше памяти, чем вектор, и вы не можете последовательно получить доступ к элементу.

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

Если у вас много пар ключ-значение и вы хотите отсортировать их по ключу, тогда карта полезна ... но она будет содержать только одно значение на ключ. Если вам нужно более одного значения для каждого ключа, вы можете использовать вектор / список в качестве значения на карте или использовать мультикарту.

Это не в STL, а в обновлении TR1 для STL: если у вас есть много пар ключ-значение, которые вы собираетесь искать по ключу, и вас не волнует их порядок вы можете использовать хеш - tr1 :: unordered_map. Я использовал его с Visual C ++ 7.1, где он назывался stdext :: hash_map. У него есть поиск O (1) вместо поиска O (log n) для map.

Answer 5

Я переработал блок-схему, чтобы иметь 3 свойства:

1. Я думаю, что контейнеры STL разделены на 2 основных класса. Базовые контейнеры и те используют базовые контейнеры для реализации политики.
2. Сначала блок-схема должна делить процесс принятия решения на основные ситуации, по которым мы должны принять решение, а затем детализировать каждый случай.
3. Некоторые расширенные контейнеры имеют возможность выбора другого базового контейнера в качестве своего внутреннего контейнера. Блок-схема должна учитывать ситуации, в которых может использоваться каждый из основных контейнеров.

Блок-схема:

Более подробная информация предоставлена ​​в этой ссылке .

Answer 6

Важным моментом, который пока кратко упоминается, является то, что если вам требуется непрерывная память (как дает массив C), то вы можете использовать только vector, array или string.

Используйте array, если размер известен во время компиляции.

Используйте string, если вам нужно работать только с типами символов и нужна строка, а не просто контейнер общего назначения.

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

Со всеми этими тремя вы можете использовать функцию-член data(), чтобы получить указатель на первый элемент контейнера.

Answer 7

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

vector: Компактная компоновка с небольшим объемом памяти или без нее на каждый содержащийся объект Эффективно перебирать. Добавить, вставить и стереть может быть дорого, особенно для сложных объектов. Дешево найти содержащийся объект по индексу, например, myVector [10]. Используйте там, где вы бы использовали массив в C. Хорошо, когда у вас много простых объектов (например, int). Не забудьте использовать reserve() перед добавлением большого количества объектов в контейнер.

list: небольшие накладные расходы памяти на каждый содержащийся объект. Эффективно перебирать. Добавить, вставить и стереть дешево. Используйте там, где вы бы использовали связанный список в C.

set (и multiset): значительные накладные расходы памяти на каждый содержащийся объект. Используйте там, где вам нужно быстро выяснить, содержит ли этот контейнер данный объект, или эффективно объединить контейнеры.

map (и multimap): значительные накладные расходы памяти на каждый содержащийся объект. Используйте там, где вы хотите хранить пары ключ-значение и быстро искать значения по ключу.

Блок-схема на шпаргалке , предложенная zdan, дает более исчерпывающее руководство.

Answer 8

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

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Это не требует больших затрат и экономит время на отладку, когда вы хотите прервать работу, когда кто-то выполняет операцию x с этой структурой.

Приходя к выбору идеальной структуры данных для работы:

Каждая структура данных предоставляет несколько операций, которые могут быть различной сложности во времени:

O (1), O (LG N), O (N) и т. Д.

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

Просто, не так ли (-:

Answer 9

Я ответил на это в другом вопросе, отмеченном как dup этого. Но я чувствую, что приятно сослаться на некоторые хорошие статьи, касающиеся решения о выборе стандартного контейнера.

Как ответил @David Thornley, std :: vector - путь, если нет других особых потребностей. Это совет, данный создателем C ++ Бьярном Страуструпом в блоге 2014 года.

Вот ссылка на статью https://isocpp.org/blog/2014/06/stroustrup-lists

и цитата из этого,

И да, я рекомендую использовать std :: vector по умолчанию.

В комментариях пользователь @NathanOliver также предоставляет еще один хороший блог, в котором есть более конкретные измерения. https://baptiste -wicht.com / posts / 2012/12 / cpp-benchmark-vector-list-deque.html .

Answer 10

Я расширил фантастическую блок-схему Майкла Перссона. Я добавил несколько категорий контейнеров, контейнер массивов и некоторые заметки. Если вам нужна ваша собственная копия, здесь - это Google Drawing. Спасибо, Микаэль, за проделанную работу! Сборщик контейнеров C ++