unordered_map和unordered的介紹和使用

unordered系列關聯式容器

unordered_map

unordered_map的接口說明

unordered_map的定義方式

unordered_map接口的使用

unordered_map的容量

unordered_map的迭代器

unordered_map的元素訪問

unordered_map的查詢

unordered_map的修改操作

unordered_multimap

unordered_set

unordered_set的定義方式

unordered_set的接口使用

unordered_multiset

unordered系列關聯式容器

在C++98中，STL提供了底層為紅黑樹結構的一系列關聯式容器，在查詢時效率可達到logN，即最差情況下需要比較紅黑樹的高度次，當樹中的節點非常多時，查詢效率也不理想。最好的查詢是，進行很少的比較次數就能夠將元素找到，因此在C++11中，STL又提供了4個 unordered系列的關聯式容器，這四個容器與紅黑樹結構的關聯式容器使用方式基本類似，只是其底層結構不同

unordered_map

1. unordered_map是存儲鍵值對的關聯式容器，其允許通過keys快速的索引到與其對應的value。

2. 在unordered_map中，鍵值通常用于惟一地標識元素，而映射值是一個對象，其內容與此鍵關聯。鍵和映射值的類型可能不同。

3. 在內部,unordered_map沒有對按照任何特定的順序排序, 為了能在常數范圍內找到key所對應的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。

4. unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。

5. unordered_maps實現了直接訪問操作符(operator[])，它允許使用key作為參數直接訪問 value。

6. 它的迭代器至少是前向迭代器。

unordered_map的接口說明

unordered_map的構造

unordered_map的定義方式

方式一：指定key和value的類型構造一個空容器。

unordered_map<int, double> um1; //構造一個key為int類型，value為double類型的空容器

方式二：拷貝構造某同類型容器的復制品。

unordered_map<int, double> um2(um1); //拷貝構造同類型容器um1的復制品

方式三：使用迭代器拷貝構造某一段內容。

//使用迭代器區間構造
string str = "nxbw";
unordered_map<int, double> mp3(str.begin(), str.end());

unordered_map接口的使用

unordered_map的容量

bool empty() const? 檢測unordered_map是否為空

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
cout << mp1.empty() << endl; // 0unordered_map<int, string> mp2;
cout << mp2.empty() << endl; // 1

size_t size() const? 獲取unordered_map的有效元素個數

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
mp1.emplace(2, "111");
mp1.emplace(3, "111");cout << mp1.size() << endl; // 3

unordered_map的迭代器

begin 返回unordered_map第一個元素的迭代器

unordered_map<int, string> mp1;unordered_map<int, string>::iterator it = mp1.begin();mp1.emplace(1, "111");
mp1.emplace(2, "111");
mp1.emplace(3, "111");cout << it->first << ' ' << it->second << endl; // 1 111

end 返回unordered_map最后一個元素下一個位置的迭代器

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
mp1.emplace(2, "111");
mp1.emplace(3, "222");unordered_map<int, string>::iterator it = mp1.end();
--it;
cout << it->first << ' ' << it->second << endl;

cbegin 返回unordered_map第一個元素的const迭代器

cend 返回unordered_map最后一個元素下一個位置的const迭代器

unordered_map的元素訪問

operator[] 返回與key對應的value，沒有一個默認值

注意：該函數中實際調用哈希桶的插入操作，用參數key與V()構造一個默認值往底層哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失敗，說明key已經在哈希桶中，將key對應的value返回。

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
mp1.emplace(2, "111");
mp1.emplace(3, "222");cout << mp1[1] << endl; // 111
mp1[1] = "333";
cout << mp1[1] << endl; // 333mp1[4] = "888";
cout << mp1[4] << endl; //插入4，并返回888

unordered_map的查詢

iterator ?nd(const K& key) 返回key在哈希桶中的位置

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
mp1.emplace(2, "222");
mp1.emplace(3, "333");//找到返回該位置的迭代器，否則返回end()迭代器
unordered_map<int, string>::iterator it = mp1.find(1);
cout << it->first << it->second << endl;if (mp1.find(4) == mp1.end()) cout << "find fail!" << endl;

size_t count(const K& key) 返回哈希桶中關鍵碼為key的鍵值對的個數

unordered_map<int, string> mp1;
mp1.emplace(1, "111");
mp1.emplace(2, "222");
mp1.emplace(3, "333");
mp1.emplace(4, "333");
mp1.emplace(5, "333");cout << mp1.count(2) << endl; //找到返回1，否則返回0

unordered_map的修改操作

insert 向容器中插入鍵值對

unordered_map<int, string> mp1;
mp1.insert(make_pair(1, "111"));
mp1.insert(make_pair(2, "111"));
mp1.insert(make_pair(3, "111"));for (const auto& e : mp1)
{cout << e.first << ' ' << e.second << endl;
}

erase 刪除容器中的鍵值對

mp1.erase(1);
mp1.erase(2);for (const auto& e : mp1)
{cout << e.first << ' ' << e.second << endl;
}

void clear() 清空容器中有效元素個數

unordered_map<int, string> mp1;
mp1.insert(make_pair(1, "111"));
mp1.insert(make_pair(2, "111"));
mp1.insert(make_pair(3, "111"));mp1.clear();
cout << mp1.empty() << endl; // 1

void swap(unordered_map&) 交換兩個容器中的元素

