目錄

unordered_map

1. pair類型

2. 關(guān)聯(lián)式容器額外的類型別名

3. 哈希桶

4.?無(wú)序容器對(duì)關(guān)鍵字類型的要求

5. Member functions

5.1 constructor、destructor、operator=

5.1.1 constructor

5.1.2 destructor

5.1.3 operator=?

5.2 Capacity

?5.2.1 empty

5.2.2 size

5.2.3 max_size

5.3 Iterators

5.4 Element access

5.4.1 operator[]

5.4.2 at

5.5 Element lookup

5.5.1 find

5.5.2 count

5.5.3 equal_range

5.6 Modifiers

5.6.1 emplace

5.6.2 emplace_hint

5.6.3 insert

5.6.4 erase

5.6.5 clear

5.6.6 swap

5.7 Buckets

5.7.1 bucket_count

5.7.2 max_bucket_count

5.7.3 bucket_size

5.7.4 bucket

5.8 Hash policy

5.8.1 load_factor

5.8.2 max_load_factor

5.8.3 rehash

5.8.4 reserve

5.9 Observers

5.9.1 hash_function

5.9.2 key_eq

5.9.3 get_allocator

6. Non-member function overloads

6.1 operators

6.2 swap

7. unordered_map對(duì)象的插入方法

8. unordered_map對(duì)象的遍歷方法

8.1 迭代器

8.2 范圍for

unordered_map

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key, T> > // unordered_map::allocator_type
           > class unordered_map;

unordered_map是一種關(guān)聯(lián)式容器，存儲(chǔ)由鍵值和映射值組合而成的元素，允許根據(jù)鍵快速檢索單個(gè)元素。

在unordered_map中，鍵值通常用于唯一標(biāo)識(shí)元素，而映射值是與該鍵相關(guān)聯(lián)的內(nèi)容的對(duì)象。鍵和映射值的類型可能不同。

在內(nèi)部，unordered_map中的元素并沒(méi)有按照鍵或映射值的任何特定順序排序，而是根據(jù)它們的哈希值組織成桶，以允許直接通過(guò)鍵值快速訪問(wèn)各個(gè)元素（平均時(shí)間復(fù)雜度是常數(shù)）。

在通過(guò)鍵訪問(wèn)單個(gè)元素時(shí)，unordered_map容器比map容器更快，盡管在通過(guò)其元素子集進(jìn)行范圍迭代時(shí)通常效率較低。

unordered_map實(shí)現(xiàn)了直接訪問(wèn)操作符（operator[]），允許使用其鍵值作為參數(shù)直接訪問(wèn)映射值。

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

unordered_map定義在頭文件unordered_map和命名空間std中。

1. pair類型

pair定義在頭文件utility和命名空間std中。

一個(gè)pair保存兩個(gè)數(shù)據(jù)成員。類似容器，pair是一個(gè)用來(lái)生成特定類型的模板。當(dāng)創(chuàng)建一個(gè)pair時(shí)，我們必須提供兩個(gè)類型名，pair的數(shù)據(jù)成員將具有對(duì)應(yīng)的類型。兩個(gè)類型不要求一樣：

pair<string, string> anon;       // 保存兩個(gè)string
pair<string, size_t> word_count; // 保存一個(gè)string和一個(gè)size_t
pair<string, vector<int>> line;  // 保存string和vector<int>

pair的默認(rèn)構(gòu)造函數(shù)對(duì)數(shù)據(jù)成員進(jìn)行值初始化。因此，anon是一個(gè)包含兩個(gè)空string的pair，line保存一個(gè)空string和一個(gè)空vector。word_count中的size_t成員值為0，而string成員被初始化為空。

我們也可以為每個(gè)成員提供初始化器：

pair<string, string> author{ "James","Joyce" };

這條語(yǔ)句創(chuàng)建一個(gè)名為author的pair，兩個(gè)成員被初始化為"James"和"Joyce"。

與其他標(biāo)準(zhǔn)庫(kù)類型不同，pair的數(shù)據(jù)成員是public的。兩個(gè)成員分別命名為first和second。我們用普通的成員訪問(wèn)符號(hào)來(lái)訪問(wèn)它們。

創(chuàng)建pair對(duì)象的函數(shù)：

想象有一個(gè)函數(shù)需要返回一個(gè)pair。在新標(biāo)準(zhǔn)下，我們可以對(duì)返回值進(jìn)行列表初始化：

