目录
一，set和map结构框架
map与set都是关联式容器，底层都是用红黑树结构实现，而map与set实际上只是套了一层膜，实际功能都是依靠红黑树结构来实现，包括迭代器。
map容器中的元素类型可看成键值对pair型，set容器中的元素可只看成key类型。在底层结构中这里的传入结构对应是set<K> -> rb_tree<K, K> map<K, V> -> rb_tree<K, pair<const K, V>>，其中rb_tree对应就是红黑树结构，其中rb_tree第二个模板参数对应的是set或map数据类型（其它复杂的这里不做考虑，我们只需实现基础功能——插入，明白具体的逻辑即可）。
这里需注意的是，由于红黑树也是二叉搜索树，插入数据时需要进行比较，而map容器的顺序是只依靠key进行比较的，map中存储数据的数据数据类型pair的比较不是只依靠key比较，所以这里还需自定义比较，即向红黑树中插入数据时，只按照key的比较进行插入。
set结构封装
template<class K>
class set
{
struct Oft
{
const K& operator()(const K& data)
{
return data; //set只有一个数据，只传入本身的数据
}
};
//..........这里是实现封装的接口
private:
RBTree<K, const K, Oft> _s; //红黑树结构
};map结构封装
template <class K, class V>
class map
{
struct Oft
{
const K& operator()(const pair<K, V>& data)
{
return data.first; //map数据是键值对，只传入first
}
};
//..........这里是实现封装的接口
private:
RBTree<K, pair<const K, V>, Oft> _m; //红黑树结构
};
再次强调一点，map和set只是封装了红黑树结构以及功能，具体实现都在红黑树结构中，所以当创建一个map或set容器，实际创建的是一颗红黑树，所以map和set存储数据的成员_s和_m的类型是红黑树，又因为set容器中数据不能修改以及map中key不可修改，value可以修改，所以这里需要用const进行部分修饰。以上类Oft传入红黑树中只用于后面红黑树插入时按照具体数据比较，具体使用请看下面红黑树结构。
二，红黑树结构设计
红黑树的具体封装之前已详细讲解过了，这里实现set和map只需修改部分即可，不再重点说明红黑树的知识，若有不明白的请观察之前博客：http://t.csdnimg.cn/sXHKp
2-1，红黑树的结点封装
结点用于存储数据，具体设计结构如下：
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
Color _color;
T _data;RBTreeNode(const T& data = T())
: _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _color(RED)
, _data(data)
{ }
};
2-2，红黑树的迭代器封装
迭代器的封装这里实现const_iterator和iterator两种类型。迭代器的常用功能有 *，->，==，!=，++，--，这里只对这些功能进行封装实现。
由于const_iterator只是限制对容器里面的数据进行修改，其它功能与iterator相同，所以这里可直接使用模板来传递const型数据或非const型数据即可。
红黑树迭代器++和--是实现的是中序遍历的下一个结点和上一个结点。
//Ptr要么是const T&（const_iterator）,要么是T&（iterator）
//Ref要么是const T*（const_iterator）,要么是T*（iterator）
//这两种具体类型是根据使用的是const_iterator还是iterator
template <class T, class Ptr, class Ref>
struct RBTreeIterator
{
private:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ptr, Ref> Self;
public:
Node* _node;
RBTreeIterator(Node* node = nullptr)
:_node(node)
{ }
Self& operator++() //前置++。中序的下一个结点
{
assert(_node);
Node* cur = _node;
//1，右子树存在，找右子树的最左结点
if (_node->_right != nullptr)
{
cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
}
//2，右子树为空，逐渐往上层找cur是parent的左孩子
else
{
Node* parent = cur->_parent;
while (parent && cur != parent->_left)
{
cur = parent;
parent = cur->_parent;
}
cur = parent;
}
_node = cur;
return *this;
}
Self operator++(int) //后置++。中序的下一个结点
{
assert(_node);
Self s(*this); //注意: 这里只是实现返回原本迭代器，浅拷贝实现即可
Node* cur = _node;
if (_node->_right != nullptr)
{
cur = _node->_right;
while (cur->_left) cur = cur->_left;
}
else
{
Node* parent = cur->_parent;
while (parent && cur != parent->_left)
{
cur = parent;
parent = cur->_parent;
}
cur = parent;
}
_node = cur;
return s;
}
Self& operator--() //前置--。中序的上一个结点
{
assert(_node);
Node* cur = _node;
//1，左子树存在，找左子树的最右结点
if (_node->_left)
{
cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
}
//2，左子树为空，逐渐往上层找cur是parent的右孩子
else
{
Node* parent = cur->_parent;
while (parent && cur != parent->_right)
{
cur = parent;
parent = cur->_parent;
}
cur = parent;
}
_node = cur;
return *this;
}
Self operator--(int) //后置--。中序的上一个结点
{
assert(_node);
Self s(*this);
Node* cur = _node;
if (_node->_left)
{
cur = _node->_left;
while (cur->_right) cur = cur->_right;
}
else
{
Node* parent = cur->_parent;
while (parent && cur != parent->_right)
{
cur = parent;
parent = cur->_parent;
}
cur = parent;
}
_node = cur;
return s;
}Ptr operator*()
{
return _node->_data;
}
Ref operator->() //实现的是“->”符号的左边是右边的地址
{
return &_node->_data;
}bool operator==(const Self& it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
};
2-2，红黑树的封装
这里我们封装插入算法和查找算法。其中插入算法中，由于旋转算法只针对于结点，所以这里的旋转跟红黑树结构里面的旋转一样。但插入数据和返回值需要做出调整。
当插入数据进行数据结点数据间的比较时，这里需要根据以上传入的Oft类型进行比较（set按自己的数据比较，map只按照key比较）。若使用红黑树版本的比较算法，set由于只存储了key数据，所以对此无影响，但是map存储的是键值对，底层键值对的比较在key相同下会比较value，这里不符合预期。
map和set底层结构插入算法的返回值都是pair<iterator, bool>，这里的返回值需做出调整。
查找算法这里只对key进行查找。
template <class K, class T, class Oft>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;RBTree() : _root(nullptr) { }
iterator begin() //左子树的最左孩子
{
assert(_root);
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return cur;
}
iterator end() //右子树的最右孩子的下一个位置，即空
{
return iterator(nullptr);
}
const_iterator begin() const
{
return begin();
}
const_iterator end() const
{
return end();
}//查找。若是map，只对key进行查找
iterator Find(const K& data)
{
assert(_root);
Oft kv;
Node* cur = _root;
while (cur)
{
if (kv(cur->_data) < data)
{
cur = cur->_right;
}
else if (kv(cur->_data) > data)
{
cur = cur->_left;
}
else
return cur;
}
return nullptr;
}
//make_pair返回值是pair,这里只需返回make_pair(插入结点迭代器，true或false)
pair<iterator, bool> Insert(const T& data) //插入
{
if (_root == nullptr) {
_root = new Node(data);
_root->_color = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Oft kv;
Node* parent = _root->_parent;
while (cur) {
if (kv(cur->_data) > kv(data)) {
parent = cur;
cur = cur->_left;
}
else if (kv(cur->_data) < kv(data)) {
parent = cur;
cur = cur->_right;
}
else return make_pair(iterator(cur), false);
}
if (kv(parent->_data) > kv(data)) {
parent->_left = new Node(data);
cur = parent->_left;
}
else {
parent->_right = new Node(data);
cur = parent->_right;
}
cur->_parent = parent;
Node* node = cur; //注意：下面的新插入结点cur会指向其它结点，这里需保存一下
while (parent && parent->_color == RED) {
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) {
Node* uncle = grandparent->_right;
if (uncle && uncle->_color == RED) {
grandparent->_color = RED;
parent->_color = uncle->_color = BLACK;
cur = grandparent;
parent = cur->_parent;
}
else {
if (cur == parent->_left) {
RotateR(grandparent);
grandparent->_color = RED;
parent->_color = BLACK;
}
else {
RotateLR(grandparent);
grandparent->_color = RED;
cur->_color = BLACK;
}
break;
}
}
else {
Node* uncle = grandparent->_left;
if (uncle && uncle->_color == RED) {
grandparent->_color = RED;
parent->_color = uncle->_color = BLACK;
cur = grandparent;
parent = cur->_parent;
}
else {
if (cur == parent->_left) {
RotateRL(grandparent);
grandparent->_color = RED;
cur->_color = BLACK;
}
else {
RotateL(grandparent);
grandparent->_color = RED;
parent->_color = BLACK;
}
break;
}
}
}
_root->_color = BLACK;
return make_pair(iterator(node), true);
}//旋转算法
void RotateL(Node* parent) //左单旋
{
Node* cur = parent->_right;
Node* curL = cur->_left;
Node* pparent = parent->_parent;
parent->_right = curL;
if (curL) curL->_parent = parent;
if (parent == _root) {
_root = cur;
_root->_parent = nullptr;
}
else {
if (pparent->_left == parent) {
pparent->_left = cur;
cur->_parent = pparent;
}
else {
pparent->_right = cur;
cur->_parent = pparent;
}
}
cur->_left = parent;
parent->_parent = cur;
}
void RotateR(Node* parent) //右单旋
{
Node* cur = parent->_left;
Node* curR = cur->_right;
Node* pparent = parent->_parent;
parent->_left = curR;
if (curR) curR->_parent = parent;
if (parent == _root) {
_root = cur;
_root->_parent = nullptr;
}
else {
if (pparent->_left == parent) {
pparent->_left = cur;
cur->_parent = pparent;
}
else {
pparent->_right = cur;
cur->_parent = pparent;
}
}
cur->_right = parent;
parent->_parent = cur;
}
void RotateLR(Node* parent) //左右旋
{
RotateL(parent->_left);
RotateR(parent);
}
void RotateRL(Node* parent) //右左旋
{
RotateR(parent->_right);
RotateL(parent);
}
private:
Node* _root;
};
三，set与map的封装
set与map的接口总封装只需调用红黑树RBTree相应的接口即可，可以说这里只是套了一层膜。这里重点说明map容器对“ [] ”的重载，即插入key和value，返回value，若不存在value时将默认构造。
//set封装
template<class K>
class set
{
struct Oft
{
const K& operator()(const K& data)
{
return data;
}
};
public:
typedef RBTreeNode<const K> Node;
typedef typename RBTree<K, const K, Oft>::iterator iterator;
typedef typename RBTree<K, const K, Oft>::const_iterator const_iterator;iterator begin()
{
return _s.begin();
}
iterator end()
{
return _s.end();
}
const_iterator begin() const
{
return _s.begin();
}
const_iterator end() const
{
return _s.end();
}iterator find(const K& k)
{
return _s.Find(k);
}pair<iterator, bool> insert(const K& data)
{
return _s.Insert(data);
}
private:
RBTree<K, const K, Oft> _s;
};//map封装
template <class K, class V>
class map
{
struct Oft
{
const K& operator()(const pair<K, V>& data)
{
return data.first;
}
};
public:
typedef RBTreeNode<pair<const K, V>> Node;
typedef typename RBTree<K, pair<const K, V>, Oft>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, Oft>::const_iterator const_iterator;iterator begin()
{
return _m.begin();
}
iterator end()
{
return _m.end();
}
const_iterator begin() const
{
return _m.begin();
}
const_iterator end() const
{
return _m.end();
}pair<iterator, bool> insert(const pair<K, V>& data)
{
return _m.Insert(data);
}iterator find(const K& data)
{
return _m.Find(data);
}V& operator[](const K& key) //这里需注意value是否存在
{
_m.Insert(make_pair(key, V()));
iterator it = find(key);
return it->second;
}
private:
RBTree<K, pair<const K, V>, Oft> _m;
};
下面我们认识一下typename关键字。在模板编程中，当模板参数是一个类型，而你又想在模板内部使用这个类型来定义另一个类型时，你需要使用 typename 关键字来告诉编译器这个标识符是一个类型名，而不是一个静态成员变量。如：上面typedef typename RBTree<K, pair<const K, V>, Oft>::iterator iterator; 因为编译器在解析模板时不知道 RBTree<K, pair<const K, V>, Oft> 的确切类型，所以不确定 RBTree<K, pair<const K, V>, Oft>::iterator iterator 是一个类型还是一个静态成员。使用 typename 关键字告诉编译器这是一个类型。总结来说，在模板编程中，当你定义的类型别名依赖于模板参数，并且这个别名是一个类型时，你需要使用 typename 关键字。在其他情况下，使用 typedef 定义类型别名时不需要 typename。