文章目录
一、源码及框架分析
SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件中。
map和set的实现结构框架核⼼部分截取出来如下：
//set.h
#ifndef __SGI_STL_SET_H
#define __SGI_STL_SET_H
#include <tree.h>
#include <stl_set.h>
//map.h
#ifndef __SGI_STL_MAP_H
#define __SGI_STL_MAP_H
#include <tree.h>
#include <stl_map.h>
//stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
}
//stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
//stl_tree.h
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
}
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
typedef __rb_tree_color_type color_type;
public:
//insert用的是第二个模板参数的左形参
pair<iterator,bool> insert_unique(const value_type& x);
//erase和find用第一个模板参数做形参
size_type erase(const key_type& x);
iterator find(const key_type& x);
protected:
size_type node_count; // keeps track of size of tree
link_type header;
}
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
通过下图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree实现key的搜索场景或者key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。
set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是pair<constkey，T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
要注意⼀下，源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。
rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板参数Key呢？尤其是set，两个模板参数是⼀样的，这是很多同学这时的⼀个疑问。要注意的是对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和ease的是Key对象。
二、模拟实现map和set
1、insert的实现
- 参考源码框架，map和set复⽤之前我们实现的红⿊树。
- 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的数据类型，我们使⽤T。
- 其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K，V>，那么insert内部进⾏插⼊逻辑⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较。
//Myset.h
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
//Mymap.h
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
//RBTree.h
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
pair<Iterator,bool> Insert(const T& data)
{
KeyOfT kot;//仿函数
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur,_root),false };
}
}
//...
2、iterator的实现
iterator实现思路分析：
iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。
迭代器++或- -的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。
set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可，
RBTree<K, const K, SetKeyOfT> _t;。map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可，
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
注意：
- begin()会返回整棵树最左节点。根据中序遍历，第一个访问的位置也就是最左的节点。
- end()会返回整棵树的最右节点的下一个节点，指向根节点的父节点，也就是nullptr。根据中序遍历，当访问到整棵树最右节点后说明整棵树已经全部访问完了，这里将根节点的父节点（nullptr）作为end()。
Iterator Begin() //整棵树最左节点
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
迭代器++的实现：
- 迭代器++时，如果it指向结点的右⼦树不为空，代表当前结点已经访问完了，下⼀个要访问的结点是右⼦树的最左节点（最小）。
- 迭代器++时，如果it指向结点的右⼦树为空，代表当前结点已经访问完了且当前结点所在的⼦树也访问完了，下一个要访问的节点是孩子是父亲左子树的那个祖先，因此要沿着当前结点到根的祖先路径向上找。
Self operator++()
{
//右不为空，下一个访问右子树最左节点（小）
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else //右为空，下一个访问孩子是父亲左的那个祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
//向上更新找到祖先
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
迭代器- -的实现：跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树。
- 特殊处理：- -end()是找整棵树的最右节点。
- 迭代器- -时，如果it指向结点的左⼦树不为空，下⼀个要访问的结点是左⼦树的最右节点（最大）。
- 迭代器++时，如果it指向结点的左⼦树为空，下一个要访问的节点是孩子是父亲右子树的那个祖先，因此要沿着当前结点到根的祖先路径向上找。
Self operator--()
{
//特殊处理 --end()，找整棵树的最右节点
if (_node == nullptr)
{
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left) //左子树不为空，找左子树的最右节点
{
Node* rightMost = _node->_left;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else //左子树为空，找孩子是父亲右子树的祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
3、map⽀持[ ]
- map要⽀持[ ]主要需要修改insert返回值⽀持，修改RBtree中的insert返回值为
pair<Iterator, bool> Insert(const T& dat)。然后重载[ ]运算符就可以实现了。
//Mymap.h
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });//尝试插入键值对{key, V()}
return ret.first->second;//返回对应值的引用
}
4、模拟实现的完整源代码
1）RBTree.h
#pragma once
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED) //初始化颜色为红色
{}
};
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}
Self operator++()
{
//右不为空，下一个访问右子树最左节点（小）
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else //右为空，下一个访问孩子是父亲左的那个祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
//向上更新找到祖先
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
//特殊处理 --end()，找整棵树的最右节点
if (_node == nullptr)
{
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left) //左子树不为空，找左子树的最右节点
{
Node* rightMost = _node->_left;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else //左子树为空，找孩子是父亲右子树的祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
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;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin() //整棵树最左节点
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
ConstIterator Begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur, _root);
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}
pair<Iterator,bool> Insert(const T& data)
{
//插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根节点为黑色
//return pair<Iterator, bool>(Iterator(_root, _root), true);
return { Iterator(_root,_root),true };
}
KeyOfT kot;//仿函数
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur,_root),false };
}
}
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;//只能插入红色节点
//链接父节点
if (kot(data) > kot(parent->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//处理颜色
//插入节点的父亲是红色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
//p u
Node* uncle = grandfather->_right;
//uncle存在且为红
if (uncle&& uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//向上更新
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或为存在为黑
else
{
if (cur == parent->_left)
{
// g
// p u
//c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //uncle在左边
{
// g
//u p
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
//u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
//u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//走到根了，根置为黑
_root->_col = BLACK;
return { Iterator(newnode,_root),true };
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (pParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
//原parent在父节点的左边
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (pParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
subR->_parent = pParent;
}
}
Node* Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (key > kot(cur->_data))
{
cur = cur->_right;
}
else if (key < kot(cur->_data))
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_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;
}
int _Size(Node* root)
{
if (root == nullptr)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
private:
Node* _root = nullptr;
};
2）Myset.h
#pragma once
#include"RBTree.h"
namespace zsy
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator; //typename关键字声明Iterator为 “类型”
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
}
3）Mymap.h
#pragma once
#include"RBTree.h"
namespace zsy
{
template<class K, class V>
class map
{
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>::ConstIterator 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();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });//尝试插入键值对{key, V()}
return ret.first->second;//返回对应值的引用
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}
4）Test.cpp
#include<iostream>
using namespace std;
#include"Myset.h"
#include"Mymap.h"
namespace zsy
{
//打印函数
void Print(const zsy::set<int>& s)
{
//反向遍历
zsy::set<int>::const_iterator it = s.end();
while (it != s.begin())
{
--it;
cout << *it << " ";
}
cout << endl;
}
void test1()
{
zsy::set<int> s;
s.insert(5);
s.insert(4);
s.insert(2);
s.insert(1);
s.insert(3);
zsy::set<int>::iterator it = s.begin();
//it+=10 //err set的key不允许修改
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//支持迭代器就支持范围for
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
Print(s);
}
void test2()
{
zsy::map<string, string> dict;
dict.insert({ "sort","排序" });
dict.insert({ "left","左边" });
dict.insert({ "right","右边" });
dict["left"] = "左边xxx";//修改
dict["insert"] = "插入";//插入
dict["string"];//插入
zsy::map<string, string>::iterator it = dict.begin();
//it->first+='x' //err key不能修改，value可以修改
it->second += 'y';
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
//支持迭代器就支持范围for
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
int main()
{
//zsy::test1();
zsy::test2();
return 0;
}
我们在这里测试一下模拟实现的set和map。
void test1() 运行结果：
void test2() 运行结果：
