Ця стаття потребує упорядкування для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть поліпшити цю статтю. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (грудень 2011) (Дізнайтеся, як і коли вилучати це шаблонне повідомлення[en])

В обчислювальній техніці асоціативні контейнери відносяться до групи шаблонів класів у стандартній бібліотеці мови програмування C++, які реалізують упорядковані асоціативні масиви . ^[1] Будучи шаблонами, вони можуть використовуватися для зберігання довільних елементів, таких як цілі числа, символьні рядки чи класи користувача. У поточній редакції стандарту C++ визначені такі контейнери: set, map, multiset, multimap . Кожен із цих контейнерів відрізняється лише обмеженнями, накладеними на їхні елементи.

Асоціативні контейнери подібні до невпорядкованих асоціативних контейнерів у стандартній бібліотеці C++, єдина відмінність полягає в тому, що невпорядковані асоціативні контейнери, як випливає з їх назви, не впорядковують свої елементи.

• Унікальність ключів : у map та set кожен ключ має бути унікальним. multimap і multiset не мають цього обмеження.
• Склад елементів : у map та multimap кожен елемент складається з ключа(key) та зіставленого значення(value). У set та multiset кожен елемент є ключовим; немає зіставлених значень.
• Порядок елементів : елементи дотримуються строгого порядку ^[1] розміщення.

Асоціативні контейнери створені для особливо ефективного доступу до елементів за їх ключем, на відміну від послідовних контейнерів, які більш ефективні для доступу до елементів за їхньою позицією(індексом). ^[1] Асоціативні контейнери гарантовано виконують операції вставки, видалення та перевірки наявності в ньому елемента за логарифмічний час – O(log n ). Таким чином, вони зазвичай реалізуються за допомогою самобалансуючих бінарних дерев пошуку(self-balancing binary search tree) та підтримують двонаправлену ітерацію. Ітератори та посилання не анулюються операціями вставки та стирання, за винятком ітераторів та посилань на видалені елементи. Визначальною характеристикою асоціативних контейнерів є те, що елементи вставляються у заздалегідь визначеному порядку, наприклад, сортуються за зростанням.

Асоціативні контейнери можна згрупувати в дві підмножини: таблиці(maps) та множини(sets). Таблиця, яку іноді називають словником, складається з пари ключ/значення. Ключ використовується для впорядкування послідовності, а значення якимось чином асоціюється з цим ключем. Наприклад, таблиця може містити ключі, що репрезентують кожне унікальне слово в тексті, і значення, що відображають кількість разів, коли це слово з'явилось у тексті. Множина — це просто контейнер унікальних елементів відсортований у висхідному порядку.

Як було зазначено раніше, map і set дозволяють вставити в контейнер лише один екземпляр ключа або елемента. Якщо потрібні кілька екземплярів елементів, використовуйте multimap або multiset .

І таблиці, і набори підтримують двонаправлені ітератори. Щоб отримати додаткові відомості про ітератори, перегляньте Ітератори .

Хоча hash_map і hash_set офіційно не є частиною стандарту STL, вони зазвичай використовуються для покращення часу пошуку. Ці контейнери зберігають свої елементи як хеш-таблицю, де кожен запис таблиці містить двонаправлений зв'язний список елементів. Щоб забезпечити найшвидший час пошуку ( O(1) ), переконайтеся, що алгоритм хешування для ваших елементів повертає рівномірно розподілені хеш-значення.

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

Контейнери визначаються в файлах заголовків, названих за іменами контейнерів, наприклад, set визначається у файлі <set> . Усі контейнери відповідають вимогам концепції контейнера, що означає, що вони мають методи begin(), end(), size(), max_size(), empty() і swap() .

Наступний приклад коду демонструє, як використовувати map<string, int> для підрахунку повторень слів у введеному рядку. Він використовує слово як ключ і кількість як значення .

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> wordcounts;
    std::string s;

    while (std::cin >> s && s != "end")
    {
        ++wordcounts[s];
    }
    
    while (std::cin >> s && s != "end")
    {
        std::cout << s << ' ' << wordcounts[s] << '\n';
    }
    
    return 0;
}

