Associative Containers in C++

Language:中文/EN

Associative Containers in C++

Associative containers support efficient keyword lookup and access. The two main associative containers are set and map. Elements in a map are key-value pairs, where the key acts as an index and the value represents the data associated with that index. Elements in a set contain only a keyword. set supports efficient keyword lookup operations, likely implemented using a hash table.

The C++ Standard Library provides eight associative containers, which differ in three dimensions:

  1. set or map
  2. Ordered or unordered—indicated by the presence or absence of the unordered prefix
  3. Allow or disallow duplicate keywords—indicated by the presence or absence of the multi prefix

This article focuses on set and map. For information on other containers, refer to the C++ API.

Using set and map

Using map:

// Count the occurrences of each word in the input
map<string, size_t> word_count;  // Create a new map
string word;
while (cin >> word)
    ++word_count[word];  // Increment the count for the word
for (const auto &w : word_count)
    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << endl;

Note that using word_count[word] in a map will add an element with the keyword word and initialize its value if the keyword is not found. Using word_count.at(word) will throw an out_of_range exception if the keyword is not found.

Using set:

// Count the occurrences of each word in the input
map<string, size_t> word_count;
set<string> exclude = {"The", "But", "And", "Or", "An"};
string word;
while (cin >> word)
    if (exclude.find(word) == exclude.end())  // If not found in set, returns end iterator
        ++word_count[word];

pair Class and Additional Type Aliases in Associative Containers

The pair class is defined in the <utility> header and holds two data members. Like containers, pair is a template used to generate specific types. When creating a pair, we must provide two type names.

pair<string, size_t> word_count;  // Holds a string and a size_t

Unlike other standard library types, the data members of pair are public, named first and second. Elements stored in a map are of pair type.

Associative containers also define other types representing the container’s key and value types:

  • key_type: The type of the container’s key
  • mapped_type: The type associated with each key, applicable only to map
  • value_type: For set, the same as key_type; for map, pair<const key_type, mapped_type>
set<string>::value_type v1;  // string
set<string>::key_type v2;    // string
map<string, int>::value_type v3;  // pair<const string, int>
map<string, int>::key_type v4;    // string
map<string, int>::mapped_type v5; // int

Iterators in Associative Containers

When dereferencing an iterator of an associative container, you get a reference to a value of the container’s value_type. For map, value_type is a pair type, where the first member holds a const key and the second member holds the value:

// Get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first;
cout << " " << map_it->second;
map_it->first = "new key";  // Error, key is const
++map_it->second;  // The value element can be changed

Keywords in a set are also const. You can read the values of elements in a set, but you cannot modify them:

set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
    *set_it = 42;  // Error, const keyword cannot be modified
    cout << *set_it << endl;
}
#C++