模板類的集合，內(nèi)部封裝組織數(shù)據(jù)的方法，也就是數(shù)據(jù)結(jié)構(gòu)

作用：存放數(shù)據(jù)

分類：

• 序列式容器 ：線性
• 關(guān)聯(lián)式容器：key-value 集合，紅黑樹(shù)實(shí)現(xiàn)
• 無(wú)序關(guān)聯(lián)容器：hash 實(shí)現(xiàn)

1、序列容器

序列式容器

• array：固定大小的數(shù)組。支持隨機(jī)訪問(wèn)迭代器。
• vector：動(dòng)態(tài)數(shù)組。支持隨機(jī)訪問(wèn)迭代器。
• deque：雙端隊(duì)列。支持隨機(jī)訪問(wèn)迭代器。
• list：雙向鏈表。只支持雙向訪問(wèn)迭代器。
• forward_list：單鏈表。只支持前向訪問(wèn)迭代器

序列式容器使用總結(jié)，當(dāng)下列操作頻繁發(fā)生時(shí)

• 在容器中間位置添加刪除元素，list
• 在容器頭部位置添加刪除元素，deque / list
• 在容器尾部位置添加刪除元素，vector / deque / list
• 訪問(wèn)容器任意位置上的元素，vector

1.1、容器共性

初始化

// 1、默認(rèn)構(gòu)造函數(shù)，空容器
容器();
// 2、構(gòu)造擁有 count 個(gè)有值 value 的元素的容器。
容器(size_type count,const T& value = T(),const Allocator& alloc = Allocator());
// 3、構(gòu)造擁有范圍 [first, last) 內(nèi)容的容器。
容器(InputIt first, InputIt last, const Allocator& alloc = Allocator());

賦值操作

// 1、重載等號(hào)操作符
operator=
// 2、assign
void assign(InputIt first, InputIt last); 	  // 以范圍 [first, last) 中元素的副本替換內(nèi)容。
void assign(size_type count, const T& value); // 將 count 個(gè) value 的副本替換內(nèi)容。

元素訪問(wèn)

at		    // 訪問(wèn)指定元素，同時(shí)越界檢查
operator[]	// 訪問(wèn)指定元素 
front 		// 訪問(wèn)第一個(gè)元素
back		// 訪問(wèn)最后一個(gè)元素

容量

// 檢查容器是否無(wú)元素
bool empty() const; 
// 容器中元素?cái)?shù)量
size_type size() const;

修改器

// 1. 刪除容器中所有元素
void clear();// 2. 插入元素
// 在 pos 前插入 value
iterator insert(const_iterator pos, T&& value);  
// 在 pos 前插入 value 的 count 個(gè)副本
iterator insert(const_iterator pos, size_type count, const T& value); 
// 原地構(gòu)造元素，并將參數(shù)args轉(zhuǎn)發(fā)給構(gòu)造函數(shù)
iterator emplace(const_iterator pos, Args&&... args);// 3. 容器末尾添加元素
void push_back(const T& value);
// 容器末尾就地構(gòu)造元素
void emplace_back(Args&&... args);// 4. 移除末尾元素
void pop_back();// 5. 刪除元素
// 移除位于 pos 的元素。
iterator erase(iterator pos);
// 移除范圍 [first, last) 中的元素。
iterator erase(iterator first, iterator last);   // 6. 改變?nèi)萜髦锌纱鎯?chǔ)元素的個(gè)數(shù)
void resize(size_type count);
void resize(size_type count, T value = T());// 7. 交換容器內(nèi)容
void swap(deque& other);

1.2、vector

• 動(dòng)態(tài)數(shù)組
• 支持隨機(jī)訪問(wèn)迭代器
• 邏輯機(jī)構(gòu)和物理結(jié)構(gòu)一致，連續(xù)線性空間，空間不足時(shí)，自動(dòng)擴(kuò)容

vector 擴(kuò)容

• 申請(qǐng)新空間：兩倍擴(kuò)容
• 移動(dòng)數(shù)據(jù)
• 釋放原空間

vector 結(jié)構(gòu)

vector 使用三個(gè)指針維護(hù)動(dòng)態(tài)數(shù)組 start, finish, end_of_storage

源碼如下：

