C++的STL库中把红黑树封装为了两个容器map与set
本博客将基于红黑树来实现map和set的封装
如果不了解红黑树，可见博客【C++高阶四】红黑树

1.将红黑树封装为泛型

我们现有的红黑树结构如下：

enum color//颜色枚举
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode//红黑树节点结构体
{
	RBTreeNode<K, V>* _left;//左指针
	RBTreeNode<K, V>* _right;//右指针
	RBTreeNode<K, V>* _parent;//父亲指针
	color _color;//颜色标记位
	pair<K, V> _kv;//KV值

	RBTreeNode(const pair<K, V>& KV)//初始化列表构造
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(KV)
		, _color(RED)
	{}
};


template<class K, class V>
class RBTree//红黑树
{
	typedef RBTreeNode<K, V> Node;//定义节点为Node
public:
	
private:
    Node* _root = nullptr;
};

这颗红黑树有一个问题，它的节点，存储的值是pair<K, V> _kv，是以键值对的形式来存储数据。但是在STL中，set只是存储key值的，只有map才存储键值对。如果我们要让红黑树可以同时作为map和set的底层，那么我们就要让这个红黑树的节点可以存储更多种类型的数据，所以要让节点RBTreeNode内部存储泛型：

template<class T>
struct RBTreeNode//红黑树节点结构体
{
	RBTreeNode<T>* _left;//左指针
	RBTreeNode<T>* _right;//右指针
	RBTreeNode<T>* _parent;//父亲指针
	color _color;//颜色标记位
	T _data;//data值

	RBTreeNode(const T& data)//初始化列表构造
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _color(RED)
	{}
};

把原先的模板template<class K, class V>换成了template<class T>，并把pair<K, V> _kv;改为了T _data

当我们需要存储键值对，那么T就是pair<K, V>
当我们只存储key值，那么T就是K

相应的，我们的RBTree本体也要修改一下：

template<class T>
class RBTree//红黑树
{
	typedef RBTreeNode<T> Node;//定义节点为Node
public:
	
private:
    Node* _root = nullptr;
};

现在尝试封装红黑树，写出map和set的基本框架：
my_set.h：

template<calss K>
class set
{
public:

private:
	RBTree<K> _tree;
}

my_map.h:

template<class K,class V>
class map
{
public:
private:
	RBTree<pair<K,V>> _tree;
}

经过这一层封装，我们的map和set的基本框架就有了
但是有一个小问题：map和set中的key值是不可以修改的，所以我们要给K的类型加上const修饰，不过要注意map中的value是可以修改的，所以不是给pair加上const修饰，而是只修饰K
my_set.h：

template<calss K>
class set
{
public:

private:
	RBTree<const K> _tree;
}

my_map.h:

template<class K,class V>
class map
{
public:
private:
	RBTree<pair<const K,V>> _tree;
}

2.泛型红黑树的修改和Find接口

原本红黑树的Find接口：

