STL標(biāo)準(zhǔn)庫與泛型編程（侯捷）

本文是學(xué)習(xí)筆記，僅供個(gè)人學(xué)習(xí)使用。如有侵權(quán)，請(qǐng)聯(lián)系刪除。

參考鏈接

Youbute: 侯捷-STL標(biāo)準(zhǔn)庫與泛型編程

B站: 侯捷 - STL

Github:STL源碼剖析中源碼 https://github.com/SilverMaple/STLSourceCodeNote/tree/master

Github:課程ppt和源碼 https://github.com/ZachL1/Bilibili-plus

介紹

介紹基于紅黑樹和hashtable的關(guān)聯(lián)式容器底層原理

關(guān)聯(lián)式容器的底層實(shí)現(xiàn)主要分為兩類：基于紅黑樹的實(shí)現(xiàn)和基于哈希表（hashtable）的實(shí)現(xiàn)。具體地，set 系列和 map 系列的關(guān)聯(lián)式容器在底層實(shí)現(xiàn)上有所不同。

1. 基于紅黑樹的實(shí)現(xiàn)：

   • set： 無序集合，存儲(chǔ)不重復(fù)的元素。元素在集合中按照鍵值的升序順序存儲(chǔ)，內(nèi)部通常采用紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。
   • map： 鍵值對(duì)的有序映射，存儲(chǔ)不重復(fù)的鍵值對(duì)。鍵值對(duì)按照鍵的升序順序存儲(chǔ)，內(nèi)部通常采用紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。
   • multiset： 無序多重集合，存儲(chǔ)允許重復(fù)的元素。元素在集合中按照鍵值的升序順序存儲(chǔ)，內(nèi)部通常采用紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。
   • multimap： 鍵值對(duì)的有序多重映射，存儲(chǔ)允許多個(gè)相同鍵的鍵值對(duì)。鍵值對(duì)按照鍵的升序順序存儲(chǔ)，內(nèi)部通常采用紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。

2. 基于哈希表的實(shí)現(xiàn)：

   • unordered_set： 無序集合，存儲(chǔ)不重復(fù)的元素。元素在集合中無序存儲(chǔ)，內(nèi)部通常采用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)。
   • unordered_map： 鍵值對(duì)的無序映射，存儲(chǔ)不重復(fù)的鍵值對(duì)。鍵值對(duì)無序存儲(chǔ)，內(nèi)部通常采用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)。
   • unordered_multiset： 無序多重集合，存儲(chǔ)允許重復(fù)的元素。元素在集合中無序存儲(chǔ)，內(nèi)部通常采用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)。
   • unordered_multimap： 鍵值對(duì)的無序多重映射，存儲(chǔ)允許多個(gè)相同鍵的鍵值對(duì)。鍵值對(duì)無序存儲(chǔ)，內(nèi)部通常采用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)。

這兩種底層實(shí)現(xiàn)各有優(yōu)劣，選擇基于紅黑樹還是哈希表的實(shí)現(xiàn)取決于具體的使用場景和需求。紅黑樹提供了有序性，適合需要有序查找的場合；而哈希表則提供了 O(1) 時(shí)間復(fù)雜度的平均查找和插入操作，適合需要高效的插入和查找的場合。

20 RB tree 深度探索

紅黑樹（Red-Black Tree）是一種自平衡的二叉搜索樹，它在插入和刪除操作時(shí)通過一系列的顏色變換和旋轉(zhuǎn)來保持樹的平衡。這種平衡性質(zhì)確保了紅黑樹的查找、插入和刪除等基本操作在最壞情況下的時(shí)間復(fù)雜度為O(log n)。

以下是紅黑樹的一些關(guān)鍵性質(zhì)：

1. 節(jié)點(diǎn)顏色： 每個(gè)節(jié)點(diǎn)都帶有顏色，要么是紅色，要么是黑色。

2. 根節(jié)點(diǎn)和葉子節(jié)點(diǎn)： 根節(jié)點(diǎn)是黑色的，葉子節(jié)點(diǎn)（通常為空節(jié)點(diǎn)或哨兵節(jié)點(diǎn)）也是黑色的。

3. 相鄰節(jié)點(diǎn)顏色： 不能有兩個(gè)相鄰的紅色節(jié)點(diǎn)，即紅色節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)都不能是紅色的。

4. 任意路徑黑色節(jié)點(diǎn)數(shù)相同： 從任意節(jié)點(diǎn)到其所有后代葉子節(jié)點(diǎn)的簡單路徑上，經(jīng)過的黑色節(jié)點(diǎn)數(shù)目相同。

這些性質(zhì)保證了紅黑樹的平衡，使得最長路徑不會(huì)超過最短路徑的兩倍，從而保證了對(duì)數(shù)時(shí)間的查找、插入和刪除操作。

紅黑樹通常用于實(shí)現(xiàn)關(guān)聯(lián)容器，如C++標(biāo)準(zhǔn)模板庫（STL）中的std::map和std::set。在這些容器中，紅黑樹提供了高效的搜索、插入和刪除操作，同時(shí)保持樹的平衡，確保了良好的性能。

紅黑樹的平衡性是通過一系列旋轉(zhuǎn)和顏色調(diào)整來實(shí)現(xiàn)的。這些操作的設(shè)計(jì)確保了在每次插入或刪除后，紅黑樹的性質(zhì)仍然得以保持。雖然紅黑樹的維護(hù)可能相對(duì)復(fù)雜，但由于其高效的性能和保持平衡的特性，它在許多應(yīng)用中被廣泛使用。

rb_tree有5個(gè)模板參數(shù)，其中key表示key，value表示key和data的整體。展示一下5個(gè)模板參數(shù)的作用

注意這里的模板參數(shù)名稱和GNU C++2.9版本名字稍有不同，但是意思是一樣的。

// Class rb_tree is not part of the C++ standard.  It is provided for
// compatibility with the HP STL.
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
{
  typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
  typedef typename _Base::allocator_type allocator_type;

  rb_tree(const _Compare& __comp = _Compare(),
          const allocator_type& __a = allocator_type())
    : _Base(__comp, __a) {}
  
  ~rb_tree() {}
};