Під час виконання програма дозволяє користувачеві вводити ряд слів, розділених пропусками, і слово "end", щоб позначити кінець введення. Після цього користувач може ввести слово, щоб отримати інформацію, скільки разів воно зустрічалося в попередньо введеному рядку.

Наведений вище приклад також демонструє, що оператор [] вставляє нові об’єкти (використовуючи конструктор за замовчуванням) у таблицю, якщо немає такого, пов’язаного з ключем. Отже, цілі чила типи ініціалізуються нулем, рядки ініціалізуються порожніми рядками тощо.

Наступний приклад ілюструє вставлення елементів у карту, за допомогою функції вставки та пошук ключа за допомогою ітератора карти та функції find():

#include <iostream>
#include <map>
#include <utility> // To use make_pair function

int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;

    // Insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('c', 3));
    
    // You can also insert elements in a different way like shown below
    // Using function value_type that is provided by all standart containers
    my_map.insert(MapType::value_type('d', 4));
    // Using the utility function make_pair
    my_map.insert(std::make_pair('e', 5));
    // Using C++11 initializer list
    my_map.insert({'f', 6});                    
    
    //map keys are sorted automatically from lower to higher. 
    //So, my_map.begin() points to the lowest key value not the key which was inserted first.
    MapType::iterator iter = my_map.begin();

    // Erase the first element using the erase function
    my_map.erase(iter);

    // Output the size of the map using size function
    std::cout << "Size of my_map: " << my_map.size() << '\n';

    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> c;

    // find will return an iterator to the matching element if it is found
    // or to the end of the map if the key is not found
    iter = my_map.find(c);
    if (iter != my_map.end()) 
    {
        std::cout << "Value is: " << iter->second << '\n';
    }
    else 
    {
        std::cout << "Key is not in my_map" << '\n';
    }

    // You can clear the entries in the map using clear function
    my_map.clear();
    
    return 0;
}

Наведений вище приклад демонструє використання деяких функцій, які надає map, наприклад insert() (розмістити елемент в таблиці), erase() (видалити елемент з таблиці), find() (перевірити наявність елемента в таблиці) тощо.

Коли програма виконується, шість елементів вставляються за допомогою функції insert(), потім перший елемент видаляється за допомогою функції erase() і виводиться розмір таблиці. Далі користувачеві пропонується ввести ключ для його пошуку у таблиці. Використовуючи створений раніше ітератор, функція find() шукає елемент із заданим ключем. Якщо ключ знайдено, програма друкує значення елемента. Якщо ні, повертає ітератор до кінця таблиці та виводить, що ключ не знайдено. Нарешті всі елементи в дереві видаляться за допомогою clear() .

Таблиці можуть використовувати ітератори, щоб вказувати на певні елементи в контейнері. Ітератор може отримати доступ як до ключа, так і до відображеного значення елемента: ^[1]

// Declares a map iterator
std::map<Key, Value>::iterator it;

// Accesses the Key value 
it->first;

// Accesses the mapped value
it->second;

// The "value" of the iterator, which is of type std::pair<const Key, Value>
(*it);

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

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> data 
    {
     { "Bobs score", 10    },
     { "Martys score", 15  },
     { "Mehmets score", 34 },
     { "Rockys score", 22  },
     // The next values are ignored because elements with the same keys are already in the map
     { "Rockys score", 23  }, 
     { "Mehmets score", 33 } 
    };
    
    // Iterate over the map and print out all key/value pairs.
    for (const auto& element : data)
    {
        std::cout << "Who(key = first): " << element.first;
        std::cout << " Score(value = second): " << element.second << '\n';
    }
    
    // If needed you can iterate over the map with the use of iterator,
    // Note that the long typename of the iterator in this case can be replaced with auto keyword
    for (std::map<std::string, int>::iterator iter = data.begin(); iter != data.end(); ++iter) 
    {
        std::cout << "Who(key = first): " << iter->first;
        std::cout << " Score(value = second): " << iter->second << '\n';
    }

    return 0;
}

• Контейнер (абстрактний тип даних)
• Стандартна бібліотека шаблонів#Контейнери
• Невпорядковані асоціативні контейнери C++