C++STL: unordered_map - Ling Yao - blog Park
The header files to be imported are different
map: #include < map >
unordered_map: #include < unordered_map >
Different internal implementation mechanisms
Map: a red black tree is implemented inside the map (red black tree is a non strictly balanced binary search tree, while AVL is a strictly balanced binary search tree). The red black tree has the function of automatic sorting. Therefore, all elements inside the map are orderly, and each node of the red black tree represents an element of the map. Therefore, a series of operations such as searching, deleting and adding to the map are equivalent to the operations on the red black tree. The elements in the map are stored according to the binary search tree (also known as binary search tree and binary sort tree. The feature is that the key values of all nodes in the left subtree are less than the key values of the root node, and the key values of all nodes in the right subtree are greater than the key values of the root node). The key values can be traversed from small to large by using medium order traversal.
unordered_map: unordered_map implements a Hash table (also known as Hash table. By mapping the key value to a position in the Hash table to access the records, the time complexity of search can reach O(1), which is widely used in massive data processing). Therefore, the arrangement order of its elements is disordered.
Advantages, disadvantages and applicability
map:
advantage:
Ordering, which is the biggest advantage of map structure. The ordering of its elements will simplify a lot of operations in many applications
The red black tree implements a red black book internally, so that many operations of map can be realized under the time complexity of lgn, so the efficiency is very high
Disadvantages: the space occupancy rate is high because the map implements a red black tree internally, which improves the operation efficiency, but because each node needs to save the parent node, child node and red / Black properties, each node occupies a lot of space
Where applicable: for those problems with sequence requirements, using map will be more efficient
unordered_map:
Advantages: because the hash table is implemented internally, its lookup speed is very fast
Disadvantages: the establishment of hash table is time-consuming
Where applicable: unordered for finding problems_ Map will be more efficient, so when you encounter a search problem, you often consider using unordered_map
Map and unordered_ Use of map
unordered_map member function:
iterator
begin returns an iterator that points to the beginning of the container
end Returns an iterator pointing to the end of the container
cbegin Returns a const_iterator that points to the beginning of the container
cend returns a constant iterator pointing to the end of the container
Capacity
size Returns the number of valid elements
max_size Return unordered_ Maximum number of elements supported by map
empty Judge whether it is empty
Element access
operator[] Access element
at Access element
Element modification
insert Insert element
erase delete element
swap exchange content
clear Empty content
Empty constructs and inserts an element
emplace_hint construct and insert an element as prompted
operation
find finds the element through the given primary key. If it is not found, it returns unordered_map::end
count returns the number of elements that match a given primary key
equal_range returns a range of elements whose values match the given search value
Buckets
bucket_count returns the number of buckets
max_bucket_count Returns the maximum number of slots
bucket_size Return slot size
bucket returns the serial number of the slot where the element is located
load_factor returns the load factor, that is, the maximum number of elements in an element slot (Bucket)
max_load_factor Returns or sets the maximum load factor
rehash Set number of slots
reserve Request to change container capacity
Insert element instance:
// unordered_map::insert
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
void display(unordered_map<string,double> myrecipe,string str)
{
cout << str << endl;
for (auto& x: myrecipe)
cout << x.first << ": " << x.second << endl;
cout << endl;
}
int main ()
{
unordered_map<string,double>
myrecipe,
mypantry = {{"milk",2.0},{"flour",1.5}};
/****************Insert*****************/
pair<string,double> myshopping ("baking powder",0.3);
myrecipe.insert (myshopping); // Copy insert
myrecipe.insert (make_pair<string,double>("eggs",6.0)); // Move insert
myrecipe.insert (mypantry.begin(), mypantry.end()); // Range insertion
myrecipe.insert ({{"sugar",0.8},{"salt",0.1}}); // Initialize array insertion (you can use two-dimensional one-time insertion)
//Insert multiple elements, or insert one element with one dimension)
myrecipe["coffee"]// = 10.0; // Insert as array
display(myrecipe,"myrecipe contains:");
/****************Search*****************/
unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");
if ( got == myrecipe.end() )
cout << "not found";
else
cout << "found "<<got->first << " is " << got->second<<"\n\n";
/****************Modification*****************/
myrecipe.at("coffee") = 9.0;
myrecipe["milk"] = 3.0;
display(myrecipe,"After modify myrecipe contains:");
/****************Erase*****************/
myrecipe.erase(myrecipe.begin()); //Passing position
myrecipe.erase("milk"); //Pass key
display(myrecipe,"After erase myrecipe contains:");
/****************Exchange*****************/
myrecipe.swap(mypantry);
display(myrecipe,"After swap with mypantry, myrecipe contains:");
/****************Empty*****************/
myrecipe.clear();
display(myrecipe,"After clear, myrecipe contains:");
return 0;
}
/*
myrecipe contains:
salt: 0.1
milk: 2
flour: 1.5
coffee: 10
eggs: 6
sugar: 0.8
baking powder: 0.3
found coffee is 10
After modify myrecipe contains:
salt: 0.1
milk: 3
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3
After erase myrecipe contains:
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3
After swap with mypantry, myrecipe contains:
flour: 1.5
milk: 2
After clear, myrecipe contains:
*/
Traversal instance
// unordered_map::bucket_count
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main ()
{
unordered_map<string,string> mymap =
{
{"house","maison"},
{"apple","pomme"},
{"tree","arbre"},
{"book","livre"},
{"door","porte"},
{"grapefruit","pamplemousse"}
};
/************begin And end iterators***************/
cout << "mymap contains:";
for ( auto it = mymap.begin(); it != mymap.end(); ++it )
cout << " " << it->first << ":" << it->second;
cout << endl;
/************bucket Operation***************/
unsigned n = mymap.bucket_count();
cout << "mymap has " << n << " buckets.\n";
for (unsigned i=0; i<n; ++i)
{
cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";
for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
cout << "[" << it->first << ":" << it->second << "] ";
cout << "\n";
}
cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;
cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;
return 0;
}
/*
mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre
house:maison
mymap has 7 buckets.
bucket #0's size:2 contains: [book:livre] [house:maison]
bucket #1's size:0 contains:
bucket #2's size:0 contains:
bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]
bucket #4's size:0 contains:
bucket #5's size:1 contains: [apple:pomme]
bucket #6's size:1 contains: [door:porte]
key:'apple' is in bucket #5
key:'computer' is in bucket #6
*/