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就是Ktemplate <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为左孩子的parentelse{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为左孩子的parentelse{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为右孩子的parentelse{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为右孩子的parentelse{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;elsegrandparent->_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;elsegrandparent->_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用于传入红黑树存储的数据类型。//红黑树中存储的值不可以改变,应加上constrbtree::RBTree<K, const K, SetKeyOfT> _t;};
};