阅读量:0
1. 背景
关联式容器
STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义。树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。2.set的介绍
1. set是按照一定次序存储元素的容器 2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。 3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的。注意： 1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。 2. set中的元素不可以重复(因此可以使用set进行去重)。 3. 使用set的迭代器遍历set中的元素，可以得到有序序列，set中的元素默认按照小于来比较3. set的使用
1. set的模板参数列表
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。 Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理 2. set的构造
| 函数声明 | 功能介绍 |
| set (const Compare& comp = Compare(), const Allocator& = Allocator() ); | 构造空的set |
| set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); | 用[first, last)区 间中的元素构造 set |
| set ( const set<Key,Compare,Allocator>& x); | set的拷贝构造 |
3. set的迭代器
| 函数声明 | 功能介绍 |
| iterator begin() | 返回set中起始位置元素的迭代器 |
| iterator end() | 返回set中最后一个元素后面的迭代器 |
| const_iterator cbegin() const | 返回set中起始位置元素的const迭代器 |
| const_iterator cend() const | 返回set中最后一个元素后面的const迭代器 |
| reverse_iterator rbegin() | 返回set第一个元素的反向迭代器，即end |
| reverse_iterator rend() | 返回set最后一个元素下一个位置的反向迭代器，即rbegin |
| const_reverse_iterator crbegin() const | 返回set第一个元素的反向const迭代器，即cend |
| const_reverse_iterator crend() const | 返回set最后一个元素下一个位置的反向const迭代器，即crbegin |
4. set的容量
| 函数声明 | 功能介绍 |
| bool empty ( ) const | 检测set是否为空，空返回true，否则返回true |
| size_type size() const | 返回set中有效元素的个数 |
5. set修改操作
| 函数声明 | 功能介绍 |
| pair<iterator,bool> insert (const value_type& x ) | 在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经 存在，返回<x在set中的位置，false> |
void erase ( iterator position ) | 删除set中position位置上的元素 |
| size_type erase ( const key_type& x ) | 删除set中值为x的元素，返回删除的元素的个数 |
| void erase ( iterator first, iterator last ) | 删除set中[first, last)区间中的元素 |
| void swap (set<Key,Compare,Allocator>&st ); | 交换set中的元素 |
| void clear ( ) | 将set中的元素清空 |
| iterator find ( const key_type& x ) const | 返回set中值为x的元素的位置 |
| size_type count ( const key_type& x ) const | 返回set中值为x的元素的个数 |
4.set的模拟实现
首先我们要使用红黑树进行封装set即可，如下是RBTree.cpp的文件，有关红黑树的详细介绍，可以点击了解C++ 红黑树。
#include <iostream> #include <vector> using namespace std; namespace rbtree { enum Color { RED, BLACK, }; //当我们需要存储键值对，那么T就是pair<K, V> //当我们只存储key值，那么T就是K template <class T> struct RBTreeNode { //构造函数 RBTreeNode(T data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} //成员变量 RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; T _data;//节点数据 Color _col;//颜色 }; //实现迭代器 template<class T, class Ref, class Ptr> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; //构造函数 RBTreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &(_node->_data); } bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; } //前置++ Self& operator++() { //如果右子树不为空，说明该树未取完，要取右子树的最左结点 if (_node->_right) { Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; } //右子树为空，说明该树已经取完，要回到cur为左孩子的parent else { Node* cur = _node, * parent = cur->_parent; while (parent && parent->_right == cur) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } //后置++ Self operator++(int) { Self old = new Self(_node); //如果右子树不为空，说明该树未取完，要取右子树的最左结点 if (_node->_right) { Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; } //右子树为空，说明该树已经取完，要回到cur为左孩子的parent else { Node* cur = _node, * parent = cur->_parent; while (parent && parent->_right == cur) { cur = parent; parent = cur->_parent; } _node = parent; } return old; } //前置-- Self& operator--() { Self old = new Self(_node); //如果左子树不为空，说明该树未取完，要取左子树的最右结点 if (_node->_left) { Node* right = _node->_left; while (right->_right) { right = right->_right; } _node = right; } //左子树为空，说明该树已经取完，要回到cur为右孩子的parent else { Node* cur = _node, * parent = cur->_parent; while (parent && parent->_left == cur) { cur = parent; parent = cur->_parent; } _node = parent; } return old; } //后置-- Self operator--(int) { //如果左子树不为空，说明该树未取完，要取左子树的最右结点 if (_node->_left) { Node* right = _node->_left; while (right->_right) { right = right->_right; } _node = right; } //左子树为空，说明该树已经取完，要回到cur为右孩子的parent else { Node* cur = _node, * parent = cur->_parent; while (parent && parent->_left == cur) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } }; //前面的K用于传入key的类型，后面的T用于传入红黑树存储的数据类型。 keyOfT仿函数，取出T对象中的key,用于比较 template<class K, class T, class KeyOfT> class RBTree { typedef typename RBTreeNode<T> Node; typedef typename RBTreeIterator<T, T&, T*> iterator; public: //构造函数 RBTree() :_root(nullptr) {} //析构函数 ~RBTree() { Destroy(_root); _root = nullptr; } iterator begin() { Node* left = _root; while (left->_left) { left = left->_left; } return iterator(left); } iterator end() { return iterator(nullptr); } pair<iterator, bool> Insert(const T& data) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } //找位置插入 Node* cur = _root, * parent = _root; while (cur) { if (kot(data) < kot(cur->_data)) { parent = cur; cur = cur->_left; } else if (kot(data) > kot(cur->_data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); cur->_parent = parent; if (kot(data) < kot(parent->_data)) { parent->_left = cur; } else { parent->_right = cur; } Node* ret = cur; //检查颜色(当连续出现两个红色时需要调整) while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; if (parent == grandparent->_left) { Node* uncle = grandparent->_right; //如果uncle存在且为红，则将parent和uncle变黑，grandparent变红 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上检查 cur = grandparent; parent = cur->_parent; } //uncle不存在或者为黑 else { //将grandparent右旋，grandparent变为红,parent变为黑 if (cur == parent->_left) { RotateR(grandparent); grandparent->_col = RED; parent->_col = BLACK; } //将parent左旋，grandparent右旋，将cur变为黑，grandparent变为红 else { RotateL(parent); RotateR(grandparent); grandparent->_col = RED; cur->_col = BLACK; } //此时最上面的结点为黑，可以直接结束 break; } } else { Node* uncle = grandparent->_left; //如果uncle存在且为红，则将parent和uncle变黑，grandparent变红 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //继续向上检查 cur = grandparent; parent = cur->_parent; } //uncle不存在或者为黑 else { //将grandparent左旋，grandparent变为红,parent变为黑 if (cur == parent->_right) { RotateL(grandparent); grandparent->_col = RED; parent->_col = BLACK; } //将parent右旋，grandparent左旋，将cur变为黑，grandparent变为红 else { RotateR(parent); RotateL(grandparent); grandparent->_col = RED; cur->_col = BLACK; } break; } } } //把根节点变为黑 _root->_col = BLACK; return make_pair(iterator(ret), true); } bool _IsRBTree(Node* root, int count, int blacknum) { if (root == nullptr) { if (count != blacknum) { return false; } return true; } if (root->_col == BLACK) { count++; } return _IsRBTree(root->_left, count, blacknum) && _IsRBTree(root->_right, count, blacknum); } bool IsRBTree() { if (_root->_col == RED) { return false; } int blacknum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { blacknum++; } cur = cur->_left; } return _IsRBTree(_root, 0, blacknum); } void _InOrder(Node* root) { KeyOfT kot; if (root == nullptr) { return; } _InOrder(root->_left); cout << kot(root->_data) << " "; _InOrder(root->_right); } void InOrder() { _InOrder(_root); cout << endl; } private: void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } //左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* grandparent = parent->_parent; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; } else { if (grandparent->_left == parent) grandparent->_left = subR; else grandparent->_right = subR; } subR->_parent = grandparent; } //右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* grandparent = parent->_parent; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; } else { if (grandparent->_left == parent) grandparent->_left = subL; else grandparent->_right = subL; } subL->_parent = grandparent; } //左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); } //右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = parent->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); } Node* _root; }; };set.cpp文件如下
#include "RBTree.cpp" namespace lbk { template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename rbtree::RBTreeIterator<K, K&, K*> iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } void InOrder() { _t.InOrder(); } private: //前面的K用于传入key的类型，后面的T用于传入红黑树存储的数据类型。 //红黑树中存储的值不可以改变，应加上const rbtree::RBTree<K, const K, SetKeyOfT> _t; }; }; 