在這段代碼中，模板參數(shù) _Key、_Value、_KeyOfValue、_Compare、_Alloc 分別用于定義一個(gè)紅黑樹的模板類 rb_tree。以下是這五個(gè)模板參數(shù)的作用：

1. _Key：

   • 表示紅黑樹節(jié)點(diǎn)的鍵（key）的類型。這是用來比較和排序節(jié)點(diǎn)的關(guān)鍵信息。

2. _Value：

   • 表示紅黑樹節(jié)點(diǎn)存儲(chǔ)的值（value，這里value表示key和data的整體）的類型。每個(gè)節(jié)點(diǎn)包含一個(gè)鍵和一個(gè)值（data）。

3. _KeyOfValue：

   • 是一個(gè)函數(shù)對(duì)象，用于從節(jié)點(diǎn)值中提取鍵。在紅黑樹中，節(jié)點(diǎn)的鍵是用來進(jìn)行比較和排序的。通過 _KeyOfValue，可以從節(jié)點(diǎn)的值中提取鍵，以確保正確的比較和排序。

4. _Compare：

   • 是一個(gè)比較函數(shù)對(duì)象，用于定義節(jié)點(diǎn)之間的順序關(guān)系。它用來比較節(jié)點(diǎn)的鍵值，從而實(shí)現(xiàn)紅黑樹的有序性。

5. _Alloc：

   • 是一個(gè)分配器類型，用于管理紅黑樹節(jié)點(diǎn)的內(nèi)存分配和釋放。默認(rèn)情況下，使用 _Value 類型的默認(rèn)分配器 __STL_DEFAULT_ALLOCATOR(_Value)。

這些模板參數(shù)允許用戶在使用紅黑樹時(shí)靈活地指定節(jié)點(diǎn)的鍵值類型、存儲(chǔ)的值類型、鍵值提取方式、比較方式以及內(nèi)存分配器。通過使用模板參數(shù)，可以實(shí)現(xiàn)通用性，使紅黑樹適用于各種不同的鍵值類型和使用場景。在實(shí)例化 rb_tree 類時(shí)，用戶可以根據(jù)實(shí)際需求提供適當(dāng)?shù)哪０鍏?shù)。

下圖中可以看到紅黑樹這個(gè)類rb_tree中的數(shù)據(jù)有三個(gè)：node_count, header, key_compare

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
    typedef __rb_tree_node<Value> rb_tree_node;
    ...
public:
    typedef rb_tree_node* link_type;
    ...
protected:
    size_type node_count; // rb_tree的大?。ü?jié)點(diǎn)數(shù)量）
    link_type header;
    Compare key_compare;  // key的大小比較準(zhǔn)則
}

下面是對(duì)成員變量header的介紹：

在這段代碼中，header 是紅黑樹中的一個(gè)成員變量，它的類型是 link_type，而 link_type 又被定義為 rb_tree_node*。這里的 header 通常用來表示紅黑樹的頭部節(jié)點(diǎn)。

紅黑樹是一種二叉搜索樹，它的節(jié)點(diǎn)被分為紅色和黑色，并且有一些平衡性質(zhì)。為了簡化算法的實(shí)現(xiàn)，通常在紅黑樹的根節(jié)點(diǎn)（root）上添加一個(gè)額外的節(jié)點(diǎn)，稱為頭部節(jié)點(diǎn)。這個(gè)頭部節(jié)點(diǎn)不包含實(shí)際的數(shù)據(jù)，其左子節(jié)點(diǎn)指向紅黑樹的最小節(jié)點(diǎn)，右子節(jié)點(diǎn)指向紅黑樹的最大節(jié)點(diǎn)，父節(jié)點(diǎn)為空（或者指向紅黑樹的根節(jié)點(diǎn)），并且顏色為黑色。

在你的代碼中，header 就是用來表示這個(gè)頭部節(jié)點(diǎn)的指針。它提供了方便的訪問紅黑樹的最小、最大節(jié)點(diǎn)等信息，同時(shí)也使得算法實(shí)現(xiàn)更加簡潔，因?yàn)椴恍枰厥馓幚砀?jié)點(diǎn)的情況。

簡而言之，header 是紅黑樹的一個(gè)關(guān)鍵節(jié)點(diǎn)，它用于簡化算法實(shí)現(xiàn)，提供對(duì)樹的一些特殊節(jié)點(diǎn)（如最小節(jié)點(diǎn)、最大節(jié)點(diǎn)）的直接訪問。

下面代碼是摘錄自源代碼，并且進(jìn)行了注釋：

struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type; // 節(jié)點(diǎn)顏色類型

  // 基本指針類型，指向節(jié)點(diǎn)的父節(jié)點(diǎn)、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
  typedef _Rb_tree_node_base* _Base_ptr;

  _Color_type _M_color; // 節(jié)點(diǎn)顏色
  _Base_ptr _M_parent; // 指向父節(jié)點(diǎn)的指針
  _Base_ptr _M_left; // 指向左子節(jié)點(diǎn)的指針
  _Base_ptr _M_right; // 指向右子節(jié)點(diǎn)的指針

  // 靜態(tài)成員函數(shù)，返回以給定節(jié)點(diǎn)為根的子樹的最小節(jié)點(diǎn)
  static _Base_ptr _S_minimum(_Base_ptr __x)
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  // 靜態(tài)成員函數(shù)，返回以給定節(jié)點(diǎn)為根的子樹的最大節(jié)點(diǎn)
  static _Base_ptr _S_maximum(_Base_ptr __x)
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};

// 帶有值域的紅黑樹節(jié)點(diǎn)結(jié)構(gòu)，繼承自基本節(jié)點(diǎn)結(jié)構(gòu)
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
  // 鏈接類型，指向具有相同值類型的節(jié)點(diǎn)
  typedef _Rb_tree_node<_Value>* _Link_type;

  _Value _M_value_field; // 節(jié)點(diǎn)的值域
};

紅黑樹的使用：輸入傳入5個(gè)模板參數(shù)，由于最后一個(gè)模板參數(shù)有默認(rèn)值，所以可以不傳，只傳4個(gè)參數(shù)。

