Associative containers (C++)

In C++, associative containers are class templates in the standard library that maintain their elements in an order determined by their keys and provide key-based lookup. They reside in namespace std and are parameterized by a key type, a comparison function, and an allocator; maps also have a mapped-value type.

The standard specifies four basic associative containers:

• std::set<T>
• std::map<K, V>
• std::multiset<T>
• std::multimap<K, V>

set and map store at most one element for each equivalent key, whereas multiset and multimap permit multiple elements with equivalent keys. Maps store a mapped value with each key; sets store keys alone.

Since C++17, alias templates for these containers have also been provided in namespace std::pmr; they use std::pmr::polymorphic_allocator as the allocator type.

std::set and std::multiset are declared in header <set>, while std::map and std::multimap are declared in header <map>.

Unlike the unordered associative containers, which organize elements into hash-table buckets and do not specify an overall iteration order, associative containers traverse their elements in non-descending key order. The two groups also provide different complexity guarantees.

std::map and std::set are commonly implemented as red-black trees, although the standard does not require that representation. Comparable ordered map and set types include java.util.TreeMap and java.util.TreeSet in Java, System.Collections.Generic.SortedDictionary and System.Collections.Generic.SortedSet in .NET, and std::collections::BTreeMap and std::collections::BTreeSet in Rust.

Design

Characteristics

• Key uniqueness: set and map store at most one element for each equivalent key. multiset and multimap allow multiple elements with equivalent keys.
• Element composition: in map and multimap, each element consists of a key and a mapped value. In set and multiset, each element is a key.
• Key ordering: each container uses a comparison object that imposes a strict weak ordering. Two keys are equivalent when neither compares less than the other; this need not be the same as equality under operator==.

Search and insertion by key have logarithmic complexity. Erasing by key is logarithmic plus the number of elements erased, while erasing through an iterator is amortized constant. Insertion does not invalidate iterators or references, and erasure invalidates only those referring to erased elements. The standard does not prescribe a particular data structure; implementations commonly use self-balancing binary search trees.

Associative-container iterators are bidirectional and traverse elements in non-descending order according to the container's comparison object. A map stores key–value pairs, while a set stores keys alone. The multi variants allow more than one element with an equivalent key.

The standard library's unordered counterparts—unordered_set, unordered_map, unordered_multiset, and unordered_multimap—use hashing. Their lookup, insertion, and erasure operations are constant time on average but can be linear in the worst case; they do not provide sorted traversal.

Performance

See also: Big O notation and Time complexity

The asymptotic complexity of common operations on associative containers is as follows:

Operation	Complexity
Finding an element by key	$O(\log n)$
Inserting an element	$O(\log n)$; amortized $O(1)$ when a correct insertion hint is supplied
Incrementing or decrementing an iterator	Amortized $O(1)$
Erasing through an iterator	Amortized $O(1)$
Erasing by key	$O(\log n+k)$, where $k$ is the number of elements erased

For unordered associative containers, finding, inserting, and erasing an element take $O(1)$ time on average and $O(n)$ time in the worst case.

Overview of functions

The <set> header declares set and multiset; the <map> header declares map and multimap. All four meet the standard requirements for allocator-aware and reversible associative containers and provide common container operations such as begin(), end(), size(), max_size(), empty(), and swap().

	set	map	multiset	multimap	Description
	(constructor)	(constructor)	(constructor)	(constructor)	Constructs the container from variety of sources
	(destructor)	(destructor)	(destructor)	(destructor)	Destructs the set and the contained elements
	operator=	operator=	operator=	operator=	Assigns values to the container
	get_allocator	get_allocator	get_allocator	get_allocator	Returns the allocator used to allocate memory for the elements
Element access	—N/a	at	—N/a	—N/a	Accesses specified element with bounds checking.
	—N/a	operator[]	—N/a	—N/a	Accesses specified element without bounds checking.
Iterators	begin	begin	begin	begin	Returns an iterator to the beginning of the container
	end	end	end	end	Returns an iterator to the end of the container
	rbegin	rbegin	rbegin	rbegin	Returns a reverse iterator to the reverse beginning of the container
	rend	rend	rend	rend	Returns a reverse iterator to the reverse end of the container
Capacity	empty	empty	empty	empty	Checks whether the container is empty
	size	size	size	size	Returns number of elements in the container.
	max_size	max_size	max_size	max_size	Returns the maximum possible number of elements in the container
Modifiers	clear	clear	clear	clear	Clears the contents.
	insert	insert	insert	insert	Inserts elements.
	emplace	emplace	emplace	emplace	Constructs elements in-place (C++11)
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	Constructs elements in-place using a hint (C++11)
	erase	erase	erase	erase	Erases elements.
	swap	swap	swap	swap	Swaps the contents with another container.
