目錄

• 關聯式容器
• 鍵值對
• 底層紅黑樹的改造
• • 仿函數
  • 紅黑樹的迭代器
  • 完整代碼
• set
• • set的文檔介紹
  • set的實現
• map
• • map的文檔介紹
  • map的實現
  • operator[]
  • 完整代碼
• multimap/multiset

---

關聯式容器

關聯式容器和序列式容器都是存儲數據的，但是唯一不同的地方就是關聯式容器存儲的是以<key, value>的鍵值對pair，并且關聯型容器如map和unordered_map等容器都是以紅黑樹和哈希桶等結構作為底層，在數據檢索和插入刪除的效率也比序列式容器高。

---

鍵值對

鍵值對其實就是一種用來表示映射關系的一種結構，結構中包含一個Key和一個value。key代表著索引的鍵值，而value代表著索引映射的數據，通過一個Key來映射一個value。例如我們可以通過身份證來找到一個人的信息，或者通過學號來找到一個學生。

下面是SGI版本的STL庫中實現的pair

template <class T1, class T2> struct pair {typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){} };

---

底層紅黑樹的改造

數據結構：紅黑樹的原理以及實現（C++）
紅黑樹的實現上一篇博客已經完成，但是如果想用來實現map和set，來需要進行改造

仿函數

因為我們需要使用一棵紅黑樹來實現KV模型的map和K模型的set，為了實現代碼復用，此時就需要用仿函數來解決這個問題，我們需要用到三個模板參數

template<class K, class T, class KOfV>

這里的K指的是key的類型，T是參數的類型。
對于KV模型的map來說，他的K即是key的類型，而T則是鍵值對pair<K, V>。
對于K模型的set來說，他的K即是key的類型，而T也是key的類型。這樣做的原因是保持代碼的一致性，方便我們進行代碼復用。

同時，我們還需要考慮如何從參數中獲取key，k模型的set還好說，因為它的參數T本身就是key，但是kv模型的map則存在了問題，因為它參數T是一個pair<K,V>的鍵值對，他的key是參數的first，此時兩邊就會存在差異。
甚至對于其他模型，還有其他的獲取Key的方法。
因為容器需要考慮的是泛用性，所以對于這種問題，可以增加一個仿函數作為模板參數，讓使用者自己提供從T中獲取key的方法即可。

例如map

struct MapKeyOfValue {const K& operator()(const std::pair<K, V>& kv){return kv.first;} };

set

struct SetKeyOfValue {const K & operator()(const K & key){return key;} };

---

紅黑樹的迭代器

紅黑樹的遍歷，其實也就是中序遍歷，那也就是說，迭代器的遍歷要基于中序。而中序的起點和終點分別是紅黑樹的最左子樹和最右子樹，那么問題來了，begin對應的是最左子樹，而end對應的是最右子樹的下一個位置，這個位置該怎么處理？按照迭代器的性質來說，最后一個位置一般都是不存儲任何數據的多余的空間，并且那塊空間是可以進行操作的，因為我們可能需要通過對end來進行–倒序遍歷，所以直接給nullptr也是行不通的。

所以我們可以設計一個這樣的結構，通過添加一個head節點來解決這個問題。

頭節點的左子樹指向最左節點，右子樹指向最右節點。同時，頭節點與根節點互相為對方的父節點。并且將頭結點設置為紅色，和根節點區分開來。

此時，begin為最左節點，end即為head節點。所以迭代器的遍歷就從最左節點出發，按照中序遍歷走完走到最右節點，然后當走到盡頭時，下一步就是走到end也就是head節點。而如果是從end–,就直接讓head訪問到他的右子樹即可。

