C++STL系列之set和map系列

前言

set和map都是關聯式容器，stl中樹形結構的有四種，set，map，multiset,multimap.本次主要是講他們的模擬實現和用法。

一、set、map、multiset、multimap

set

set的中文意思是集合，集合就說明不允許重復的元素
1…set是按照一定次序存儲元素的容器
2. 在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
3. 在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。
4. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代。
5. set在底層是用紅黑樹來實現的
6. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但在底層實際存放的是由<value, value>構成的鍵值對。這個后面模擬實現會講原因。
6. 使用set的迭代器遍歷set中的元素，可以得到有序序列
7. set中的元素默認按照小于來比較
8.set中的元素不可以重復，所以可以用set來去重
9.set中的迭代器是雙向迭代器
在這里插入圖片描述
T是key，Compare是仿函數來控制比較規則，Alloc是空間配置器
構造函數沒什么可說的，看一眼就懂了，這里的T有很大意義，后面模擬會提到。

重要函數

在這里插入圖片描述
畫橫線的就是比較重要的，有幾個注意事項：
1.關于insert，庫里面的insert是提供迭代器位置插入的，這樣做的目的有兩個：
1.與其他stl的insert保持一致，比如vector，list都提供迭代器插入
2.看下面的emplace_hint，emplace版本的構造一般是直接在容器內部構造，而emplace_hint對應的版本就是迭代器位置插入，hint是提示，若pos指向的位置恰好是元素應插入的位置或鄰近位置（如插入有序序列時，pos指向當前最后一個元素），紅黑樹可直接從pos開始驗證，跳過大部分查找步驟，插入效率接近 O (1)；?即使pos是錯誤提示，set 仍會按正常邏輯查找正確位置（退化至 O (log n)），但不會破壞元素的有序性
2.count就是計數，set里一定是一，這個接口是給multi版本使用的
3.lower_bound是大于等于元素的位置，upper_bound是大于元素的位置，這樣是為了維護迭代器左閉右開的性質

map

1… map是關聯容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。
2. 在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair:
typedef pair<const key, T> value_type;
3. 在內部，map中的元素總是按照鍵值key進行比較排序的。
4. map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
5. map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
6. map通常被實現為紅黑樹
在這里插入圖片描述
第二個參數給的是T而不是Value，這里也有很大意義，后面模擬實現會提到，其他和set一樣。

重要函數

map的重要接口和set類似，只多了比較重要的[] 和 at，都是通過key返回value的引用,他們的實現都得益于insert
在這里插入圖片描述
[]功能很強大，支持修改，插入、插入 + 修改

int main()
{map<int, int> mp;mp.insert({ 0,1 });mp[0] = 2;mp[2];mp[3] = 3;return 0;
}

[]的實現實際上是這樣,模擬實現還需要使用

V& operator[](const K& key)
{pair<K,V> pr = make_pair(key,V());iterator it = insert(pr).first;return *it.second;
}

multi系列

multi中文意思是多重，就意味著允許鍵值對冗余，也就是key可以重復。
count的作用是給他的，如果想使用可以重復的集合就用multiset
multimap中沒有提供[],因為key是可以重復的，那我該返回哪個呢？所以就不提供

二、模擬實現

set和map的使用都比較簡單，主要還是在模擬上。

框架

第一個問題就來了，一個是key模型，一個是key-value模型，難道要寫成兩份代碼嗎？之前list的迭代器提到了，其實庫里面很杜絕這種相似代碼寫兩份的，我們看看庫里是怎么解決的，其實上面提供了一點消息就是T
在這里插入圖片描述
都搞成了兩個參數<K,T>,其中T對于set就是K，對于map就是pair< K,V> ,這樣就可以通過一份代碼來實現set和map，先搭一個框架，節點存放的就是T類型了

template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color color;	T _kv;RBTreeNode(const T& p):_left(nullptr),_right(nullptr),_parent(nullptr),color(Color::RED),_kv(p){}
};
template<class K,class T>
class RBTree {typedef RBTreeNode<T> Node;private: Node* _root;
}

set里面放的就是RBTree<K, K> _t;
map里面就是RBTree<K,pair<K, V> _t;
到了插入，又出現新問題了，現在insert能跑了嗎？bool insert(const T& p)傳的是T啊，對于set倒是能比大小，map呢？pair有一套自己的比較大小的規則，但是和實際插入的規則不同啊，所以還需要一個參數KofT，取出T中的K
map:

