set和map
- 前言
- 一、使用
- 1. set
- (1)、模板參數列表
- (2)、常見構造
- (3)、find和count
- (4)、insert和erase
- (5)、iterator
- (6)、lower_bound和upper_bound
- 2. multiset
- 3. map
- (1)、模板參數列表
- (2)、構造
- (3)、modifiers和operations
- (4)、operator[]
- 4. multimap
- 二、封裝
- RBTree
- 迭代器原理
- RBTree實現代碼
- map
- set
- 三、總結
前言
本文介紹的是樹型關聯式容器。
關聯式容器：用來存儲數據，存儲的是<key, value>結構的鍵值對，在檢索時效率更高。主要有這四種：map，set，multimap，multiset。
鍵值對：用來標識具有一一對應關系的結構，該結構一般包含兩個成員變量key和value，key表示鍵值，value表示與key對應的信息。
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){}
};
一、使用
1. set
(1)、模板參數列表
(2)、常見構造
void test_constructor()
{set<int> s1; //無參構造int arr[] = { 10,20,30,40,50 };set<int> s2(arr, arr + 5); //數組范圍構造set<int> s3(s2.begin(), s2.end()); //迭代器區間構造set<int> s4(s3); //拷貝構造
}
(3)、find和count
void test_find()
{set<int> s;s.insert(5);s.insert(10);s.insert(8);s.insert(2);//find return value: iterator(val is found)//otherwise set::end if (s.find(5) != s.end()){cout << "find:找到了" << endl; }//count return value:1 (val is found),or 0 otherwiseif (s.count(5)){cout << "count:找到了" << endl; }
}
(4)、insert和erase
void test_modify()
{//insert//去重+排序set<int> s;s.insert(10);s.insert(5);s.insert(6);s.insert(5);s.insert(5);s.insert(7);s.insert(2);for (auto e : s){cout << e << " "; //2 5 6 7 10}cout << endl;//迭代器set<int>::iterator sit;pair<set<int>::iterator, bool> ret; //接收插入返回值//pair<iterator, bool> insert(const value_type & val); insert參數列表ret = s.insert(1);if (ret.second == true)sit = ret.first;cout << *sit << endl; //1ret = s.insert(1);if (ret.second == false) sit = ret.first;cout << *sit << endl; //1//iterator insert(iterator position, const value_type & val); insert參數列表sit = s.insert(sit, 20);cout << *sit << endl; //20// template <class InputIterator>//void insert(InputIterator first, InputIterator last); insert參數列表int arr[] = { 0,10,15 }; // 10 already in set, not inserteds.insert(arr, arr + 3);for (auto e : s){cout << e << " "; //0 1 2 5 6 7 10 15 20}cout << endl;/////erase//void erase(iterator position); erase參數列表s.erase(sit); //*sit = 20//size_type erase(const value_type & val); erase參數列表int e_ret = s.erase(0);cout << e_ret << endl;for (auto e : s){cout << e << " "; //1 2 5 6 7 10 15}cout << endl;//void erase(iterator first, iterator last); erase參數列表s.erase(s.begin(), s.end());for (auto e : s){cout << e << " "; //empty}cout << endl;
}
(5)、iterator
void test_iteator()
{int arr[] = { 10,20,30,40,50 };set<int> s(arr, arr + 5);set<int>::iterator it = s.begin();set<int>::const_iterator cit = s.cbegin();set<int>::reverse_iterator rit = s.rbegin();set<int>::const_reverse_iterator crit = s.crbegin();while (it != s.end()){cout << *it << " "; //10 20 30 40 50it++;}cout << endl;while (cit != s.cend()){cout << *cit << " "; //10 20 30 40 50cit++;}cout << endl;while (rit != s.rend()){cout << *rit << " "; //50 40 30 20 10rit++;}cout << endl;while (crit != s.crend()){cout << *crit << " "; //50 40 30 20 10crit++;}cout << endl;
}
(6)、lower_bound和upper_bound
//iterator lower_bound(const value_type & val) const; lower_bound的聲明
//iterator upper_bound(const value_type & val) const; upper_bound的聲明
//pair<iterator, iterator> equal_range(const value_type& val) const; equal_range的聲明
void test_bound()
{set<int> s;set<int>::iterator itlow, itup;for (size_t i = 1; i < 10; i++){s.insert(i * 10); //10 20 30 40 50 60 70 80 90}//左閉右開[30,70)itlow = s.lower_bound(30);itup = s.upper_bound(60);cout << *itlow << endl; //30cout << *itup << endl; //70set<int>::iterator it = s.lower_bound(35);// s > 35cout << *it << endl; //40//*it = 50; //不能修改，保護鍵值s.erase(itlow, itup);for (auto e : s){cout << e << " "; //10 20 70 80 90}cout << endl;////equal_range - most_use multiset//pair<set<int>::const_iterator, set<int>::const_iterator> auto ret1 = s.equal_range(15);itlow = ret1.first;itup = ret1.second;//因為不存在15，所以itlow和itup是一段不存在的區間cout << *itlow << endl; //20 cout << *itup << endl; //20 左開右閉auto ret2 = s.equal_range(80);itlow = ret2.first;itup = ret2.second;//[80,90)cout << *itlow << endl; //80 cout << *itup << endl; //90auto ret = s.equal_range(90);itlow = ret.first;itup = ret.second;//程序直接崩潰，到最后了cout << *itlow << endl; //90 cout << *itup << endl; //end()
}
2. multiset
這里的演示就不和set一樣分開表示了，主要是multiset不去重
void test_multiset()
{//排序int arr[] = { 7, 7, 7, 3, 6, 5, 2, 3, 3, 3 };multiset<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));//不去重for (auto& e : s){cout << e << " ";}cout << endl;multiset<int>::iterator pos = s.find(3); //返回中序遍歷的第一個3while (pos != s.end()) //find失敗返回end(){//*pos = 10; //err 不能修改，保護鍵值cout << *pos << " ";++pos;}cout << endl;cout << s.count(3) << endl; //4個3pair<multiset<int>::iterator, multiset<int>::iterator> ret = s.equal_range(7);multiset<int>::iterator itlow = ret.first;multiset<int>::iterator itup = ret.second;// [itlow, itup)// [7,end()) s.equal_range(7);//cout << *itlow << endl;//cout << *itup << endl; //error *itup沒有值// [itlow, itup)// [5,5) s.equal_range(4); ret = s.equal_range(4);itlow = ret.first;itup = ret.second;cout << *itlow << endl;cout << *itup << endl; //oks.erase(itlow, itup); //沒有進行刪除 [5, 5)for (auto e : s){cout << e << " ";}cout << endl;
}
3. map
(1)、模板參數列表
(2)、構造
void test_constructor()
{map<string, string> dict;//"insert"和"插入"都分別有隱式類型轉換，const char* 轉成const string&//不能直接進行隱式類型轉換，原因：多參數pair<string, string> kv1("insert", "插入");dict.insert(kv1);dict.insert(pair<string, string>("sort", "排序")); //匿名對象//常用// C++98dict.insert(make_pair("string", "字符串"));// C++11 多參數的構造函數隱式類型轉換dict.insert({ "string", "字符串" }); //{}會自動調用pair的構造// 隱式類型的轉換 構造+拷貝構造（優化）string str1 = "hello";pair<string, string> kv2 = { "string", "字符串" };//const pair<string, string>& kv2 = { "string", "字符串" }; 引用一個臨時變量
}
(3)、modifiers和operations
void test_modifiers()
{map<string, string> dict;dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("insert", "插入"));dict.insert(make_pair("success", "成功"));//key已經有了就不會插入 //pair<iterator,bool> insert (const value_type& val); 插入的參數列表pair<map<string, string>::iterator, bool> ret = dict.insert(make_pair("insert", "xxx"));if (ret.second == false) {cout << "element already existed:";cout << ret.first->first << ":" << ret.first->second << endl;}//iterator insert (iterator position, const value_type& val); 插入的參數列表map<string, string>::iterator it = dict.begin();it = dict.insert(it, make_pair("begin", "開始")); // max efficiency insertingcout << it->first << ":" << it->second << endl;/*template <class InputIterator>void insert(InputIterator first, InputIterator last);*/ //插入的參數列表map<string, string> copymap;//iterator find (const key_type& k); //查找的參數列表，返回值是查找這個位置的迭代器，如果沒查找到，返回end()copymap.insert(dict.begin(), dict.find("success")); it = dict.begin();while (it != dict.end()){//it->first = "xxx"; //error//it->second = "sss"; //ok//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;int number = dict.erase("sucess");cout << number << endl;for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}
}
(4)、operator[]
注意key不存在，operator[]是插入，at是拋異常
void test_operator()
{string arr[] = { "西瓜", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };map<string, int> countMap;for (const auto& e : arr){auto it = countMap.find(e);if (it == countMap.end()){countMap.insert(make_pair(e, 1)); //首次插入}else{it->second++; //統計次數}}//pair<map<char, int>::iterator, bool>::iterator it = this->insert(make_pair(k,mapped_type()))//(*(it.first)).secondfor (const auto& e : arr){//查找e是否存在，如果不存在進行插入，如果存在，返回valuecountMap[e]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}
4. multimap
multimap和map的唯一不同，前者的key可以重復
二、封裝
set和map的封裝的底層結構使用的都是紅黑樹（這篇博客介紹了紅黑樹的旋轉），在STL中set底層實際存儲的數據是鍵值對< value, value >，這樣就可以調用同個紅黑樹。
RBTree
迭代器原理
雙向迭代器 -> 根據紅黑樹的特征:
- 迭代器++，只需要判斷當前位置的右側節點的情況
- 迭代器- -，只需要判斷當前位置的左側節點的情況
- 迭代器++
- 右孩子不為空，訪問右子樹的最左節點（最小節點）。
- 右孩子為空，下一個訪問的是孩子是父親左的祖先節點。
代碼實現：
Self& operator++()
{//右不為空if (_node->_right){//右子樹的最左節點（右子樹最小節點）Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else //右為空{Node* cur = _node;Node* parent = cur->_parent;//父節點為空，或者當前節點不是父節點的左孩子，循環繼續while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}//parent為空的情況和找到下一個節點的情況_node = parent;}return *this;
}
- 迭代器–
- 左孩子不為空，訪問左子樹的最右節點（最大節點）。
- 左孩子為空，下一個訪問的是孩子是父親右的祖先節點。
Self& operator--()
{//左孩子不為空if (_node->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else //左孩子為空{ //孩子是父親右的那個節點Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}//parent為空的情況和找到下一個節點的情況_node = parent;}return *this;
}
RBTree實現代碼
//節點的顏色
enum Color
{RED,BLACK
};//這里一個模板參數T就可以，這個T既是set的key，也是map的value
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _color;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(RED){}
};//迭代器
template<class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;//無論被實例化成什么，都是普通迭代器typedef __TreeIterator<T, T*, T&> Iterator;//這個類被實列化成const迭代器時，這個函數是一個構造，支持普通迭代器構造const迭代器//這個類被實列化成普通迭代器時，這個函數是一個拷貝構造__TreeIterator(const Iterator& it):_node(it._node){}Node* _node;//節點初始化__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator--(){if (_node->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else { //孩子是父親右的那個節點Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}//parent為空的情況和找到下一個節點的情況_node = parent;}return *this;}Self& operator++(){//右不為空if (_node->_right){//右子樹的最左節點（右子樹最小節點）Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else //右為空{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}//parent為空的情況和找到下一個節點的情況_node = parent;}return *this;}
};//set->RBTree<K, K, SetKeyOfT> _t;
//map->RBTree<K, pair<K, V>, MapKeyOfT> _t;//KeyOfT是上層傳下來的仿函數
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){//區分，這里和STL源碼中的結束方式不同，return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}const_iterator end() const{return iterator(nullptr);}//傳K的作用Node* Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}//沒找到，返回nullptrreturn nullptr;}//注意insert的返回值是一個鍵值對pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_color = BLACK;return make_pair(iterator(_root), true);}//尋找要鏈接新節點的位置Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}//插入節點 + 鏈接cur = new Node(data);cur->_color = RED;//保存節點，用于返回Node* newnode = cur;if (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//調整 這里parent是否為空，是為了下一次循環判斷// 如果parent->_color == BLACK也不用玩了while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u為紅if (uncle && uncle->_color == RED){parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//繼續向上調整cur = grandfather;parent = cur->_parent;}else //u不存在 或 存在且為黑{if (cur == parent->_left){// g// p//cRotateR(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{// g// p// c RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}//調整完之后，就不需要繼續改變了break;}}else //grandfather->_right == parent{Node* uncle = grandfather->_left;//u為紅if (uncle && uncle->_color == RED){parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//繼續向上調整cur = grandfather;parent = cur->_parent;}else //u不存在 或 存在且為黑{if (cur == parent->_right){//g// p// cRotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{//g// p//c RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}//調整完之后，就不需要繼續改變了break;}}}//根節點的顏色改成黑色_root->_color = BLACK;return make_pair(iterator(newnode), true);}//判斷該樹是不是紅黑樹bool IsBalance(){return _IsBalance(_root);}//計算紅黑樹的高度int Height(){return Height(_root);}private:int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool CheckColor(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark){return false;}return true;}//計算每條路徑的黑色節點if (root->_color == BLACK){++blacknum;}if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出現連續紅色節點" << endl;return false;}return CheckColor(root->_left, blacknum, benchmark)&& CheckColor(root->_right, blacknum, benchmark);}bool _IsBalance(Node* root){if (root == nullptr){return true;}if (root->_color != BLACK){return false;}//基準值 --> 用于比較別的路徑黑色節點個數int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)benchmark++;cur = cur->_left;}return CheckColor(root, 0, benchmark);}//旋轉//都是二叉樹的旋轉，所以和AVLTree的旋轉一樣，只不過這里沒有平衡因子void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;//重新鏈接parent->_right = curleft;if (curleft)curleft->_parent = parent;cur->_left = parent;//提前保存parent->_parent,可能是根節點，也可能是子樹的根節點Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}private:Node* _root = nullptr;
};
map
namespace kpl
{template<class K, class V>class map{//RBTree仿函數的主要作用在這里，set的封裝只是跟跑struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}
set
namespace kpl
{template<class K>class set{//仿函數struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;//set只保留一個const即可const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){//這里返回值的first的迭代器是普通迭代器，用普通迭代器接收pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);//使用普通迭代器構造一個const的迭代器，這里就體現出迭代器實現中的那個拷貝構造return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};
}
三、總結
set
- 插入的元素只需要value，不用鍵值對
- set中的元素不能重復（set可以去重）
- 單個元素的訪問速度比unordered_set慢
- 中序遍歷有序，使用其迭代器訪問也是有序
- 不允許修改，破壞結構
map
- map中的元素是鍵值對
- map中的key是唯一的，不能修改，但是value可以修改
- 中序遍歷有序，使用其迭代器訪問也是有序
- 支持operator[]
- 單個元素的訪問速度比unordered_set慢
multiset和multimap（區分set和map）
multiset的value可以重復，multimap的key也可以重復
: Blob Analysis（連通性解析）)