Node* Find(const K& key)
{
	Node* cur = _root;

	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if(cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

1. 第一个问题：我们已经把模板从template<class K, class V>换成了template<class T>，现在已经没有K这个类型了，意味着我们在给Find传参的时候，不可以直接传const K& key
   但我们在红黑树中查找一定是需要key的，所以我们要在模板参数中加一个K，也就是template<class K, class T>，前面的K用于传入key的类型，后面的T用于传入红黑树存储的数据类型

所以修改后的泛型红黑树框架如下：

template<class K ,class T>
class RBTree//红黑树
{
	typedef RBTreeNode<T> Node;//定义节点为Node
public:
	
private:
    Node* _root = nullptr;
};

2. 第二个问题：我们对红黑树的节点类RBTreeNode改造后，其内部存储的已经不是_kv了，而是_data，对于set而言，这个_data是没有first这个成员的，因此我们不能直接通过_kv.first这种方式来访问key；但是对于map而言，这个key还是_data中的成员变量first。也就是map和set取用key值的方式不同，我们无法统一处理

为了用统一的方式从_data中获得 map和set 各自的key，我们在红黑树的外部写仿函数，然后在仿函数的内部返回key值
所以给红黑树传入第三个模板参数KeyOfT：

template<class K ,class T，class KeyOfT>//KeyOfT是仿函数，用于得到T类对象中的key
class RBTree//红黑树
{
	typedef RBTreeNode<T> Node;//定义节点为Node
public:
	
private:
    Node* _root = nullptr;
};

修改完红黑树后，要分别给set和map类添加仿函数：
set：

template<calss K>
class set
{
public:
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	RBTree<K,K, SetKeyOfT> _tree;
}

map:

template<class K,class V>
class map
{
public:
	struct MapKeyOfT
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree<K,pair<const K, V>, MapKeyOfT> _tree;
}

再对Find函数进行改造：

bool Find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;

	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if(kot(cur->_data) > key)
		{
			cur = cur->_left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

3.迭代器

先搭建出迭代器iterator的基本框架：

template<class T,class Ptr,class Ref>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T,Ptr,Ref> Self;
	
	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{}
	
    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }

    bool operator==(const Self& s)
    {
        return _node == s._node;
    }
};

中序遍历可以通过递归按照“左子树 - 根 - 右子树”的顺序遍历，但迭代器该如何移动？

当迭代器指向蓝色方框位置时，说明迭代器就遍历到了这里，说明左子树已经遍历完成，遍历蓝色方框（根）后就要遍历右子树（找到右子树的最左节点）
蓝色方框移动：

当迭代器指向蓝色方框位置时，右子树为空，说明以蓝色框为根的整颗子树都遍历完毕了，也说明以紫色框为根的整颗子树都遍历完毕了（中序遍历，根节点一定在右子树前遍历完），那么我们就要向上移动蓝色方框，直到蓝色方框是其父节点的左子树时，将蓝色方框向上移动给其父节点
蓝色方框移动：

1. 如果迭代器当前节点的右子树不为空，遍历右子树（找到右子树的最左节点）
2. 如果迭代器当前节点的右子树为空，向上找第一个满足条件的节点：该节点其左子树是自己的前一个节点

代码如下：

Self& operator++()
{
	if (_node->_right)
	{
		Node* cur = _node->_right;
		while (cur->left)
		{
			cur = cur->_left;
		}

		_node = cur;
	}
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

operator–同理，只是规律相反：

1. 如果迭代器当前节点的左子树不为空，遍历左子树（找到左子树的最右节点）
2. 如果迭代器当前节点的左子树为空，向上找第一个满足条件的节点：该节点的右子树是自己的前一个节点

Self& operator--()
{
	if (_node->_left)
	{
		Node* cur = _node->_left;
		while (cur->right)
		{
			cur = cur->_right;
		}

		_node = cur;
	}
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

接下来我们要把迭代器的类封装进RBTree中，首先在RBTree中定义出iterator和const_iterator：

typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;

接着写出begin，end的iterator接口：

iterator begin()//中序遍历的第一个节点是整棵树的最左侧节点
{
	Node* cur = _root;
	while (cur->_left)
	{
		cur = cur->_left;
	}
	return iterator(cur);
}

iterator end()
{
    return iterator(nullptr);
}

const_iterator的begin和end同理：

const_iterator begin()const
{
	Node* cur = _root;
	while (cur && cur->_left)
	{
		cur = cur->_left;
	}
	return const_iterator(cur);
}

const_iterator end()const
{
	return const_iterator(nullptr);
}

我们再封装出map和set的迭代器，直接复用RBTree的迭代器接口即可：
mySet.h：

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

iterator begin()
{
	return _tree.begin();
}

iterator end()
{
	return _tree.end();
}

const_iterator begin()const
{
	return _tree.begin();
}

const_iterator end()const
{
	return _tree.end();
}

myMap.h：

typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::iterator  iterator;
typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::const_iterator  const_iterator;

iterator begin()
{
	return _tree.begin();
}

iterator end()
{
	return _tree.end();
}

const_iterator begin()const
{
	return _tree.begin();
}

const_iterator end()const
{
	return _tree.end();
}

在typedef的时候，由于RBTree是一个模板，我们到模板的域中访问了变量，而编译器无法区分模板中const_iterator的是变量还是类型，所以编译器会默认把它视为一个变量。如果它是一个类型，那么我们要明确告诉编译器，即通过typename 关键词，否则const_iterator会被识别为一个变量，而不是一个类型

由于STL中，find接口返回的是迭代器，所以我们还要把find的返回值改为迭代器，而不是使用布尔值返回

iterator Find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;

	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)
		{
			cur = cur->_left;
		}
		else
		{
			return iterator(cur);
		}
	}
	return end();
}

4.insert接口

在map和set中，insert的返回值比较特殊，其会返回pair<iterator, bool>

1. 如果插入值data原先存在，此时iterator指向原先的data节点，bool值返回false表示插入失败
2. 如果插入值data原先不存在，此时iterator指向新插入的data节点，bool值返回true表示插入成功

RBTree：

