Welcome to the third tutorial in the C++ Standard Template Library series featuring Associative Containers. In our previous tutorial we discussed about the Sequence Containers focusing on the linked list, deque and STL array.
We also saw the inner workings of the vector, list, forward list, deque and array classes and how they can be used in the C++ Standard Template Library.
In case you missed the beginning of this series, you can get up to speed on the overview of the C++ Standard Template Library so as to get up to speed with what is being discussed here.
What are Associative Containers in C++ STL?
An associative container in STL is a container where each element of the container has a value that is associated with a key. In some cases the key and value can be the same while in other cases they can be of different values.
The properties of these key/value pairs will be discussed more in depth when we look at the different types of Associative Containers.
These containers consist of the following. Set, Multiset, Map, and Multimap. Their characteristics will be highlighted shortly.
Associative Containers Implementation
These containers are always implemented using a binary tree and are always sorted ascending. The sorting is done internally and automatically, therefore, an element is always inserted in its proper place all the time. Likewise, when an element is removed from the container, the remaining elements will be resorted to keeping the tree in the correct order all the time.
Set
The major characteristics of a set is that the elements contained within it must be unique.There are a few characteristics to note about the set.
- A set does not allow duplicate elements.
- Insertions into a set is fast and takes logarithmic time as opposed to linear time like the sequence containers
- Traversing a set is slow
- Finding an element is also faster than sequence containers by taking logarithmic time
- When inserting elements into the set with the “insert” method, it returns a pair. The first element is pointer to the new element. If the element already existed it returns a pointer to the existing duplicate. The second element is a boolean that returns true if successful and false if the element already exists
- Elements cannot be modified
- Set does not allow random access and does not have the
[]operator
Some Examples of the Set usage.
Multiset
The multiset Associative containers have the same rules as the set with the only major difference being the multiset allows duplicate elements to be inserted into the data structure.
Declaring a multiset is as follows:
multiset ms;
Map
Now that we are in agreement that Associative Containers are always sorted, in reality, that may not be the ideal situation for every programmer. Sometimes you want to sort using other criteria. This is where a map steps in.
Whereby sets and multisets are sorted by the value which also doubles as the key. A map contains a corresponding Key/Value pair and is sorted by the key.
Here is an example of the implementation of a map:
Multimap
Multimaps are Associative Containers of type map that allow duplicate keys. The keys themselves cannot be modified but the values can. The type returned from a multimap and map are of type
pair
Maps and multimaps also follow the rest of the characteristics of the set and multiset.
In the next part in this series on the C++ Standard Template Library we will be taking a look at unordered associative containers. Meanwhile you can get to brush up on the previous tutorial where we discussed the details of the Sequence containers in regards to Linked Lists, deques and the STL array.
Found this article interesting? Follow Brightwhiz on Facebook, Twitter, and YouTube to read and watch more content we post.