brief introduction

Obviously , The two header files are map,set Corresponding to header file unordered edition . So they have an important property :

Disorder of order
How to disorder order

this unorder Implied , The underlying implementation of classes in these two header files ----Hash.
That's why , You can declare these unordered When template class , Pass in a custom hash function , It's a hash function (hash function object).

Elements with the same hash value are placed in the same bucket (bucket) in .

Why disorder

Mapping is provided at , In the case of aggregate function , Focus on quick acquisition of elements .

Using tree structure ( Mangrove , Binary search tree, etc ) Realized map,set, Looking for , obtain , When modifying elements , It is usually necessary to traverse the tree structure from top to bottom from the root node , So the time complexity is linear ;
Through hash table , As long as the hash function and bucket size are selected properly , Time complexity will be constant ( Function only needs to be called once , And make a small search ).

Unidirectional iterator

The implementation of hash table complicates the two-way traversal on the container , There seems to be no way to be efficient and fast .
therefore ,unorder Version of map and set Forward iterator only ( wrong unorder Version provides bidirectional iterators ).

What functions are missing

lower_bound
upper_bound
Normal version map and set, They are ordered containers , Every element can be judged before which one it should be , After which ;
This version of the container is different , Because they're out of order , Can't prioritize each element . therefore , The container does not have enough information to calculate these two boundaries ( However, it is still feasible to compare the equality of elements ).

What more functions

Concept out of implementation , There are many special functions necessary for this version of class template .

Barrel related (Bucket)

bucket_count : Number of barrels .
max_bucket_count : Maximum number of barrels .
bucket_size : Barrel size , Capacity .
bucket : Locate the bucket position of a given element .
Hash policy

load_factor : return load factor, That is, the ratio of the current element quantity of the container to the barrel quantity .
max_load_factor : Return or set maximum load factor.
rehash : Set the number of buckets , And re hash the elements .
reserve : Request to reserve the number of buckets to the given value .
be aware , No function can change the capacity of a barrel , Maybe barrels are also growing dynamically .

Observers

hash_function : Return hash function ( Passed in as a parameter on declaration , Or default at funtional In the header file hash).
key_eq : return key Equality predicate of , Situation and hash_function be similar .

-------------------------------------------------------------------------------------

C++ 11 Four new unordered Association containers are added to the standard , namely  
unordered_map  mapping  
unordered_multimap  Multiple mapping  
unordered_set  aggregate  
unordered_multiset  Multiple sets

And ordinary map and set The basic functions of , But the internal implementation is totally different . 
map And set Red black tree  
unordered_map and unordered_set The implementation method of is hash function , So the unordered Association container will not be based on key Value sorts the stored elements .

<>unordered_map

Insert operation :
 
*
#include<bits/stdc++.h>

*
using namespace std;

*
typedef pair<string,size_t> pss;

*
int main()

*
{

*
ios::sync_with_stdio(false);

*  
*
unordered_map<string,size_t> u_map;

*
pss p1={"efg",2};

*  
*
string s="abc";

*
u_map[s]++;// Insert with subscript

*  
*
u_map.insert(p1);// use nsert Function inserts a pair

*  
*
u_map.insert({{"www",2},{"wqwe",3}});// Insert an initialization list

*  
*  
*
vector<pss> vp={{"wrrr",2},{"ttt",3}};

*  
*
u_map.insert(vp.begin(),vp.end());// Insert an iterator range

*  
*
for(auto x:u_map)

*
cout<<x.first<<" "<<x.second<<endl;

*
return 0;

*
}

Find and delete operations

Find function :find

And other containers find Same method , Parameter contents can be iterators , Or it could be key value . 
Return content as iterator , If the find does not exist , Return iterator tail .
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*
auto it=u_map.find("qq");

*
if(it!=u_map.end())

*
cout<<it->first<<" "<<it->second<<endl;

*  
Delete function :earse

