C++ map and unordered_map usage and differences

Go to: Map and unordered_ The difference and use of map_ Chen Yunjia's column - CSDN blog_ unordered_map and map

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


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


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:

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  

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  

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  

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 ()
     mypantry = {{"milk",2.0},{"flour",1.5}};
     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:");
     unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");
     if ( got == myrecipe.end() )
         cout << "not found";
         cout << "found "<<got->first << " is " << got->second<<"\n\n";
     myrecipe.at("coffee") = 9.0;
     myrecipe["milk"] = 3.0;
     display(myrecipe,"After modify myrecipe contains:");
     myrecipe.erase(myrecipe.begin());  //Passing position
     myrecipe.erase("milk");    //Pass key
     display(myrecipe,"After erase myrecipe contains:");
     display(myrecipe,"After swap with mypantry, myrecipe contains:");
     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 =
     /************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 
 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

Keywords: C++ data structure map

Added by gazalec on Sat, 06 Nov 2021 01:16:45 +0200