C++無序關聯容器（一）-使用場合和常用函數
碎碎念：
C++11定義了四個無序容器，說是無序，即容器裡面的元素關鍵字無序，因為這些容器不是使用比較運算符來組織元素，而是使用一個哈希函數，和關鍵字類型的==運算符。
對我們普通人來說，一般考慮的都是它的使用場合和其常用的成員函數，所以我們先來介紹這兩個東西。這裡拿map舉例，set同理。
使用場合：
無序容器支持對單個元素的快速檢索，元素在無序容器裡面沒有被排序，而是依靠他們的哈希值被組織進叫做桶的數據結構中。無序容器比map檢索速度快。支持下標訪問。
我們知道，map底層是紅黑樹，查找效率是logn，而無序容器底層是哈希表，查找效率是常數級別。所以，C++primer上說，在關鍵字類型的元素沒有明顯的序的情況下，或者在某些應用中，維護元素有序的代價非常高昂，採用無序容器代替map來說效果會好。
常用的函數：
1.使用無序容器必須加頭文件： #include <unordered_map>
2.初始化：
unordered_map<string, int> A({ {"123", 1},{"456",4} });//C++11列表初始化
unordered_map<string, int> B(A);//copy
unordered_map<string, int> C(A.begin(), A.end());//range
3.更新：
unordered_map<string, int> A{ {"123", 1},{"456",4} };
unordered_map<string, int> B{ {"789", 7},{"101112",10} };
3.1 insert()
A.insert(make_pair<string,int>("123", 5))//插入單個pair
A.insert({ "123", 5 });//插入單個pair
A.insert({{ "123", 5 }, { "456",4 }});//插入多個pair
A.insert(B.begin(),B.end())//插入一個無序容器。
3.2 emplace()添加
unordered_map<string, int> A{ {"123", 1},{"456",4} };
A.emplace("5",4);
3.3 insert()和emplace()區別
c++11標準引入了emplace()，與insert()相對應。empalce操作構造而不是拷貝元素。
1.當我們調用insert()時，我們將元素類型的對象傳遞給它們，這些類型被拷貝到容器中。
2.當我們調用emplace()，會在容器管理的內存空間內直接創建對象。
註：
1.emplace()的參數根據元素的類型變化，參數必須與元素類型的構造函數相匹配。
2.insert()和emplace()只有在關鍵值key在容器中不存在時，才會把該元素插入容器中。
否則如果容器中有關鍵值為key的元素，則什麼也不做。
3.insert和emplace的返回值是一個pair，它的first是一個迭代器，指向具有給定關鍵字的元素，second是一個bool，指出元素是否插入成功。
4.容量相關
unordered_map<string, int> A{ {"123", 1},{"456",4} };
A.size() //返回容器的容量
A.empty()//如果容器為空，返回true，否則返回false
A.max_size()//返回最大容量
5.元素訪問
5.1 下標訪問
unordered_map<string, int> A{ {"123", 1},{"456",4} };
1. A["789"]=7;
如果key為"789"的元素不存在，則插入一個新的元素到容器。
如果key為"789"的元素存在，則保留它的key，更新它的value。
2. int i=A["101"];
如果key為"101"的元素不存在，則返回其對應類型的初始值，int為0。
如果key為"101"的元素存在，則返回其value。
5.2 at訪問
unordered_map<string, int> A{ {"123", 1},{"456",4} };
1.A.at("123")=5;
如果key為"123"的元素存在，則更新其value。如果不存在，拋出一個異常。
http://2.int i=A.at("123");
如果key為"123"的元素存在，則返回其value，如果不存在，則拋出一個異常。
5.3 下標訪問和at訪問的區別：
at訪問時，如果元素的key值不存在，會拋出異常，
下標訪問如果元素的key值不存在，則添加一個關鍵之為key的元素，並對其進行值初始化。
6.查找元素
unordered_map<string, int> A{ {"123", 1},{"456",4} };
1.A.find("123");
如果找到了key為123的元素，則返回其對應的迭代器，如果沒找到，則返回A.end();
常用的用法為if(A.find("123")!=A.end()){}//如果找到了。
2.A.count("123");
如果容器中有key為123的元素，則返回其個數，在map中也就是1，不存在返回0；
7.刪除元素。
unordered_map<string, int> A{ {"123", 1},{"456",4} };
1.A.erase("123");//從A中刪除每個關鍵字為"123"的元素。返回刪除元素的個數。
2.auto w=A.find("123"); A.erase(w)//從A中刪除迭代器w指向的元素。返回w之後元素的迭代器。
8.清空容器
unordered_map<string, int> A{ {"123", 1},{"456",4} };
A.clear();//所有的元素從容器中移除，並且調用他們的構造函數，容器的大小變為0.
9.關於桶的函數:unordered_map<string, int> A{ {"123", 1},{"456",4} };
9.1桶的介面
1. A.bucket_count(); //返回正在使用的桶的數目
2. A.max_bucket_count()//容器能容納的最多的桶的數目
3. A.bucket_size(n) //第n個桶中有多少元素
4. A.bucket(k) //關鍵字為K的元素在第幾個桶中，返回的是int。
9.2哈希策略
1. A.load_factor() //返回每個桶的平均元素數量 float值。 A.size()/A.bucket_count()
2. A.rehash(n)//重組存儲，使得桶的數量大於n
3. A.reserve(n)//通過設置預期容器的大小，使得我們不必因為元素的增加多次重組存儲。
9.3桶迭代
1. A.begin(n)，A.end(n)//返回桶n的首元素迭代器和尾後迭代器。
舉例:依次輸出每個桶中的元素：
int main()
{
std::unordered_map<std::string, std::string> mymap;
mymap = { { "Australia","Canberra" },{ "U.S.","Washington" },{ "France","Paris" } };
std::cout << "mymap contains:";
for (auto it = mymap.begin(); it != mymap.end(); ++it)
std::cout << " " << it->first << ":" << it->second;
std::cout << std::endl;
std::cout << "mymaps buckets contain:
";
for (unsigned i = 0; i < mymap.bucket_count(); ++i)
{
std::cout << "bucket #" << i << " contains:";
for (auto local_it = mymap.begin(i); local_it != mymap.end(i); ++local_it)
{
std::cout << " " << local_it->first << ":" << local_it->second;
}
std::cout << std::endl;
}
system("pause");
return 0;
}
推薦閱讀：
