What is a Mapping Container Class?
A mapping container class is a data structure that stores key-value pairs, where each key uniquely corresponds to a value. For example, in a student grade management system, we can use the student ID as the key and the corresponding grade as the value. By using the student ID as the key, we can quickly find the student’s grade. C++ provides mapping container classes such as the map class and unordered_map class.
map Class
The map class is implemented based on a red-black tree, which is a self-balancing binary search tree. All elements in the map are automatically sorted based on their keys, with the default being in ascending order. For example, when creating a map where int is the key type and string is the value type, the inserted elements will be sorted in ascending order based on the int type keys. The basic operations of a map include insertion, lookup, and deletion.
Insertion Operation
The map container class provides four main methods for insertion.
1. Inserting using the [] operator
You can directly insert or modify elements using the subscript operator. If the key does not exist, a new element is automatically created; if it exists, the original value is overwritten. For example:
map m;m[1] = "Alice"; // Insert new elementm[1] = "Bob"; // Modify existing element2. Inserting using insert(pair)
Explicitly construct a pair object for insertion, returning a pair where second indicates whether the insertion was successful (returns false if the key exists). For example:
auto ret = m.insert(pair(2, "Charlie"));if(ret.second) cout << "Insertion successful";3. Inserting using make_pair
A more concise way to construct a pair, with automatic type deduction. For example:
m.insert(make_pair(3, "David"));4. Inserting using value_type
Insert using the internal type definition of the map to ensure type safety. For example:
m.insert(map::value_type(4, "Eve"));Complete example demonstrating the four methods:
#include<map>#include<iostream>using namespace std;int main() { map<int,string> students; // Four insertion methods students[101] = "Alice"; students.insert(pair<int,string>(102, "Bob")); students.insert(make_pair(103, "Charlie")); students.insert(map<int,string>::value_type(104, "David")); // Iterate and output for(auto& s : students) cout << s.first << ": " << s.second << endl; return 0;}Lookup Operation
The map container class provides various methods for lookup operations.
1. Querying using the [] operator
Access the value directly using the key; if the key does not exist, a default constructed value is automatically inserted. For example:
map ages;ages["Alice"] = 25;cout << ages["Alice"]; // Outputs 25cout << ages["Bob"]; // Outputs 0 (automatically inserted)2. Querying using the find() method
Returns an iterator pointing to the element; if not found, returns end(), and does not automatically insert a new element. For example:
auto it = ages.find("Charlie");if(it != ages.end()) { cout << it->second; // Outputs value} else { cout << "Not found";}3. Querying using the count() method
Returns the number of times the key exists (for map, it can only be 0 or 1). For example:
if(ages.count("David") > 0) { cout << "Exists";}4. Querying using the at() method
Access the value using the key; if the key does not exist, throws an out_of_range exception. For example:
try { cout << ages.at("Eve");} catch(const out_of_range&e) { cerr << "Key not found";}5. Querying using equal_range (suitable for multimap)
Returns a pair of iterators representing the range of matching keys. For example:
multimap mm;mm.insert({"Alice", 25});mm.insert({"Alice", 30});auto range = mm.equal_range("Alice");for(auto it = range.first; it != range.second; ++it) { cout << it->second << endl; // Outputs 25 and 30}Complete example code:
#include<map>#include<iostream>using namespace std;int main() { map<string,int> scores = { {"Math", 90}, {"English", 85} }; // Various query methods cout << scores["Math"] << endl; // 90 auto it = scores.find("English"); if(it != scores.end()) { cout << it->second << endl; // 85 } cout << scores.count("Science") << endl; // 0 try { cout << scores.at("History") << endl; } catch(...) { cout << "Subject not found" << endl; } return 0;}Deletion Operation
The map class provides various methods for deleting elements; below are the main deletion methods and their usage scenarios.
1. Deleting using erase() by iterator
Deletes the element at the specified position, returning an iterator to the next element. For example:
map m = {{1, "A"}, {2, "B"}, {3, "C"}};auto it = m.find(2);if(it != m.end()) { m.erase(it); // Delete element with key 2}2. Deleting using erase() by key
Directly delete an element by key, returning the number of deleted elements (for map, it can be 0 or 1). For example:
int count = m.erase(3); // Delete element with key 3cout << "Deleted " << count << " elements";3. Deleting using erase() by range
Deletes all elements within the range of iterators. For example:
auto first = m.find(1);auto last = m.find(3);m.erase(first, last); // Delete elements in the range [first,last)5. erase_if() supported since C++11 (C++20 standard)
Conditionally delete elements. For example:
map m = {{1, "A"}, {2, "BB"}, {3, "CCC"}};erase_if(m, [](const auto& item) { return item.second.size() > 1; // Delete elements with value length greater than 1});Complete example code:
#include<map>#include<iostream>using namespace std;int main() { map<int,string> students = { {101, "Alice"}, {102, "Bob"}, {103, "Charlie"}, {104, "David"}, {105, "Eve"} }; // 1. Delete by key students.erase(102); // 2. Delete by iterator auto it = students.find(103); if(it != students.end()) { students.erase(it); } // 3. Delete by range auto first = students.find(104); auto last = students.find(105); students.erase(first, last); // Output remaining elements for(const auto& s : students) { cout << s.first << ": " << s.second << endl; } // 4. Clear map students.clear(); cout << "Size after clearing: " << students.size(); return 0;}unordered_map Class
The unordered_map class is implemented based on a hash table. The working principle of a hash table is to map keys to hash values using a hash function, and then determine the storage location of elements based on the hash value, enabling fast lookup, insertion, and deletion operations. The unordered_map and map have similar basic interface forms for insertion, lookup, and deletion operations.
Examples of Using Mapping Container Classes
1. Counting Word Occurrences
In text processing, it is often necessary to count the occurrences of each word in the text, and unordered_map is very suitable for this scenario. Below is an example code:
#include <iostream>#include <unordered_map>#include <string>#include <sstream>int main() { std::string text = "this is a test this is a test"; std::unordered_map<std::string,int> wordCount; std::stringstream ss(text); std::string word; while (ss >> word) { if (wordCount.find(word) != wordCount.end()) { wordCount[word]++; } else { wordCount[word] = 1; } } for (const auto& pair : wordCount) { std::cout << "Word: " << pair.first << ", Occurrences: " << pair.second << std::endl; } return 0;}The example first defines a std::unordered_map type wordCount container to store words and their occurrences. It uses std::stringstream to split the input text by words, then iterates through each word. If the word already exists in wordCount, its corresponding value (occurrence count) is incremented; if the word does not exist, it is inserted into wordCount with its occurrence count initialized to 1. Finally, it iterates through the wordCount container to output each word and its occurrence count.
2. Implementing a Caching Mechanism
In practical development, a caching mechanism can significantly improve program performance and reduce repeated access to resources. Below is a simple caching mechanism example using unordered_map:
#include <iostream>#include <unordered_map> // Simulate a complex calculation functionint complexCalculation(int num) { std::cout << "Performing complex calculation: " << num << std::endl; return num * num;} class Cache {public: int getValue(int key) { if (cache.find(key) != cache.end()) { std::cout << "Getting value from cache: " << key << std::endl; return cache[key]; } else { int value = complexCalculation(key); cache[key] = value; std::cout << "Calculating and caching value: " << key << std::endl; return value; } } private: std::unordered_map<int,int> cache;};int main() { Cache cache; cache.getValue(5); cache.getValue(5); cache.getValue(10); return 0;}The example code defines a Cache class, which contains an unordered_map type member variable cache to store cached data. The getValue method first checks if a value with the key exists in the cache; if it does, it returns that value, indicating it was retrieved from the cache; if it does not exist, it calls the complexCalculation function to perform the complex calculation, stores the result in the cache, and returns that result, indicating it was calculated and cached.
In the main function, calling cache.getValue multiple times shows that for the same key, the second call retrieves the value directly from the cache without needing to perform the complex calculation again, thus improving program efficiency.