template<class T, class Ptr, class Ref> class __RBTreeIterator {public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ptr, Ref> Self;__RBTreeIterator(Node* node) : _node(node){}Ref operator *(){return _node->_data;}//調用時其實調用的是->->，這里返回的是數據對象的指針，然后再從指針中取數據。編譯器優化所以只看到一個Ptr operator ->(){return &_node->_data;}//紅黑樹迭代器的++ --其實就是其在中序遍歷中的次序變化Self& operator++(){/*中序遍歷：先訪問所有節點的左子樹，接著訪問這些節點的右子樹。而++，其實就是其在中序遍歷的下一個位置1.如果當前節點的右子樹不為空，則說明當前節點的右子樹還沒遍歷完，下一個位置則是右子樹的最左節點。2.如果此時右子樹為空，則說明當前節點的所有子樹訪問完，但是當前節點也可能為其他樹的右子樹，所以一直往上，找到孩子為父親的左子樹的結點，那個父親的位置則是下一個位置*/if (_node->_right){Node* cur = _node->_right;//找到右子樹的最左節點while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父節點為空或者孩子節點為父節點的左子樹while (parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator++(int){Self temp(*this);++(*this);return temp;}/*而--，其實就是其在中序遍歷的上一個位置，思路和++差不多1.如果當前節點的左子樹不為空，則訪問左子樹的最右節點2.如果此時左子樹為空，則說明子樹的最左節點已經訪問，接著就往上查找，找到孩子為父親的右節點的位置，那個父親就是下一個位置*/Self& operator--(){if (_node->_parent->_parent == _node && _node->_color == RED){//如果此節點為頭結點，則說明--應該回到最右子樹的位置，也就是頭結點的右子樹，而因為頭結點和根節點形成閉環，所以當//_node->_parent->_parent == _node，并且color為紅時，說明為_head。_node = _node->_right;}else if (_node->_left){Node* cur = _node->_left;//找到左子樹的最右節點while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父節點為空或者孩子節點為父節點的右子樹while (parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator--(int){Self temp(*this);--(*this);return temp;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}private:Node* _node; };

完整代碼

按照上面說的對紅黑樹進行改造

#pragma once #include<iostream>namespace lee {enum Color{BLACK,RED,};template<class T>struct RBTreeNode{RBTreeNode(const T& data = T(), const Color& color = RED) : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}Node* _left;Node* _right;Node* _parent;T _data;Color _color;};template<class T, class Ptr, class Ref>class __RBTreeIterator{public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ptr, Ref> Self;__RBTreeIterator(Node* node) : _node(node){}Ref operator *(){return _node->_data;}//調用時其實調用的是->->，這里返回的是數據對象的指針，然后再從指針中取數據。編譯器優化所以只看到一個Ptr operator ->(){return &_node->_data;}//紅黑樹迭代器的++ --其實就是其在中序遍歷中的次序變化Self& operator++(){/*中序遍歷：先訪問所有節點的左子樹，接著訪問這些節點的右子樹。而++，其實就是其在中序遍歷的下一個位置1.如果當前節點的右子樹不為空，則說明當前節點的右子樹還沒遍歷完，下一個位置則是右子樹的最左節點。2.如果此時右子樹為空，則說明當前節點的所有子樹訪問完，但是當前節點也可能為其他樹的右子樹，所以一直往上，找到孩子為父親的左子樹的結點，那個父親的位置則是下一個位置*/if (_node->_right){Node* cur = _node->_right;//找到右子樹的最左節點while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父節點為空或者孩子節點為父節點的左子樹while (parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator++(int){Self temp(*this);++(*this);return temp;}/*而--，其實就是其在中序遍歷的上一個位置，思路和++差不多1.如果當前節點的左子樹不為空，則訪問左子樹的最右節點2.如果此時左子樹為空，則說明子樹的最左節點已經訪問，接著就往上查找，找到孩子為父親的右節點的位置，那個父親就是下一個位置*/Self& operator--(){if (_node->_parent->_parent == _node && _node->_color == RED){//如果此節點為頭結點，則說明--應該回到最右子樹的位置，也就是頭結點的右子樹，而因為頭結點和根節點形成閉環，所以當//_node->_parent->_parent == _node，并且color為紅時，說明為_head。_node = _node->_right;}else if (_node->_left){Node* cur = _node->_left;//找到左子樹的最右節點while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父節點為空或者孩子節點為父節點的右子樹while (parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator--(int){Self temp(*this);--(*this);return temp;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}private:Node* _node;};template<class K, class T, class KOfV>class RBTree{public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, T*, T&> iterator;typedef __RBTreeIterator<T, const T*, const T&> const_iterator;RBTree() : _head(new Node(T(), RED)){_head->_left = _head;_head->_right = _head;_head->_parent = _head;}~RBTree(){destory(_head->_parent);}//頭結點的左子樹即是begin()iterator begin() {return iterator(_head->_left);}//頭結點本身就是end()iterator end() {return iterator(_head);}const_iterator begin() const{return iterator(_head->_left);}const_iterator end() const{return iterator(_head);}Node* leftMax(){Node* cur = _head->_parent;while (cur && cur->_left){cur = cur->_left;}return cur;}Node* rightMax(){Node* cur = _head->_parent;while (cur && cur->_right){cur = cur->_right;}return cur;}void _InOrderTravel(Node* root) const{if (root == nullptr)return;_InOrderTravel(root->_left);std::cout << root->_data.first << ':' << root->_data.second << std::endl;_InOrderTravel(root->_right);}void InOrderTravel() const{_InOrderTravel(_head->_parent);}void destory(Node*& root){Node* node = root;if (!root)return;destory(node->_left);destory(node->_right);delete node;node = nullptr;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//如果subLR存在，則讓他的父節點指向parent。if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//兩種情況//如果parent為根節點，則讓subL成為新的根節點if (parent == _head->_parent){_head->_parent = subL;subL->_parent = _head;}//如果不是根節點，則改變subL與其祖父節點的指向關系else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _head->_parent){_head->_parent = subR;subR->_parent = _head;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}iterator Find(const T& data){//根據二叉搜索樹的性質，從根節點出發，比根節點大則查找右子樹，比根節點小則查找左子樹Node* cur = _head->_parent;KOfV kofv;while (cur){//比根節點大則查找右子樹if (koft(data) > kofv(cur->_data)){cur = cur->_right;}//比根節點小則查找左子樹else if (koft(data) < kofv(cur->_data)){cur = cur->_left;}//相同則返回else{return iterator(cur);}}//遍歷完則說明查找不到，返回falsereturn iterator(_head);}std::pair<iterator, bool> Insert(const T& data){KOfV kofv;//按照二叉搜索樹的規則先找到位置//創建根節點if (_head->_parent == _head){Node* root = new Node(data, BLACK);//形成環形結構root->_parent = _head;_head->_left = root;_head->_right = root;_head->_parent = root;return std::make_pair(iterator(_head->_parent), true);}Node* cur = _head->_parent;Node* parent = _head;while (cur){if (kofv(data) > kofv(cur->_data)){parent = cur;cur = cur->_right;}else if (kofv(data) < kofv(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair(iterator(cur), false);}}//新插入節點為紅色cur = new Node(data, RED);//保存插入的結點，因為后面會往上更新紅黑樹，所以cur可能會變化。Node* newNode = cur;//判斷插入位置if (kofv(cur->_data) > kofv(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新紅黑樹，如果父節點的顏色為黑，則說明滿足條件，不需要處理，如果為紅，則說明不滿足，需要處理。while (cur != _head->_parent->_parent && parent && parent->_color == RED){Node* ppNode = parent->_parent;//如果父節點為祖父的左子樹if (ppNode->_left == parent){//此時判斷叔叔節點的狀態，紅黑樹狀態取決于叔叔Node* uncle = ppNode->_right;//第一種情況，如果叔叔節點存在且為紅，則直接把父親和叔叔變黑，祖父節點邊紅即可。然后再從祖父的位置繼續往上調整if (uncle && uncle->_color == RED){//變色uncle->_color = parent->_color = BLACK;ppNode->_color = RED;//繼續往上cur = ppNode;parent = cur->_parent;}/*叔叔節點為黑或者不存在，此時有兩種情況情況二：cur為父節點的左子樹，即直線狀態。情況三：cur為父節點的右子樹，即折線狀態。情況二單旋一次后更改顏色即可完成對于情況三，如果將其進行一次旋轉后再稍微處理，就可以轉換成情況二*/else{//因為這里的雙旋和AVL不一樣，可以不用處理平衡因子，所以如果為折線則先旋轉處理后，將其轉換為直線處理即可。//第三種情況，折線狀態，轉換為直線狀態處理if (parent->_right == cur){RotateL(parent);//單旋后再交換節點，即可變成直線狀態。std::swap(parent, cur);}//處理第二種狀態RotateR(ppNode);parent->_color = BLACK;ppNode->_color = RED;//處理完成break;}}//如果父親為祖父的右子樹else{//此時叔叔為左子樹。Node* uncle = ppNode->_left;if (uncle && uncle->_color == RED){uncle->_color = parent->_color = BLACK;ppNode->_color = RED;cur = ppNode;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(parent);std::swap(cur, parent);}RotateL(ppNode);ppNode->_color = RED;parent->_color = BLACK;break;}}}//為了防止不小心把根節點改為紅色，最后手動改為黑色即可_head->_parent->_color = BLACK;//插入后更新頭結點的狀態。_head->_left = leftMax();_head->_right = rightMax();return std::make_pair(iterator(newNode), true);}/*判斷是否為紅黑樹，就是判斷其是否滿足紅黑樹的特性特性： 1.根節點必須為黑節點2.不存在連續的紅結點3.從某一節點出發到其所有的葉子節點，其中經過的黑色節點數量相等*/bool IsRBTree(){if (_head->_parent == nullptr){//空樹也是紅黑樹return true;}//違反性質1if (_head->_parent->_color != BLACK){return false;}//獲取從根節點出發的任意一條子路徑的黑色節點數，這里選取最左子樹。Node* cur = _head->_parent;size_t blackCount = 0;size_t count = 0;while (cur){if (cur->_color == BLACK){blackCount++;}cur = cur->_left;}//遞歸判斷其他路徑的黑色節點數return _IsRBTree(_head->_parent, count, blackCount);}bool _IsRBTree(Node* root, size_t count, const size_t blackCount){//此時說明已經走到葉子節點，判斷黑色節點數是否相等，不相等則違反性質3if (root == nullptr){if (count != blackCount){return false;}else{return true;}}//如果沒走完，就接著判斷其他情況//判斷性質2，如果存在連續的紅結點，則返回錯誤Node* parent = root->_parent;if (parent && root->_color == RED && parent->_color == RED){return false;}//如果當前節點為黑色，則記錄if (root->_color == BLACK){count++;}//接著遞歸判斷當前節點的所有路徑return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);}private://封裝一個頭結點，頭結點的父親指向根節點，左子樹指向begin()也就是最左節點，右子樹則為最右節點，這么做的意義是因為end(）要返回最右節點的下一個節點。//并且頭結點為紅色，用于區分根節點Node* _head;}; }

---

set

set的文檔介紹

set的文檔介紹

文檔介紹

set是按照一定次序存儲元素的容器

在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。set中的元素 不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。

在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。

set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直 接迭代。

set在底層是用紅黑樹實現的。

注意事項

與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但 在底層實際存放的是由<value, value>構成的鍵值對。

set中插入元素時，只需要插入value即可，不需要構造鍵值對。

set中的元素不可以重復(因此可以使用set進行去重)。

使用set的迭代器遍歷set中的元素，可以得到有序序列

set中的元素默認按照小于來比較

set中查找某個元素，時間復雜度為：O(logN)

set中的元素不允許修改(為什么?)

set中的底層使用紅黑樹實現

set的實現

#pragma once #include"RBTree.hpp"namespace lee {template<class K>class set{public:struct SetKeyOfValue{const K & operator()(const K & key){return key;}};typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}iterator find(const K& key){return _tree.Find(key);}std::pair<iterator, bool> insert(const K& key){return _tree.Insert(key);}private:RBTree<K, K, SetKeyOfValue> _tree;}; };

---

map

map的文檔介紹

map的文檔介紹

文檔介紹

map是關聯容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。

在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值 key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，
為其取別名稱為pair: typedef pair value_type;

在內部，map中的元素總是按照鍵值key進行比較排序的。

map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行 直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。

map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。

map通常被實現為紅黑樹

注意事項

map中的的元素是鍵值對

map中的key是唯一的，并且不能修改

默認按照小于的方式對key進行比較

map中的元素如果用迭代器去遍歷，可以得到一個有序的序列

map的底層為平衡搜索樹(紅黑樹)，查找效率比較高

支持[]操作符，operator[]中實際進行插入查找。

map的實現

operator[]

在map中，我們可以通過[]操作符來實現數據的查找和刪除，這是個十分便利的東西，那么他是如何實現的呢？

其實他底層調用的是Insert，而Insert的返回值是一對鍵值對pair，pair的成員是那個位置的迭代器還有插入是否成功的bool值，因為map的key是具有唯一性的，所以使用[]第一次訪問時，就相當于通過key來插入了一個默認value類型的數據，如果已經有了，就不插入而是相當于使用了查找的功能，然后通過返回的迭代器，來獲取到value的引用。

V& operator[](const K& key) {std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));return ret.first->second; }

完整代碼

#pragma once #include"RBTree.hpp"namespace lee {template<class K, class V>class map{public:struct MapKeyOfValue{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};//模板要在調用時才會初始化，所以這里要加上typename表明為類型名typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::iterator iterator;typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}iterator find(const K& key){return _tree.Find(std::make_pair(key, V()));}std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _tree.Insert(kv);}V& operator[](const K& key){std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));return ret.first->second;}private:RBTree<K, std::pair<K, V>, MapKeyOfValue> _tree;}; };

---

multimap/multiset

multi的意思就是多的意思，而multimap和multiset就是可以具有重復key值的map和set,實現起來也很簡單，和上面的代碼一樣，只需要改變插入時的判斷即可，因為原來的插入如果key值相同時，就直接返回false。

只需要在第一項中的>改為>=即可

while (cur) {if (kofv(data) >= kofv(cur->_data)){parent = cur;cur = cur->_right;}else if (kofv(data) < kofv(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair(iterator(cur), false);} } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的C++ STL : 模拟实现STL中的关联式容器map和set的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。