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
Daily Recommendation