pair<Node*,bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_color = BLACK;//根节点是黑的
		return make_pair(_root,true);
	}

	Node* cur = _root;
	Node* parent = nullptr;
	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(cur, false);//相等就插入失败
		}
	}

	cur = new Node(data);
	Node* newnode = cur;//cur会不停变动，但最后返回的是新插入的那个节点
	//链接
	if (kot(parent->_data) < kot(data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	//此时new出来的节点的parent还指向空
	cur->_parent = parent;

	//新插入节点的父亲 存在 且是 红色,再调整
	while (parent && parent->_color == RED)
	{
		Node* grandfather = parent->_parent;

		if (parent == grandfather->_left)//新插入的节点其父节点在子树左侧
		{
			Node* uncle = grandfather->_right;

			if (uncle && uncle->_color == RED)//uncle存在且为红
			{
				uncle->_color = parent->_color = BLACK;
				grandfather->color = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			else//uncle不存在 或uncle是黑色
			{
				if (cur = parent->left)//grandfather和parent和cur是线性
				{
					RotateR(grandfather);
					grandfather->color = RED;
					parent->color = BLACK;
				}
				else//grandfather和parent和cur是折线型
				{
					RotateL(parent);
					RotateR(grandfather);

					cur->color = BLACK;
					grandfather->_color = RED;
				}

				break;//旋转后一定满足要求，跳出循环
			}
		}
		else//新插入的节点其父节点在子树右侧
		{
			Node* uncle = grandfather->_left;

			if (uncle && uncle->_color == RED)//uncle 存在 且为 红色
			{
				uncle->_color = parent->_color = BLACK;
				grandfather->color = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			else//uncle 不存在 或为 黑色
			{
				if (cur = parent->right)//grandfather和parent和cur是线性
				{
					RotateL(grandfather);
					grandfather->color = RED;
					parent->color = BLACK;
				}
				else//grandfather和parent和cur是折线型
				{
					RotateR(parent);
					RotateL(grandfather);

					cur->color = BLACK;
					grandfather->_color = RED;
				}

				break;//旋转后一定满足要求，跳出循环
			}
		}
	}
	_root->color = BLACK;
	return make_pair(newnode,true);
}

map：

pair<Node*, bool> insert(const pair<K, V>& kv)
{
	return _tree.Insert(kv);
}

set：

pair<Node*, bool> insert(const K& key)
{
	return _tree.Insert(key);
}

5.map的operator[]接口

map还重载了[]，这个重载比较复杂，但是非常有用，其声明：

V& operator[] (const K& key);

作用：接受一个key值，然后返回这个key对应的value的引用
等价于下列代码：

(*((this->insert(make_pair(key,V()))).first)).second

我们将以上代码拆解为四个部分解读
第一部分：

make_pair(key, V( ))

这是在利用参数k，通过make_pair()构造一个pair,这个pair的value使用了V( )（V就是value的类型）来调用默认构造,最后就得到了一个pair<key, value>

第二层：

this->insert( )

上一层我们构造了一个pair<key, value>，然后它作为参数传入到这个insert()中，相当于把刚刚构造的节点插入进map中。map的插入后，不论成功与否，都会返回一个pair<Node*, bool>，Node*用于指向key，bool用于标识插入是否成功。所以这一层最后得到了一个pair，分别存储了指向key的指针和bool值

第三层：

( ).first

上一层中我们得到了pair<Node*, bool>，这一层访问它的first，也就是访问了Node*，所以这一层得到了指向key值的地址

第四层：

(*( )).second

上一层拿到了指向key的地址，这一层先对地址解引用*( )，此时就得到了一个map的节点。而map的节点是pair<key, value>，所以我们解引用得到了一个pair，随后通过( ).second访问pair<key, value>的second，也就是value。最后返回这个value的引用

operator[]实现：

V& operator[](const K& key)
{
    pair<Node*,bool>& ret = insert(make_pair(key, V()));

    return ret.first->second;
}

operator[ ]的作用：

1. 插入一个key值：
   dict["left"];
   以上语句在dict中插入了一个key = "left"的节点，尽管其没有value
2. 插入一对key - value：
   dict["left"] = "左边";
   由于operator[ ]返回的是对应的引用，因此我们可以直接給返回值赋值，此时我们就插入了一个节点key = "left" ，value = "左边"
3. 修改key对应的value：
   dict[“coffe”] = "咖啡";
   如果我们的dict原先就存在key = "coffe"的节点，以上代码可以修改这个key的value值
4. 得到key对应的value：
   cout << dict["coffe"] << endl;
   由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出

由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出

6.总代码展示

RBTree.h:

enum color//颜色枚举
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode//红黑树节点结构体
{
	RBTreeNode<T>* _left;//左指针
	RBTreeNode<T>* _right;//右指针
	RBTreeNode<T>* _parent;//父亲指针
	color _color;//颜色标记位
	T _data;//data值

	RBTreeNode(const T& data)//初始化列表构造
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _color(RED)
	{}
};

template<class T, class Ptr, class Ref>
struct RBTreeIterator//红黑树迭代器
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ptr, Ref> Self;

	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur->right)
			{
				cur = cur->_right;
			}

			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}

public:
	Node* _node;
};