cout << "sizeof(_Rb_tree<...>)= " << sizeof(_Rb_tree<int,int,_Identity<int>,less<int>>) << endl; //24

這里第四個(gè)參數(shù)為std里面默認(rèn)的less比較函數(shù)對(duì)象，我們進(jìn)入源碼看一下具體實(shí)現(xiàn)細(xì)節(jié)：里面重載了operator()

  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

這里_Identity的作用：

在C++中，_Identity 通常是一個(gè)簡單的函數(shù)對(duì)象，也被稱為標(biāo)識(shí)函數(shù)對(duì)象或身份函數(shù)對(duì)象。其作用是返回傳入的值本身，即 operator() 返回其參數(shù)。

對(duì)應(yīng)下圖中的identity

上圖中identity的作用

下面是直接可運(yùn)行的測試紅黑樹的代碼，可以復(fù)制粘貼使用：

// 修改自侯捷的代碼
#include <set>
#include <functional>
#include <iostream>
using namespace std;

namespace jj31
{
void test_Rb_tree()
{
	//G2.9 vs. G4.9 : 
	  //rb_tree => _Rb_tree, 
	  //identity<> => _Identity<>
	  //insert_unique() => _M_insert_unique()
	  //insert_equal() => _M_insert_equal()
		 
	cout << "\ntest_Rb_tree().......... \n";
     
	_Rb_tree<int, int, _Identity<int>, less<int>> itree;
	cout << itree.empty() << endl;  //1
	cout << itree.size() << endl;   //0

	itree._M_insert_unique(3);
	itree._M_insert_unique(8);
	itree._M_insert_unique(5);
	itree._M_insert_unique(9);
	itree._M_insert_unique(13);
	itree._M_insert_unique(5);  //no effect, since using insert_unique().
	cout << itree.empty() << endl;  //0
	cout << itree.size() << endl;   //5
	cout << itree.count(5) << endl; //1

	itree._M_insert_equal(5);
	itree._M_insert_equal(5);
	cout << itree.size() << endl;   //7, since using insert_equal().
	cout << itree.count(5) << endl; //3       
}															 
}

int main(int argc, char** argv) 
{
	jj31::test_Rb_tree();	
	return 0;
}

_Rb_tree容器的類結(jié)構(gòu)

設(shè)計(jì)模式中的handle和body，把接口和實(shí)現(xiàn)分離

類的組織結(jié)構(gòu)如下：map和set 它倆has a rb_tree，rb_tree 它has a rb_tree_impl, 它has a rb_tree_node_base。這里的has a表示composition組合（下圖中的黑色菱形）

補(bǔ)充紅黑樹的右旋，源代碼如下：

// 紅黑樹右旋操作
inline void _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
    // 將 __x 的左子節(jié)點(diǎn)設(shè)為 __y
    _Rb_tree_node_base* __y = __x->_M_left;

    // 將 __y 的右子節(jié)點(diǎn)設(shè)為 __x 的左子節(jié)點(diǎn)
    __x->_M_left = __y->_M_right;

    // 如果 __y 的右子節(jié)點(diǎn)非空，則將其右子節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為 __x
    if (__y->_M_right != 0)
        __y->_M_right->_M_parent = __x;

    // 將 __y 的父節(jié)點(diǎn)設(shè)為 __x 的父節(jié)點(diǎn)
    __y->_M_parent = __x->_M_parent;

    // 如果 __x 是根節(jié)點(diǎn)，則將 __y 設(shè)為新的根節(jié)點(diǎn)
    if (__x == __root)
        __root = __y;
    // 如果 __x 是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則將 __y 設(shè)為 __x 父節(jié)點(diǎn)的右子節(jié)點(diǎn)
    else if (__x == __x->_M_parent->_M_right)
        __x->_M_parent->_M_right = __y;
    // 如果 __x 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則將 __y 設(shè)為 __x 父節(jié)點(diǎn)的左子節(jié)點(diǎn)
    else
        __x->_M_parent->_M_left = __y;

    // 將 __x 設(shè)為 __y 的右子節(jié)點(diǎn)
    __y->_M_right = __x;

    // 將 __y 設(shè)為 __x 的父節(jié)點(diǎn)
    __x->_M_parent = __y;
}

還有_Rb_tree_rebalance，_Rb_tree_rebalance_for_erase等具體實(shí)現(xiàn)，這里不列舉。

21 set、multiset深度探索

容器set和multiset

std::set 和 std::multiset 是 C++ 標(biāo)準(zhǔn)庫中的關(guān)聯(lián)容器，它們都基于紅黑樹實(shí)現(xiàn)。它們的主要區(qū)別在于元素的唯一性：

1. std::set：

   • 所有元素的鍵（key）都是唯一的，即集合中不允許存在相同的元素。
   • 插入相同的元素會(huì)被容器拒絕（被忽略）。

2. std::multiset：

   • 允許集合中存在相同的元素，即元素的鍵可以重復(fù)。
   • 插入相同的元素是允許的，所有相同的元素都被插入到容器中。

下面是一個(gè)簡單的示例來說明兩者之間的區(qū)別：

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    // 使用 std::set
    std::set<int> uniqueSet;
    uniqueSet.insert(1);
    uniqueSet.insert(2);
    uniqueSet.insert(1);  // 重復(fù)元素，被忽略

    std::cout << "std::set elements: ";
    for (const auto& elem : uniqueSet) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    // 使用 std::multiset
    std::multiset<int> multiSet;
    multiSet.insert(1);
    multiSet.insert(2);
    multiSet.insert(1);  // 允許重復(fù)元素

    std::cout << "std::multiset elements: ";
    for (const auto& elem : multiSet) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    return 0;
}

上述代碼中，std::set 中的重復(fù)元素被忽略，而 std::multiset 中允許存在重復(fù)元素。選擇使用哪一個(gè)取決于你的需求，如果需要保持元素的唯一性，使用 std::set；如果允許重復(fù)元素，使用 std::multiset。

這里實(shí)現(xiàn)的原理是什么呢？

set元素的key必須唯一，因?yàn)樗黫nsert()調(diào)用的是紅黑樹的insert_unique()；

