网站和微网站,机器人软件开发平台,网站界面排版好看,原生态旅游网站开发需求分析1. map 和 set 的介绍
⭐map 与 set 分别是STL中的两种序列式容器;
它们是一种树形数据结构的容器#xff0c;且其的底层构造为一棵红黑树;
而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能
⭐当然也…1. map 和 set 的介绍
⭐map 与 set 分别是STL中的两种序列式容器;
它们是一种树形数据结构的容器且其的底层构造为一棵红黑树;
而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能
⭐当然也提到了红黑树与AVL树的区别
1、AVL树保证了严格的平衡其树高不会很高使其查找效率较高但是就是因为要不断旋转保证平衡因此 当插入和删除时较多的旋转会影响效率
2、红黑树不用保证严格的平衡查找的时间复杂度为 O(logN) 级别和AVL树在 插入和删除 中只需要较少的旋转因此 插入和删除 效率较高
综合考虑 map 和 set 使用 红黑树作为底层容器 2. map 和 set 的结构 在 map 与 set 的使用过程中由于 set 容器的底层树节点存储着数据为 key T 类型
而 map 的底层树节点存储着数据为一个键值对 key/value; pair类型
所以可能会联想到在STL中的这两个容器是否使用的是不同的红黑树
而实际在 STL 的源码中可以看到对于这两个容器而言所使用的是同一个红黑树即调用同一棵红黑树并且利用泛型的特性来控制两个容器中所使用的对应的参数; 那么既然是同一棵红黑树应该如何对这棵树进行修改 使得该树能够同时兼容 map 的 key/value 键值对数据存储 和 set 的 key 数据存储 呢 3、对红黑树的进一步修改
在我们的上一章节 讲解了红黑树的各种基础构造本章对红黑树进一步修改融入 迭代器 以及 泛型化使其更加适配 map 与 set 1修改一将节点数据类型换成 T 泛型的思想 将节点中数据变量 换成 类型T 当 T key 类型时该节点对应 set 容器 当 T pairkey, value 类型时该节点对应 map 容器 这样就初步实现同一节点类模板可以对应 多种数据类型适应 set 和 map templateclass T
struct RBTreeNode
{T _data; // 泛型化思想_data 可以是 Key 类型也可以是 pairKey, Value 类型// .....
};先前 set 和 map 要设计两套 红黑树类
为了适应 set
templateclass Key
class RBTree
{}
为了适应 map
templateclass Key, class Value
class RBTree
{} 现在节点类泛型化了红黑树类也要对应修改
templateclass T
class RBTree
{} 2修改二应用仿函数 修改 插入函数 insert 内部比较逻辑 ⭐之前没修改时为了适应 set 和 map 要设计两种传参类型 为了适应 set bool insert(const K key)
{} 为了适应 map bool insert(const pairK, V kv)
{} ⭐insert 函数内部比较键值大小的部分 也有两套设计 当 T key 时对应 setinsert 函数内部比较键值大小的部分直接比较键值 key if (cur-_key key) {// .....
} 当 T key/value 时对应 mapinsert 函数内部比较键值大小的部分还要指定键值对的 first if (cur-_kv.first kv.first) {// .....
} 现在 节点数据泛型为 T函数 insert 传参类型和内部某些比较逻辑都需要做调整 ⭐ 修改传参类型
bool insert(const T data)
{} ⭐内部某些比较逻辑使用仿函数
因为我们那里的就是要用 键值 key 比较因此 set 可以直接用节点数据 key 比较而 map 需要用 节点数据pair的first 比较这里就有区别因此需要仿函数“统一化”
1set 使用仿函数时当操作数类型为 K 类型则直接识别使用 set 的仿函数 set_KeyOfT 中的 operator() 函数返回 key即返回一个键值
templateclass K
class set
{// set 中的仿函数struct set_KeyOfT {const K operator()(const K key) {return key;}};// ....... 其他补充
private:RBTreeK, set_KeyOfT _tree;
};
2map 当操作数类型为 pairkey, value 键值对类型则直接识别为 map 的仿函数 map_KeyOfT 中的 operator() 函数返回 pairkey, value 的 first 即也返回一个 键值)
templateclass K, class V
class map
{struct map_KeyOfT {const K operator()(const pairK, V kv) {return kv.first;}};// ....... 其他补充private:RBTreepairconst K, V, map_KeyOfT _tree;
}; 在 红黑树类模板中添加 仿函数的类型class KeyOfT
templateclass T, class KeyOfT
class RBTree
{} 仿函数的应用
KeyOfT kot; // 创建一个仿函数类对象
if (kot(cur-_data) kot(data)) // data 可能是 key类型可能是 pairkey, value 类型
// 使用仿函数调用operator() 自动识别 data 的类型放回 键值 key 进行比较 3修改三给 红黑树类模板 再加一个 类型 class K 我们实现 find 和 insert 函数时insert 函数参数类型是 T 表示 data 可以是 key 类型也可以是 pair key, value 类型
但是 find 函数参数可以是 T 类型吗
不可以无论是 map or setfind 函数都是查找 键值 key固定要用 key 若 find 的参数是 T 类型当 T key 时直接可以使用当 T pair key, value 时就不能直接使用 T 来查找就要使用 T.first就使得两个类型造就两种使用逻辑
因此 我们可以额外传一个 键值既然是固定要用的就多传一个
templateclass K, class T, class KeyOfT
class RBTree
{} 至此我们红黑树类模板中 第一个参数 K 用于传键值key第二个参数 T 为泛型用于 接收两种类型兼容set 和 map 两种第三个参数为 仿函数 4修改四插入函数 insert 的 返回值 改为 pair 类型
在STL中,无论是 map 容器还是 set 容器其插入函数Insert()函数的返回值都是为一个pairiterator,bool
1、若是插入成功则返回新插入节点的迭代器位置 与 true (迭代器的实现将在下文中提到)
2、若是插入失败则返回与需要插入的数据相同的节点位置 与 false 例如 STL 库中的 map 的 insert 函数源码 pairiterator,bool insert (const value_type val); value_type 就是 pair K, V pair 是一个类模板 我们的 插入函数 返回值修改为
pairiterator, bool insert(const T data) 4. 迭代器
因为需要将 红黑树封装进容器 map 和 set 中容器会涉及各种操作需要迭代器
因此我们先实现 红黑树的迭代器 因为 map 和 set 的底层是 红黑树因此 他们的 迭代器就是将一个树节点指针封装成一个类 1.1 基础类框架和函数
基础函数重载点操作符、重载箭头操作符、重载不等于操作符、构造函数 templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _p;Ref operator*() {return _p-_data;}Ptr operator-() {return (_p-_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!(const Self x) {return _p ! x._p;}RBTreeIterator(Node* p):_p(p){}
}; 1.2 重载前置 和 前置--
关于前置
在 二叉搜索树中 前置需要使迭代器指向 中序遍历的 下一个位置
因此设计前置 就需要模拟中序遍历找到下一个节点 中序遍历顺序是左孩子 --- 根 --- 右孩子
若当前节点为 节点 5按照中序下一个位置是 节点 7即 根节点从左孩子到根节点
若当前节点为 节点 7按照中序下一个位置是 节点 9即 右孩子从根节点到右孩子
若当前节点为 节点 9按照中序右孩子为 空证明已经走完一个中序左根右应该回溯到 祖先节点寻找 当前节点为 父亲的左孩子的关系即 从节点9 一直到 节点 7此时 节点7 是父亲节点 11 的左孩子这样满足 从左孩子到根节点 即节点 9 的下一个位置就是 节点 11
若当前节点为 节点 11按照中序下一个位置是 节点 12即右子树的 最左节点在右子树循环向下找到右子树的最左节点 综合上面几种情况可以得出以下逻辑
1、右不为空则 自己就是 根右子树最左节点就是中序下一个while() 循环 找 右子树的 最左节点
2、右为空则 cur 和 parent 沿着到根节点的路径向上查找直到 孩子 cur 是父亲 parent 的 left
此时 parent 就是中序的下一个节点
伪代码 定义 cur 当前位置 ifcur 的 右不为空 循环找右子树的最左节点 else ifcur 的 右为空 定义 parent whileparent 不为 空 且 parent 的左 不为 cur 循环结束parent 就是 中序的写一个节点 实际代码 Self operator() {Node* cur _p;if (cur-_right) {cur cur-_right;while (cur-_left) { // 注意这里是 cur-_left 我们目的是到最左节点不是 空节点cur cur-_left;}}else {Node* parent cur-_parent;while (parent parent-_left ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;
} 关于前置-- 重载前置-- 也 同理就是倒着中序遍历右 根 左
注意前置-- 的第一个节点可能为 end()本文中我们将 end() 设置为 最后一个节点的下一个节点即为 NULL
当对 end() NULL 前置-- 时可能导致空指针访问的错误因此需要特殊处理
end() 的前一个即为 二叉树的 最后一个节点中序遍历的最后一个右子树的最右节点 Node* cur _p;
// 如果 cur 为 nullptr 代表现在指向 end()
// 特殊处理
if (cur nullptr) {cur _root;while (cur cur-_right) {cur cur-_right;}//_p cur;
} 前置-- 的代码 // 减减 和 加加的 逻辑刚好相反
Self operator--() {Node* cur _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur nullptr) {cur _root;while (cur cur-_right) {cur cur-_right;}//_p cur;}// 下面的逻辑和 前置 差不多镜像反转理解即可else if (cur-_left) {cur cur-_left;while (cur-_right) {cur cur-_right;}}else {Node* parent cur-_parent;while (parent parent-_right ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;
} 1.3 将 迭代器封装进 红黑树
这里定义了begin() / end() 且为 iterator 和 const_iterator 两个版本
此处红黑树的 begin 是整棵二叉搜索树的 最左边的节点即中序遍历的第一个节点因此需要循环操作 templateclass K, class T, class KeyOfT
class RBTree
{
public:typedef RBTreeNodeT Node;// 定义迭代器typedef RBTreeIteratorT, T, T* iterator;typedef RBTreeIteratorT, const T, const T* const_iterator;// 迭代器iterator begin() {Node* cur _root;while (cur cur-_left) {cur cur-_left;}return iterator(cur, _root);}iterator end() {return iterator(nullptr, _root);}const_iterator begin() const {Node* cur _root;while (cur cur-_left) {cur cur-_left;}return const_iterator(cur, _root);}const_iterator end() const {return const_iterator(nullptr, _root);}private:Node* _root nullptr;
};就是上面这一部分封装了迭代器其他的红黑树代码部分上一章都实现了这里暂不赘述 1.4 ⭐ 迭代器类 完整代码
注释都有解释了若不明白可以评论区讨论或私信
// T 节点中的数据类型
// Ref引用类型 T 或 const T
// Ptr指针类型 T* 或 const T*
templateclass T, class Ref , class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node; // 重定义节点类命名typedef RBTreeIteratorT, Ref, Ptr Self; // 对自己的迭代器类型重命名Node* _p; // 迭代器中指向节点的指针Ref operator*() {return _p-_data;}Ptr operator-() {return (_p-_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!(const Self x) {return _p ! x._p;}bool operator(const Self x) const {return _p x._p;}// 我写的函数 cur 有点冗余其实代码可以更加精简Self operator() {Node* cur _p;if (cur-_right) {cur cur-_right;while (cur-_left) { // 注意这里是 cur-_left 我们目的是到最左节点不是 空节点cur cur-_left;}}else {Node* parent cur-_parent;while (parent parent-_left ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;}// 减减 和 加加的 逻辑刚好相反Self operator--() {Node* cur _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur nullptr) {cur _root;while (cur cur-_right) {cur cur-_right;}//_p cur;}// 下面的逻辑和 前置 差不多镜像反转理解即可else if (cur-_left) {cur cur-_left;while (cur-_right) {cur cur-_right;}}else {Node* parent cur-_parent;while (parent parent-_right ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;}RBTreeIterator(Node* p, Node* root):_p(p){}
}; 5. ⭐红黑树 完全体含迭代器适配 map 和 set 的泛型
含有
红黑树节点类
迭代器类
红黑树类拷贝构造、赋值运算符重载、析构、插入函数、4种旋转函数、查找 find、中序遍历、求树的高度、求树的节点个数、判断树是否平衡
#pragma once
#includeiostream
#includevector
#includeassert.h
using namespace std;// 设置颜色枚举值
enum Colour {RED,BLACK
};templateclass T
struct RBTreeNode
{typedef RBTreeNodeT Node;T _data; // 泛型化思想_data 可以是 Key 类型也可以是 pairKey, Value 类型Node* _left;Node* _right;Node* _parent;Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};// T 节点中的数据类型
// Ref引用类型 T 或 const T
// Ptr指针类型 T* 或 const T*
templateclass T, class Ref , class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node; // 重定义节点类命名typedef RBTreeIteratorT, Ref, Ptr Self; // 对自己的迭代器类型重命名Node* _p; // 迭代器中指向节点的指针Node* _root; Ref operator*() {return _p-_data;}Ptr operator-() {return (_p-_data);}// 两个迭代器比较相等 就是直接比较 两个指针bool operator!(const Self x) {return _p ! x._p;}bool operator(const Self x) const {return _p x._p;}// 我写的函数 cur 有点冗余其实代码可以更加精简Self operator() {Node* cur _p;if (cur-_right) {cur cur-_right;while (cur-_left) { // 注意这里是 cur-_left 我们目的是到最左节点不是 空节点cur cur-_left;}}else {Node* parent cur-_parent;while (parent parent-_left ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;}// 减减 和 加加的 逻辑刚好相反Self operator--() {Node* cur _p;// 如果 cur 为 nullptr 代表现在指向 end()// 特殊处理if (cur nullptr) {cur _root;while (cur cur-_right) {cur cur-_right;}//_p cur;}// 下面的逻辑和 前置 差不多镜像反转理解即可else if (cur-_left) {cur cur-_left;while (cur-_right) {cur cur-_right;}}else {Node* parent cur-_parent;while (parent parent-_right ! cur) {cur parent;parent parent-_parent;}cur parent;}_p cur;return *this;}RBTreeIterator(Node* p, Node* root):_p(p),_root(root){}
};templateclass K, class T, class KeyOfT
class RBTree
{
public:typedef RBTreeNodeT Node;typedef RBTreeIteratorT, T, T* iterator;typedef RBTreeIteratorT, const T, const T* const_iterator;RBTree() default;~RBTree() {destory(_root);_root nullptr;}// 拷贝构造RBTree(const RBTreeK, T, KeyOfT t) {_root CopyTree(t._root);}// 赋值重载RBTreeK, T, KeyOfT operator(const RBTreeK, T, KeyOfT t) {RBTree tmp(t);std::swap(_root, tmp._root);return *this;}// 迭代器iterator begin() {Node* cur _root;while (cur cur-_left) {cur cur-_left;}return iterator(cur, _root);}iterator end() {return iterator(nullptr, _root);}const_iterator begin() const {Node* cur _root;while (cur cur-_left) {cur cur-_left;}return const_iterator(cur, _root);}const_iterator end() const {return const_iterator(nullptr, _root);}// 查找iterator find(const K key) const {Node* cur _root;while (cur) {if ((cur-_data).first key) {cur cur-_right;}else if ((cur-_data).first key) {cur cur-_left;}else return iterator(cur, _root);}return end();}// 插入// 插入成功就是 true迭代器指向新插入的节点// 插入失败就是 false迭代器指向已存在的那个节点pairiterator, bool insert(const T data) {if (_root nullptr) {_root new Node(data);_root-_col BLACK; // 根节点一定是黑的return make_pair(iterator(_root, _root), true);}// 利用仿函数KeyOfT kot;Node* cur _root;Node* parent cur;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(iterator(cur, _root), false);}// 在 cur 的位置插入该节点cur new Node(data);cur-_col RED; // 新增节点给 红的Node* newNode cur; // 这里记录以下初始的 cur避免下面各种操作改变 cur// 父连子子连父if (kot(parent-_data) kot(data)) parent-_left cur;else parent-_right cur;cur-_parent parent;// 变色调整while (parent parent-_col RED) {Node* Grandfather parent-_parent;/*gp u*/// 父亲是 爷爷 的左孩子if (parent Grandfather-_left) {Node* Uncle Grandfather-_right;// 叔叔是 红色三人变色cur指爷if (Uncle Uncle-_col RED) {parent-_col BLACK;Uncle-_col BLACK;Grandfather-_col RED;cur Grandfather;parent cur-_parent;}// 叔叔是 黑色旋转后变色else if (Uncle nullptr || Uncle-_col BLACK) {// 看 cur 的位置决定单旋 or 双旋if (cur parent-_left) { /* 右单旋 变色gp uc*/rotateLL(Grandfather);// 爷变红父变黑Grandfather-_col RED;parent-_col BLACK;}else if (cur parent-_right) {/* 双旋先左旋后右旋 变色gp uc*/rotateRR(parent); // p 先 左旋rotateLL(Grandfather); // g 再右旋// 爷变红cur 变黑Grandfather-_col RED;cur-_col BLACK;}break;}}// 父亲是 爷爷 的右孩子else if (parent Grandfather-_right) {Node* Uncle Grandfather-_left;// 叔叔是 红色三人变色cur指爷if (Uncle Uncle-_col RED) {parent-_col BLACK;Uncle-_col BLACK;Grandfather-_col RED;cur Grandfather;parent cur-_parent;}// 叔叔是 黑色旋转后变色else if (Uncle nullptr || Uncle-_col BLACK) {// 看 cur 的位置决定单旋 or 双旋if (cur parent-_right) {/* 左单旋 变色gu pc*/rotateRR(Grandfather);// 爷变红父变黑Grandfather-_col RED;parent-_col BLACK;}else if (cur parent-_left) {/* 双旋先右旋后左旋 变色gu pc*/rotateLL(parent); // p 先 右旋rotateRR(Grandfather); // g 再左旋// 爷变红cur 变黑Grandfather-_col RED;cur-_col BLACK;}break;}}}// 修改一根节点强制变色_root-_col BLACK;return make_pair(iterator(newNode, _root), true);}// RR型左单旋void rotateRR(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;// 1、subRL变成parent的右孩子parent-_right subRL;// subRL 是有可能为 空的if (subRL) {subRL-_parent parent;}// 2、parent变成subR的左孩子subR-_left parent;parent-_parent subR;// 3、subR变成当前子树的根// parentParent 是指 刚开始的 parent 的父亲若 parent 是 _root 则 parentParent 为空否则不为空则该树就是子树if (parentParent) {if (parent parentParent-_right)parentParent-_right subR;else parentParent-_left subR;subR-_parent parentParent;}// 如果 parentParent nullptr说明 parent 是该树的 _root_root 的 parent 是空else {_root subR;subR-_parent nullptr;}}// LL型右单旋void rotateLL(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;// 1、subLR变成parent的左孩子parent-_left subLR;// subRL 是有可能为 空的if (subLR) {subLR-_parent parent;}// 2、parent变成subL的右孩子subL-_right parent;parent-_parent subL;// 3、subL 变成当前子树的根// parentParent 是指 刚开始的 parent 的父亲若 parent 是 _root 则 parentParent 为空否则不为空则该树就是子树if (parentParent) {if (parent parentParent-_right)parentParent-_right subL;else parentParent-_left subL;subL-_parent parentParent;}// 如果 parentParent nullptr说明 parent 是该树的 _root_root 的 parent 是空else {_root subL;subL-_parent nullptr;}}// LR 型subL 先 左旋 parent 右旋void rotateLR(Node* parent) {rotateRR(parent-_left);rotateLL(parent);}// RL 型subR 先 右旋 parent 左旋void rotateRL(Node* parent) {rotateLL(parent-_right);rotateRR(parent);}// 中序遍历void InOrder() {_InOrder(_root);cout \n;}// 获取根节点Node* GetRoot() {return _root;}// 获取该树的高度int Height() {return _Height(_root);}// 获取节点个数int Size() {return _Size(_root);}// 判断是否是 红黑树bool IsValidRBTree() {if (_root nullptr) return false;else if (_root _root-_col RED) return false;// 遍历一条路记录一条路上一共固定有多少个黑色节点int cnt 0;Node* cur _root;while (cur) {if (cur-_col BLACK) cnt;cur cur-_left;}return _IsValidRBTree(_root, 0, cnt);}private:// 判断是否是 红黑树bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){// 1、看根节点是否是 黑的// 2、看每条路径的 黑色节点数量是否相同// 3、检查是否有连续的红节点遇到一个红节点就判断其父亲是否是 红的//走到null之后判断 k 和 blackCount 是否相等即一条路径上的 黑色节点数量是否为固定值if (pRoot nullptr){if (k ! blackCount){cout 违反性质四每条路径中黑色节点的个数必须相同 endl;return false;}return true;}// 统计黑色节点的个数if (pRoot-_col BLACK)k;// 检测当前节点与其双亲是否都为红色Node* pParent pRoot-_parent;if (pParent pParent-_col RED pRoot-_col RED){cout 违反性质三没有连在一起的红色节点 endl;return false;}return _IsValidRBTree(pRoot-_left, k, blackCount) _IsValidRBTree(pRoot-_right, k, blackCount);}int _Size(Node* pRoot) {if (pRoot nullptr) return 0;//if (pRoot-_left nullptr pRoot-_right nullptr) return 1;return 1 _Size(pRoot-_left) _Size(pRoot-_right);}int _Height(Node* pRoot) {if (pRoot nullptr)return 0;return 1 max(_Height(pRoot-_left), _Height(pRoot-_right));}// 销毁一棵树后序遍历void destory(Node* root) {if (root nullptr) {return;}destory(root-_left);destory(root-_right);delete root;}// 拷贝一棵树Node* CopyTree(const Node* root) {if (root nullptr) {return nullptr;}Node* newRoot new Node(root-_kv);newRoot-_left CopyTree(root-_left);newRoot-_right CopyTree(root-_right);return newRoot;}void _InOrder(const Node* root) {if (root nullptr) {return;}_InOrder(root-_left);cout (root-_kv).first : (root-_kv).second \n;_InOrder(root-_right);}Node* _root nullptr;
}; 6. ⭐封装 set 完整代码
红黑树的代码 前面已经实现在 set 中直接调用一个红黑树即可记得在 set.h 要放入 红黑树的头文件
templateclass K
class set
{struct set_KeyOfT {const K operator()(const K key) {return key;}};
public:typedef typename RBTreeK, const K, set_KeyOfT::iterator iterator;typedef typename RBTreeK, const K, set_KeyOfT::const_iterator const_iterator;// 直接调用红黑树的 插入函数pairiterator, bool insert(const K key) {return _tree.insert(key);}// 迭代器都是直接调用底层红黑树的 函数iterator begin() {return _tree.begin();}iterator end() {return _tree.end();}const_iterator begin() const {return _tree.begin();}const_iterator end() const {return _tree.end();}iterator find(const K key) {return _tree.find(key);}private:RBTreeK, const K, set_KeyOfT _tree;
}; 7. ⭐封装 map 完整代码
红黑树的代码 前面已经实现在 map 中直接调用一个红黑树即可记得在 map .h 要放入 红黑树的头文件
templateclass K, class V
class map
{struct map_KeyOfT {const K operator()(const pairK, V kv) {return kv.first;}};
public:typedef typename RBTreeK, pairconst K, V, map_KeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, map_KeyOfT::const_iterator const_iterator;pairiterator, bool insert(const pairK, V kv) {return _tree.insert(kv);}// 迭代器iterator begin() {return _tree.begin();}iterator end() {return _tree.end();}const_iterator begin() const {return _tree.begin();}const_iterator end() const {return _tree.end();}iterator find(const K key) {return _tree.find(key);}V operator[](const K key) {pairiterator, bool pr insert(make_pair(key, V()));return pr.first-second;}private:RBTreeK, pairconst K, V, map_KeyOfT _tree;
};