template <class _Tp, class _Alloc> 
class _Vector_base {
protected:_Tp* _M_start;	      // 指向使用空間的第一個(gè)元素	_Tp* _M_finish;	      // 指向使用空間的最后一個(gè)元素的下一個(gè)位置_Tp* _M_end_of_storage; // 指向可用空間的最后一個(gè)位置的下一個(gè)位置
};

通過(guò)三個(gè)指針可以實(shí)現(xiàn)一些基本接口

iterator begin() { return _M_start; }
iterator end() { return _M_finish; }size_type size() const { return size_type(end() - begin()); }
size_type capacity() const { return size_type(_M_end_of_storage - begin()); }
bool empty() const { return begin() == end(); }reference operator[](size_type __n) { return *(begin() + __n); }reference front() { return *begin(); }
reference back() { return *(end() - 1); }

* vector 擴(kuò)容原理

vector 擴(kuò)容

• 申請(qǐng)新空間：兩倍擴(kuò)容。
• 拷貝舊空間的元素到新空間：新空間前半段存放舊數(shù)據(jù)，后半段存放新插入的數(shù)據(jù)。
• 釋放原空間。

注意：初始化時(shí)，數(shù)組空間大小為 0，擴(kuò)容后，新空間大小為 1。此后，都是兩倍擴(kuò)容操作。

添加元素時(shí)，先檢測(cè)空間是否夠用

• size != capacity，在待插入位置構(gòu)造新元素
• size == capacity，則進(jìn)行 vector 擴(kuò)容

void push_back() {// 檢測(cè)是否有可用空間// 空間足夠if (_M_finish != _M_end_of_storage) {construct(_M_finish);++_M_finish;}// 空間不夠，申請(qǐng)新的空間else_M_insert_aux(end());
}

空間足夠，在待插入位置構(gòu)造新元素

template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {new ((void*) __p) _T1(__value); // 定位new表達(dá)式：在 _p 位置上構(gòu)造一個(gè)對(duì)象
}template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {_Construct(__p, __value);
}

空間不夠，擴(kuò)容操作

template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{// 檢測(cè)是否有可用空間，該函數(shù)會(huì)被其他函數(shù)調(diào)用，所以需要再次檢查if (_M_finish != _M_end_of_storage) {construct(_M_finish, *(_M_finish - 1));++_M_finish;_Tp __x_copy = __x;copy_backward(__position, _M_finish - 2, _M_finish - 1);*__position = __x_copy;}else {const size_type __old_size = size();// 1、申請(qǐng)新空間：若舊空間大小為 0（初始化），則新空間大小為 1；否則，新空間為舊空間大小的 2 倍const size_type __len = __old_size != 0 ? 2 * __old_size : 1;iterator __new_start = _M_allocate(__len);iterator __new_finish = __new_start;// 2、將舊空間的元素復(fù)制到新空間// push_back 操作前半段用來(lái)存放舊數(shù)據(jù)，后半段用來(lái)存放新數(shù)據(jù)__STL_TRY {// 將舊數(shù)據(jù)拷貝到新空間__new_finish = uninitialized_copy(_M_start, __position, __new_start);// 為新元素設(shè)定初值construct(__new_finish, __x);// 調(diào)整水位++__new_finish;// 拷貝插入點(diǎn)后的舊數(shù)據(jù)（insert操作也可能導(dǎo)致擴(kuò)容）__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);}// 3、釋放舊空間__STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len)));destroy(begin(), end());_M_deallocate(_M_start, _M_end_of_storage - _M_start);_M_start = __new_start;_M_finish = __new_finish;_M_end_of_storage = __new_start + __len;}
}

* vector 迭代器失效

vector 支持隨機(jī)訪問(wèn)迭代器，普通指針天生具備。

typedef _Tp value_type;
typedef value_type* iterator;

插入元素

• 尾部插入：
  • size < capacity，尾迭代器失效
  • size == capacity，所有迭代器失效（動(dòng)態(tài)數(shù)組擴(kuò)容，重新分配空間）
• 中間插入：
  • size <= capacity，插入位置后的所有迭代器失效
  • size == capacity，所有迭代器失效（動(dòng)態(tài)數(shù)組擴(kuò)容，重新分配空間）

例：在遍歷容器元素的過(guò)程中，添加元素的操作很危險(xiǎn)。一旦發(fā)生擴(kuò)容操作，申請(qǐng)新的存儲(chǔ)空間，而迭代器仍指向原空間，導(dǎo)致越界。