multiset元素的key可以重復(fù)，因?yàn)樗黫nsert()調(diào)用的是紅黑樹的insert_equal()。

set和multiset對(duì)迭代器的支持：

std::set 和 std::multiset 都支持迭代器，通過迭代器可以遍歷容器中的元素。以下是一個(gè)簡單的示例，演示了如何使用迭代器遍歷這兩個(gè)容器：

#include <iostream>
#include <set>

int main() {
    // 使用 std::set
    std::set<int> uniqueSet;
    uniqueSet.insert(1);
    uniqueSet.insert(2);
    uniqueSet.insert(3);

    // 使用迭代器遍歷 std::set
    std::cout << "std::set elements: ";
    for (auto it = uniqueSet.begin(); it != uniqueSet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 使用 std::multiset
    std::multiset<int> multiSet;
    multiSet.insert(1);
    multiSet.insert(2);
    multiSet.insert(1);

    // 使用迭代器遍歷 std::multiset
    std::cout << "std::multiset elements: ";
    for (auto it = multiSet.begin(); it != multiSet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    return 0;
}

上述代碼中，使用 begin() 函數(shù)獲取容器的起始迭代器，使用 end() 函數(shù)獲取容器的結(jié)束迭代器，然后通過迭代器遍歷容器中的元素。注意，std::multiset 中存在重復(fù)元素，因此迭代器會(huì)遍歷所有相同的元素。

容器set

有三個(gè)模板參數(shù)，

template <class _Key, class _Compare, class _Alloc>
class set {
public:
  // typedefs:

  typedef _Key     key_type;
  typedef _Key     value_type;
  typedef _Compare key_compare;
  typedef _Compare value_compare;
private:
  typedef _Rb_tree<key_type, value_type, 
                  _Identity<value_type>, key_compare, _Alloc> _Rep_type; // 紅黑樹
  _Rep_type _M_t;  // red-black tree representing set
public:
  typedef typename _Rep_type::const_pointer pointer;
  typedef typename _Rep_type::const_pointer const_pointer;
  typedef typename _Rep_type::const_reference reference;
  typedef typename _Rep_type::const_reference const_reference;
  typedef typename _Rep_type::const_iterator iterator;  // 這里iterator是const iterator，這種迭代器不允許改內(nèi)容
  typedef typename _Rep_type::const_iterator const_iterator;
  typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  typedef typename _Rep_type::size_type size_type;
  typedef typename _Rep_type::difference_type difference_type;
  typedef typename _Rep_type::allocator_type allocator_type;
...
}

22 map、multimap深度探索

std::map 和 std::multimap 是 C++ 標(biāo)準(zhǔn)庫中的關(guān)聯(lián)容器，它們都基于紅黑樹實(shí)現(xiàn)，用于存儲(chǔ)鍵值對(duì)。它們的主要區(qū)別在于元素的唯一性：

1. std::map：

   • 所有元素的鍵（key）都是唯一的，即地圖中不允許存在相同的鍵。
   • 插入相同的鍵會(huì)導(dǎo)致已存在的元素被替換。

2. std::multimap：

   • 允許存在相同的鍵，即鍵可以重復(fù)。
   • 插入相同的鍵是允許的，所有相同的鍵都會(huì)被插入到容器中。

以下是一個(gè)簡單的示例，說明兩者之間的區(qū)別：

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // 使用 std::map
    std::map<int, std::string> uniqueMap;
    uniqueMap[1] = "One";
    uniqueMap[2] = "Two";
    uniqueMap[1] = "New One";  // 替換已存在的鍵值對(duì)

    std::cout << "std::map elements: ";
    for (const auto& elem : uniqueMap) {
        std::cout << "{" << elem.first << ": " << elem.second << "} ";
    }
    std::cout << "\n";

    // 使用 std::multimap
    std::multimap<int, std::string> multiMap;
    multiMap.insert({1, "One"});
    multiMap.insert({2, "Two"});
    multiMap.insert({1, "Another One"});  // 允許重復(fù)鍵

    std::cout << "std::multimap elements: ";
    for (const auto& elem : multiMap) {
        std::cout << "{" << elem.first << ": " << elem.second << "} ";
    }
    std::cout << "\n";

    return 0;
}

在上述代碼中，std::map 中的重復(fù)鍵會(huì)導(dǎo)致已存在的元素被替換，而 std::multimap 中允許存在相同的鍵，插入相同的鍵會(huì)添加新的鍵值對(duì)。選擇使用哪一個(gè)取決于你的需求，如果需要保持鍵的唯一性，使用 std::map；如果允許重復(fù)鍵，使用 std::multimap。

容器map

set不允許改變?cè)兀峭ㄟ^把迭代器指定為const iterator來做的；map不需要修改key，是通過指定key為 const類型來做的。

template <class _Key, class _Tp, class _Compare, class _Alloc>
class map {
public:
// typedefs:

  typedef _Key                  key_type;
  typedef _Tp                   data_type;
  typedef _Tp                   mapped_type;
  typedef pair<const _Key, _Tp> value_type; // 這里_Key被指定為const，不能被修改
  typedef _Compare              key_compare;
    

private:
  typedef _Rb_tree<key_type, value_type, 
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  _Rep_type _M_t;  // red-black tree representing map
public:
  typedef typename _Rep_type::pointer pointer;
  typedef typename _Rep_type::const_pointer const_pointer;
  typedef typename _Rep_type::reference reference;
  typedef typename _Rep_type::const_reference const_reference;
  typedef typename _Rep_type::iterator iterator;
  typedef typename _Rep_type::const_iterator const_iterator;
  typedef typename _Rep_type::reverse_iterator reverse_iterator;
  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

下面的select1st取出key

下圖展示了select1st的實(shí)現(xiàn)，它是一個(gè)functor，函數(shù)對(duì)象。功能是取出pair中的第一個(gè)元素

multimap不允許使用[]插入，但是map允許使用[]插入

這句話指的是在 C++ 的 std::map 和 std::multimap 中使用 operator[] 進(jìn)行元素插入的差異。

• std::map：對(duì)于 std::map，使用 operator[] 可以進(jìn)行元素的插入。如果鍵不存在于 map 中，operator[] 會(huì)插入一個(gè)具有給定鍵的新元素，并返回對(duì)應(yīng)的值的引用。如果鍵已經(jīng)存在，它將返回已存在鍵的值的引用，不會(huì)插入新元素。如果需要插入或修改元素，operator[] 是一種方便的方式。

