Контейнеры стандартной библиотеки C++

Стандартная библиотека предоставляет различные типобезопасные контейнеры для хранения коллекций связанных объектов. Контейнеры — это шаблоны классов. При объявлении переменной контейнера укажите тип элементов, которые будет хранить контейнер. Контейнеры могут создаваться с использованием списков инициализаторов. Они имеют функции-члены для добавления и удаления элементов и выполнения других операций.

Итерация элементов в контейнере и доступ к отдельным элементам осуществляются с помощью итераторов. Итераторы можно использовать явным образом с помощью их функций-членов и операторов и глобальных функций. Вы можете также использовать их неявно, например с помощью цикла range-for. Итераторы для всех контейнеров стандартной библиотеки C++ имеют общий интерфейс, но каждый контейнер определяет собственные специализированные итераторы.

Контейнеры можно разделить на три категории: последовательные контейнеры, ассоциативные контейнеры и контейнеры-адаптеры.

Контейнеры последовательности

Последовательные контейнеры поддерживают указанный пользователем порядок вставляемых элементов.

Контейнер vector ведет себя как массив, но может автоматически увеличиваться по мере необходимости. Он поддерживает прямой доступ и связанное хранение и имеет очень гибкую длину. По этим и многим другим причинам контейнер vector является наиболее предпочтительным последовательным контейнером для большинства областей применения. Если вы сомневаетесь в выборе вида последовательного контейнера, начните с использования вектора. Дополнительные сведения см. в разделе vector "Класс".

Контейнер array имеет некоторые сильные стороны vector, но длина не так гибка. Дополнительные сведения см. в разделе array "Класс".

Контейнер deque (двусторонняя очередь) обеспечивает быструю вставку и удаление в начале и в конце контейнера. Он делится преимуществами vectorслучайного доступа и гибкой длины, но не является непрерывным. Дополнительные сведения см. в разделе deque "Класс".

list Контейнер — это двунаправленный список, который обеспечивает двунаправленный доступ, быстрые вставки и быстрые удаления в любом месте контейнера, но вы не можете случайно получить доступ к элементу в контейнере. Дополнительные сведения см. в разделе list "Класс".

Контейнер forward_list — однонаправленный список. Это версия контейнера list только с доступом в прямом направлении. Дополнительные сведения см. в разделе forward_list "Класс".

Ассоциативные контейнеры

В ассоциативных контейнерах элементы вставляются в предварительно определенном порядке — например, с сортировкой по возрастанию. Также доступны неупорядоченные ассоциативные контейнеры. Ассоциативные контейнеры можно объединить в два подмножества: сопоставления (set) и наборы (map).

Контейнер map, который иногда называют словарем, состоит из пар "ключ-значение". Ключ используется для упорядочивания последовательности, а значение связано с ключом. Например, map может содержать ключи, представляющие каждое уникальное ключевое слово в тексте, и соответствующие значения, которые обозначают количество повторений каждого слова в тексте. map — это неупорядоченная версия unordered_map. Дополнительные сведения см. в разделе "Класс и unordered_map класс".map

set — это контейнер уникальных элементов, упорядоченных по возрастанию. Каждое его значение также является и ключом. set — это неупорядоченная версия unordered_set. Дополнительные сведения см. в разделе "Класс и unordered_set класс".set

Контейнеры map и set разрешают вставку только одного экземпляра ключа или элемента. Если необходимо включить несколько экземпляров элемента, следует использовать контейнер multimap или multiset. Неупорядоченные версии этих контейнеров — unordered_multimap и unordered_multiset. Дополнительные сведения см. в разделе "Класс", "Класс", "Класс", unordered_multimapmultiset"Класс" и unordered_multiset "Класс".multimap

Упорядоченные контейнеры map и set поддерживают двунаправленные итераторы, а их неупорядоченный аналоги — итераторы с перебором в прямом направлении. Дополнительные сведения см. в разделе Итераторы.

Разнородный поиск в ассоциативных контейнерах (C++ 14)

Упорядоченные ассоциативные контейнеры (map, multimap, set и multiset) теперь поддерживают разнородный поиск, что означает, что вам больше не требуется передавать тот же тип объекта, что и ключ или элемент в таких функциях-членах, как find() и lower_bound(). Вы можете передать объект любого типа, для которого определен перегруженный operator<, позволяющий выполнять сравнение с типом ключа.

Разнородный поиск включен на основе согласия при указании std::less<>std::greater<> или "бриллиантового functor" сравнения при объявлении переменной контейнера, как показано ниже:

std::set<BigObject, std::less<>> myNewSet;

Если используется средство сравнения, заданное по умолчанию, контейнер ведет себя точно так же, как в C++ 11 и более ранних версиях.

В следующем примере показано, как перегрузить operator< пользователей std::set для поиска просто путем передачи небольшой строки, которую можно сравнить с членом каждого объекта BigObject::id .