刪除元素

• 尾部刪除：尾迭代器失效
• 中間刪除：刪除位置后的所有迭代器失效（元素前移）

例：刪除 vector 中值為 val 的所有元素。下面是容易導(dǎo)致錯(cuò)誤的做法

// 錯(cuò)誤寫(xiě)法：刪除后，元素前移，當(dāng)前刪除位置后的所有迭代器失效
for (auto it = numbers.begin(); it != numbers.end(); ++it) {if (val == *it) {numbers.erase(it);} 
}

錯(cuò)誤的原因在于：

• 刪除連續(xù)相同元素，刪除后元素前移，跳過(guò)第二個(gè)要?jiǎng)h除的元素
• 刪除最后一個(gè)元素，刪除后元素前移，迭代器指向 end() 的下一個(gè)位置，發(fā)生越界

正確的寫(xiě)法

for (auto it = vec.begin(); it != vec.end();) {  if (val == *it) { // 刪除元素后，不能執(zhí)行 ++操作it = vec.erase(it); } else {//未刪除元素，執(zhí)行++操作++it; } 
}

1.3、deque

• 雙端隊(duì)列
• 支持隨機(jī)訪問(wèn)迭代器
• 邏輯結(jié)構(gòu)，連續(xù)空間，雙端開(kāi)口，首尾插入移除元素 O(1)
• 物理離散，物理結(jié)構(gòu)由多個(gè)片段構(gòu)成，片段內(nèi)部連續(xù)，片段間不連續(xù)，片段的控制由中控器完成。

修改器接口

// 容器頭部插入元素
void push_front( const T& value );
// 容器頭部就地構(gòu)造元素
void emplace_front( Args&&... args );
// 移除容器頭部元素
void pop_front();

deque 結(jié)構(gòu)

物理結(jié)構(gòu)由多個(gè)片段構(gòu)成，片段內(nèi)部連續(xù)，片段之間不連續(xù)，片段的控制由中控器完成。

deque 組成

• 中控器：map 數(shù)組，其中的每個(gè)元素（node 節(jié)點(diǎn)）是一個(gè)指針，指向一塊較大的連續(xù)空間（緩沖區(qū)）。
• 緩沖區(qū)：buffer 緩沖區(qū)，實(shí)際存放數(shù)據(jù)的區(qū)域

源碼如下：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {protected: typedef pointer* _Map_pointer; // 二級(jí)指針static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }protected:using _Base::_M_map;		// 連續(xù)空間，每個(gè)元素是一個(gè)指針，指向一個(gè) bufferusing _Base::_M_map_size;	// 容納的指針數(shù)量using _Base::_M_start;	// 哨兵，指向 buffer 起始位置using _Base::_M_finish;	// 哨兵，指向 buffer 結(jié)束位置

緩沖區(qū) buffer 大小默認(rèn) 512

// 返回每個(gè)緩沖區(qū)可容納元素?cái)?shù)量
inline size_t __deque_buf_size(size_t __size) {return __size < 512 ? size_t(512 / __size) : size_t(1);
}

deque 迭代器

deque 邏輯連續(xù)，體現(xiàn)在 operator++ 和 operator–運(yùn)算。deque 迭代器需要判斷緩沖區(qū)位置，其次當(dāng)?shù)魈幱诰彌_區(qū)邊緣，為了能夠正確跳躍至上一個(gè)或下一個(gè)緩沖區(qū)，需要中控器的支持。

dueque 迭代器組成

• cur：指向 buffer 的當(dāng)前元素
• fast：哨兵，指向 buffer 起始位置
• last：哨兵，指向 buffer 結(jié)束位置
• node：指向中控器

源碼如下

template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {// 支持迭代器typedef random_access_iterator_tag iterator_category;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _Tp** _Map_pointer;typedef _Deque_iterator _Self;typedef _Tp** _Map_pointer; // 二級(jí)指針，指向 buffer_Tp* _M_cur;   // 指向 buffer 的當(dāng)前元素_Tp* _M_first; // 哨兵，指向 buffer 起始位置_Tp* _M_last;  // 哨兵，指向 buffer 結(jié)束位置_Map_pointer _M_node; // 中控器，二級(jí)指針...
};

deque 插入元素，首先判斷插入元素在 deque 的位置

  iterator insert(iterator position, const value_type& __x) {// 1、若插入位置是頭部if (position._M_cur == _M_start._M_cur) {push_front(__x);return _M_start;}// 2、若插入位置是尾部else if (position._M_cur == _M_finish._M_cur) {push_back(__x);iterator __tmp = _M_finish;--__tmp;return __tmp;}// 3、若插入位置在中間else {return _M_insert_aux(position, __x);}}

在 deque 中間位置插入，需要移動(dòng)元素，為了減少移動(dòng)元素次數(shù)，這里有一個(gè)巧妙的設(shè)計(jì)，判斷插入點(diǎn)前和插入點(diǎn)后的元素?cái)?shù)量，移動(dòng)元素?cái)?shù)量少的一端。