  #include <iostream>
  #include <map>
  
  int main() {
      std::map<int, std::string> myMap;
  
      // 使用 operator[] 插入元素
      myMap[1] = "One";
      myMap[2] = "Two";
  
      // 輸出 map 的元素
      for (const auto& elem : myMap) {
          std::cout << "{" << elem.first << ": " << elem.second << "} ";
      }
      std::cout << "\n";
  
      return 0;
  }
  

• std::multimap：相反，對(duì)于 std::multimap，operator[] 不允許進(jìn)行元素的插入。這是因?yàn)?multimap 允許存在相同的鍵，而 operator[] 無法確定是應(yīng)該插入新元素還是返回已存在鍵的值。

  #include <iostream>
  #include <map>
  
  int main() {
      std::multimap<int, std::string> myMultiMap;
  
      // 以下行將導(dǎo)致編譯錯(cuò)誤，因?yàn)?operator[] 不允許插入新元素
      // myMultiMap[1] = "One";
      // myMultiMap[2] = "Two";
  
      // 可以使用 insert 插入元素
      myMultiMap.insert({1, "One"});
      myMultiMap.insert({2, "Two"});
      myMultiMap.insert({1, "Another One"});  // 允許插入相同的鍵
  
      // 輸出 multimap 的元素
      for (const auto& elem : myMultiMap) {
          std::cout << "{" << elem.first << ": " << elem.second << "} ";
      }
      std::cout << "\n";
  
      return 0;
  }
  

總的來說，使用 operator[] 進(jìn)行插入操作在 std::map 中是允許的，但在 std::multimap 中是不允許的。在 std::multimap 中插入元素通常使用 insert 函數(shù)。

map中的[] 操作符的實(shí)現(xiàn)如下，里面先調(diào)用lower_bound進(jìn)行查找，然后再insert元素

23 hashtable深度探索（上）

容器hashtable

容器 hashtable 指的是哈希表，它是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)關(guān)聯(lián)容器，如 C++ 標(biāo)準(zhǔn)庫中的 std::unordered_map 和 std::unordered_set。

哈希表的基本思想是將鍵（key）通過哈希函數(shù)映射到一個(gè)固定范圍的索引，然后在該索引處存儲(chǔ)對(duì)應(yīng)的值（或者鏈表、二叉樹等數(shù)據(jù)結(jié)構(gòu)）。這樣可以在期望的常數(shù)時(shí)間內(nèi)（平均情況下）進(jìn)行插入、刪除和查找操作。

在 C++ 標(biāo)準(zhǔn)庫中，std::unordered_map 是使用哈希表實(shí)現(xiàn)的關(guān)聯(lián)容器，用于存儲(chǔ)鍵值對(duì)。std::unordered_set 是存儲(chǔ)唯一元素的集合，同樣使用哈希表實(shí)現(xiàn)。這些容器允許在平均情況下以常數(shù)時(shí)間執(zhí)行插入、刪除和查找操作，但在最壞情況下可能會(huì)有更高的時(shí)間復(fù)雜度，具體取決于哈希函數(shù)的質(zhì)量和沖突處理的方法。

哈希表的實(shí)現(xiàn)通常涉及以下關(guān)鍵點(diǎn)：

1. 哈希函數(shù)（Hash Function）： 將鍵映射到索引的函數(shù)。良好的哈希函數(shù)應(yīng)該盡可能均勻地分布鍵，以減少?zèng)_突的發(fā)生。

2. 沖突處理（Collision Resolution）： 當(dāng)兩個(gè)不同的鍵被映射到相同的索引時(shí)，發(fā)生沖突。沖突處理的方法包括鏈地址法、開放地址法等。

3. 負(fù)載因子（Load Factor）： 哈希表中實(shí)際元素個(gè)數(shù)與桶的數(shù)量之比。負(fù)載因子的選擇會(huì)影響哈希表的性能，通常需要在保持高效性能和減少?zèng)_突之間進(jìn)行權(quán)衡。

哈希表是一種高效的數(shù)據(jù)結(jié)構(gòu)，特別適用于需要頻繁插入、刪除和查找操作的場景。

在哈希表中，桶（bucket）和鏈表（linked list）是兩個(gè)重要的概念，它們用于解決哈希沖突。

1. 桶（Bucket）：

   • 定義： 桶是哈希表中的一個(gè)存儲(chǔ)位置，通常是一個(gè)數(shù)組，每個(gè)元素稱為一個(gè)桶。
   • 作用： 哈希表中的每個(gè)桶對(duì)應(yīng)一個(gè)哈希值，桶的數(shù)量通常是一個(gè)固定的值，決定了哈希表的大小。元素通過哈希函數(shù)映射到具體的桶。

2. 鏈表（Linked List）：

   • 定義： 鏈表是一種數(shù)據(jù)結(jié)構(gòu)，可以存儲(chǔ)多個(gè)元素，每個(gè)元素包含一個(gè)值和一個(gè)指向下一個(gè)元素的指針。
   • 作用： 當(dāng)多個(gè)鍵被映射到同一個(gè)桶時(shí)，就會(huì)發(fā)生哈希沖突。為了解決沖突，每個(gè)桶可以使用鏈表來存儲(chǔ)具有相同哈希值的鍵值對(duì)。這樣，當(dāng)發(fā)生沖突時(shí)，新的元素可以被添加到該桶對(duì)應(yīng)的鏈表中。

在哈希表中，使用鏈表來處理沖突的方法被稱為“鏈地址法”（Chaining）。具體來說，每個(gè)桶維護(hù)一個(gè)鏈表，當(dāng)沖突發(fā)生時(shí)，新元素會(huì)被添加到鏈表中。如果多個(gè)元素映射到同一個(gè)桶，它們就形成了一個(gè)鏈表。這樣，相同哈希值的元素可以在同一個(gè)桶中找到。