pair<string, int> process(vector<string>& v)
{
	// 處理v
	if (!v.empty())
		return { v.back(), v.back().size() }; // 列表初始化
	else
		return pair<string, int>(); // 隱式構(gòu)造返回值
}

若v不為空，我們返回一個(gè)由v中最后一個(gè)string及其大小組成的pair。否則，隱式構(gòu)造一個(gè)空pair，并返回它。

在較早的C++版本中，不允許用花括號(hào)包圍的初始化器來(lái)返回pair這種類型的對(duì)象，必須顯式構(gòu)造返回值:

if (!v.empty())
	return pair<string, int>(v.back(), v.back().size());

我們還可以用make_pair來(lái)生成pair對(duì)象，pair的兩個(gè)類型來(lái)自于make_pair的參數(shù)：

if (!v.empty())
	return make_pair(v.back(), v.back().size());

2. 關(guān)聯(lián)式容器額外的類型別名

對(duì)于set類型，key_type和value_type是一樣的：set中保存的值就是關(guān)鍵字。在一個(gè)map中，元素是鍵值對(duì)。即，每個(gè)元素是一個(gè)pair對(duì)象，包含一個(gè)關(guān)鍵字和一個(gè)關(guān)聯(lián)的值。由于我們不能改變一個(gè)元素的關(guān)鍵字，因此這些pair的關(guān)鍵字部分是const的：

set<string>::value_type vl;       // v1是一個(gè)string
set<string>::key_type v2;         // v2是一個(gè)string
map<string, int>::value_type v3;  // v3是一個(gè)pair<const string, int>
map<string, int>::key_type v4;    // v4是一個(gè)string
map<string, int>::mapped_type v5; // v5是一個(gè)int

與序列式容器一樣，我們使用作用域運(yùn)算符來(lái)提取一個(gè)類型的成員——例如，map<string, int>::key_type。

只有map類型（unordered_map、unordered_multimap、multimap和map）才定義了mapped_type。

3. 哈希桶

無(wú)序容器在存儲(chǔ)上組織為一組桶，每個(gè)桶保存零個(gè)或多個(gè)元素。無(wú)序容器使用一個(gè)哈希函數(shù)將元素映射到桶。為了訪問(wèn)一個(gè)元素，容器首先計(jì)算元素的哈希值，它指出應(yīng)該搜索哪個(gè)桶。容器將具有一個(gè)特定哈希值的所有元素都保存在相同的桶中。如果容器允許重復(fù)關(guān)鍵字，所有具有相同關(guān)鍵字的元素也都會(huì)在同一個(gè)桶中。因此，無(wú)序容器的性能依賴于哈希函數(shù)的質(zhì)量和桶的數(shù)量和大小。

對(duì)于相同的參數(shù)，哈希函數(shù)必須總是產(chǎn)生相同的結(jié)果。理想情況下，哈希函數(shù)還能將每個(gè)特定的值映射到唯一的桶。但是，將不同關(guān)鍵字的元素映射到相同的桶也是允許的。當(dāng)一個(gè)桶保存多個(gè)元素時(shí)，需要順序搜索這些元素來(lái)查找我們想要的那個(gè)。計(jì)算一個(gè)元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一個(gè)桶中保存了很多元素，那么查找一個(gè)特定元素就需要大量比較操作。

4.?無(wú)序容器對(duì)關(guān)鍵字類型的要求

默認(rèn)情況下，無(wú)序容器使用關(guān)鍵字類型的==運(yùn)算符來(lái)比較元素，它們還使用一個(gè)hash<key_type>類型的對(duì)象來(lái)生成每個(gè)元素的哈希值。標(biāo)準(zhǔn)庫(kù)為內(nèi)置類型（包括指針）提供了hash模板。還為一些標(biāo)準(zhǔn)庫(kù)類型，包括string和智能指針類型定義了hash。因此，我們可以直接定義關(guān)鍵字是內(nèi)置類型（包括指針類型）、string還有智能指針類型的無(wú)序容器。

但是，我們不能直接定義關(guān)鍵字類型為自定義類類型的無(wú)序容器。與容器不同，不能直接使用哈希模板，而必須提供我們自己的hash模板版本。

5. Member functions

5.1 constructor、destructor、operator=

5.1.1 constructor

// empty (1)
explicit unordered_map(size_type n,
					   const hasher& hf = hasher(),
					   const key_equal& eql = key_equal(),
					   const allocator_type& alloc = allocator_type());