Lookup	count	count	count	count	Returns the number of elements matching specific key.
	find	find	find	find	Finds an element with specific key.
	equal_range	equal_range	equal_range	equal_range	Returns a range of elements matching specific key.
	lower_bound	lower_bound	lower_bound	lower_bound	Returns an iterator to the first element with a key not less than the given value.
	upper_bound	upper_bound	upper_bound	upper_bound	Returns an iterator to the first element with a key greater than a certain value.
Observers	key_comp	key_comp	key_comp	key_comp	Returns the key comparison function.
	value_comp	value_comp	value_comp	value_comp	Returns the value comparison function. In set and multiset this function is equivalent to key_comp, since the elements are composed from a key only.

Usage

The following code demonstrates how to use the map<string, int> to count occurrences of words. It uses the word as the key and the count as the value.

import std;

using std::cin;
using std::map;
using std::string;

int main(int argc, char* argv[]) {
    map<string, int> wordCounts;
    string s;

    while (cin >> s && s != "end") {
        ++wordCounts[s];
    }
    
    while (cin >> s && s != "end") {
        std::println("{} {}", s, wordCounts[s]);
    }
    
    return 0;
}

When executed, program lets user type a series of words separated by spaces, and a word "end" to signify the end of input. Then user can input a word to query how many times it has occurred in the previously entered series.

The example also demonstrates that operator[] inserts an element with a value-initialized mapped value when the map does not already contain an equivalent key. Consequently, integral mapped values are initialized to zero and std::string values to empty strings.

The following example illustrates inserting elements into a map using the insert function and searching for a key using a map iterator and the find function:

import std;

using TreeMapOfCharInt = std::map<char, int>;

using std::cin;
using std::pair;

int main() {
    TreeMapOfCharInt myMap;

    // Insert elements using insert function
    myMap.insert(pair<char, int>('a', 1));
    myMap.insert(pair<char, int>('b', 2));
    myMap.insert(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 standard containers
    myMap.insert(TreeMapOfCharInt::value_type('d', 4));
    // Using the utility function make_pair
    myMap.insert(std::make_pair('e', 5));
    // Using C++11 initializer list
    myMap.insert({'f', 6});                    
    
    // map keys are sorted automatically from lower to higher. 
    // So, myMap.begin() points to the lowest key value not the key which was inserted first.
    TreeMapOfCharInt::iterator iter = myMap.begin();

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

    // Output the size of the map using size function
    std::println("Size of myMap: {}", myMap.size());

    std::println("Enter a key to search for: ");
    char c;
    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 = myMap.find(c);
    if (iter != myMap.end()) {
        std::println("For key {}, value is: {}", iter->first, iter->second);
    } else {
        std::println("Key {} is not in myMap", c);
    }

    // Clear the entries in the map using clear function
    myMap.clear();
    
    return 0;
}

Example shown above demonstrates the usage of some of the functions provided by map, such as insert() (place element into the map), erase() (remove element from the map), find() (check presence of the element in the container), etc.

When program is executed, six elements are inserted using the insert() function, then the first element is deleted using erase() function and the size of the map is outputted. Next, the user is prompted for a key to search for in the map. Using the iterator created earlier, the find() function searches for an element with the given key. If it finds the key, the program prints the element's value. If it doesn't find it, an iterator to the end of the map is returned and it outputs that the key could not be found. Finally all the elements in the tree are erased using clear().

Iterators

Maps may use iterators to point to specific elements in the container. An iterator can access both the key and the mapped value of an element:

// 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);

Below is an example of looping through a map to display all keys and values using iterators:

import std;

using std::map;
using std::string;

int main(int argc, char* argv[]) {
    map<string, int> data {
        { "Bob's score", 10 },
        { "Marty's score", 15 },
        { "Mehmet's score", 34 },
        { "Rocky's score", 22 },
        // The next values are ignored because elements with the same keys are already in the map
        { "Rocky's score", 23 }, 
        { "Mehmet's score", 33 } 
    };
    
    // Iterate over the map and print out all key/value pairs.
    for (const auto& [key, value] : data) {
        std::println("Who(key = first): {}", key);
        std::println("Score(value = second): {}", value);
    }
    
    // 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 (map<string, int>::iterator iter = data.begin(); iter != data.end(); ++iter) {
        std::println("Who(key = first): {}", iter->first);
        std::println("Score(value = second): {}", iter->second);
    }

    return 0;
}

See also

• Sequence container (C++)
• Unordered associative containers (C++)