在 C++ 標(biāo)準(zhǔn)庫的 std::unordered_map 和 std::unordered_set 中，通常就是通過鏈地址法來處理哈希沖突的。如果鏈表變得太長，可能會(huì)導(dǎo)致性能下降，因此一些實(shí)現(xiàn)還會(huì)在鏈表變得過長時(shí)轉(zhuǎn)換為更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，比如紅黑樹，以提高查找效率。這樣的優(yōu)化稱為“鏈表到樹的轉(zhuǎn)化”（List to Tree Conversion）或“桶的再哈希”（Bucket Rehashing）。

下圖中，上方的hashtable中桶的個(gè)數(shù)為53（編號(hào)為0到52），然后當(dāng)桶放完之后，比如達(dá)到54個(gè)元素之后，就要擴(kuò)充桶的數(shù)量。

Rehashing（再哈希） 是哈希表中的一個(gè)重要操作，它涉及調(diào)整哈希表的大小，通常是為了保持哈希表的負(fù)載因子在一個(gè)合適的范圍內(nèi)。負(fù)載因子是指哈希表中實(shí)際元素個(gè)數(shù)與桶的數(shù)量之比。

當(dāng)負(fù)載因子過大時(shí)，哈希沖突的概率會(huì)增加，從而導(dǎo)致查找、插入和刪除操作的效率下降。為了避免這種情況，當(dāng)負(fù)載因子達(dá)到某個(gè)閾值時(shí)，哈希表就會(huì)執(zhí)行 rehashing 操作。

Rehashing 的主要步驟包括：

1. 創(chuàng)建新的桶數(shù)組： 首先，創(chuàng)建一個(gè)新的桶數(shù)組，通常將桶的數(shù)量調(diào)整為原來的兩倍（或其他倍數(shù)）。

2. 遍歷舊桶數(shù)組： 將原有的鍵值對(duì)重新映射到新的桶數(shù)組中。這通常涉及到重新計(jì)算鍵的哈希值，并將鍵值對(duì)插入到新的桶中。由于桶的數(shù)量發(fā)生了改變，新的哈希函數(shù)可能也會(huì)不同。

3. 釋放舊桶數(shù)組： 釋放原來的桶數(shù)組的內(nèi)存空間。

Rehashing 的好處包括：

• 維護(hù)負(fù)載因子： 通過調(diào)整桶的數(shù)量，可以保持哈希表的負(fù)載因子在一個(gè)適當(dāng)?shù)姆秶鷥?nèi)，提高哈希表的性能。

• 減少哈希沖突： 重新分配桶的位置，有助于減少鍵值對(duì)之間的哈希沖突。

• 適應(yīng)變化： 當(dāng)元素的數(shù)量發(fā)生變化時(shí)，rehashing 使哈希表能夠適應(yīng)新的負(fù)載情況，從而保持高效性能。

在 C++ 標(biāo)準(zhǔn)庫中，std::unordered_map 和 std::unordered_set 等容器在內(nèi)部通常會(huì)自動(dòng)執(zhí)行 rehashing 操作，以確保哈希表的性能。 Rehashing 的觸發(fā)條件和實(shí)現(xiàn)方式可能因不同的實(shí)現(xiàn)而異，但通常是在負(fù)載因子超過某個(gè)閾值時(shí)觸發(fā)的。

下面是常用的桶的大小的值

// Note: assumes long is at least 32 bits.
enum { __stl_num_primes = 28 };

static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul, 
  1610612741ul, 3221225473ul, 4294967291ul
};

下面是從hashtable的源代碼中摘錄的代碼

template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
public:
  typedef _Key key_type;
  typedef _Val value_type;
  typedef _HashFcn hasher;
  typedef _EqualKey key_equal;

  typedef size_t            size_type;
  typedef ptrdiff_t         difference_type;
  typedef value_type*       pointer;
  typedef const value_type* const_pointer;
  typedef value_type&       reference;
  typedef const value_type& const_reference;

  hasher hash_funct() const { return _M_hash; }
  key_equal key_eq() const { return _M_equals; }

private:
  typedef _Hashtable_node<_Val> _Node;

private:
  // 3個(gè)函數(shù)對(duì)象
  hasher                _M_hash;
  key_equal             _M_equals;
  _ExtractKey           _M_get_key;
  //buckets桶的實(shí)現(xiàn)是用的vector
  vector<_Node*,_Alloc> _M_buckets;
  size_type             _M_num_elements;  // 記錄元素個(gè)數(shù)
...
}

template <class _Val>
struct _Hashtable_node // 上面所說每個(gè)桶所串起來的鏈表節(jié)點(diǎn)
{
  _Hashtable_node* _M_next;
  _Val _M_val;
};  

對(duì)六個(gè)模板參數(shù)的解釋：

1. _Val：

   • 含義： 表示哈希表中存儲(chǔ)的值的類型。
   • 用途： 哈希表存儲(chǔ)的是鍵值對(duì)，_Val 表示鍵值對(duì)中的值的類型。

2. _Key：

   • 含義： 表示哈希表中存儲(chǔ)的鍵的類型。
   • 用途： 哈希表存儲(chǔ)的是鍵值對(duì)，_Key 表示鍵值對(duì)中的鍵的類型。

3. _HashFcn：

   • 含義： 表示哈希函數(shù)的類型。
   • 用途： _HashFcn 指定了計(jì)算鍵的哈希值的方法，它是一個(gè)函數(shù)對(duì)象（函數(shù)或函數(shù)指針），用于將鍵轉(zhuǎn)換為哈希值。

4. _ExtractKey：

   • 含義： 表示從鍵值對(duì)中提取鍵的方法的類型。
   • 用途： _ExtractKey 是一個(gè)函數(shù)對(duì)象，用于從鍵值對(duì)中提取鍵，它定義了哈希表如何獲取鍵值對(duì)中的鍵。

5. _EqualKey：

   • 含義： 表示鍵的相等比較方法的類型。
   • 用途： _EqualKey 是一個(gè)函數(shù)對(duì)象，用于判斷兩個(gè)鍵是否相等，它定義了哈希表中鍵的相等性比較。

