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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Блок-схема:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Просто, не правда ли (-:

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

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

Как ответил @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 .