template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{// 插入點(diǎn)前元素個(gè)數(shù)difference_type __index = __pos - _M_start;value_type __x_copy = __x;// 比較插入點(diǎn)前的元素?cái)?shù)量與插入點(diǎn)后的元素?cái)?shù)量// 選擇元素較少的一端移動(dòng)元素// 1、若插入點(diǎn)前元素個(gè)數(shù)較少if (size_type(__index) < this->size() / 2) {// 頭端插入與第一個(gè)元素值相同的元素push_front(front());iterator __front1 = _M_start;++__front1;iterator __front2 = __front1;++__front2;__pos = _M_start + __index;iterator __pos1 = __pos;++__pos1;// 元素前移copy(__front2, __pos1, __front1);}// 2、若插入點(diǎn)后元素個(gè)數(shù)較少else {// 尾端插入與最后一個(gè)元素值相同的元素push_back(back());iterator __back1 = _M_finish;--__back1;iterator __back2 = __back1;--__back2;__pos = _M_start + __index;copy_backward(__pos, __back2, __back1);}// 插入元素*__pos = __x_copy;return __pos;
}

deque 模擬連續(xù)空間

deque 迭代器模擬連續(xù)空間

reference operator[](size_type __n) { return _M_start[difference_type(__n)]; }reference front() { return *_M_start; }reference back() {iterator __tmp = _M_finish;--__tmp;return *__tmp;
}size_type size() const { return _M_finish - _M_start; }bool empty() const { return _M_finish == _M_start; }

**operator ***

reference operator*() const { return *_M_cur; }

set_node

實(shí)現(xiàn) node 節(jié)點(diǎn) (buffer) 跳轉(zhuǎn)

void _M_set_node(_Map_pointer __new_node) {_M_node = __new_node;_M_first = *__new_node;_M_last = _M_first + difference_type(_S_buffer_size());
}

difference_type operator-

兩個(gè)迭代器的距離 = 兩個(gè)迭代器間的 buffers 總長(zhǎng)度 + 起始 buffer 長(zhǎng)度 + 末尾（當(dāng)前）buffer 長(zhǎng)度

• 兩個(gè)迭代器間的 buffers 長(zhǎng)度：bufferSize * 首尾 buffer 間的 buffers 數(shù)量，-1 是排除起始邊界 buffer
• 起始 buffer 的元素?cái)?shù)量：__x._M_last - __x._M_cur
• 末尾 buffer 的元素?cái)?shù)量：_M_cur - _M_first