explicit unordered_map(const allocator_type& alloc);
// range (2)
template <class InputIterator>
unordered_map(InputIterator first, InputIterator last,
			  size_type n,
			  const hasher& hf = hasher(),
			  const key_equal& eql = key_equal(),
			  const allocator_type& alloc = allocator_type());
// copy (3)
unordered_map(const unordered_map& ump);
unordered_map(const unordered_map& ump, const allocator_type& alloc);
// move (4)
unordered_map(unordered_map&& ump);
unordered_map(unordered_map&& ump, const allocator_type& alloc);
// initializer list (5)
unordered_map(initializer_list<value_type> il,
			  size_type n,
			  const hasher& hf = hasher(),
			  const key_equal& eql = key_equal(),
			  const allocator_type& alloc = allocator_type());

// n表示初始桶的最小數(shù)量，不是容器中元素的數(shù)量

5.1.2 destructor

~unordered_map();

5.1.3 operator=?

// copy (1)
unordered_map& operator=(const unordered_map& ump);
// move (2)
unordered_map& operator=(unordered_map&& ump);
// initializer list (3)
unordered_map& operator=(intitializer_list<value_type> il);

5.2 Capacity

?5.2.1 empty

bool empty() const noexcept;
// 檢測(cè)unordered_map是否為空，是返回true，否則返回false

5.2.2 size

size_type size() const noexcept;
// 返回unordered_map中元素的個(gè)數(shù)

5.2.3 max_size

size_type max_size() const noexcept;
// 返回unordered_map能夠容納的最大元素個(gè)數(shù)

5.3 Iterators

// begin
// container iterator (1)
iterator begin() noexcept;
const_iterator begin() const noexcept;
// bucket iterator (2)
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;

// end
// container iterator (1)
iterator end() noexcept;
const_iterator end() const noexcept;
// bucket iterator (2)
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;

// cbegin
// container iterator (1)
const_iterator cbegin() const noexcept;
// bucket iterator (2)
const_local_iterator cbegin(size_type n) const;

// cend
// container iterator (1)
const_iterator cend() const noexcept;
// bucket iterator (2)
const_local_iterator cend(size_type n) const;

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
    unordered_map<string, string> ump{ {"iterator","迭代器"},{"begin","開(kāi)始"},{"end","結(jié)束"} };

    cout << "ump contains:" << endl;
    unordered_map<string, string>::iterator it = ump.begin();
    while (it != ump.end())
    {
        cout << it->first << " " << it->second << endl;
        // 等價(jià)于cout << (*it).first << " " << (*it).second << endl;
        ++it;
    }
    // ump contains :
    // iterator 迭代器
    // begin 開(kāi)始
    // end 結(jié)束

    cout << "ump's buckets contain:" << endl;
    for (int i = 0; i < ump.bucket_count(); ++i)
    {
        cout << "bucket #" << i << " contains:";
        unordered_map<string, string>::local_iterator lit = ump.begin(i);
        while (lit != ump.end(i))
        {
            cout << " " << lit->first << " " << lit->second;
            // 等價(jià)于cout << " " << (*lit).first << " " << (*lit).second;
            ++lit;
        }
        cout << endl;
    }
    // ump's buckets contain:
    // bucket #0 contains:
    // bucket #1 contains:
    // bucket #2 contains: end 結(jié)束
    // bucket #3 contains:
    // bucket #4 contains:
    // bucket #5 contains:
    // bucket #6 contains: begin 開(kāi)始
    // bucket #7 contains: iterator 迭代器

    return 0;
}

5.4 Element access

5.4.1 operator[]

mapped_type& operator[](const key_type& k);
mapped_type& operator[](key_type&& k);
// 如果k與某個(gè)元素的關(guān)鍵字相匹配，返回對(duì)其映射值的引用
// 如果k與任何元素的關(guān)鍵字不匹配，插入一個(gè)關(guān)鍵字為k的新元素，并返回對(duì)其映射值的引用

5.4.2 at

mapped_type& at(const key_type& k);
const mapped_type& at(const key_type& k) const;
// 如果k與某個(gè)元素的關(guān)鍵字相匹配，返回對(duì)其映射值的引用
// 如果k與任何元素的關(guān)鍵字不匹配，拋異常