struct mapKOfT {const K& operator()(const pair<K, V>& kv){return kv.first;}
};
private:RBTree<K,pair<K, V>,mapKOfT> _t;

set:

struct SetKOfT {const K& operator()(const K& kv){return kv;}
};
RBTree<K, K, SetKOfT> _t;

insert就會變成KOfT koft;涉及到比大小都用koft套一層

到目前為止，基本的框架已經完事了。下一步，迭代器

迭代器

先看庫里的迭代器怎么玩的
在這里插入圖片描述
set為什么要這么搞呢？因為set本身就不支持任何的修改，所以set這兩個都是const_iterator
但是對于map，map的value要支持修改，key不支持，所以不能搞成const，那他的key怎么防止修改呢？這個后面提，其實第一張圖片已經看到了。

主要還是++ – begin end怎么實現：
迭代器架子很好搭建，因為有了list的基礎

框架

template<class T,class Ref,class Ptr>
struct RBTree_Iterator
{typedef RBTreeNode<T> Node;typedef RBTree_Iterator<T, Ref, Ptr> Self;Node* _node;RBTree_Iterator(Node* node):_node(node){}Ref operator*(){return _node->_kv;}Ptr operator->(){return &_node->_kv;}Self& operator--(){}Self operator--(int){}Self operator++(int){}bool operator!=(const Self& ot)const{return _node != ot._node;}bool operator==(const Self& ot)const{return _node == ot._node;}
};

紅黑樹里面：

typedef RBTree_Iterator<T, T&, T*> iterator;
typedef RBTree_Iterator<T, const T&, const T*> const_iterator;

關于begin end ++ 和 - -

迭代器區間是左閉右開，begin就是最小元素，end呢，可以給空嗎？不可以，因為要支持–end()走到上一個元素，庫里的實現是搞了個類似哨兵位頭節點的東西。
這個頭節點，左孩子是最小節點也就是begin(),右孩子是最大節點，
頭節點的父親是根，根的父親是頭節點
在這里插入圖片描述
但是這樣維護起來比較麻煩，模擬實現只是為了了解底層，造不出更好的。所以這里不使用頭節點方式，end就按空節點來存放（但實際上不是這樣）

begin

begin其實就是找到最左節點返回就可以

iterator begin()
{Node* cur = _root;while (cur && cur->_left) cur = cur->_left;//考慮cur主要是考慮這是一顆空樹的問題return iterator(cur);
}

++ 和 - -

在這里插入圖片描述
上代碼：

