unordered_map的定義
哈希表在 C++ 標(biāo)準(zhǔn)庫中的實(shí)現(xiàn)有一段歷史。在 C++98/03 標(biāo)準(zhǔn)中，沒有正式定義標(biāo)準(zhǔn)的哈希表容器。不過，許多 C++ 標(biāo)準(zhǔn)庫實(shí)現(xiàn)（例如STLPort、SGI STL等）提供了 hash_map 和 hash_set 等擴(kuò)展容器，這些容器提供了哈希表的功能。
隨著 C++11 標(biāo)準(zhǔn)的引入，正式引入了 std::unordered_map 和 std::unordered_set 等哈希表容器作為 C++ 標(biāo)準(zhǔn)庫的一部分。這些容器在 C++11 標(biāo)準(zhǔn)中進(jìn)行了規(guī)范化，并提供了標(biāo)準(zhǔn)的接口和語法，以便開發(fā)者能夠在不同的 C++ 標(biāo)準(zhǔn)庫實(shí)現(xiàn)之間更輕松地移植代碼。
因此，雖然哈希表容器在 C++98/03 標(biāo)準(zhǔn)之前已經(jīng)存在，但它在 C++11 標(biāo)準(zhǔn)中經(jīng)歷了一些重要的改進(jìn)和規(guī)范化，成為了 C++ 標(biāo)準(zhǔn)庫的一部分，也因此被更廣泛地使用。
1. 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;
C++ 中的 std::unordered_map 的模板定義是 C++ 標(biāo)準(zhǔn)庫中的一個(gè)關(guān)聯(lián)容器（Associative Container），用于實(shí)現(xiàn)鍵值對的哈希表。下面是對該模板參數(shù)的解釋：
- Key：表示哈希表中的鍵類型，也就是用來查找值的類型。
- T：表示哈希表中的值類型，即與鍵相關(guān)聯(lián)的值的類型。
-
Hash：表示哈希函數(shù)的類型，用于計(jì)算鍵的哈希值。默認(rèn)情況下，使用
std::hash<Key>作為哈希函數(shù)。 -
Pred：表示鍵比較的謂詞，用于確定兩個(gè)鍵是否相等。默認(rèn)情況下，使用
std::equal_to<Key>作為鍵比較謂詞。 -
Alloc：表示分配器類型，用于分配內(nèi)存。默認(rèn)情況下，使用
std::allocator<std::pair<const Key, T>>作為分配器類型。
std::unordered_map 是一個(gè)用于存儲鍵值對的容器，它使用哈希表來實(shí)現(xiàn)快速查找和插入。通過提供這些模板參數(shù)，可以自定義鍵、值類型以及哈希函數(shù)、鍵比較方式和內(nèi)存分配方式，以滿足不同的應(yīng)用需求。
例如，你可以創(chuàng)建一個(gè) std::unordered_map 實(shí)例，用于將字符串作為鍵，整數(shù)作為值，并且使用自定義的哈希函數(shù)和鍵比較方式。下面是一個(gè)示例：
#include <iostream>
#include <unordered_map>
#include <string>
// 自定義哈希函數(shù)
struct MyHash {
size_t operator()(const std::string& key) const {
// 簡單示例：將字符串的長度作為哈希值
return key.length();
}
};
// 自定義鍵比較謂詞
struct MyEqual {
bool operator()(const std::string& lhs, const std::string& rhs) const {
// 比較字符串是否相等
return lhs == rhs;
}
};
int main() {
std::unordered_map<std::string, int, MyHash, MyEqual> myMap;
myMap["apple"] = 5;
myMap["banana"] = 3;
std::cout << "apple: " << myMap["apple"] << std::endl;
std::cout << "banana: " << myMap["banana"] << std::endl;
return 0;
}
在這個(gè)示例中，我們創(chuàng)建了一個(gè)自定義的哈希函數(shù) MyHash 和鍵比較謂詞 MyEqual，并將它們用于 std::unordered_map 的模板參數(shù)中，以自定義鍵的哈希方式和比較方式。這允許我們根據(jù)字符串的長度來計(jì)算哈希值，并檢查字符串是否相等。
2. unordered_map的成員類型
以下別名是unordered_map的成員類型。它們被成員函數(shù)廣泛用作參數(shù)和返回類型
unordered_map構(gòu)造函數(shù)
empty (1)
explicit unordered_map ( size_type n = /* see below */,
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 = /* see below */,
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 = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type() );
-
默認(rèn)構(gòu)造函數(shù) (1)：
explicit unordered_map ( size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );- 創(chuàng)建一個(gè)空的
unordered_map，可選地指定容器的初始桶數(shù)n、哈希函數(shù)hf、鍵比較謂詞eql和分配器alloc。
-
使用分配器的構(gòu)造函數(shù) (1)：
explicit unordered_map ( const allocator_type& alloc );- 創(chuàng)建一個(gè)空的
unordered_map，使用指定的分配器alloc。
-
范圍構(gòu)造函數(shù) (2)：
template <class InputIterator> unordered_map ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );- 通過迭代器范圍
[first, last)中的元素來初始化unordered_map，可選地指定初始桶數(shù)n、哈希函數(shù)hf、鍵比較謂詞eql和分配器alloc。
-
拷貝構(gòu)造函數(shù) (3)：
unordered_map ( const unordered_map& ump );- 創(chuàng)建一個(gè)新的
unordered_map，并使用另一個(gè)unordered_mapump中的內(nèi)容進(jìn)行拷貝構(gòu)造。 unordered_map ( const unordered_map& ump, const allocator_type& alloc );- 創(chuàng)建一個(gè)新的
unordered_map，并使用另一個(gè)unordered_mapump中的內(nèi)容進(jìn)行拷貝構(gòu)造，同時(shí)指定分配器alloc。
-
移動(dòng)構(gòu)造函數(shù) (4)：
unordered_map ( unordered_map&& ump );- 創(chuàng)建一個(gè)新的
unordered_map，并從另一個(gè)unordered_mapump中移動(dòng)內(nèi)容。 unordered_map ( unordered_map&& ump, const allocator_type& alloc );- 創(chuàng)建一個(gè)新的
unordered_map，并從另一個(gè)unordered_mapump中移動(dòng)內(nèi)容，同時(shí)指定分配器alloc。
-
初始化列表構(gòu)造函數(shù) (5)：
unordered_map ( initializer_list<value_type> il, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );- 使用初始化列表
il中的元素來初始化unordered_map，可選地指定初始桶數(shù)n、哈希函數(shù)hf、鍵比較謂詞eql和分配器alloc。
以下是關(guān)于如何使用 std::unordered_map 構(gòu)造函數(shù)的一些示例：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 示例 1: 默認(rèn)構(gòu)造函數(shù)
std::unordered_map<int, std::string> myMap; // 創(chuàng)建一個(gè)空的 unordered_map
// 示例 2: 范圍構(gòu)造函數(shù)
std::unordered_map<char, int> charCount;
std::string text = "hello world";
for (char c : text) {
charCount[c]++;
}
std::unordered_map<char, int> copyMap(charCount.begin(), charCount.end());
// 示例 3: 拷貝構(gòu)造函數(shù)
std::unordered_map<int, double> sourceMap = {{1, 1.1}, {2, 2.2}, {3, 3.3}};
std::unordered_map<int, double> copyOfSource(sourceMap);
// 示例 4: 移動(dòng)構(gòu)造函數(shù)
std::unordered_map<std::string, int> source;
source["apple"] = 5;
source["banana"] = 3;
std::unordered_map<std::string, int> destination(std::move(source));
// 示例 5: 初始化列表構(gòu)造函數(shù)
std::unordered_map<std::string, int> fruitCount = {
{"apple", 5},
{"banana", 3},
{"cherry", 8}
};
// 輸出示例
for (const auto& pair : fruitCount) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
unordered_map賦值運(yùn)算符重載
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 );
賦值操作符允許你將一個(gè) std::unordered_map 的內(nèi)容賦值給另一個(gè) std::unordered_map。以下是這些操作符及其重載方式的簡要說明：
-
拷貝賦值操作符 (1)：
unordered_map& operator= (const unordered_map& ump);- 將一個(gè)已存在的
std::unordered_map的內(nèi)容拷貝給另一個(gè)已存在的std::unordered_map。
-
移動(dòng)賦值操作符 (2)：
unordered_map& operator= (unordered_map&& ump);- 將一個(gè)已存在的
std::unordered_map的內(nèi)容移動(dòng)給另一個(gè)已存在的std::unordered_map。這個(gè)操作會(huì)將原有的std::unordered_map置為有效但不再可用的狀態(tài)。
-
初始化列表賦值操作符 (3)：
unordered_map& operator= (initializer_list<value_type> il);- 使用初始化列表
il中的元素來賦值給std::unordered_map。這個(gè)操作會(huì)替換原有的內(nèi)容。
這些賦值操作符允許你在不同的情況下更新 std::unordered_map 的內(nèi)容，可以用于拷貝、移動(dòng)或替換哈希表中的鍵值對。以下是一些示例：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> source = {{"apple", 5}, {"banana", 3}};
std::unordered_map<std::string, int> destination;
// 拷貝賦值操作符示例
destination = source;
// 移動(dòng)賦值操作符示例
std::unordered_map<std::string, int> otherSource = {{"cherry", 8}};
destination = std::move(otherSource);
// 初始化列表賦值操作符示例
destination = {{"grape", 12}, {"orange", 6}};
// 輸出示例
for (const auto& pair : destination) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
這些示例演示了如何使用不同的賦值操作符來更新 std::unordered_map 的內(nèi)容。無論是拷貝、移動(dòng)還是用初始化列表替換，都可以根據(jù)需要輕松地更新哈希表對象的內(nèi)容。
unordered_map容量函數(shù)（Capacity）
-
empty()函數(shù):bool empty() const noexcept;- 用于檢查
std::unordered_map是否為空。如果哈希表中不包含任何鍵值對，則返回true；否則返回false。該函數(shù)是不會(huì)拋出異常的。
-
size()函數(shù):size_type size() const noexcept;- 返回
std::unordered_map中存儲的鍵值對的數(shù)量。即返回哈希表的大小。如果哈希表為空，則返回 0。該函數(shù)是不會(huì)拋出異常的。
-
max_size()函數(shù):size_type max_size() const noexcept;- 返回
std::unordered_map可以容納的最大鍵值對數(shù)量，通常受到系統(tǒng)資源限制。這個(gè)值在不同的系統(tǒng)和編譯器上可能會(huì)有所不同。該函數(shù)是不會(huì)拋出異常的。
這些函數(shù)使你能夠查詢和管理 std::unordered_map 的狀態(tài)。例如，你可以使用 empty() 來檢查哈希表是否為空，使用 size() 獲取其當(dāng)前大小，以及使用 max_size() 查看哈希表可以容納的最大大小。
示例：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> myMap;
// 使用 empty() 函數(shù)檢查是否為空
if (myMap.empty()) {
std::cout << "Map is empty." << std::endl;
} else {
std::cout << "Map is not empty." << std::endl;
}
// 添加一些鍵值對
myMap[1] = "one";
myMap[2] = "two";
myMap[3] = "three";
// 使用 size() 函數(shù)獲取大小
std::cout << "Size of the map: " << myMap.size() << std::endl;
// 使用 max_size() 函數(shù)獲取最大容量
std::cout << "Max size of the map: " << myMap.max_size() << std::endl;
return 0;
}
unordered_map迭代器（Iterators）
1. 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;
-
begin()函數(shù) (容器迭代器):iterator begin() noexcept;const_iterator begin() const noexcept;- 這兩個(gè)版本的
begin()函數(shù)用于返回指向std::unordered_map的第一個(gè)元素（鍵值對）的迭代器。第一個(gè)版本返回非常量迭代器，而第二個(gè)版本返回常量迭代器。這些函數(shù)是不會(huì)拋出異常的。
-
begin(size_type n)函數(shù) (桶迭代器):-
local_iterator begin(size_type n); -
const_local_iterator begin(size_type n) const; -
這兩個(gè)版本的
begin(size_type n)函數(shù)用于返回指向特定桶（bucket）中第一個(gè)元素的迭代器，其中n是要訪問的桶的索引。第一個(gè)版本返回非常量桶迭代器，而第二個(gè)版本返回常量桶迭代器。這些函數(shù)允許你在哈希表中的特定桶內(nèi)迭代元素。
-
2. 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;
-
end()函數(shù) (容器迭代器):
iterator end() noexcept;const_iterator end() const noexcept;- 這兩個(gè)版本的
end()函數(shù)用于返回指向std::unordered_map的尾部（末尾）的迭代器。第一個(gè)版本返回非常量迭代器，而第二個(gè)版本返回常量迭代器。這些函數(shù)是不會(huì)拋出異常的。
-
end(size_type n)函數(shù) (桶迭代器):-
local_iterator end(size_type n); -
const_local_iterator end(size_type n) const; -
這兩個(gè)版本的
end(size_type n)函數(shù)用于返回指向特定桶（bucket）中的尾部（末尾）的迭代器，其中n是要訪問的桶的索引。第一個(gè)版本返回非常量桶迭代器，而第二個(gè)版本返回常量桶迭代器。這些函數(shù)允許你在哈希表中的特定桶內(nèi)迭代元素的末尾。
-
這些迭代器函數(shù)使你能夠在 std::unordered_map 中遍歷元素，不僅可以遍歷整個(gè)容器，還可以遍歷特定桶內(nèi)的元素。以下是一些示例代碼：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
// 使用容器迭代器 begin()
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
// 使用桶迭代器 begin(size_type n)
size_t bucketIndex = myMap.bucket(2); // 獲取鍵 2 所在的桶索引
for (auto it = myMap.begin(bucketIndex); it != myMap.end(bucketIndex); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
return 0;
}
在這個(gè)示例中，我們展示了如何使用容器迭代器 begin() 和 end()遍歷整個(gè)哈希表，并使用桶迭代器 begin(size_type n) 和end(size_type n) 遍歷特定桶中的元素。這些迭代器函數(shù)允許你有效地遍歷和訪問 std::unordered_map 中的元素。
3. cbegin()
container iterator (1)
const_iterator cbegin() const noexcept;
bucket iterator (2)
const_local_iterator cbegin ( size_type n ) const;
-
cbegin()函數(shù) (常量容器迭代器):const_iterator cbegin() const noexcept;- 這個(gè)函數(shù)返回一個(gè)指向
std::unordered_map的第一個(gè)元素（鍵值對）的常量迭代器。它允許對哈希表進(jìn)行只讀遍歷，不允許修改哈希表的內(nèi)容。該函數(shù)是不會(huì)拋出異常的。
-
cbegin(size_type n)函數(shù) (常量桶迭代器):const_local_iterator cbegin(size_type n) const;- 這個(gè)函數(shù)用于返回指向特定桶（bucket）中第一個(gè)元素的常量桶迭代器，其中
n是要訪問的桶的索引。它允許只讀遍歷特定桶中的元素，不允許修改哈希表的內(nèi)容。該函數(shù)是不會(huì)拋出異常的。
4. cend()
container iterator (1)
const_iterator cend() const noexcept;
bucket iterator (2)
const_local_iterator cend ( size_type n ) const;
-
cend()函數(shù) (常量容器迭代器):const_iterator cend() const noexcept;- 這個(gè)函數(shù)返回一個(gè)指向
std::unordered_map的尾部（末尾）的常量迭代器。它允許對哈希表進(jìn)行只讀遍歷，不允許修改哈希表的內(nèi)容。該函數(shù)是不會(huì)拋出異常的。
-
cend(size_type n)函數(shù) (常量桶迭代器):const_local_iterator cend(size_type n) const;- 這個(gè)函數(shù)用于返回指向特定桶（bucket）中的尾部（末尾）的常量桶迭代器，其中
n是要訪問的桶的索引。它允許只讀遍歷特定桶中的元素，不允許修改哈希表的內(nèi)容。該函數(shù)是不會(huì)拋出異常的。
這些常量迭代器函數(shù)對于在只讀模式下訪問 std::unordered_map 的元素非常有用。以下是一個(gè)示例代碼：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
// 使用常量容器迭代器 cbegin()
for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
// 使用常量桶迭代器 cbegin(size_type n)
size_t bucketIndex = myMap.bucket(2); // 獲取鍵 2 所在的桶索引
for (auto it = myMap.cbegin(bucketIndex); it != myMap.cend(bucketIndex); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
return 0;
}
在這個(gè)示例中，我們使用常量容器迭代器 cbegin() 和cend()遍歷整個(gè)哈希表，并使用常量桶迭代器 cbegin(size_type n) 和cend(size_type n)遍歷特定桶中的元素。這些常量迭代器函數(shù)允許你在只讀模式下訪問 std::unordered_map 中的元素，確保不會(huì)修改哈希表的內(nèi)容。
unordered_map元素訪問和元素查找函數(shù)
1. operator[]
-
mapped_type& operator[] ( const key_type& k );：- 這個(gè)重載函數(shù)接受一個(gè)
const引用類型的鍵（key_type），并返回與該鍵關(guān)聯(lián)的值（mapped_type）的引用。 - 如果鍵（
k）存在于unordered_map中，它將返回該鍵的值的引用，允許你修改該值。 - 如果鍵（
k）不存在，它將在unordered_map中插入該鍵-值對，并返回一個(gè)默認(rèn)構(gòu)造的值的引用（通常為該類型的默認(rèn)值）。 - 這意味著你可以通過
operator[]來讀取或修改unordered_map中的值，而不需要顯式地檢查鍵是否存在或插入鍵-值對。
- 這個(gè)重載函數(shù)接受一個(gè)
-
mapped_type& operator[] ( key_type&& k );：- 這個(gè)重載函數(shù)接受一個(gè)右值引用類型的鍵（
key_type），并返回與該鍵關(guān)聯(lián)的值（mapped_type）的引用。 - 與第一個(gè)重載函數(shù)類似，如果鍵（
k）存在于unordered_map中，它將返回該鍵的值的引用，允許你修改該值。 - 如果鍵（
k）不存在，它將在unordered_map中插入該鍵-值對，并返回一個(gè)默認(rèn)構(gòu)造的值的引用。
- 這個(gè)重載函數(shù)接受一個(gè)右值引用類型的鍵（
以下是使用std::unordered_map的operator[]重載函數(shù)的示例：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> myMap;
// 使用 operator[] 插入鍵-值對
myMap["apple"] = 3;
myMap["banana"] = 2;
myMap["cherry"] = 5;
// 訪問鍵的值并修改它
std::cout << "Number of apples: " << myMap["apple"] << std::endl;
myMap["apple"] = 4;
// 訪問不存在的鍵，會(huì)插入默認(rèn)值并返回引用
std::cout << "Number of oranges: " << myMap["orange"] << std::endl;
// 使用右值引用的 operator[] 插入鍵-值對
std::string fruit = "grape";
myMap[std::move(fruit)] = 6;
// 遍歷輸出所有鍵-值對
for (const auto& kv : myMap) {
std::cout << kv.first << ": " << kv.second << std::endl;
}
return 0;
}
在這個(gè)示例中，我們使用operator[]插入鍵-值對，訪問并修改已存在的鍵的值，以及訪問不存在的鍵，它會(huì)自動(dòng)插入默認(rèn)值。還演示了使用右值引用的operator[]來插入新的鍵-值對。最后，我們遍歷輸出了所有鍵-值對。
2. at
-
修改值的
at函數(shù)：mapped_type& at(const key_type& k); mapped_type& at(key_type&& k);這兩個(gè)重載版本允許你根據(jù)鍵
k修改關(guān)聯(lián)容器中的值。如果鍵k存在于容器中，它會(huì)返回對應(yīng)的值的引用，允許你修改這個(gè)值。如果鍵k不存在，它會(huì)拋出std::out_of_range異常。示例代碼：
std::unordered_map<std::string, int> myMap; myMap["apple"] = 3; // 使用 at 函數(shù)修改值 myMap.at("apple") = 4;如果鍵
"apple"存在，它將修改值為4。 -
只讀訪問值的
at函數(shù)：const mapped_type& at(const key_type& k) const;這個(gè)重載版本允許你只讀訪問容器中的值。它返回與鍵
k相關(guān)聯(lián)的值的常量引用。如果鍵k不存在，它也會(huì)拋出std::out_of_range異常。示例代碼：
std::unordered_map<std::string, int> myMap; myMap["apple"] = 3; // 使用 at 函數(shù)只讀訪問值 int numberOfApples = myMap.at("apple");如果鍵
"apple"存在，它將返回值3，并且你可以將其存儲在變量numberOfApples中。
總之，at 函數(shù)是一個(gè)用于安全地訪問關(guān)聯(lián)容器中元素的方法，因?yàn)樗鼤?huì)檢查鍵是否存在并在必要時(shí)拋出異常。這有助于避免訪問不存在的鍵而導(dǎo)致的未定義行為。
3. find
-
非常量容器的
find函數(shù)：iterator find(const key_type& k);這個(gè)版本的
find函數(shù)用于非常量容器，返回一個(gè)迭代器（iterator）。如果容器中存在鍵k，則迭代器指向與鍵k相關(guān)聯(lián)的元素；如果鍵k不存在，它返回容器的end()迭代器，表示未找到。示例代碼：
std::unordered_map<std::string, int> myMap; myMap["apple"] = 3; // 使用 find 函數(shù)查找鍵 "apple" auto it = myMap.find("apple"); if (it != myMap.end()) { // 找到了，輸出值 std::cout << "Value of 'apple': " << it->second << std::endl; } else { // 未找到 std::cout << "Key 'apple' not found." << std::endl; } -
常量容器的
find函數(shù)：const_iterator find(const key_type& k) const;這個(gè)版本的
find函數(shù)用于常量容器，返回一個(gè)常量迭代器（const_iterator）。它的功能與非常量版本相同，但不允許修改容器中的元素。示例代碼：
const std::unordered_map<std::string, int> myMap = { {"apple", 3}, {"banana", 2}, {"cherry", 5} }; // 使用 const find 函數(shù)查找鍵 "banana" auto it = myMap.find("banana"); if (it != myMap.end()) { // 找到了，輸出值 std::cout << "Value of 'banana': " << it->second << std::endl; } else { // 未找到 std::cout << "Key 'banana' not found." << std::endl; }
總之，find 函數(shù)是一個(gè)用于在關(guān)聯(lián)容器中查找特定鍵的非常有用的方法。如果你需要查找鍵是否存在并訪問與之關(guān)聯(lián)的值，find 函數(shù)是一個(gè)安全且高效的選擇。
4. count
size_type count(const key_type& k) const;
-
k：要查找的鍵。 -
size_type：返回值類型，通常是一個(gè)無符號整數(shù)類型，表示鍵k在容器中的出現(xiàn)次數(shù)。
count 函數(shù)會(huì)在容器中查找鍵 k，并返回鍵的出現(xiàn)次數(shù)。如果鍵 k 存在于容器中，count 函數(shù)將返回 1 或更大的正整數(shù)，表示鍵出現(xiàn)的次數(shù)。如果鍵 k 不存在，函數(shù)將返回 0，表示鍵沒有出現(xiàn)。
示例代碼：
std::unordered_map<std::string, int> myMap = {
{"apple", 3},
{"banana", 2},
{"cherry", 5}
};
// 計(jì)算鍵 "apple" 在容器中的出現(xiàn)次數(shù)
size_t appleCount = myMap.count("apple");
std::cout << "The count of 'apple': " << appleCount << std::endl;
// 計(jì)算鍵 "grape" 在容器中的出現(xiàn)次數(shù)
size_t grapeCount = myMap.count("grape");
std::cout << "The count of 'grape': " << grapeCount << std::endl;
在上面的示例中，count 函數(shù)首先計(jì)算鍵 “apple” 在容器中的出現(xiàn)次數(shù)（應(yīng)為 1），然后計(jì)算鍵 “grape” 在容器中的出現(xiàn)次數(shù)（應(yīng)為 0）。count 函數(shù)對于檢查某個(gè)鍵是否存在于容器中以及統(tǒng)計(jì)鍵的出現(xiàn)次數(shù)非常有用。如果你需要知道某個(gè)鍵是否存在以及它出現(xiàn)了多少次，可以使用 count 函數(shù)進(jìn)行查詢。
5. equal_range
pair<iterator,iterator>
equal_range ( const key_type& k );
pair<const_iterator,const_iterator>
equal_range ( const key_type& k ) const;
-
k：要查找的鍵。 -
pair：返回值類型，一個(gè)包含兩個(gè)迭代器的容器，表示范圍的起始和結(jié)束位置。 -
iterator和const_iterator：迭代器類型，表示容器的迭代器和常量迭代器。
equal_range 函數(shù)會(huì)在容器中查找鍵 k，然后返回一個(gè) pair，其中第一個(gè)元素是指向范圍的開始位置的迭代器，第二個(gè)元素是指向范圍的結(jié)束位置的迭代器。這個(gè)范圍包括了所有鍵等于 k 的元素。
示例代碼：
std::map<int, std::string> myMap = {
{1, "one"},
{2, "two"},
{2, "another two"}, // 注意：鍵 2 重復(fù)
{3, "three"}
};
// 查找鍵 2 在容器中的范圍
auto range = myMap.equal_range(2);
// 輸出范圍中的元素
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
在上面的示例中，equal_range 函數(shù)查找鍵 2 在 myMap 中的范圍，并返回一個(gè)包含范圍的起始和結(jié)束迭代器的 pair。然后，我們使用迭代器遍歷范圍，輸出范圍中的元素。
equal_range 函數(shù)在處理關(guān)聯(lián)容器中的重復(fù)鍵時(shí)非常有用，因?yàn)樗试S你查找所有具有相同鍵的元素，并迭代遍歷它們。
unordered_map修飾符函數(shù)
1. emplace
template <class... Args>
pair<iterator, bool> emplace ( Args&&... args );
std::unordered_map 的 emplace 函數(shù)用于在哈希表中插入新的鍵值對，并返回一個(gè) std::pair，其中包含一個(gè)迭代器和一個(gè)布爾值。
-
Args&&... args是模板參數(shù)包，允許你傳遞任意數(shù)量的參數(shù)。 -
pair<iterator, bool>是返回值類型，其中iterator是插入或已存在鍵值對的迭代器，bool表示插入是否成功。如果鍵已存在，則迭代器指向已存在的鍵值對，布爾值為false；如果鍵不存在，則迭代器指向新插入的鍵值對，布爾值為true。
以下是 emplace 函數(shù)的示例用法：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<int, std::string> myMap;
// 使用 emplace 插入鍵值對
auto result1 = myMap.emplace(1, "One");
if (result1.second) {
std::cout << "Insertion successful. Key: " << result1.first->first << ", Value: " << result1.first->second << std::endl;
} else {
std::cout << "Key already exists. Key: " << result1.first->first << ", Value: " << result1.first->second << std::endl;
}
// 嘗試再次插入相同的鍵值對
auto result2 = myMap.emplace(1, "Another One");
if (result2.second) {
std::cout << "Insertion successful. Key: " << result2.first->first << ", Value: " << result2.first->second << std::endl;
} else {
std::cout << "Key already exists. Key: " << result2.first->first << ", Value: " << result2.first->second << std::endl;
}
return 0;
}
在上述示例中，首先使用 emplace 函數(shù)插入一個(gè)鍵值對，然后再次嘗試插入相同的鍵值對。根據(jù)返回的布爾值可以確定插入是否成功，以及插入的鍵值對是已存在的還是新插入的。
2. emplace_hint
與 emplace 不同，emplace_hint 允許你提供一個(gè)提示位置，以提高插入操作的性能。
以下是對 emplace_hint 函數(shù)的參數(shù)和用法的簡要說明：
-
position：這是一個(gè)迭代器，它指示了插入位置的提示。新元素將插入到position之前。這個(gè)參數(shù)可以幫助容器更高效地插入元素，但不是必需的。 -
Args&&... args：這是一個(gè)可變參數(shù)模板，用于傳遞新元素的構(gòu)造參數(shù)。根據(jù)元素類型的構(gòu)造函數(shù)，你可以傳遞任意數(shù)量的參數(shù)。 - 返回值：
emplace_hint返回一個(gè)迭代器，指向插入的新元素，或者如果插入失敗，則返回一個(gè)指向容器中現(xiàn)有元素的迭代器。
下面是一個(gè)示例，演示了如何使用 emplace_hint 向 std::unordered_map 中插入新的鍵值對：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> myMap;
// 使用 emplace_hint 插入元素
auto hint = myMap.emplace_hint(myMap.begin(), 1, "One");
myMap.emplace_hint(hint, 2, "Two");
myMap.emplace_hint(hint, 3, "Three");
// 遍歷 unordered_map 并打印鍵值對
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
在這個(gè)示例中，emplace_hint 被用來插入新的鍵值對，通過 hint 提示位置，以提高插入的效率。注意，emplace_hint 可以在任何位置插入元素，但通常你會(huì)使用提示位置以避免不必要的搜索和移動(dòng)操作。
3. insert
-
pair<iterator, bool> insert(const value_type& val)：將一個(gè)鍵值對val插入到unordered_map中。如果插入成功，返回一個(gè)pair，其中的iterator指向插入的元素，bool表示插入是否成功。示例：
std::unordered_map<int, std::string> myMap; std::pair<int, std::string> pairToInsert(1, "One"); auto result = myMap.insert(pairToInsert); if (result.second) { std::cout << "Insertion successful." << std::endl; } else { std::cout << "Insertion failed (key already exists)." << std::endl; } -
template <class P> pair<iterator, bool> insert(P&& val)：使用移動(dòng)語義，將一個(gè)鍵值對val插入到unordered_map中。同樣返回一個(gè)pair，表示插入結(jié)果。示例：
std::unordered_map<int, std::string> myMap; auto result = myMap.insert(std::make_pair(1, "One")); if (result.second) { std::cout << "Insertion successful." << std::endl; } else { std::cout << "Insertion failed (key already exists)." << std::endl; } -
iterator insert(const_iterator hint, const value_type& val)：在給定的位置hint處插入一個(gè)鍵值對val。這個(gè)函數(shù)允許你提供一個(gè)位置提示，以提高插入效率。示例：
std::unordered_map<int, std::string> myMap; auto hint = myMap.begin(); // 可以是任何迭代器位置 myMap.insert(hint, std::make_pair(1, "One")); -
template <class P> iterator insert(const_iterator hint, P&& val)：與第三個(gè)函數(shù)類似，使用移動(dòng)語義插入鍵值對，同時(shí)提供位置提示。示例：
std::unordered_map<int, std::string> myMap; auto hint = myMap.begin(); // 可以是任何迭代器位置 myMap.insert(hint, std::make_pair(1, "One")); -
template <class InputIterator> void insert(InputIterator first, InputIterator last)：用一對迭代器[first, last)指定的范圍內(nèi)的元素插入到unordered_map中。示例：
std::unordered_map<int, std::string> myMap; std::vector<std::pair<int, std::string>> data = {{1, "One"}, {2, "Two"}, {3, "Three"}}; myMap.insert(data.begin(), data.end()); -
void insert(initializer_list<value_type> il)：使用初始化列表中的元素插入到unordered_map中。示例：
std::unordered_map<int, std::string> myMap; myMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});
這些函數(shù)提供了多種插入鍵值對的方式，使你可以根據(jù)需求選擇最合適的方法。
4. erase
-
iterator erase(const_iterator position)：通過迭代器位置position刪除對應(yīng)鍵值對。返回指向刪除元素之后位置的迭代器。示例：
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}}; auto it = myMap.find(2); // 找到鍵為2的位置 if (it != myMap.end()) { myMap.erase(it); // 刪除鍵為2的元素 } -
size_type erase(const key_type& k)：通過鍵k刪除對應(yīng)的鍵值對。返回刪除的元素個(gè)數(shù)（0或1，因?yàn)殒I在unordered_map中是唯一的）。示例：
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}}; size_t erased = myMap.erase(2); // 刪除鍵為2的元素 std::cout << "Erased " << erased << " element(s)." << std::endl; -
iterator erase(const_iterator first, const_iterator last)：通過一對迭代器[first, last)刪除指定范圍內(nèi)的鍵值對。返回指向刪除操作之后位置的迭代器。示例：
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}}; auto first = myMap.begin(); // 范圍起始位置 auto last = myMap.find(2); // 范圍結(jié)束位置，找到鍵為2的位置 if (last != myMap.end()) { myMap.erase(first, last); // 刪除范圍內(nèi)的元素 }
這些函數(shù)提供了不同的方式來刪除 unordered_map 中的元素，根據(jù)需求可以選擇最合適的方法。
5. clear
-
void clear() noexcept;：清空unordered_map中的所有鍵值對。這個(gè)操作會(huì)使unordered_map變?yōu)榭?，但不?huì)改變?nèi)萜鞯娜萘俊?/p>示例：
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}}; std::cout << "Size before clear: " << myMap.size() << std::endl; myMap.clear(); // 清空 unordered_map std::cout << "Size after clear: " << myMap.size() << std::endl;輸出：
Size before clear: 3 Size after clear: 0
這個(gè)函數(shù)是一個(gè)無異常操作 (noexcept)，意味著它不會(huì)拋出異常。它可以在需要清空 unordered_map 的情況下使用，以釋放容器占用的資源。
6. swap
-
void swap ( unordered_map& ump );：交換當(dāng)前unordered_map與參數(shù)ump所表示的unordered_map的內(nèi)容。這個(gè)操作不會(huì)改變?nèi)萜鞯娜萘浚皇墙粨Q它們的內(nèi)容。示例：
std::unordered_map<int, std::string> map1 = {{1, "One"}, {2, "Two"}}; std::unordered_map<int, std::string> map2 = {{3, "Three"}, {4, "Four"}}; std::cout << "map1 before swap:" << std::endl; for (const auto& pair : map1) { std::cout << pair.first << ": " << pair.second << std::endl; } std::cout << "map2 before swap:" << std::endl; for (const auto& pair : map2) { std::cout << pair.first << ": " << pair.second << std::endl; } map1.swap(map2); // 交換 map1 和 map2 的內(nèi)容 std::cout << "map1 after swap:" << std::endl; for (const auto& pair : map1) { std::cout << pair.first << ": " << pair.second << std::endl; } std::cout << "map2 after swap:" << std::endl; for (const auto& pair : map2) { std::cout << pair.first << ": " << pair.second << std::endl; }輸出：
map1 before swap: 1: One 2: Two map2 before swap: 3: Three 4: Four map1 after swap: 3: Three 4: Four map2 after swap: 1: One 2: Two
這個(gè)函數(shù)非常有用，因?yàn)樗梢栽诓恍枰獎(jiǎng)?chuàng)建臨時(shí)對象的情況下，高效地交換兩個(gè) unordered_map 的內(nèi)容。
unordered_map桶函數(shù)
1. bucket_count
bucket_count 函數(shù)用于獲取 std::unordered_map 容器中當(dāng)前桶（buckets）的數(shù)量。桶是哈希表中的存儲位置，用于存儲鍵值對。
size_type bucket_count() const noexcept;
-
size_type：表示無符號整數(shù)類型，通常是size_t。 -
bucket_count()：該函數(shù)沒有參數(shù)。 -
const：表示該函數(shù)不會(huì)修改容器的內(nèi)容。 -
noexcept：表示該函數(shù)不會(huì)拋出異常。
該函數(shù)返回當(dāng)前 unordered_map 容器中桶的數(shù)量。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
map[1] = "One";
map[2] = "Two";
map[3] = "Three";
map[4] = "Four";
std::cout << "Bucket count: " << map.bucket_count() << std::endl;
return 0;
}
在這個(gè)示例中，bucket_count 函數(shù)返回當(dāng)前 std::unordered_map 中的桶數(shù)量，該數(shù)量取決于哈希函數(shù)和負(fù)載因子等因素。這個(gè)數(shù)量通常會(huì)比容器中實(shí)際的元素?cái)?shù)量大，以確保元素能夠均勻分布在桶中，從而提高查詢性能。
2. max_bucket_count
max_bucket_count 函數(shù)用于獲取 std::unordered_map 容器支持的最大桶（buckets）數(shù)量。桶是哈希表中的存儲位置，用于存儲鍵值對。
size_type max_bucket_count() const noexcept;
-
size_type：表示無符號整數(shù)類型，通常是size_t。 -
max_bucket_count()：該函數(shù)沒有參數(shù)。 -
const：表示該函數(shù)不會(huì)修改容器的內(nèi)容。 -
noexcept：表示該函數(shù)不會(huì)拋出異常。
該函數(shù)返回 std::unordered_map 容器支持的最大桶數(shù)量。這個(gè)值通常受到底層哈希表實(shí)現(xiàn)和系統(tǒng)資源限制的影響。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 獲取最大桶數(shù)量并輸出
std::cout << "Max bucket count: " << map.max_bucket_count() << std::endl;
return 0;
}
在這個(gè)示例中，max_bucket_count 函數(shù)返回 std::unordered_map 容器支持的最大桶數(shù)量。這個(gè)值是由編譯器和系統(tǒng)決定的，通常取決于系統(tǒng)的可用內(nèi)存和哈希表實(shí)現(xiàn)。
3. bucket_size
bucket_size 函數(shù)用于獲取指定桶中的元素?cái)?shù)量，它需要傳入一個(gè)桶的索引作為參數(shù)。
size_type bucket_size(size_type n) const;
-
size_type：表示無符號整數(shù)類型，通常是size_t。 -
bucket_size(n)：該函數(shù)接受一個(gè)參數(shù)n，表示要查詢的桶的索引。 -
const：表示該函數(shù)不會(huì)修改容器的內(nèi)容。
這個(gè)函數(shù)返回指定桶中的元素?cái)?shù)量。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 插入一些鍵值對
map[1] = "one";
map[2] = "two";
map[3] = "three";
// 獲取第一個(gè)桶中的元素?cái)?shù)量
size_t bucketIndex = map.bucket(1); // 獲取鍵為1的元素所在的桶的索引
size_t bucketSize = map.bucket_size(bucketIndex); // 獲取該桶的元素?cái)?shù)量
std::cout << "Bucket size for key 1: " << bucketSize << std::endl;
return 0;
}
在這個(gè)示例中，我們創(chuàng)建了一個(gè) std::unordered_map 容器，插入了一些鍵值對，并使用 bucket_size 函數(shù)獲取特定桶中的元素?cái)?shù)量。請注意，我們首先使用 bucket 函數(shù)獲取了鍵為1的元素所在的桶的索引。然后，我們使用 bucket_size 函數(shù)獲取了該桶中的元素?cái)?shù)量。
4. bucket
bucket 函數(shù)用于獲取給定鍵所屬的桶的索引，它需要傳入一個(gè)鍵作為參數(shù)。
size_type bucket(const key_type& k) const;
-
size_type：表示無符號整數(shù)類型，通常是size_t。 -
bucket(k)：該函數(shù)接受一個(gè)參數(shù)k，表示要查詢的鍵。 -
const：表示該函數(shù)不會(huì)修改容器的內(nèi)容。
這個(gè)函數(shù)返回指定鍵所屬的桶的索引。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> map;
// 插入一些鍵值對
map["one"] = 1;
map["two"] = 2;
map["three"] = 3;
// 獲取鍵所屬的桶的索引
size_t bucketIndex1 = map.bucket("one");
size_t bucketIndex2 = map.bucket("three");
std::cout << "Bucket index for key 'one': " << bucketIndex1 << std::endl;
std::cout << "Bucket index for key 'three': " << bucketIndex2 << std::endl;
return 0;
}
在這個(gè)示例中，我們創(chuàng)建了一個(gè) std::unordered_map 容器，插入了一些鍵值對，并使用 bucket 函數(shù)獲取特定鍵所屬的桶的索引。我們分別獲取了鍵 “one” 和 “three” 所在的桶的索引。
unordered_map哈希策略函數(shù)
1. load_factor
float load_factor() const noexcept;
load_factor 函數(shù)用于獲取當(dāng)前散列表的負(fù)載因子，它返回一個(gè) float 值表示負(fù)載因子。
負(fù)載因子是指當(dāng)前散列表中包含的元素?cái)?shù)量與桶的總數(shù)之比。通常，負(fù)載因子越小，散列表的性能越好，因?yàn)闆_突的概率較低。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 設(shè)置一些鍵值對
map[1] = "one";
map[2] = "two";
map[3] = "three";
// 獲取當(dāng)前負(fù)載因子
float lf = map.load_factor();
std::cout << "Load Factor: " << lf << std::endl;
return 0;
}
在這個(gè)示例中，我們創(chuàng)建了一個(gè) std::unordered_map 容器，并插入了一些鍵值對。然后，我們使用 load_factor 函數(shù)獲取了當(dāng)前負(fù)載因子，并將其打印出來。
2. max_load_factor
max_load_factor 函數(shù)用于設(shè)置或獲取散列表的最大負(fù)載因子。最大負(fù)載因子是在發(fā)生重新哈希（rehashing）之前允許的最大負(fù)載因子。
-
float max_load_factor() const noexcept;：獲取當(dāng)前散列表的最大負(fù)載因子。 -
void max_load_factor(float z);：設(shè)置散列表的最大負(fù)載因子為z。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 獲取當(dāng)前最大負(fù)載因子
float maxLF = map.max_load_factor();
std::cout << "Current Max Load Factor: " << maxLF << std::endl;
// 設(shè)置最大負(fù)載因子為新值
map.max_load_factor(0.75);
// 獲取新的最大負(fù)載因子
maxLF = map.max_load_factor();
std::cout << "Updated Max Load Factor: " << maxLF << std::endl;
return 0;
}
在這個(gè)示例中，我們首先獲取了當(dāng)前散列表的最大負(fù)載因子，然后將其修改為新值。通過調(diào)用 max_load_factor 函數(shù)，可以控制散列表在重新哈希之前的負(fù)載因子，以優(yōu)化性能。
3. rehash
rehash 函數(shù)用于重新調(diào)整散列表的桶（buckets）數(shù)量，以便容納至少 n 個(gè)元素，以提高散列表的性能。重新哈希會(huì)更改桶的數(shù)量，重新分布元素，因此它可能會(huì)耗費(fèi)一些時(shí)間。
-
void rehash(size_type n);：重新調(diào)整散列表的桶的數(shù)量，使其至少能夠容納n個(gè)元素。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 添加一些元素
map[1] = "One";
map[2] = "Two";
map[3] = "Three";
// 獲取當(dāng)前桶的數(shù)量
size_t currentBucketCount = map.bucket_count();
std::cout << "Current Bucket Count: " << currentBucketCount << std::endl;
// 重新調(diào)整桶的數(shù)量
map.rehash(10);
// 獲取新的桶的數(shù)量
currentBucketCount = map.bucket_count();
std::cout << "Updated Bucket Count: " << currentBucketCount << std::endl;
return 0;
}
在這個(gè)示例中，我們首先添加了一些元素到散列表中，然后使用 rehash 函數(shù)將桶的數(shù)量重新調(diào)整為 10。重新哈?？赡軙?huì)在添加大量元素后用于優(yōu)化性能，以確保負(fù)載因子保持在合適的范圍內(nèi)。
4. reserve
reserve 函數(shù)用于預(yù)留至少能夠容納 n 個(gè)元素的桶空間，以提高散列表的性能。這個(gè)函數(shù)可以幫助你在插入大量元素之前分配足夠的桶空間，以避免頻繁的重新哈希操作。
-
void reserve(size_type n);：預(yù)留至少能夠容納n個(gè)元素的桶空間。
示例代碼：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> map;
// 預(yù)留足夠的桶空間
map.reserve(100); // 預(yù)留至少能容納 100 個(gè)元素的桶空間
// 添加一些元素
for (int i = 0; i < 100; ++i) {
map[i] = "Value " + std::to_string(i);
}
// 獲取當(dāng)前桶的數(shù)量
size_t currentBucketCount = map.bucket_count();
std::cout << "Current Bucket Count: " << currentBucketCount << std::endl;
return 0;
}
在這個(gè)示例中，我們使用 reserve 函數(shù)預(yù)留了至少能夠容納 100 個(gè)元素的桶空間，然后向散列表中添加了 100 個(gè)元素。這可以幫助提高性能，因?yàn)轭A(yù)留了足夠的桶空間，避免了在插入元素時(shí)頻繁的重新哈希操作。
unordered_map開散列形式模擬實(shí)現(xiàn)
修改上篇哈希博客的哈希表實(shí)現(xiàn)
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
-
operator()是函數(shù)調(diào)用運(yùn)算符的重載，允許對象像函數(shù)一樣被調(diào)用。 - 函數(shù)接受一個(gè)參數(shù)
key，該參數(shù)表示要計(jì)算哈希值的鍵。 - 函數(shù)體內(nèi)，
(size_t)key將鍵key強(qiáng)制轉(zhuǎn)換為size_t類型，以得到其哈希值。 - 哈希值是一個(gè)用于標(biāo)識鍵在哈希表中位置的數(shù)值。通常，哈希函數(shù)會(huì)將不同的鍵映射到不同的哈希值，以便在哈希表中進(jìn)行高效的查找操作
哈希迭代器增加
template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef __HashIterator<K, T, Hash, KeyOfT> Self;
Node* _node;
HT* _pht;
__HashIterator(Node* node, HT* pht)
:_node(node)
, _pht(pht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
// 當(dāng)前桶中迭代
_node = _node->_next;
}
else
{
// 找下一個(gè)桶
Hash hash;
KeyOfT kot;
size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
++i;
for (; i < _pht->_tables.size(); ++i)
{
if (_pht->_tables[i])
{
_node = _pht->_tables[i];
break;
}
}
// 說明后面沒有有數(shù)據(jù)的桶了
if (i == _pht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
-
typedef HashNode<T> Node;：為HashNode<T>類型起一個(gè)別名Node，HashNode通常表示哈希表中的節(jié)點(diǎn)。 -
typedef HashTable<K, T, Hash, KeyOfT> HT;：為HashTable模板類實(shí)例化后的類型起一個(gè)別名HT，HashTable通常表示哈希表。 -
typedef __HashIterator<K, T, Hash, KeyOfT> Self;：為迭代器自身的類型起一個(gè)別名Self，這個(gè)別名在迭代器內(nèi)部用于定義迭代器類型。 -
Node* _node;：指向當(dāng)前迭代節(jié)點(diǎn)的指針。迭代器用于遍歷哈希表中的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的信息存儲在_node中。 -
HT* _pht;：指向哈希表的指針。哈希表的信息存儲在_pht中，迭代器可能需要訪問哈希表的屬性以實(shí)現(xiàn)迭代操作。 -
T& operator*()：重載*運(yùn)算符，使迭代器可以像指針一樣用*來訪問當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)。 -
T* operator->()：重載->運(yùn)算符，使迭代器可以像指針一樣用->來訪問當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)。 -
Self& operator++()：重載前置自增運(yùn)算符++，使迭代器可以前進(jìn)到下一個(gè)節(jié)點(diǎn)。該函數(shù)會(huì)檢查當(dāng)前桶內(nèi)是否還有節(jié)點(diǎn)，如果有，則移到下一個(gè)節(jié)點(diǎn)；否則，找到下一個(gè)非空桶，將_node指向該桶的第一個(gè)節(jié)點(diǎn)。 -
bool operator!=(const Self& s) const：重載不等于運(yùn)算符!=，用于比較兩個(gè)迭代器是否不相等。 -
bool operator==(const Self& s) const：重載等于運(yùn)算符==，用于比較兩個(gè)迭代器是否相等。
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
-
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;：這一行定義了iterator類型為__HashIterator的別名，從而使你能夠像使用普通的 C++ 迭代器一樣使用它。 -
iterator begin()函數(shù)：這個(gè)函數(shù)返回指向哈希表中第一個(gè)非空桶的迭代器。它通過遍歷_tables容器中的桶，找到第一個(gè)非空桶，并創(chuàng)建一個(gè)對應(yīng)的迭代器，然后返回該迭代器。如果沒有找到非空桶，就返回end()迭代器，表示遍歷結(jié)束。 -
iterator end()函數(shù)：這個(gè)函數(shù)返回表示遍歷結(jié)束的迭代器。它返回一個(gè)迭代器，其中的_node成員為nullptr，表示當(dāng)前沒有有效節(jié)點(diǎn)可供迭代。這在標(biāo)識迭代結(jié)束時(shí)非常有用。
添加__stl_num_primes函數(shù)
inline size_t __stl_next_prime(size_t n)
{
static const size_t __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return -1;
}
-
__stl_num_primes定義了一個(gè)常量數(shù)組，其中包含了一系列素?cái)?shù)值。這些素?cái)?shù)值是經(jīng)過精心選擇的，用于在數(shù)據(jù)結(jié)構(gòu)的容量擴(kuò)展時(shí)作為新容量的候選值。 - 函數(shù)首先遍歷這個(gè)素?cái)?shù)數(shù)組，找到第一個(gè)大于給定數(shù)
n的素?cái)?shù)，并返回它。這個(gè)操作保證了容器的大小總是選擇了一個(gè)足夠大的素?cái)?shù)，以降低哈希沖突的概率。 - 如果沒有找到適合的素?cái)?shù)，函數(shù)返回 -1，這表示發(fā)生了異常情況，可以根據(jù)需要進(jìn)行錯(cuò)誤處理。
這個(gè)函數(shù)的主要目的是為了優(yōu)化哈希表的性能，確保它的容量總是選擇一個(gè)適當(dāng)?shù)乃財(cái)?shù)，以提高哈希算法的效率(參考STL源碼)。文章來源：http://www.zghlxwxcb.cn/news/detail-722261.html
修改insert函數(shù)
pair<iterator, bool> Insert(const T& data)
{
Hash hash;
KeyOfT kot;
// 去重
iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}
// 負(fù)載因子到1就擴(kuò)容
if (_size == _tables.size())
{
vector<Node*> newTables;
newTables.resize(__stl_next_prime(_tables.size()), nullptr);
// 舊表中節(jié)點(diǎn)移動(dòng)映射新表
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hash(kot(data)) % _tables.size();
// 頭插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_size;
return make_pair(iterator(newnode, this), true);
}
- 首先，代碼創(chuàng)建了一個(gè)
Hash和一個(gè)KeyOfT的實(shí)例，這是為了獲取鍵的哈希值和鍵本身。 - 接下來，代碼通過調(diào)用
Find(kot(data))函數(shù)來檢查是否已經(jīng)存在具有相同鍵的元素。如果找到了相同的鍵，就不進(jìn)行插入操作，而是返回一個(gè)pair，其中iterator部分指向已存在的元素，而bool部分設(shè)置為false表示插入失敗。 - 如果沒有找到相同的鍵，就會(huì)繼續(xù)進(jìn)行插入操作。首先，代碼檢查當(dāng)前哈希表的負(fù)載因子是否達(dá)到了1（即元素個(gè)數(shù)等于哈希表大?。绻堑脑?，就需要進(jìn)行擴(kuò)容操作。
- 擴(kuò)容操作會(huì)創(chuàng)建一個(gè)新的哈希表
newTables，其大小通過調(diào)用__stl_next_prime(_tables.size())來確定，這確保了新的表大小是一個(gè)素?cái)?shù)。然后，代碼會(huì)遍歷舊的哈希表，將每個(gè)節(jié)點(diǎn)重新映射到新的哈希表中。這是為了保持哈希表的均勻分布和減少哈希沖突的可能性。 - 最后，代碼計(jì)算待插入元素的哈希值，并將新節(jié)點(diǎn)插入到新的哈希表中。這是通過在頭部插入方式實(shí)現(xiàn)的，新節(jié)點(diǎn)的
_next指針指向當(dāng)前桶的頭節(jié)點(diǎn)，然后更新當(dāng)前桶的頭節(jié)點(diǎn)為新節(jié)點(diǎn)。同時(shí)，元素個(gè)數(shù)_size會(huì)增加 1。 - 最終，代碼返回一個(gè)
pair，其中iterator部分指向新插入的元素，而bool部分設(shè)置為true表示插入成功。
添加桶函數(shù)
size_t Size()
{
return _size;
}
// 表的長度
size_t TablesSize()
{
return _tables.size();
}
// 桶的個(gè)數(shù)
size_t BucketNum()
{
size_t num = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
++num;
}
}
return num;
}
size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
size_t len = 0;
Node* cur = _tables[i];
while (cur)
{
++len;
cur = cur->_next;
}
if (len > maxLen)
{
maxLen = len;
}
}
return maxLen;
}
-
Size(): 這個(gè)函數(shù)返回哈希表中元素的總數(shù)量，即哈希表的大小。 -
TablesSize(): 此函數(shù)返回哈希表內(nèi)部存儲桶的數(shù)量，也就是哈希表的實(shí)際大小。 -
BucketNum(): 這個(gè)函數(shù)用于計(jì)算當(dāng)前哈希表中非空桶的數(shù)量，也就是包含元素的桶的個(gè)數(shù)。 -
MaxBucketLenth(): 此函數(shù)用于查找哈希表中最長桶的長度，也就是具有最多元素的桶中元素的數(shù)量。
修改后HashTable.h全部代碼
#pragma once
#include<iostream>
#include<utility>
#include<vector>
#include<string>
using namespace std;
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
namespace Bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
// 前置聲明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef __HashIterator<K, T, Hash, KeyOfT> Self;
Node* _node;
HT* _pht;
__HashIterator(Node* node, HT* pht)
:_node(node)
, _pht(pht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
// 當(dāng)前桶中迭代
_node = _node->_next;
}
else
{
// 找下一個(gè)桶
Hash hash;
KeyOfT kot;
size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
++i;
for (; i < _pht->_tables.size(); ++i)
{
if (_pht->_tables[i])
{
_node = _pht->_tables[i];
break;
}
}
// 說明后面沒有有數(shù)據(jù)的桶了
if (i == _pht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
typedef HashNode<T> Node;
template<class K, class T, class Hash, class KeyOfT>
friend struct __HashIterator;
public:
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
inline size_t __stl_next_prime(size_t n)
{
static const size_t __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return -1;
}
pair<iterator, bool> Insert(const T& data)
{
Hash hash;
KeyOfT kot;
// 去重
iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}
// 負(fù)載因子到1就擴(kuò)容
if (_size == _tables.size())
{
vector<Node*> newTables;
newTables.resize(__stl_next_prime(_tables.size()), nullptr);
// 舊表中節(jié)點(diǎn)移動(dòng)映射新表
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hash(kot(data)) % _tables.size();
// 頭插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_size;
return make_pair(iterator(newnode, this), true);
}
iterator Find(const K& key)
{
if (_tables.size() == 0)
{
return end();
}
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return false;
}
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
// 1、頭刪
// 2、中間刪
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
size_t Size()
{
return _size;
}
// 表的長度
size_t TablesSize()
{
return _tables.size();
}
// 桶的個(gè)數(shù)
size_t BucketNum()
{
size_t num = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
++num;
}
}
return num;
}
size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
size_t len = 0;
Node* cur = _tables[i];
while (cur)
{
++len;
cur = cur->_next;
}
if (len > maxLen)
{
maxLen = len;
}
}
return maxLen;
}
private:
vector<Node*> _tables;
size_t _size = 0; // 存儲有效數(shù)據(jù)個(gè)數(shù)
};
};
利用哈希表封裝實(shí)現(xiàn)unordered_map
#pragma once
#include "HashTable.h"
namespace yulao
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
};
}
這里我們就將unordered_map的基礎(chǔ)功能簡易實(shí)現(xiàn)完畢啦！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-722261.html
到了這里，關(guān)于一篇文章讓你熟悉unordered_map及其模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