6. _Alloc：

   • 含義： 表示用于分配內(nèi)存的分配器的類型。
   • 用途： _Alloc 指定了哈希表內(nèi)存的分配方式，它是一個(gè)分配器類模板，用于管理哈希表的內(nèi)存分配和釋放。

總體而言，這些模板參數(shù)定義了哈希表的基本特性，包括存儲(chǔ)的鍵值對(duì)的類型、哈希函數(shù)、鍵的提取方法、鍵的相等比較方法以及內(nèi)存分配器。通過提供不同的類型，可以實(shí)現(xiàn)不同類型的哈希表，適應(yīng)不同的使用場景。

看一下hashtable的迭代器，有兩個(gè)元素_M_cur和_M_ht

struct _Hashtable_iterator {
  typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
          _Hashtable;
  typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 
                              _ExtractKey, _EqualKey, _Alloc>
          iterator;
  typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 
                                    _ExtractKey, _EqualKey, _Alloc>
          const_iterator;
  typedef _Hashtable_node<_Val> _Node;

  typedef forward_iterator_tag iterator_category;
  typedef _Val value_type;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef _Val& reference;
  typedef _Val* pointer;

  _Node* _M_cur; // 指向具體的node，就是具體的元素
  _Hashtable* _M_ht;  //指向hashtable本身，就是指向具體的桶buchet

  _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
    : _M_cur(__n), _M_ht(__tab) {}
  _Hashtable_iterator() {}
  reference operator*() const { return _M_cur->_M_val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
  iterator& operator++();
  iterator operator++(int);
  bool operator==(const iterator& __it) const
    { return _M_cur == __it._M_cur; }
  bool operator!=(const iterator& __it) const
    { return _M_cur != __it._M_cur; }
};

對(duì)上述代碼的解釋：

這段代碼是 hashtable 的迭代器 _Hashtable_iterator 的定義。對(duì)于哈希表而言，其迭代器的設(shè)計(jì)通常涉及遍歷桶（buckets）和桶中元素的過程。

1. _Node* _M_cur;：

   • _M_cur 是指向具體元素的節(jié)點(diǎn) _Node 的指針。在哈希表中，每個(gè)桶都是一個(gè)鏈表或其他數(shù)據(jù)結(jié)構(gòu)，_M_cur 指向鏈表中的某個(gè)節(jié)點(diǎn)，即具體的元素。

2. _Hashtable* _M_ht;：

   • _M_ht 是指向哈希表本身的指針。它用于指示當(dāng)前迭代器所屬的哈希表，即指向具體的桶數(shù)組。

3. iterator& operator++();：

   • operator++ 是前綴遞增運(yùn)算符，用于將迭代器指向下一個(gè)元素。在哈希表的迭代器中，這通常意味著移動(dòng)到當(dāng)前桶鏈表的下一個(gè)節(jié)點(diǎn)。

4. iterator operator++(int);：

   • operator++(int) 是后綴遞增運(yùn)算符。它返回當(dāng)前迭代器的副本，并將原始迭代器移動(dòng)到下一個(gè)元素。同樣，對(duì)于哈希表，這通常意味著移動(dòng)到當(dāng)前桶鏈表的下一個(gè)節(jié)點(diǎn)。

5. bool operator==(const iterator& __it) const 和 bool operator!=(const iterator& __it) const：

   • 用于比較兩個(gè)迭代器是否相等。在哈希表的迭代器中，相等通常表示兩個(gè)迭代器指向相同的元素。

哈希表的迭代器并不一定按桶從小到大的順序排列。它們的遍歷順序可能會(huì)受到哈希表內(nèi)部桶的分布、哈希函數(shù)等因素的影響。具體而言，哈希表迭代器可能會(huì)按照桶的索引從小到大的順序進(jìn)行遍歷，但在每個(gè)桶內(nèi)，元素的順序可能不同。由于哈希表的設(shè)計(jì)目的是提高查找效率，而不是有序存儲(chǔ)元素，因此迭代器的順序不一定是嚴(yán)格有序的。

24 hashtable深度探索（下）

下面講一下hashtable具體怎么用，具體的6個(gè)模板參數(shù)怎么指定，如下圖所示。

// 模板參數(shù)
template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
// 具體指定為：
hashtable<const char*,
		  const char*,
		  hash<const char*>,
		  identity<const char*>
          eqstr,
		  alloc>
ht<50, hash<const char*>(), eqstr());

ht.insert_unique("kiwi");
ht.insert_unique("plum");
ht.insert_unique("apple");

struct eqstr{
    bool operator()(const char* s1, const char* s2) const
    { return strcmp(s1, s2) == 0;}
}

解釋與注釋：

1. _Val：

   • 模板參數(shù)中： _Val 是哈希表中存儲(chǔ)的值的類型。
   • 具體指定為： const char*，表示存儲(chǔ)的值為字符串指針。

2. _Key：

   • 模板參數(shù)中： _Key 是哈希表中存儲(chǔ)的鍵的類型。
   • 具體指定為： const char*，表示鍵的類型為字符串指針。

3. _HashFcn：

   • 模板參數(shù)中： _HashFcn 是哈希函數(shù)的類型。
   • 具體指定為： hash<const char*>，表示使用 hash 函數(shù)對(duì)象來計(jì)算字符串指針的哈希值。

4. _ExtractKey：

   • 模板參數(shù)中： _ExtractKey 是從鍵值對(duì)中提取鍵的方法的類型。
   • 具體指定為： identity<const char*>，表示使用 identity 函數(shù)對(duì)象來提取字符串指針作為鍵。

5. _EqualKey：

   • 模板參數(shù)中： _EqualKey 是鍵的相等比較方法的類型。
   • 具體指定為： eqstr，表示使用自定義的比較函數(shù)對(duì)象 eqstr 來判斷兩個(gè)鍵是否相等。

6. _Alloc：

   • 模板參數(shù)中： _Alloc 是用于分配內(nèi)存的分配器的類型。
   • 具體指定為： alloc，表示使用標(biāo)準(zhǔn)分配器 alloc。