unordered_map<int, string> mp1;
mp1.insert(make_pair(1, "111"));
mp1.insert(make_pair(2, "222"));
mp1.insert(make_pair(3, "333"));unordered_map<int, string> mp2;
mp2.insert(make_pair(4, "444"));
mp2.insert(make_pair(5, "555"));
mp2.insert(make_pair(6, "666"));mp1.swap(mp2);cout << "mp1: " << endl;
for (const auto& e : mp1)
{cout << e.first << ' ' << e.second << endl;
}cout << "mp2: " << endl;
for (const auto& e : mp2)
{cout << e.first << ' ' << e.second << endl;
}

unordered_multimap

unordered_multimap容器與unordered_map容器的底層數據結構是一樣的，都是哈希表，其次，它們所提供的成員函數的接口都是基本一致的，這里就不再列舉了，這兩種容器唯一的區別就是，unordered_multimap容器允許鍵值冗余，即unordered_multimap容器當中存儲的鍵值對的key值是可以重復的。

unordered_multimap<int, string> mp;
mp.emplace(1, "111");
mp.emplace(2, "111");
mp.emplace(3, "111");
mp.emplace(2, "111");
mp.emplace(3, "111");for (const auto& e : mp)
{cout << e.first << ' ' << e.second << ' ';
}

由于unordered_multimap容器允許鍵值對的鍵值冗余，因此該容器中成員函數find和count的意義與unordered_map容器中的也有所不同：

成員函數find	功能
unordered_map容器	返回鍵值為key的鍵值對的迭代器
unordered_multimap容器	返回底層哈希表中第一個找到的鍵值為key的鍵值對的迭代器

成員函數count	功能
unordered_map容器	鍵值為key的鍵值對存在則返回1，不存在則返回0（find成員函數可替代）
unordered_multimap容器	返回鍵值為key的鍵值對的個數（find成員函數不可替代）

其次，由于unordered_multimap容器允許鍵值對的鍵值冗余，調用[ ]運算符重載函數時，應該返回鍵值為key的哪一個鍵值對的value的引用存在歧義，因此在unordered_multimap容器當中沒有實現[ ]運算符重載函數。

unordered_set

在C++98中，STL提供了底層為紅黑樹結構的一系列關聯式容器，在查詢時的效率可達到O ( l o g N ) O(logN)O(logN)，即最差情況下需要比較紅黑樹的高度次，當樹中的結點非常多時，查詢效率也不理想。最好的查詢是，進行很少的比較次數就能夠將元素找到，因此在C++11中，STL又提供了4個unordered系列的關聯式容器，這四個容器與紅黑樹結構的關聯式容器使用方式基本類似，只是其底層結構不同。

unordered_set的定義方式

方式一：構造一個某類型的空容器。

unordered_set<int> us1; //構造int類型的空容器

方式二：拷貝構造某同類型容器的復制品。

unordered_set<int> us2(us1); //拷貝構造同類型容器us1的復制品

方式三：使用迭代器拷貝構造某一段內容。

string str("abcedf");
unordered_set<char> us3(str.begin(), str.end()); //構造string對象某段區間的復制品

unordered_set的接口使用

unordered_set當中常用的成員函數如下：

成員函數	功能
insert	插入指定元素
erase	刪除指定元素
find	查找指定元素
size	獲取容器中元素的個數
empty	判斷容器是否為空
clear	清空容器
swap	交換兩個容器中的數據
count	獲取容器中指定元素值的元素個數

unordered_set當中迭代器相關函數如下：

成員函數	功能
begin	獲取容器中第一個元素的正向迭代器
end	獲取容器中最后一個元素下一個位置的正向迭代器

使用示例：

int main()
{unordered_set<int> st;st.insert(1);st.insert(4);st.insert(4);st.insert(2);st.insert(3);st.insert(2);//去重 遍歷容器元素方式一for (const auto& e : st){cout << e << ' '; // 1 4 2 3}cout << endl;//刪除元素方式一 使用key值st.erase(1);//刪除元素方式二 使用迭代器unordered_set<int>::iterator it = st.find(1);if (it != st.end()){st.erase(it);}//遍歷容器元素方式二unordered_set<int>::iterator it = st.begin();while(it != st.end()){cout << *it << ' '; //1 4 3 2it++;}cout << endl;//容器中值為2的元素cout << st.count(2) << endl;//容器大小cout << st.size() << endl;//判斷容器是否為空，為空返回真，否則假cout << st.empty() << endl;//交換兩個容器的數據unordered_set<int> rst( {5, 4, 6, 7} );rst.swap(rst);for (const auto& e : rst){cout << e << ' ';}cout << endl;return 0;
}

unordered_multiset

unordered_multiset容器與unordered_set容器的底層數據結構是一樣的，都是哈希表，其次，它們所提供的成員函數的接口都是基本一致的，這里就不再列舉了，這兩種容器唯一的區別就是，unordered_multiset容器允許鍵值冗余，即unordered_multiset容器當中存儲的元素是可以重復的。

unordered_multiset<int> st;
st.insert(1);
st.insert(1);
st.insert(2);
st.insert(2);
st.insert(3);
st.insert(3);for (const auto& e : st)
{cout << e << ' '; // 1 1 2 2 3 3
}
cout << endl;

由于unordered_multimap容器允許鍵值對的鍵值冗余，因此該容器中成員函數find和count的意義與unordered_map容器中的也有所不同：

成員函數find	功能
unordered_map容器	返回鍵值為key的鍵值對的迭代器
unordered_multimap容器	返回底層哈希表中第一個找到的鍵值為key的鍵值對的迭代器

成員函數count	功能
unordered_map容器	鍵值為key的鍵值對存在則返回1，不存在則返回0（find成員函數可替代）
unordered_multimap容器	返回鍵值為key的鍵值對的個數（find成員函數不可替代）