//set->RBTree<K,K,SetKeyOfT> _tree;
//map->RBTree<K,pair<const K,T>,MapKeyOfT> _tree;
template<class K, class T,class KeyOfT>
class RBTree//红黑树
{
	typedef RBTreeNode<T> Node;//定义节点为Node
public:
	typedef RBTreeIterator<T, T*, T&> iterator;
	typedef RBTreeIterator<T, const T*, const T&> const_iterator;

	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator begin()const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

	const_iterator end()const
	{
		return const_iterator(nullptr);
	}

	pair<Node*,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_color = BLACK;//根节点是黑的
			return make_pair(_root,true);
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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(cur, false);//相等就插入失败
			}
		}

		cur = new Node(data);
		Node* newnode = cur;//cur会不停变动，但最后返回的是新插入的那个节点
		//链接
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//此时new出来的节点的parent还指向空
		cur->_parent = parent;

		//新插入节点的父亲 存在 且是 红色,再调整
		while (parent && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;

			if (parent == grandfather->_left)//新插入的节点其父节点在子树左侧
			{
				Node* uncle = grandfather->_right;

				if (uncle && uncle->_color == RED)//uncle存在且为红
				{
					uncle->_color = parent->_color = BLACK;
					grandfather->color = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//uncle不存在 或uncle是黑色
				{
					if (cur = parent->left)//grandfather和parent和cur是线性
					{
						RotateR(grandfather);
						grandfather->color = RED;
						parent->color = BLACK;
					}
					else//grandfather和parent和cur是折线型
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->color = BLACK;
						grandfather->_color = RED;
					}

					break;//旋转后一定满足要求，跳出循环
				}
			}
			else//新插入的节点其父节点在子树右侧
			{
				Node* uncle = grandfather->_left;

				if (uncle && uncle->_color == RED)//uncle 存在 且为 红色
				{
					uncle->_color = parent->_color = BLACK;
					grandfather->color = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//uncle 不存在 或为 黑色
				{
					if (cur = parent->right)//grandfather和parent和cur是线性
					{
						RotateL(grandfather);
						grandfather->color = RED;
						parent->color = BLACK;
					}
					else//grandfather和parent和cur是折线型
					{
						RotateR(parent);
						RotateL(grandfather);

						cur->color = BLACK;
						grandfather->_color = RED;
					}

					break;//旋转后一定满足要求，跳出循环
				}
			}
		}
		_root->color = BLACK;
		return make_pair(newnode,true);
	}

	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_ + left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* parentparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left = parent)
			{
				parentparent->_left = subR;
			}
			else
			{
				parentparent->_right = subR;
			}
			subR->_parent = parentparent;
		}
		subR->_bf = parent->_bf = 0;
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		subL->_bf = parent->_bf = 0;
	}
	

	iterator Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;

		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return iterator(cur);
			}
		}
		return end();
	}
private:
	Node* _root = nullptr;
};

my_set.h:

#include "RBTree.h"

namespace lhc
{
	template<class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;


		iterator begin()
		{
			return _tree.begin();
		}

		iterator end()
		{
			return _tree.end();
		}

		const_iterator begin()const
		{
			return _tree.begin();
		}

		const_iterator end()const
		{
			return _tree.end();
		}

		pair<Node*, bool> insert(const K& key)
		{
			return _tree.Insert(key);
		}
	private:
		RBTree<K,K, SetKeyOfT> _tree;
	};
}

my_map.h:

#include "RBTree.h"

namespace lhc
{
	template<class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

		typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::iterator  iterator;
		typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::const_iterator  const_iterator;

		iterator begin()
		{
			return _tree.begin();
		}

		iterator end()
		{
			return _tree.end();
		}

		const_iterator begin()const
		{
			return _tree.begin();
		}

		const_iterator end()const
		{
			return _tree.end();
		}

		V& operator[](const K& key)
		{
			pair<Node*, bool>& ret = insert(make_pair(key, V()));

			return ret.first->second;
		}

		pair<Node*, bool> insert(const pair<K, V>& kv)
		{
			return _tree.Insert(kv);
		}
	private:

		RBTree<K,pair<const K, V>, MapKeyOfT> _tree;
	};
}