C++ Maps
Ordered vs Unordered Maps
C++ STL provides std::map container which maps a key to a value and maintains the key in an ordered fashion. Another STL container std::unordered_map also maps a key to a value but no ordering is maintained. Two values can not have the same key in both containers.
Below code shows the difference between the two. In the case of ordered map, the order of the keys is maintained irrespective of the order in which they are entered.
#include <iostream>
#include <map>
#include <unordered_map>
int main()
{
std::map<std::string, std::string> empRecords;
// insert an entry
empRecords.insert({ "MAR", "Maria" });
empRecords["CHR"] = "Christoph";
empRecords.insert(std::make_pair("SEB", "Sebastian"));
std::cout << "Employee Records using Ordered Map\n";
for (const auto& [key, val] : empRecords)
std::cout << "Emp Code: " << key << " , Emp Name: " << val << std::endl;
std::cout << std::endl << std::endl;
std::unordered_map<std::string, std::string> empRecordsUnOrder;
// insert an entry
empRecordsUnOrder.insert({ "MAR", "Maria" });
empRecordsUnOrder["CHR"] = "Christoph";
empRecordsUnOrder.insert(std::make_pair("SEB", "Sebastian"));
std::cout << "Employee Records using Unordered Map\n";
for (const auto& [key, val] : empRecordsUnOrder)
std::cout << "Emp Code: " << key << " , Emp Name: " << val << std::endl;
return 0;
}
Output:
Employee Records using Ordered Map
Emp Code: CHR , Emp Name: Christoph
Emp Code: MAR , Emp Name: Maria
Emp Code: SEB , Emp Name: Sebastian
Employee Records using Unordered Map
Emp Code: MAR , Emp Name: Maria
Emp Code: CHR , Emp Name: Christoph
Emp Code: SEB , Emp Name: Sebastian
Internally, the maps are implemented using Self-balancing Binary Search Tree (like Red-Black Tree). That is how the key order is maintained. Due to this, ordered maps are expensive in insertion, deletion and search operations. The complexity of all three operations is log(n). Also the maps needs to reordered after every insert and delete operation.
On the other hand, unordered maps are implemented using Hash Table since they don’t require any ordering. The average time complexity is O(1) and O(n) in worst case for insert, delete and search operations.
Multimaps
We read above about maps and that every key in a map should be unique i.e. no two values can have the same key. Multimap is different in a way that it can store two values with same key. Similar to maps, C++ STL provides ordered multimaps (std::multimap) and unordered multimaps (std::unordered_multimap). Ordered multimaps store the keys in sorted order. Unordered multimaps store the keys in random order, but the pairs with same key value are stored together. Internal implementation is similar to maps.