difference_type operator-(const _Self& __x) const {// 兩個(gè)迭代器間的 buffers 總長(zhǎng)度 + 起始 buffer 長(zhǎng)度 + 末尾（當(dāng)前）buffer 長(zhǎng)度return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}

operator++

// 前置++
_Self& operator++() {++_M_cur;// 判斷是否到了 buffer 邊界（終點(diǎn)）if (_M_cur == _M_last) {// 跳轉(zhuǎn)至下一個(gè)node節(jié)點(diǎn)(buffer)的起點(diǎn)_M_set_node(_M_node + 1);_M_cur = _M_first;}return *this; 
}// 后置++
_Self operator++(int)  {_Self __tmp = *this;// 前置++實(shí)現(xiàn)后置++++*this;return __tmp;
}

operator–

// 前置--
_Self& operator--() {// 判斷是否到了 buffer 邊界（起點(diǎn)）if (_M_cur == _M_first) {// 跳轉(zhuǎn)至前一個(gè)node節(jié)點(diǎn)(buffer)的終點(diǎn)_M_set_node(_M_node - 1);_M_cur = _M_last;}--_M_cur;return *this;
}// 后置--
_Self operator--(int) {_Self __tmp = *this;// 前置--實(shí)現(xiàn)后置----*this;return __tmp;
}

operator+=

_Self& operator+=(difference_type __n) {difference_type __offset = __n + (_M_cur - _M_first);// 目標(biāo)位置在同一 buffer 內(nèi)if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))_M_cur += __n;// 目標(biāo)位置不在同一 buffer 內(nèi)else {difference_type __node_offset =__offset > 0 ? __offset / difference_type(_S_buffer_size()): -difference_type((-__offset - 1) / _S_buffer_size()) - 1;// 切換到目標(biāo) node 節(jié)點(diǎn)(buffer)_M_set_node(_M_node + __node_offset);// 切換至正確元素_M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));}return *this;}

operator+

_Self operator+(difference_type __n) const {_Self __tmp = *this;// 內(nèi)部調(diào)用 += 實(shí)現(xiàn)return __tmp += __n;
}

operator-=

內(nèi)部調(diào)用 +=，偏移量 -n

// 內(nèi)部調(diào)用 += -n
_Self& operator-=(difference_type __n) { return *this += -__n; }

operator-

內(nèi)部調(diào)用 -=

_Self operator-(difference_type __n) const {_Self __tmp = *this;return __tmp -= __n;
}

1.4、list

• list 雙向鏈表
• 支持雙向訪問(wèn)迭代器
• 物理結(jié)構(gòu)：循環(huán)雙向鏈表
• 邏輯結(jié)構(gòu)：雙向鏈表

list 特殊操作

// 1、從一個(gè)鏈表轉(zhuǎn)移元素到另一個(gè)鏈表
// 移動(dòng)一個(gè)鏈表到另一個(gè)鏈表的某個(gè)指定位置
void splice(const_iterator pos, list& other);
void splice(const_iterator pos, list&& other)
// 移動(dòng)一個(gè)鏈表中的某個(gè)元素到另一個(gè)鏈表的某個(gè)指定位置
void splice(const_iterator pos, list& other, const_iterator it)
void splice(const_iterator pos, list&& other, const_iterator it);
// 移動(dòng)一對(duì)迭代器范圍元素到另一個(gè)鏈表的某個(gè)指定位置
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last)
void splice(const_iterator pos, list&& other,const_iterator first, const_iterator last)// 2、對(duì)元素進(jìn)行排序
void sort();
template< class Compare > void sort(Compare comp);
template <typename T>
struct Compare {bool operator()(const T &a, const T &b) const {return a < b;}
}; // 3、合并兩個(gè)已排序的鏈表
void merge(list& other);// 4、將該鏈表的所有元素的順序反轉(zhuǎn)
void reverse();// 5、移除滿足特定標(biāo)準(zhǔn)的元素
void remove(const T& value);
void remove_if(UnaryPredicate p)// 6、刪除連續(xù)的重復(fù)元素
void unique();

list 結(jié)構(gòu)

list 通過(guò) node 指針可以實(shí)現(xiàn)遍歷循環(huán)鏈表，尾端留有空白節(jié)點(diǎn)，符合左閉右開(kāi)，成為 last 迭代器。

list node

• prev：指向前一個(gè)節(jié)點(diǎn)
• next：指向下一個(gè)節(jié)點(diǎn)
• data：存儲(chǔ)數(shù)據(jù)

struct _List_node_base {_List_node_base* _M_next;_List_node_base* _M_prev;
};template <class _Tp>
struct _List_node : public _List_node_base {_Tp _M_data;
};

list 迭代器

template<class _Tp, class _Ref, class _Ptr>
struct _List_iterator : public _List_iterator_base {// 1、typedeftypedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef _List_node<_Tp> _Node;// 2、運(yùn)算符重載...
};  

運(yùn)算符重載

reference operator*() const { return ((_Node*) _M_node)->_M_data; }pointer operator->() const { return &(operator*()); }void _M_incr() { _M_node = _M_node->_M_next; }
void _M_decr() { _M_node = _M_node->_M_prev; }_Self& operator++() { this->_M_incr();return *this;
}
_Self operator++(int) { _Self __tmp = *this;	// 先調(diào)用重載=，在調(diào)用重載*，因此這里調(diào)用的是拷貝構(gòu)造this->_M_incr();return __tmp;
}
_Self& operator--() { this->_M_decr();return *this;
}
_Self operator--(int) { _Self __tmp = *this;this->_M_decr();return __tmp;
}

2、關(guān)聯(lián)式容器

2.1、容器共性

容器共性

• 底層實(shí)現(xiàn)：紅黑樹(shù)，查找元素時(shí)間復(fù)雜度O(logN)
• 默認(rèn)情況下，按照關(guān)鍵字 key 升序排列
• 不能修改關(guān)鍵字 key 的值
• 支持雙向訪問(wèn)迭代器

面試：紅黑樹(shù)的特征

• 節(jié)點(diǎn)是紅色或黑色
• 根節(jié)點(diǎn)必須是黑色
• 葉子節(jié)點(diǎn)都是黑色
• 紅色節(jié)點(diǎn)的孩子節(jié)點(diǎn)必須是黑色的。黑色節(jié)點(diǎn)的孩子節(jié)點(diǎn)可以是黑色的。
• 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑的黑色節(jié)點(diǎn)的個(gè)數(shù)相同

擴(kuò)展：從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上不存在連續(xù)的紅色節(jié)點(diǎn)

• 最短路徑，節(jié)點(diǎn)都是黑色的；
• 最長(zhǎng)路徑，紅黑相間，2 * 黑色節(jié)點(diǎn)數(shù) - 1，紅色節(jié)點(diǎn)數(shù) = 黑色節(jié)點(diǎn)數(shù) - 1

2.2、容器特性

容器分類：set / map，key 唯一；multiset / multimap，key 不唯一。

set

• 存放 key 的有序集合
• 插入操作：insert，返回std::pair<iterator, bool>
• 查找操作，count / find
• 刪除操作：erase

map

• 存放鍵值對(duì)，pair<const key, value>?？梢允褂?code>std::pair或std::make_pair存放元素。
• 支持下標(biāo)訪問(wèn)運(yùn)算符，注意：查詢時(shí)對(duì)應(yīng)的 key 若不存在，會(huì)直接創(chuàng)建該 key 的記錄

3、無(wú)序關(guān)聯(lián)式容器

3.1、容器共性

• 底層實(shí)現(xiàn)：哈希表（桶 + 單鏈表）
• 存放的元素是無(wú)序的
• 針對(duì)自定義類型：必須自定義 std::hash和 std::equal_to

面試：hash table

• 哈希沖突：不同的 key，散列到相同的地址，即 H(key1) == H(key2)
• 哈希沖突解決方法：鏈地址法（STL）、開(kāi)放定址法、再散列法
• 裝載因子 = 實(shí)際裝載數(shù)據(jù)的長(zhǎng)度 n / 哈希表長(zhǎng) m，當(dāng)負(fù)載因子過(guò)大時(shí)，rehash

3.2、容器特性

• unordered_set

• unordered_map

• unordered_multiset

• unordered_multimap

例：自定義 point 類型，無(wú)法使用無(wú)序關(guān)聯(lián)式容器。

定義std::hash

• 自定義函數(shù)對(duì)象
• 擴(kuò)展std::hash的模板特化版本
• 函數(shù)調(diào)用運(yùn)算符設(shè)計(jì)成 const 版本

// 1、自定義哈希函數(shù)
// 1.1、擴(kuò)展 std::hash 的模板特化版本
namespace std {
template <>
// 1.2、自定義函數(shù)對(duì)象
struct hash<Point> {// 1.3、函數(shù)調(diào)用運(yùn)算符設(shè)計(jì)成 const 版本size_t operator()(const Point & rhs) const {// 自定義哈希函數(shù)return (rhs.getX() << 1) ^ (rhs.getY() << 1);}
};

定義 std::equal_to：重載函數(shù)調(diào)用運(yùn)算符，或重載等號(hào)運(yùn)算符，或使用模板特化

bool operator() (const T &lhs, const T &rhs) const {return lhs == rhs;
}bool operator== (const T &lhs, const T &rhs) {return lhs == rhs;
}namespace std {
template <>
struct equal_to<Point> {bool operator()(const Point &lhs, const Point &rhs) const {return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.}
};
}//end of namespace std