Element access系列函數(shù)使用示例：?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-834673.html

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;

	ump['b'];      // 插入一個(gè)關(guān)鍵字為'b'的元素，但沒(méi)有對(duì)映射值進(jìn)行初始化
	ump['d'] = 20; // 插入一個(gè)關(guān)鍵字為'd'的元素，并將映射值初始化為20	
	cout << "ump['b'] = " << ump['b'] << endl; // ump['b'] = 0
	cout << "ump['d'] = " << ump['d'] << endl; // ump['d'] = 20

	ump['b'] = 50; // 修改關(guān)鍵字為'b'的元素的映射值為50
	cout << "ump['b'] = " << ump.at('b') << endl; // ump['b'] = 50
	cout << "ump['d'] = " << ump.at('d') << endl; // ump['d'] = 20

	return 0;
}

5.5 Element lookup

5.5.1 find

iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
// 返回一個(gè)迭代器，指向第一個(gè)關(guān)鍵字為k的元素，若k不在容器中，則返回end迭代器

5.5.2 count

size_type count(const key_type& k) const;
// 返回關(guān)鍵字等于k的元素的數(shù)量
// 對(duì)于不允許重復(fù)關(guān)鍵字的容器，返回值永遠(yuǎn)是0或1

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;
	ump.insert({ 'g',30 });
	ump.insert(make_pair('a', 10));
	ump.insert(pair<char, int>('f', 50));
	ump['b'];
	ump['d'] = 20;

	auto it = ump.find('f');
	if (it != ump.end())
	{
		cout << "f在unordered_map中" << endl;
	}
	else
	{
		cout << "f不在unordered_map中" << endl;
	}
	// f在unordered_map中

	it = ump.find('h');
	if (it != ump.end())
	{
		cout << "h在unordered_map中" << endl;
	}
	else
	{
		cout << "h不在unordered_map中" << endl;
	}
	// h不在unordered_map中

	if (ump.count('a'))
	{
		cout << "a在unordered_map中" << endl;
	}
	else
	{
		cout << "a不在unordered_map中" << endl;
	}
	// a在unordered_map中

	if (ump.count('c'))
	{
		cout << "c在unordered_map中" << endl;
	}
	else
	{
		cout << "c不在unordered_map中" << endl;
	}
	// c不在unordered_map中

	return 0;
}

5.5.3 equal_range

pair<iterator, iterator> equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
// 返回一個(gè)迭代器pair，表示關(guān)鍵字等于k的元素的范圍（左閉右開(kāi)的區(qū)間）
// 若k不存在，pair的兩個(gè)成員均為end迭代器
// 對(duì)于不允許重復(fù)關(guān)鍵字的容器，返回的范圍最多只包含一個(gè)元素

5.6 Modifiers

5.6.1 emplace

template <class... Args> pair<iterator, bool> emplace(Args&&... args);
// 對(duì)應(yīng)insert，區(qū)別是：
// 當(dāng)調(diào)用insert時(shí)，我們將元素類型的對(duì)象傳遞給它們，這些對(duì)象被拷貝到容器中
// 當(dāng)調(diào)用emplace時(shí)，則是將參數(shù)傳遞給元素類型的構(gòu)造函數(shù)，然后使用這些參數(shù)在容器管理的內(nèi)存空間中直接構(gòu)造元素

5.6.2 emplace_hint

template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
// 對(duì)應(yīng)insert的(3)和(4)，區(qū)別是：
// 當(dāng)調(diào)用insert時(shí)，我們將元素類型的對(duì)象傳遞給它們，這些對(duì)象被拷貝到容器中
// 當(dāng)調(diào)用emplace時(shí)，則是將參數(shù)傳遞給元素類型的構(gòu)造函數(shù)，然后使用這些參數(shù)在容器管理的內(nèi)存空間中直接構(gòu)造元素

5.6.3 insert

// (1) 成功返回pair<插入位置, true>，失敗返回pair<插入位置, false>
pair<iterator, bool> insert(const value_type& val);
// (2)
template <class P> pair<iterator, bool> insert(P&& val);
// (3)
iterator insert(const_iterator hint, const value_type& val);
// (4)
template <class P> iterator insert(const_iterator hint, P&& val);
// (5)
template <class InputIterator> void insert(InputIterator first, InputIterator last);
// (6)
void insert(initializer_list<value_type> il);

// 插入

5.6.4 erase

// by position(1)
iterator erase(const_iterator position);
// by key(2)
size_type erase(const key_type& k);
// range(3)
iterator erase(const_iterator first, const_iterator last);

// 刪除

5.6.5 clear

void clear() noexcept;
// 清空

5.6.6 swap

void swap(unordered_map& ump);
// 交換

5.7 Buckets

5.7.1 bucket_count

size_type bucket_count() const noexcept;
// 返回unordered_map中桶的個(gè)數(shù)

