unordered_map

unordered_map 的介紹文檔

unordered_map 的介紹文檔：來自cpluscplus.com 的中文翻譯

1. unordered_map是存儲<key, value>鍵值對的關聯式容器，其允許通過keys快速的索引到與
   其對應的value。
2. 在unordered_map中，鍵值通常用于惟一地標識元素，而映射值是一個對象，其內容與此
   鍵關聯。鍵和映射值的類型可能不同。
3. 在內部,unordered_map沒有對<kye, value>按照任何特定的順序排序, 為了能在常數范圍內
   找到key所對應的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。
4. unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭
   代方面效率較低。
5. unordered_maps實現了直接訪問操作符(operator[])，它允許使用key作為參數直接訪問
   value。
6. 它的迭代器至少是前向迭代器。

unordered_map 是 C++11 的語法，C++98 是沒有 unordered_map 的

構造函數

unordered_map 存儲的數據是：key-value 的結構，因此實例化 unordered_map 需要傳入兩個模板參數。unordered-map 的底層數據結構是哈希表。unordered_map 數據 key-value 形式的存儲你可以理解為哈希表存儲了一個 pair 。傳入的第一個模板參數就是 pair 的 first，傳入的第二個模板參數就是 pair 的 second。

• unordered_map 可以無參構造，這是在做算法題用的比較多的。
• unordered_map 可以使用 initializer_list 來初始化。initializer_list 是 C++11 的語法。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash1; //這是無參構造unordered_map<int, int> hash2({{1,1}, {2,2}, {3,3}}); //這是使用initializer_list來構造return 0;
}

bool empty() const

這個函數用來判斷哈希表是否為空，為空返回 true；否則返回 false。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash1; //這是無參構造unordered_map<int, int> hash2({{1,1}, {2,2}, {3,3}}); //這是使用initializer_list來構造cout << hash1.empty() << endl; //輸出：1cout << hash2.empty() << endl; //輸出：0return 0;
}

size_t size() const

這個函數用來獲取哈希表中有效元素的個數。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash1; //這是無參構造unordered_map<int, int> hash2({{1,1}, {2,2}, {3,3}}); //這是使用initializer_list來構造cout << hash1.size() << endl; //輸出：1cout << hash2.size() << endl; //輸出：3return 0;
}

迭代器

• begin：返回哈希表中第一個元素的位置對應的迭代器。
• end：返回的迭代器并不指向任何元素，而是指向容器中最后一個元素之后的位置。因此，返回的值不應被取消引用。
  有了 begin 和 end 迭代器，我們就可以遍歷 unordered_map 了。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造auto it = hash2.begin();while(it != hash2.end()){cout << it->first << " " << it->second << endl;++it;}return 0;
}

我們看到最后遍歷得到的結果與插入的順序并不相同。這也證明了 unordered_map 是一個無序容器。僅僅存儲一個 key-value 的數據。

const V& operator[](const K& key)

這個函數和 map 的 operator[] 很像。
如果 key 與容器中某個元素的鍵相匹配，函數會返回其映射值(value)的引用。

如果 key 與容器中任何元素的鍵不匹配，函數將插入一個具有該鍵的新元素，并返回其映射值的引用。請注意，即使沒有為元素分配映射值（元素是使用默認構造函數構造的），容器的大小也會增加一個。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造cout << hash2[10] << endl; //輸出：10hash2[40]; // 使用 operator[] 訪問key為 40 的元素，但是不存在，會插入一個 key 為 40 的元素，value我們沒有指定，那么會調用 value 類型的默認構造函數：int() 作為 40 這個 key 值的 value 值cout << hash2[40] << endl; //輸出：0return 0;
}

iterator find(const K& key)

在 unordered_map 中查找 key，如果查找成功返回該位置對應的迭代器，如果查找失敗，那么返回 unordered_map::end ，就是 end 迭代器。
下面的代碼中，我們使用 find 查找一個元素，通過得到的迭代器訪問他的 value。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造auto it = hash2.find(10);if(it == hash2.end()) cout << "此元素不存在" << endl;else cout << it->second << endl; //輸出：10return 0;
}

size_t count(const K& key) const

搜索容器中鍵為 key 的元素，并返回找到的元素個數。由于 unordered_map 容器不允許鍵重復，這意味著如果容器中存在鍵為 key 的元素，函數實際返回 1，否則返回 0。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造cout << hash2.count(10) << endl; //輸出：1cout << hash2.count(40) << endl; //輸出：0return 0;
}

pair<iterator, bool> insert ( const pair<K, V>& kv )

這個函數和 map 的 insert 完全一樣。
你可以向 unordered_map 中插入一個鍵值對。
函數返回一個 pair 對象，其第一個元素是一個迭代器，指向容器中新插入的元素或鍵等價的元素，另一個 bool 值表示該元素是否插入成功。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造pair<unordered_map<int, int>::iterator, bool> ret1 = hash2.insert(make_pair(40, 40));cout << "插入成功與否：" << ret1.second << endl; //插入成功，ret1.second 為 1pair<unordered_map<int, int>::iterator, bool> ret2 = hash2.insert(make_pair(30, 0));cout << ret2.first->second << endl; //插入失敗，得到的是原 key 為 30 的元素對應的 value：30 而不是新插入的 0return 0;
}

insert 函數也可以插入 initializer_list 和構造函數那里一樣：
hash2.insert({60,60})

erase 函數

erase 有三個重載的版本：

• 第一個版本：刪除一個迭代器位置的元素。
• 第二個版本：刪除鍵為 k 的元素。
• 第三個版本：刪除一個迭代器區間。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造hash2.erase(hash2.begin()); //第一個版本hash2.erase(30); //第二個版本hash2.erase(hash2.begin(), hash2.end()); //第三個版本return 0;
}

void clear() const

清空 unordered_map 中所有的元素。

#include<iostream>
#include<unordered_map>
using namespace std;int main()
{unordered_map<int, int> hash2({{10,10}, {20,20}, {30,30}}); //這是使用initializer_list來構造hash2.clear();cout << hash2.size() << endl; // 輸出：0return 0;
}

unordered_set

這是 unordered_set 的介紹文檔：來自 cpluscplus.com。

• unordered_set 是一種不按特定順序存儲唯一元素的容器，可以根據元素的值快速檢索單個元素。

• 在 unordered_set 中，元素的值同時也是其鍵，可以唯一地識別該元素。鍵是不可變的，因此，unordered_set 中的元素一旦進入容器就不能修改，但可以插入和移除。

• 在內部，unordered_set 中的元素不按任何特定順序排序，而是根據它們的哈希值組織成桶，以便直接按其值快速訪問單個元素（平均時間復雜度不變）。

• 無序集容器在按鍵訪問單個元素時比集合容器更快，但在對元素子集進行范圍迭代時，其效率通常較低。

• 容器中的迭代器至少是前向迭代器。

unordere_set 存儲的數據只有一個 key。
unordered_set 與 unordered_map 的接口完全相同。這里就不再贅述了。