Comparison of features
1. std::map
- Underlying implementation:Based on red and black trees (a self-balancing binary search tree).
- Element order: Elements are arranged in ascending order of keys.
- Uniqueness of keys: Each key can only appear once, and elements that insert duplicate keys will be ignored.
- Find efficiency: The time complexity of the search operation is O ( l o g n ) O(log n) O(logn),in n n nis the number of elements in the container.
- Insert and Delete Efficiency: The time complexity of the insertion and deletion operations is also O ( l o g n ) O(log n) O(logn)。
2. std::unordered_map
- Underlying implementation: Based on hash table.
- Element order: There is no specific order of elements, and the storage location is determined by the hash value of the key.
- Uniqueness of keys: Each key can only appear once, and the element that inserts the duplicate key will overwrite the original element.
- Find efficiency: On average, the time complexity of the search operation is O ( 1 ) O(1) O(1), but in the worst case scenario it may be achieved O ( n ) O(n) O(n)。
- Insert and Delete Efficiency: On average, the time complexity of the insertion and deletion operations is O ( 1 ) O(1) O(1)。
3. std::multimap
- Underlying implementation: Also based on red and black trees.
- Element order: Elements are arranged in ascending order of keys.
- Uniqueness of keys: Allow key duplication, that is, multiple elements can have the same key.
- Find efficiency: The time complexity of the search operation is O ( l o g n ) O(log n) O(logn)。
- Insert and Delete Efficiency: The time complexity of the insertion and deletion operations is O ( l o g n ) O(log n) O(logn)。
4. std::unordered_multimap
- Underlying implementation: Based on hash table.
- Element order: The elements have no specific order, and the storage location is determined by the hash value of the key.
- Uniqueness of keys: Allow keys to be repeated.
- Find efficiency: On average, the time complexity of the search operation is O ( 1 ) O(1) O(1), at worst O ( n ) O(n) O(n)。
- Insert and Delete Efficiency: On average, the time complexity of the insertion and deletion operations is O ( 1 ) O(1) O(1)。
5. hash_map(SGI STL extension)
- Underlying implementation: Based on hash table.
- Element order: The elements have no specific order, and the storage location is determined by the hash value of the key.
- Uniqueness of keys: Each key can only appear once, and the element that inserts the duplicate key will overwrite the original element.
- Find efficiency: On average, the time complexity of the search operation is O ( 1 ) O(1) O(1), at worst O ( n ) O(n) O(n)。
-
Insert and Delete Efficiency: On average, the time complexity of the insertion and deletion operations is O ( 1 ) O(1) O(1)。
In early C++ standards (such as C++98, C++03) there arehash_map, but it is not part of the standard library, but comes from the SGI STL extension. In C++11 and later standards,hash_mapquiltstd::unordered_mapAlternative,std::unordered_mapBecome a standard hash table implementation. However, some compilers still support ithash_map, the following is for youhash_mapAnd compare and give the corresponding C++ sample code.
C++ sample code
#include <iostream>
#include <map>
#include <unordered_map>
#include <ext/hash_map> // For compilers that support hash_map// Demonstrate the use of std::mapvoid testStdMap() {
std::map<int, std::string> myMap;
myMap[1] = "apple";
myMap[2] = "banana";
myMap[1] = "cherry"; // Repeat key 1, which will overwrite the original value std::cout << "std::map:" << std::endl;
for (const auto& pair : myMap) {
std::cout << << ": " << << std::endl;
}
}
// Demonstrate the use of std::unordered_mapvoid testUnorderedMap() {
std::unordered_map<int, std::string> myUnorderedMap;
myUnorderedMap[1] = "apple";
myUnorderedMap[2] = "banana";
myUnorderedMap[1] = "cherry"; // Repeat key 1, which will overwrite the original value std::cout << "\nstd::unordered_map:" << std::endl;
for (const auto& pair : myUnorderedMap) {
std::cout << << ": " << << std::endl;
}
}
// Demonstrate the use of std::multimapvoid testMultiMap() {
std::multimap<int, std::string> myMultiMap;
({1, "apple"});
({2, "banana"});
({1, "cherry"}); // key 1 repeats, allowing insertion std::cout << "\nstd::multimap:" << std::endl;
for (const auto& pair : myMultiMap) {
std::cout << << ": " << << std::endl;
}
}
// Demonstrate the use of std::unordered_multimapvoid testUnorderedMultiMap() {
std::unordered_multimap<int, std::string> myUnorderedMultiMap;
({1, "apple"});
({2, "banana"});
({1, "cherry"}); // key 1 repeats, allowing insertion std::cout << "\nstd::unordered_multimap:" << std::endl;
for (const auto& pair : myUnorderedMultiMap) {
std::cout << << ": " << << std::endl;
}
}
// Demonstrate the use of hash_mapvoid testHashMap() {
__gnu_cxx::hash_map<int, std::string> myHashMap;
myHashMap[1] = "apple";
myHashMap[2] = "banana";
myHashMap[1] = "cherry"; // Repeat key 1, which will overwrite the original value std::cout << "\nhash_map:" << std::endl;
for (const auto& pair : myHashMap) {
std::cout << << ": " << << std::endl;
}
}
int main() {
testStdMap();
testUnorderedMap();
testMultiMap();
testUnorderedMultiMap();
testHashMap();
return 0;
}Code explanation
-
testStdMapFunctions are demonstratedstd::mapWhen using the use of the elements that insert the duplicate key, the elements will overwrite the original value, and the elements will be arranged in ascending order of the key. -
testUnorderedMapFunctions are demonstratedstd::unordered_mapWhen using the use of the elements that insert duplicate keys, the elements will also overwrite the original value, and the elements have no specific order. -
testMultiMapFunctions are demonstratedstd::multimapThe use of the , allows the elements of the repeated key to be inserted, and the elements are arranged in ascending order of the key. -
testUnorderedMultiMapFunctions are demonstratedstd::unordered_multimapThe use of the elements that allow the insertion of duplicate keys, without a specific order of the elements. -
testHashMapFunctions are demonstratedhash_mapInserting the repeating key elements will overwrite the original value, and the elements have no specific order.
It should be noted thathash_mapNot part of standard C++, if the compiler you are using does not support itext/hash_mapHeader file, code may not be compiled. It is recommended to use standardstd::unordered_map。
This is the end of this article about various map comparisons of C++. For more related C++ map comparison content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!