Consider the example of managing the store inventory. You should find the price of an item given the name of the product. In case your container is a vector of structures, you will need to search through the container to find the price:
#include <iostream>
#include <vector>
struct InventoryItem {
std::string name;
double price;
};
double get_price(const std::vector<InventoryItem>& inventory, const std::string& name) {
for (const auto& item : inventory) {
if (item.name == name) {
return item.price;
}
}
return -1.0; // Not found
}The code is correct and functional, however, it is slow. As the number of items grows to thousands, the function to find the price should make a larger and larger number of string comparisons. Such a search has the linear-time complexity. We need an associative container for quick search with a non-numeric key.
Behavior of Maps and Unordered Maps
The C++ Standard Library implements two principal associative containers, which can be used to store elements in form of key-value pairs: an ordered map and an unordered map. In both containers all the keys are stored uniquely, each of them being linked with some particular value.
Internally, the ordered map is implemented as the balanced binary search tree, usually a red-black tree. Since it is a tree, the keys are stored in some sorted order. The process of searching, insertion and removal of elements in an ordered map runs in logarithmic time. Iteration of an ordered map gives the elements sorted alphabetically/numerically by their keys.
The maps associate each unique key with a mapped value. In the ordered map iteration follows the order of keys, in the unordered map the iteration order is unknown. The ordered map supports the range queries, such as getting the first key which is not less than some boundary (which the hash table cannot give you directly).
On the other hand, the unordered map is implemented as a hash table. It doesn't keep any order among its keys. Rather, it uses a hash function to get an index of a particular bucket, and it guarantees the average constant time complexity of the processes of lookup, insertion and deletion. In most cases when the task doesn't involve any sorting and is lookup-intensive, unordered map is the choice to go.
While iterating over the containers, each of their elements is stored as a pair. The key is accessible by the means of the first member variable, the value - by the means of the second member variable. Since the key is used internally by the container to organize the data, it is immutable.
#include <iostream>
#include <map>
#include <string>
int main() {
// Declare a map where keys are strings and values are doubles
std::map<std::string, double> inventory;
// Insert elements using the subscript operator
inventory["apple"] = 0.99;
inventory["banana"] = 0.59;
inventory["cherry"] = 2.99;
// Print the elements (they will be sorted alphabetically by key)
for (const auto& item : inventory) {
std::cout << item.first << ": $" << item.second << "\n";
}
return 0;
}Accessing Elements and Handling the Cases When Key Is Missing
For the extraction of values from maps the subscript operator or bounds-checked member function can be used. However, these two ways differ greatly in what happens if the key is not in the container.
The subscript operator inserts the value-initialized mapped value if there is no such key. This may be handy while implementing the counter, however, in the case when you just want to read the map without changing it, this method is incorrect. Apply search, membership-checking or bounds-checked access function depending on your needs. The conditional emplacement member function helps you not to construct a mapped value when the key is already present.
The subscript operator is handy, however, it has a dangerous side effect: if the key you requested is not in the map, the map will insert this key into itself with some default-constructed value, such as 0 for integers or "" for strings. This may cause the accidental insertion and increase of the size of the container.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> student_grades;
student_grades["Alice"] = 95;
// Bob does not exist, but this call inserts him with a grade of 0
std::cout << "Bob's grade: " << student_grades["Bob"] << "\n";
// The size is now 2 because Bob was implicitly added
std::cout << "Map size: " << student_grades.size() << "\n";
return 0;
}If you don't want your container to be modified, use the bounds-checked member function. It will throw the out-of-range exception if there is no such key. Also you can check the presence of the key before accessing it by means of the search member function or the modern membership-checking member function.
The search function returns an iterator pointing at the key-value pair if it is found, or the end iterator if there is no such key. The membership-checking function returns the boolean value, so it is suitable for conditional checking.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> grades{
{"Alice", 95},
{"Bob", 88}
};
// Safe lookup using find()
auto it = grades.find("Charlie");
if (it != grades.end()) {
std::cout << "Charlie's grade: " << it->second << "\n";
} else {
std::cout << "Charlie not found.\n";
}
// Safe lookup using C++20 contains()
if (grades.contains("Alice")) {
std::cout << "Alice is enrolled.\n";
}
return 0;
}Custom Classes or Structures as Keys
While choosing the custom classes or structures as keys, you will have to meet the requirements of the container. For the ordered map the key should support the ordering operations, as the tree needs to sort the elements. For the unordered map the key should support equality and a special hash function, which is defined for the key in the standard hash namespace.
Exercise: std::map and std::unordered_mapStarter code, hints and solutionOpenClose
Practice: std::map and std::unordered_map
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Insert Charlie with grade 91 using emplace before the lookup and print the map size. Predict what find returns and distinguish insertion from observation.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> grades{
{"Alice", 95},
{"Bob", 88}
};
// Safe lookup using find()
auto it = grades.find("Charlie");
if (it != grades.end()) {
std::cout << "Charlie's grade: " << it->second << "\n";
} else {
std::cout << "Charlie not found.\n";
}
// Safe lookup using C++20 contains()
if (grades.contains("Alice")) {
std::cout << "Alice is enrolled.\n";
}
return 0;
}Hints
grades.find("Charlie") searches without inserting a record. If found, it->second is the mapped grade, while it->first would be the name.
Add a {"Charlie", grade} entry and revisit the first condition. Avoid using grades["Charlie"] merely to test existence: subscripting a missing key inserts it.
Worked solution
emplace adds Charlie with grade 91 before the lookup. find then reaches that existing key and the map size becomes 3. This insertion is deliberate rather than a side effect of testing with operator[].
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> grades{
{"Alice", 95},
{"Bob", 88}
};
// Safe lookup using find()
grades.emplace("Charlie", 91);
auto it = grades.find("Charlie");
if (it != grades.end()) {
std::cout << "Charlie's grade: " << it->second << "\n";
} else {
std::cout << "Charlie not found.\n";
}
// Safe lookup using C++20 contains()
if (grades.contains("Alice")) {
std::cout << "Alice is enrolled.\n";
}
std::cout << "Map size: " << grades.size() << '\n';
return 0;
}
Example output
Charlie's grade: 91
Alice is enrolled.
Map size: 3
0 comments
No comments yet. Be the first.