5.7.2 max_bucket_count

size_type max_bucket_count() const noexcept;
// 返回unordered_map能夠容納的最大桶個(gè)數(shù)

5.7.3 bucket_size

size_type bucket_size(size_type n) const;
// 返回桶n中元素的個(gè)數(shù)

5.7.4 bucket

size_type bucket(const key_type& k) const;
// 返回關(guān)鍵字為k的元素所在的桶號(hào)

5.8 Hash policy

5.8.1 load_factor

float load_factor() const noexcept;
// 返回負(fù)載因子（每個(gè)桶平均元素的數(shù)量，元素的數(shù)量/桶的數(shù)量）

5.8.2 max_load_factor

// get(1)
float max_load_factor() const noexcept;
// set(2)
void max_load_factor(float z);

// 獲取或設(shè)置最大負(fù)載因子

5.8.3 rehash

void rehash(size_type n);
// 設(shè)置桶的數(shù)量

5.8.4 reserve

void reserve(size_type n);
// 將桶數(shù)設(shè)置為最適合包含至少n個(gè)元素的桶數(shù)

5.9 Observers

5.9.1 hash_function

hasher hash_function() const;
// 返回哈希函數(shù)

5.9.2 key_eq

key_equal key_eq() const;
// 返回關(guān)鍵字等價(jià)比較謂詞

5.9.3 get_allocator

allocator_type get_allocator() const noexcept;
// 返回空間配置器

6. Non-member function overloads

6.1 operators

// equality (1)
template <class Key, class T, class Hash, class Pred, class Alloc>
bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& lhs, const unordered_map<Key, T, Hash, Pred, Alloc>& rhs);
// inequality (2)
template <class Key, class T, class Hash, class Pred, class Alloc>
bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& lhs, const unordered_map<Key, T, Hash, Pred, Alloc>& rhs);

6.2 swap

template <class Key, class T, class Hash, class Pred, class Alloc>
void swap(unordered_map<Key, T, Hash, Pred, Alloc>& lhs, unordered_map<Key, T, Hash, Pred, Alloc>& rhs);

7. unordered_map對(duì)象的插入方法

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;

	// 插入
	ump.insert({ 'g',30 });
	ump.insert(make_pair('a', 10));
	ump.insert(pair<char, int>('f', 50));
	ump.insert(unordered_map<char, int>::value_type('h', 70));
	ump['b'];
	ump['d'] = 20;

	for (auto& e : ump)
	{
		cout << e.first << " " << e.second << endl;
	}
	// g 30
	// a 10
	// f 50
	// h 70
	// b 0
	// d 20

	return 0;
}

8. unordered_map對(duì)象的遍歷方法

8.1 迭代器

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;

	// 插入
	ump.insert({ 'g',30 });
	ump.insert(make_pair('a', 10));
	ump.insert(pair<char, int>('f', 50));
	ump.insert(unordered_map<char, int>::value_type('h', 70));
	ump['b'];
	ump['d'] = 20;

	unordered_map<char, int>::iterator it = ump.begin();
	while (it != ump.end())
	{
		cout << it->first << " " << it->second << endl;
		++it;
	}
	// g 30
	// a 10
	// f 50
	// h 70
	// b 0
	// d 20

	return 0;
}

8.2 范圍for

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;

	// 插入
	ump.insert({ 'g',30 });
	ump.insert(make_pair('a', 10));
	ump.insert(pair<char, int>('f', 50));
	ump.insert(unordered_map<char, int>::value_type('h', 70));
	ump['b'];
	ump['d'] = 20;

	for (auto& e : ump)
	{
		cout << e.first << " " << e.second << endl;
	}
	// g 30
	// a 10
	// f 50
	// h 70
	// b 0
	// d 20

	return 0;
}

#include <unordered_map>
#include <iostream>
using namespace std;

int main()
{
	unordered_map<char, int> ump;

	// 插入
	ump.insert({ 'g',30 });
	ump.insert(make_pair('a', 10));
	ump.insert(pair<char, int>('f', 50));
	ump.insert(unordered_map<char, int>::value_type('h', 70));
	ump['b'];
	ump['d'] = 20;

	for (auto& [x, y] : ump) // C++17 結(jié)構(gòu)化綁定
	{
		cout << x << " " << y << endl;
	}
	// g 30
	// a 10
	// f 50
	// h 70
	// b 0
	// d 20

	return 0;
}

到了這里，關(guān)于【C++關(guān)聯(lián)式容器】unordered_map的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！