And other containers erase Same method , Parameters can be iterators , Or it could be key value .
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*
u_map.erase("www");// Directly according to key Value delete

*  
*
for(auto x:u_map)

*
cout<<x.first<<" "<<x.second<<endl;

<> Barrel management

Because the implementation of unordered Association container is based on hash function , Then we need to solve the conflict , Open address method and zipper method are commonly used to solve conflicts . stay C++ Of unordered_map among , What is used is ” bucket ” Method of , In other words, the conflicting elements are all stored in a bucket . Use the zipper diagram as an example

stay unordered_map The hash policy used in can be customized by the user through function overloading .

Traverse each barrel , And output the elements in the bucket
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*  
*
for(auto i=0;i<u_map.bucket_count();i++)

*
{

*
for(auto it=u_map.begin(i);it!=u_map.end(i);it++)// Add parameters to iterator , Select the number of buckets

*
{

*
cout<<"bucket: "<<i<<" "<<it->first<<" "<<it->second<<endl;

*
}

*  
*
}

How to view the content to be saved hash After function processing hash value ? have access to hash_function function .
 
*
typedef unordered_map<string,size_t> string_int_map

*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*
string_int_map::hasher fn=u_map.hash_function();

*  
*
for(auto it=vp.begin();it!=vp.end();it++)

*
{

*
cout<<it->first<<" The hash value of is : "<<fn(it->first)<<endl;

*
}

<> Custom type

stay unordered_map In the middle of the structure or class Overload required for operation == operator , Customize at the same time hash function .
 
*
#include<bits/stdc++.h>

*
using namespace std;

*  
*
struct node

*
{

*
string name;

*
int number;

*
node(){}

*
bool operator==(const node& n) const// heavy load == operator

*
{

*
return name==n.name;

*
}

*
};

*  
*
struct myhash// custom hash function

*
{

*
size_t operator()(const node &n) const

*
{

*
return n.name.size();// As long as the name hash value

*
}

*
};

*
int main()

*
{

*
ios::sync_with_stdio(false);

*  
*
unordered_map<node,size_t,myhash> u_map;

*  
*
node n;

*
n.name="mike";

*
n.number=100;

*  
*
u_map.insert({n,10});

*  
*  
*
return 0;

*
}

If a structure or class uses a member of the system as its function hash Value , You can do the following  

For example, a structure is defined , It has num and res Two int Type member , Now I want to store this structure in unordered_set among , among hash According to res The hash function of , I don't want to write it myself , I hope I can use the system's own right int Processed hash function .
 
*
typedef unordered_set<int> usi;

*  
*
struct node

*
{

*
int num;

*
int res;

*
node(int n,int r){ num = n, res = r;}

*
bool operator==(const node& n) const// heavy load == operator

*
{

*
return res==n.res;

*
}

*
};

*
struct myhash

*
{

*
size_t operator()(const node &n) const

*
{

*
usi::hasher fn= usi().hash_function();

*
//usi It's a unordered_set<int>

*
// Select its hash function as the hash function in our definition structure

*
return fn(n.res);// handle res Value is returned

*
}

*
};

*
// Use this when declaring unordered_set<node,myhash>

unordered_set Operation and nature of unordered_map Roughly similar .

In terms of efficiency ,hash The operation time complexity of is O(1), But in the real world , Need to hash Detailed design of the function of , Otherwise, the cost of efficiency and memory will be large .

Technology
©2019-2020 Toolsou All rights reserved,
First knowledge python Skills summary GDOI2019 travels c Linguistic 5 Three common sorting methods Python Basic knowledge and notes " Cephalosporin wine Say go and go "? DANGER ! Don't drink alcohol when taking these drugs Thorough explanation from Zhongtai vue The component page height is adaptive according to the screen size Classical algorithm - recursion ( The case of raw rabbit ) Big data tells you , How tired are Chinese women about keras use fit_generator Encountered in StopIteration