Self& operator--()
{Node* nodeleft = _node->_left;if (nodeleft){while (nodeleft->_right) nodeleft = nodeleft->_right;_node = nodeleft;return *this;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;return *this;}}
Self operator--(int)
{Node* tmp(_node);--(*this);return RBTree_Iterator(tmp);
}
Self& operator++()
{Node* noderight = _node->_right;if (noderight){while (noderight->_left) noderight = noderight->_left;_node = noderight;}else{Node* cur = _node;Node* parent = cur->_parent;//父親有可能會為空，比如三角形結點的樹while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}//如果父親是空，說明這棵樹已經遍歷完全了//如果父親不是空，正常父親給Node_node = parent;}return *this;
}
Self operator++(int)
{Self tmp(_node);++(*this);return tmp;
}

此時基本上紅黑樹里面的迭代器基本完全了，實現map和set
注意：這里不加typename編譯不通過，原因：
類模板沒有被實例化，沒有生成具體代碼，編譯器不敢去里面找iterator
都沒有檢查代碼錯誤，取到的有可能是內部類或者靜態成員變量或者類型，加上typename就是告訴他是類型

//set:
typedef typename RBTree<K, K, SetKOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKOfT>::const_iterator const_iterator;//map:
typedef typename RBTree<K, pair<K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, mapKOfT>::const_iterator const_iterator;

對于set的begin、end 和 cbegin、cend接口，const版本正常寫，這里如果再寫一個非const版本的會報錯誤，因為既然是非const，this指針會調用紅黑樹里非const版本的begin，返回非const迭代器，此時無法傳給set里的const迭代器，所以只需要實現一個。

iterator begin()const
{return _t.begin();
}
iterator end()const
{return _t.end();
}

對于map的begin、end系列正常就可以了

iterator begin()
{return _t.begin();
}
iterator end()
{return _t.end();
}const_iterator begin()const
{return _t.begin();
}
const_iterator end()const
{return _t.end();
}

set、map防止修改

剛才已經講了，set防止修改的方式就是迭代器都是const迭代器
那map呢？map不想讓key修改，可以讓value修改，來看庫里的實現
在這里插入圖片描述
他把那個T里面的key都換成了const key，我們也這么實現。
有的人會有疑問？那我map<const int ,int> mp;不是有兩個const嗎？不會報錯嗎？
不會，C++對重復的const編譯器會進行優化成一個const。

typedef typename RBTree<K, pair<const K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, mapKOfT>::const_iterator const_iterator;
RBTree<K,pair<const K, V>,mapKOfT> _t;

這樣map就做到了不能修改K但是可以修改V的效果。

map的【】實現

上面說了，第一件事就是改insert的返回值，主要就是改return的地方，搞成一個pair就可以了

pair<iterator,bool> insert(const T& p)
{KOfT koft;if (_root == nullptr){_root = new Node(p);_root->color = Color::BLACK;return make_pair(iterator(_root),true);}else{Node* cur = _root;Node* parent = nullptr;while (cur){//用T了之后還有點問題 set是K，map是pair<k,v>怎么比？//再傳一個模板用來取出key即可if (koft(cur->_kv) < koft(p)){parent = cur;cur = cur->_right;}else if (koft(cur->_kv) > koft(p)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(p);Node* newnode = cur;if (koft(parent->_kv) < koft(p)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//這之前都是搜索樹的邏輯//while (parent && parent->color == Color::RED){Node* grandf = parent->_parent;if (grandf->_left == parent){Node* uncle = grandf->_right;//叔叔存在且為紅if (uncle && uncle->color == Color::RED){//判斷uncle->color = parent->color = Color::BLACK;grandf->color = Color::RED;//繼續判斷cur = grandf;parent = cur->_parent;}//叔叔不存在或者為黑else{//開旋//if (parent->_left == cur){RotateRight(grandf);parent->color = Color::BLACK;grandf->color = Color::RED;}else{//parent->right  是cur，grandf的左邊是parentRotateLeft(parent);RotateRight(grandf);cur->color = Color::BLACK;grandf->color = Color::RED;}}}//祖父的右邊是父親else{Node* uncle = grandf->_left;//uncle不存在 或者uncle為黑//uncle為紅if (uncle && uncle->color == Color::RED){parent->color = uncle->color = Color::BLACK;grandf->color = Color::RED;cur = grandf;parent = cur->_parent;}//uncle為黑或者不存在else{//旋轉//   grandf//uncle                parent//curif (cur == parent->_right){RotateLeft(grandf);parent->color = Color::BLACK;grandf->color = Color::RED;}else{RotateRight(parent);RotateLeft(grandf);cur->color = Color::BLACK;grandf->color = Color::RED;}}}}_root->color = Color::BLACK;return make_pair(iterator(newnode), true);}
}

改完之后就可以實現operator[]了，一句話看著不舒服可以分開

V& operator[](const K& key)
{return (*(insert(make_pair(key, V())).first)).second;
}

set的insert也需要跟著改。

改完之后跑了一段代碼，發現set的跑不過，map的可以，為什么呢？
在這里插入圖片描述
所以在迭代器里需要提供一個普通迭代器構造const迭代器，庫里面實現的很牛。

typedef RBTree_Iterator<T, T&, T*> iterator;
RBTree_Iterator(const iterator& it)//可以拿普通迭代器構造const迭代器:_node(it._node)
{}

搞了一個迭代器參數永遠是<T,T&,T*>無論外面傳進來是const迭代器還是普通迭代器這里都是普通迭代器。
對于下面這個構造函數：
1.如果是普通迭代器，相當于普通迭代器的拷貝構造
2.如果是const迭代器，相當于普通迭代器來構造const迭代器。這樣就能跑了。

另外，這一塊其實也是庫里一直都有的設計。任何的容器都支持const迭代器給非const迭代器

list<int> lt;
list<int>::const_iterator it = lt.begin();

三、完整代碼

個人gitee

總結

map和set的東西不少，需要好好練習和掌握。