1. unordered series containers
In C++98, STL provides a series of associative containers with red-black tree structures at the bottom, including set, multiset, map and multimap. The time complexity of query operations for these containers is O ( log N ) O(logN)O(logN), where N is the number of elements in the container.
In order to improve query efficiency, C++11 introduced unordered_map and unordered_set, two underlying hash table-based associative containers. Compared with associative containers with a red-black tree structure, the unordered series of containers have higher query efficiency on average, and the time complexity is a constant level O ( 1 ) O(1)O(1). When hash functions are well designed and don’t have too many collisions, they can perform very well on operations such as insertion, lookup, and deletion.
unordered_map is a container that stores key-value pairs, each key uniquely corresponds to a value; and unordered_set is a container that stores unique elements. They are used similarly to associative containers with a red-black tree structure, providing methods such as insert, erase, and find to operate elements.
Note: The order of elements of unordered_map and unordered_set is determined based on the hash value calculated by the hash function, so they cannot guarantee that the order of the elements is stable. If you need an ordered container, you can still use an associative container with a red-black tree structure.
2. unordered_map
1. Introduction to unordered_map
unordered_map is an associative container in the C++ standard library, which is implemented based on a hash table. unordered_map provides a way to store key-value pairs, where each key uniquely corresponds to a value. It is designed for insertion, search, and deletion operations with constant time complexity in the average case.
Unordered_map is similar to map in usage, but its internal structure is different. unordered_map uses a hash function to map keys into buckets, and uses linked lists or other data structures within buckets to resolve conflicts. Through the hash function and bucket structure, the value corresponding to the key can be quickly located.
?Function characteristics
Constant time complexity: On average, the insertion, search, and deletion operations of unordered_map all have constant time complexity. This is because the hash table makes full use of the hashing properties of the hash function to quickly locate elements.
Unordered storage: Unlike map, unordered_map does not store keys in order, but stores them according to the hash value calculated by the hash function. Therefore, the result of traversing unordered_map is unordered.
Custom hash function: unordered_map supports custom hash function. According to the type of key, a hash function that meets the requirements can be implemented to improve query efficiency. If no custom hash function is provided, the default hash function will be used.
Conflict handling: Due to the limitations of hash functions, multiple elements may be mapped to the same bucket, which is a conflict. unordered_map uses linked lists or other data structures to resolve conflicts and ensure correct storage and search of key-value pairs.
Support various data types: unordered_map can store key-value pairs of various data types, including built-in types and custom types.
Note: When using unordered_map, you need to include the header file
2. unordered_map interface
–Constructor
Default constructor:
unordered_map
Create an empty unordered_map object using the default constructor.
List initialization constructor:
unordered_map
Use an initialization list to create an unordered_map object and initialize the key-value pairs in it.
Interval constructor:
template
unordered_map(InputIt first, InputIt last);
Creates an unordered_map object from elements in the specified range. The range is specified by the iterators first and last, which can be an array, container, or other data structure that implements a forward iterator.
Copy constructor:
unordered_map(const unordered_map & amp; other);
Use another unordered_map object for copy construction to create an identical copy of the original unordered_map.
Move constructor:
unordered_map(unordered_map & amp; & amp; other) noexcept;
Use another unordered_map object for move construction, create a new unordered_map object, and steal resources from the original object.
| Constructor | Function introduction |
| unordered_map() | Recognize the constructor and create an empty unordered_map object. |
| unordered_map(initializer_list |
The list initialization constructor uses the initialization list to create an unordered_map object and initialize the key-value pairs in it. |
| unordered_map(const unordered_map & amp;) | Copy constructor, create An identical copy of the original unordered_map. |
| unordered_map(unordered_map & amp; & amp;) noexcept | Move construction Function, creates a new unordered_map object and steals resources from the original object. |
| unordered_map(size_type) | Constructor to create a map with the specified number of buckets unordered_map object. |
| unordered_map(size_type, const hasher & amp;, const key_equal & amp;) | Constructor that creates an unordered_map object with the specified number of buckets, hash function, and equality comparison operator. |
| template unordered_map(InputIt, InputIt) | Interval constructor, specified from An unordered_map object is created for the elements in the range. |
– Capacity of unordered_map
| Function declaration | Function introduction |
| unordered_map::size | Returns the number of key-value pairs in unordered_map. |
| unordered_map::empty | Determine whether unordered_map is empty and return true or false. |
| unordered_map::max_size | Returns the maximum number of elements that unordered_map can accommodate . |
You can use iterators to traverse all elements in unordered_map. The sample code is as follows:
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map = {<!-- -->{1, "one"}, {2, "two"}, {3, "three"}};
// Use an iterator to traverse unordered_map and print the key-value pairs
for (auto it = map.begin(); it != map.end(); + + it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
// Use the find function to find the element with the specified key
auto findIt = map.find(2);
if (findIt != map.end()) {
std::cout << "Key: " << findIt->first << ", Value: " << findIt->second << std::endl;
}
return 0;
}
– Element access of unordered_map
Subscript operator []: Use keys as indexes to access and modify elements in unordered_map. If the key exists, the corresponding value is returned; if the key does not exist, the key is inserted into the unordered_map and a default constructed value is returned.
std::unordered_map<std::string, int> map = {<!-- -->{"apple", 1}, {"banana", 2}, {"orange", 3}};
int value = map["apple"]; // The value corresponding to the access key "apple"
map["banana"] = 5; // Modify the value corresponding to the key "banana"
map["grape"] = 4; // Insert a new key "grape" and correspond to a value
Use the member function at(): use keys as parameters to access and modify elements in unordered_map. If the key exists, the corresponding value is returned; if the key does not exist, the std::out_of_range exception is thrown.
std::unordered_map<std::string, int> map = {<!-- -->{"apple", 1}, {"banana", 2}, {"orange", 3}};
int value = map.at("apple"); // The value corresponding to the access key "apple"
map.at("banana") = 5; // Modify the value corresponding to the key "banana"
map.at("grape") = 4; // throws exception because key "grape" does not exist
– Unordered_map modification operation
| Function declaration | Function introduction |
| insert | Insert key-value pairs into the container |
| erase | Delete the container Key-value pairs |
| void clear() | Clear the number of valid elements in the container |
| void swap(unordered_map & amp;) | Swap elements in two containers |
– Bucket operation of unordered_map
| Function declaration | Function introduction |
| size_t bucket_count()const | Returns the total number of buckets in the hash bucket |
| size_t bucket_size(size_t n) const | Returns the total number of valid elements in bucket n |
| size_t bucket(const K & amp; key) | Returns the bucket number where the element key is located |
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57457 people are learning the system