7. 哈希表實(shí)例化：

   • ht<50, hash<const char*>(), eqstr() 表示具體實(shí)例化了哈希表對(duì)象 ht。
   • 指定了哈希表的桶數(shù)量為 50，使用 hash<const char*> 計(jì)算哈希值，以及使用 eqstr 進(jìn)行鍵的相等性比較。

8. 插入元素：

   • ht.insert_unique("kiwi")、ht.insert_unique("plum")、ht.insert_unique("apple") 分別插入了字符串 “kiwi”、“plum”、“apple”。

9. 比較函數(shù)對(duì)象定義：

   • struct eqstr 定義了一個(gè)比較函數(shù)對(duì)象，用于在哈希表中比較字符串指針的相等性。

介紹hash function

在C++中，對(duì) operator() 的重載允許對(duì)象實(shí)例被像函數(shù)一樣調(diào)用，這使得對(duì)象可以表現(xiàn)得像函數(shù)一樣。通過重載 operator()，你可以將一個(gè)類實(shí)例的行為定義為可調(diào)用的，就像調(diào)用函數(shù)一樣。這種特性在C++中常常被稱為“函數(shù)對(duì)象”或“仿函數(shù)”。

作用和意義：

1. 可調(diào)用性： 通過重載 operator()，你可以將對(duì)象實(shí)例看作可調(diào)用的實(shí)體，就像函數(shù)一樣。這樣的對(duì)象可以被像函數(shù)一樣調(diào)用，而不必使用函數(shù)調(diào)用運(yùn)算符 ()。

2. 狀態(tài)保持： 函數(shù)對(duì)象可以保持狀態(tài)，因?yàn)樗鼈兛梢杂谐蓡T變量。這使得函數(shù)對(duì)象能夠在調(diào)用之間保持狀態(tài)信息。

3. 靈活性： 函數(shù)對(duì)象可以像普通函數(shù)一樣傳遞給其他函數(shù)，也可以作為函數(shù)對(duì)象的成員傳遞給其他對(duì)象。

具體的使用示例：

#include <iostream>

// 示例：函數(shù)對(duì)象類，重載了operator()，用于比較兩個(gè)整數(shù)的大小
struct CompareIntegers {
    bool operator()(int a, int b) const {
        return a < b;
    }
};

int main() {
    // 使用函數(shù)對(duì)象進(jìn)行比較
    CompareIntegers compare;

    int x = 5, y = 10;

    // 通過函數(shù)對(duì)象比較兩個(gè)整數(shù)
    bool result = compare(x, y);

    // 輸出結(jié)果
    std::cout << "Is x less than y? " << std::boolalpha << result << std::endl;

    return 0;
}

在上面的示例中，CompareIntegers 是一個(gè)函數(shù)對(duì)象類，它重載了 operator()，用于比較兩個(gè)整數(shù)的大小。通過實(shí)例化 CompareIntegers 類，并調(diào)用 operator()，可以像函數(shù)一樣比較兩個(gè)整數(shù)的大小。這種方式比傳遞函數(shù)指針更靈活，因?yàn)楹瘮?shù)對(duì)象可以保持狀態(tài)，并且可以輕松地通過類的成員傳遞額外的參數(shù)。函數(shù)對(duì)象在STL中的算法、容器等地方經(jīng)常被使用。

下面是一種hash

inline size_t __stl_hash_string(const char* __s)
{
  unsigned long __h = 0; 
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;
  
  return size_t(__h);
}

25 hash set、hash multiset, hash map、hash multimap概念

視頻缺失

26 unordered容器概念

在C++的標(biāo)準(zhǔn)庫中，unordered_set、unordered_multiset、unordered_map、unordered_multimap 分別對(duì)應(yīng)哈希集合、哈希多重集合、哈希映射以及哈希多重映射。以下是它們的概念和特點(diǎn)：

1. unordered_set：

   • 概念： 無序集合，存儲(chǔ)不重復(fù)的元素，內(nèi)部使用哈希表實(shí)現(xiàn)。
   • 特點(diǎn)： 元素?zé)o序存儲(chǔ)，插入、刪除、查找操作的平均時(shí)間復(fù)雜度為 O(1)。

2. unordered_multiset：

   • 概念： 無序多重集合，存儲(chǔ)允許重復(fù)的元素，內(nèi)部使用哈希表實(shí)現(xiàn)。
   • 特點(diǎn)： 元素?zé)o序存儲(chǔ)，插入、刪除、查找操作的平均時(shí)間復(fù)雜度為 O(1)。

3. unordered_map：

   • 概念： 無序映射，存儲(chǔ)鍵值對(duì)，內(nèi)部使用哈希表實(shí)現(xiàn)。
   • 特點(diǎn)： 鍵值對(duì)無序存儲(chǔ)，通過鍵進(jìn)行查找、插入、刪除的平均時(shí)間復(fù)雜度為 O(1)。

4. unordered_multimap：

   • 概念： 無序多重映射，存儲(chǔ)允許多個(gè)相同鍵的鍵值對(duì)，內(nèi)部使用哈希表實(shí)現(xiàn)。
   • 特點(diǎn)： 鍵值對(duì)無序存儲(chǔ)，通過鍵進(jìn)行查找、插入、刪除的平均時(shí)間復(fù)雜度為 O(1)。

這些容器是C++11及更高版本引入的，它們?cè)谑褂脮r(shí)不保證元素的順序，而是通過哈希表提供快速的查找性能。每個(gè)元素被映射到哈希表的一個(gè)桶中，這使得查找操作的時(shí)間復(fù)雜度較低。然而，由于使用哈希表，它們不提供元素的有序性。如果需要有序性，應(yīng)考慮使用 std::set、std::multiset、std::map、std::multimap。

后記

完成容器底層的學(xué)習(xí)。本文主要記錄基于紅黑樹的容器和基于hashtable的容器。文章來源地址http://www.zghlxwxcb.cn/news/detail-811835.html

到了這里，關(guān)于STL標(biāo)準(zhǔn)庫與泛型編程（侯捷）筆記4的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！