We are now down to the fifth part in our series on the C++ Standard Template Library. Today we shall be dealing with the unordered associative containers.
These unordered containers include the unordered Set or Multiset and the Unordered Map or Multimap. If you have no clue what those mean you can check out this this link and read about the associative containers.
Just in case you don’t know what the C++ Standard Template Library (STL) is you can go to the start of this series and play catch up. It is easy reading with examples and by the time you get back here you will be in good shape.
As usual this article assumes you have prior knowledge of the C++ programming language as well as a good understanding of STL from the previous articles in this series. So lets get started.
What are the Unordered Associative Containers?
Unordered Associative Containers are generally introduced in C++11. These are simply associative containers whereby the order of the elements within those containers are not defined.
The implementation of these containers internally is the hash table or an array of linked lists. The general term is an array of buckets with a list of entries. The hash function is used to determine the value of an element which is then placed in an entry based on the the value of the element.
Finding an element in unordered associative containers takes constant time which is generally the fastest possible of the various search methods.
Here is some code illustrating the use of the unordered set:
General Traits of the Unordered Associative Containers
- Unordered Multiset: This is an unordered set. In this case this container allows duplicate elements as opposed to the none duplicate restriction found in the Set.
- Unordered Map: This is an unordered set of pairs. You can find more details about it in part four of this series.
- Unordered Multimap: Just like multiset is to set, this container is an unordered map that allows duplicate keys.
Properties of Unordered Associative Containers
- There is fast search and insert at any one place in the container in the form of constant time
- The elements of unordered set and unordered multiset cannot be changed whatsoever
- The keys of unordered map and unordered multimap cannot be changed
Seeing there is no associative array, we have to implement it using the map and unordered map as seen in the example below:
The problem with using the array to attempt to modify the container poses problems where the elements cannot be altered. Look at this example
Some Interesting Points on Associative Arrays
- Search is constant time on unordered mas while on map its logarithmic time
- An unordered map may degrade to linear time search in some cases so its not always ideal
- You cannot implement associative arrays in multimaps and unordered multimaps because they lack the [] operator essential for arrays. They also don’t have unique keys.
What Else Should I Know?
Available in fundamental container classes is the container adapters designed to meet common but special needs. The stack for instance provides push() , pop() and top() as seen used in previous examples.
The queue implements push() , pop() , front() and back() while priority queue implements push() , pop() and top() just like the stack.
Well that’s it for now with the unordered associative containers in C++11 STL. We have now set the ground for taking a look at the Iterators and Algorithms which we will be introduced in part 6 of the Standard Template Library series on Algorithms and Iterators.
Ref:
https://isocpp.org/
Found this article interesting? Follow Brightwhiz on Facebook, Twitter, and YouTube to read and watch more content we post.