#include <set>
#include <string>
#include <iostream>
#include <functional>

using namespace std;

class BigObject
{
public:
    string id;
    explicit BigObject(const string& s) : id(s) {}
    bool operator< (const BigObject& other) const
    {
        return this->id < other.id;
    }

    // Other members....
};

inline bool operator<(const string& otherId, const BigObject& obj)
{
    return otherId < obj.id;
}

inline bool operator<(const BigObject& obj, const string& otherId)
{
    return obj.id < otherId;
}

int main()
{
    // Use C++14 brace-init syntax to invoke BigObject(string).
    // The s suffix invokes string ctor. It is a C++14 user-defined
    // literal defined in <string>
    BigObject b1{ "42F"s };
    BigObject b2{ "52F"s };
    BigObject b3{ "62F"s };
    set<BigObject, less<>> myNewSet; // C++14
    myNewSet.insert(b1);
    myNewSet.insert(b2);
    myNewSet.insert(b3);
    auto it = myNewSet.find(string("62F"));
    if (it != myNewSet.end())
        cout << "myNewSet element = " << it->id << endl;
    else
        cout << "element not found " << endl;

    // Keep console open in debug mode:
    cout << endl << "Press Enter to exit.";
    string s;
    getline(cin, s);
    return 0;
}

//Output: myNewSet element = 62F

Для поддержки разнородного поиска были перегружены следующие функции-члены в картах, мультикартах, наборах и нескольких наборах:

1. поиск

2. count

3. lower_bound

4. upper_bound

5. equal_range

Контейнеры-адаптеры

Контейнер-адаптер — это разновидность последовательного или ассоциативного контейнера, который ограничивает интерфейс для простоты и ясности. Адаптеры контейнеров не поддерживают итераторы.

Контейнер queue соответствует семантике FIFO (первым поступил — первым обслужен). Первый элемент, который отправляется, то есть вставляется, в очередь, должен быть первым элементом, извлекаемым из очереди. Дополнительные сведения см. в разделе queue "Класс".

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

Контейнер stack соответствует семантике LIFO (последним поступил — первым обслужен). Последний элемент, отправленный в стек, становится первым извлекаемым элементом. Дополнительные сведения см. в разделе stack "Класс".

Так как адаптеры контейнеров не поддерживают итераторы, их нельзя использовать с алгоритмами стандартной библиотеки C++. Дополнительные сведения см. в разделе Алгоритмы.

Требования для элементов контейнеров

Как правило, элементы, вставленные в контейнер стандартной библиотеки C++, могут быть практически любого типа объекта, если их можно копировать. Элементы, доступные только для перемещения — например, объекты vector<unique_ptr<T>>, создаваемые с помощью unique_ptr<>, — также можно использовать, если вы не вызываете функции-члены, которые пытаются скопировать их.

Деструктор не может вызывать исключение.

Для упорядоченных ассоциативных контейнеров — ранее описанных в этом разделе — необходимо определить открытый оператор сравнения. По умолчанию оператор имеет operator<значение, но поддерживаются даже типы, с которыми не работают operator< .

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

Доступ к элементам контейнера

Доступ к элементам контейнеров осуществляется с помощью итераторов. Дополнительные сведения см. в разделе Итераторы.

Примечание.

Для перебора коллекций стандартной библиотеки C++ можно также использовать циклы for на основе диапазонов.

Сравнение контейнеров

Все контейнеры перегружают оператор == для сравнения двух контейнеров одного типа, содержащих элементы одного типа. Вы можете использовать == для сравнения векторной<строки с другой<векторной строкой>, но ее нельзя использовать для сравнения векторной<> строки со строкой> списка<или векторной строкой> с векторным<<символом*>.> В C++98/03 можно использовать std::equal или std::mismatch сравнивать различные типы контейнеров и /или типы элементов. В C++11 можно также использовать std::is_permutation. Но во всех этих случаях функции предполагают, что контейнеры имеют одинаковую длину. Если второй диапазон короче первого, результат будет неопределенным. Если второй диапазон длиннее, результат также может быть неверным, поскольку сравнение не будет выполнено за пределами первого диапазона.

Сравнение контейнеров разного типа (C++ 14)

В C++14 и более поздних версиях можно сравнить разные контейнеры и (или) различные типы элементов с помощью одной из std::equalstd::mismatchstd::is_permutation перегрузок функций, которые принимают два полных диапазона. Эти перегрузки позволяют сравнивать контейнеры разной длины. Эти перегрузки намного менее подвержены ошибкам пользователя и оптимизированы для возврата значения false в одно и то же время, когда сравниваются контейнеры разной длины. Поэтому мы рекомендуем использовать эти перегрузки, если у вас нет четкой причины не использовать или вы используете std::list контейнер, который не используется из оптимизации с двумя диапазонами.

См. также

Параллельные контейнеры
<sample container>
Потокобезопасность в стандартной библиотеке C++