目录
为府谷等地区用户提供了全套网页设计制作服务，及府谷网站建设行业解决方案。主营业务为
成都网站建设、成都网站设计、府谷网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
一、map/set 的封装
1.1 封装思路
1.2 红黑树节点调整
1.3 map 和 set 的定义
1.4 仿函数 KeyOfValue
1.5 map/set 的插入
二、map/set 迭代器实现
2.1 迭代器的定义
2.2 解引用运算符重载
2.3 成员访问运算符重载
2.4 (不)等于运算符重载
2.5 begin() 与 end()
2.6 ++ 运算符重载
2.7 -- 运算符重载
2.8 [ ]下标访问运算符重载
三、源代码+测试用例
3.1 map/set
3.2 迭代器
3.3 测试用例
3.4 红黑树
一、map/set 的封装
在实现了红黑树的部分功能后，我们可以便可以将红黑树作为底层结构来封装map 和 set ，其中map是 K-Value 模型 ，而 set 是 Key 模型。
我们接下来将使用模板、仿函数用一棵红黑树实现 map和set。
1.1 封装思路
因为 map 存储的是 pair ，而 set 存储的是 Key ，所以其解决的根本方向就是：
如果是 map，红黑树中就按照 pair 的 K 进行比较，从而插入；
如果是 set，红黑树中就按照 Key 值进行比较，进而插入。
让 map / set 主动传出待比较的数据，红黑树只用根据数据间关系进行插入即可，不用在乎待比较的数据是何种结构。
1.2 红黑树节点调整
上文我们实现的红黑树是按照键值对的方式进行存储的，而接下来我们要同时封装 map/set，故不能直接定死存储的结构，所以我们在此进行修改。
将原来的 kv 模型改为 data 模型，data 即是比较的数据内容。
注意，将 Kv模型改为 data后，插入与查找中比较的代码都要进行更新，稍后会讲解。
1.3 map 和 set 的定义
map 和 set 底层都使用的红黑树，所以我们 map/set的功能就是调用红黑树的成员函数即可。
templateclass Map
{
private:
RBTree>_t;
};
templateclass Set
{
private:
RBTree_t;
};
因为 Map 有两个模板参数，而 Set 只有一个模板参数。所以当我们使用的一个红黑树实现时，要进行匹配处理。即使 Set 是一个模板参数，在调用红黑树时也要传入两个模板参数。因为第一个模板参数是匹配 Map 满足红黑树的两个模板参数，而第二个模板参数是为了让底层红黑树拿到比较的数据。
为什么 Map 除了传入 pair 外，第一个参数直接传入 K，为什么不能省略？
因为 Find 的存在，map中 Find 函数是直接按 pair 中的 K 进行查找的，所以要额外设置该参数。
1.4 仿函数 KeyOfValue
接下来我们就要将数据取出供红黑树比较了，如果是 map，就按 pair 中的 K去比较，如果是 set，就按 Key 比较。
为此我们可以在 map 和 set 内部定义一个仿函数将其数据取出。
templateclass Map
{
//Map-keyofvalue 仿函数
struct MapKeyOfvalue
{
const K& operator()(const std::pair& kv)
{
return kv.first;
}
};
private:
RBTree>_t;
};
templateclass Set
{
//Set-keyofvalue 仿函数
struct SetKeyOfvalue
{
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree_t;
};
然后我们将其仿函数也作为模板，传入红黑树中，对应的，红黑树要添加一个模板参数来接收该仿函数。
改动代码如下：
改动这些之后，我们便要将红黑树中比较数据大小的地方进行修改
用仿函数将数据取出，然后进行比较：
//根据模板参数创建仿函数
KeyOfvalue kovalue;
if (!_root)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//比较处————进行改动
if (kovalue(cur->_data) >kovalue(data))
{
parent = cur;
cur = cur->_left;
}
//比较处————进行改动
else if (kovalue(cur->_data)< kovalue(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//创建新节点，使用data进行构造
cur = new Node(data);
//比较处————进行改动
if (kovalue(parent->_data) >kovalue(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
这样，红黑树便可以适配 map/set 的插入了。
1.5 map/set 的插入
接下来 map/set 的插入直接套用红黑树的即可。
代码如下：
//map的插入，插入pair
bool insert(const pair& kv)
{
return _t.Insert(kv);
}
//set的插入，插入key
bool insert(const K& key)
{
return _t.Insert(key);
}
接下来进行测试，看我们map/set能否正常的插入数据。
二、map/set 迭代器实现
2.1 迭代器的定义
// 节点数据 引用/const引用 指针/const指针
templatestruct __RBTreeIterator
{
typedef RBTreeNodeNode;
typedef __RBTreeIteratorself;
Node* _node;
public:
__RBTreeIterator(Node* node)
:_node(node)
{}
}
首先，我们要明确，其实 map/set 只是一层套壳，其中的功能都是由红黑树实现后，再封装到map/set中供我们使用，迭代器也不例外。
2.2 解引用运算符重载
解引用即返回该节点的存储的数据，主要用于 set 中，返回该数据的引用。
Ref operator*()
{
return _node->_data;
}
2.3 成员访问运算符重载
成员访问操作符即返回该节点的地址，主要用于 map 中，方便访问 pair 中的first以及second。
Ptr operator->()
{
return &(_node->_data);
}
2.4 (不)等于运算符重载
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
2.5 begin() 与 end()
迭代器常用成员函数begin()与end()，其中begin()对应红黑树的最左节点，end()对应最后一个节点的下一个节点，即nullptr(为了简化，并未设置哨兵节点实现将其完美实现)
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
如果 map/set 中想使用红黑树中的迭代器，我们需要在 map/set 中进行声明。
声明如下：
如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
告诉编译器这是一个类型，并不是一个静态变量
//如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
//告诉编译器这是一个类型，并不是一个静态变量
typedef typename RBTree, MapKeyOfvalue>::iterator iterator;
注意：typename受限定符限制，尽量放在public下
2.6 ++ 运算符重载
首先我们需要明确，迭代器++是让当前迭代器指向红黑树中序遍历的下一个节点。
以下图的35节点为例。
- 当迭代器指向 35 时，进行 ++，指向右子树最左节点，即 40。
- 当迭代器指向 40 时，进行 ++，右子树为空，指向父节点，即 45。
- 当迭代器指向 45 时，进行 ++，指向右子树最左节点，即 48。
- 当迭代器指向 48 时，进行 ++，指向未遍历的父节点，即 50。
分析上面的情况，发现迭代器 ++ 始终围绕着右子树是否存在进行。
现在我们将其抽象化，分析其规律。
- 右子树不为空，进行 ++ 则是指向右子树中序的第一个(最左节点)。
- 右子树为空，++ 找孩子不是父亲右节点的祖先。
代码实现：
self& operator++()
{
//如果右子树存在
if (_node->_right)
{
Node* left = _node->_right;
//则寻找右子树的最左节点
while (left->_left)
{
left = left->_left;
}
_node = left;
}
//如果右子树不存在
else
{
//找孩子不是父亲右节点的节点
Node* parent = _node->_parent;
Node* cur = _node;=
while (cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
//防止最后一个节点寻找祖先导致程序崩溃
if (parent == nullptr)
{
break;
}
}
_node = parent;
}
return *this;
}
需要注意，当 ++ 到最后一个节点的时候。有可能在寻找非父亲右节点的祖先时，父节点一路走到 nullptr 的情况，如图：
所以在每次 parent 更新时都进行一次判断，即可。
测试：
这里顺序把后置 ++ 的代码实现一下，直接套用前置 ++ 即可。
//迭代器后置++
self operator++(int)
{
self it_temp(_node);
++(*this);
return it_temp;
}
2.7 -- 运算符重载
有了前面++的模拟实现，实现 --就是反着遍历即可。
- 左子树不为空，进行 -- 则是指向左子树中序的最后一个(最右节点)。
- 左子树为空，-- 找孩子不是父亲左节点的祖先。
代码如下:
self& operator--()
{
//如果左子树存在
if (_node->left)
{
//找左子树的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = rihgt;
}
//如果左子树不存在
else
{
//找孩子不是父亲左节点的节点
Node* parent = _node->parent;
Node* cur = _node;
while (parent->_left == cur)
{
cur = cur->_parent;
parent = parent->_parent;
if (parent == nullptr)
{
break;
}
}
_node = parent;
}
return *this;
}
2.8 [ ]下标访问运算符重载
我们来看 map 的 [ ] 下标访问操作符，其中 [ ]返回的是mapped_type(pair) 类型。
我们便要对 map 中 insert 的返回值做出修改：
注意，set 中的 insert 也是返回 pair，虽然很反常，但是官方库中确实是这样书写的。
因为只有 set 没有 [ ] 运算符重载，所以我们 set 中不必提供该函数，只用在 map 中提供即可。
首先，我们向 map 中 insert 数据 pair；pair的第一个参数为用户传入的 key 值，第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int，则调用 int的构造函数，如果是 string ，则默认构造 string)。
pairresult = insert(make_pair(key, V()));
然后我们返回迭代器指向的 pair 数据中的second。
//result.first取出迭代器，使用->运算符重载取出data地址，访问second并返回
return result.first->second;
完整的函数书写如下：
V& operator[](const K& key)
{
pairresult = insert(make_pair(key, V()));
//如果存在，则插入失败
//如果不存在，则插入数据
//无论是否存在,都返回 second;
return result.first->second;
}
接下来我们要对红黑树的 Insert 的返回值处进行改动，进而契合 map 的 pair 数据类型。改动有三处，这里贴图大家观察即可。
测试：
三、源代码+测试用例
3.1 map/set
namespace brant
{
templateclass Map
{
public:
struct MapKeyOfvalue
{
const K& operator()(const std::pair& kv)
{
return kv.first;
}
};
//外层要想使用红黑树的iterator，
typedef typename RBTree, MapKeyOfvalue>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pairinsert(const pair& kv)
{
return _t.Insert(kv);
}
void InOrder()
{
_t.Inorder();
}
V& operator[](const K& key)
{
pairresult = insert(make_pair(key, V()));
return result.first->second;
}
private:
RBTree, MapKeyOfvalue>_t;
};
templateclass Set
{
struct SetKeyOfvalue
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pairinsert(const K& key)
{
return _t.Insert(key);
}
void InOrder()
{
_t.Inorder();
}
private:
RBTree_t;
};
}
3.2 迭代器
enum Color { RED, BLACK };
templatestruct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
T _data;
Color _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
// 节点数据 引用/const引用 指针/const指针
templatestruct __RBTreeIterator
{
typedef RBTreeNodeNode;
typedef __RBTreeIteratorself;
typedef __RBTreeIteratoriterator;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
//map常使用operator ->返回地址，然后通过——>访问
Ptr operator->()
{
return &(_node->_data);
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
iterator begin()
{
Node* left = _node;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
self& operator++()
{
//如果右子树存在
if (_node->_right)
{
Node* left = _node->_right;
//则寻找右子树的最左节点
while (left->_left)
{
left = left->_left;
}
_node = left;
}
//如果右子树不存在
else
{
//找孩子不是父亲右的节点
Node* parent = _node->_parent;
Node* cur = _node;
while (cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
//防止最后一个节点寻找祖先导致程序崩溃
if (parent == nullptr)
{
break;
}
}
_node = parent;
}
return *this;
}
self operator++(int)
{
self it_temp(_node);
++(*this);
return it_temp;
}
self& operator--()
{
if (_node->left)
{
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
Node* parent = _node->parent;
Node* cur = _node;
while (parent->_left == cur)
{
cur = cur->_parent;
parent = parent->_parent;
if (parent == nullptr)
{
break;
}
}
_node = parent;
}
return *this;
}
};
3.3 测试用例
void test_iterator()
{
brant::Sets;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
brant::Set::iterator it_set = s.begin();
cout<< "set:"<< endl;
while (it_set != s.end())
{
cout<< *it_set<< " ";
it_set++;
}
cout<< endl;
brant::Mapm;
m.insert(make_pair(1, 100));
m.insert(make_pair(2, 200));
m.insert(make_pair(3, 300));
m.insert(make_pair(4, 400));
m.insert(make_pair(5, 500));
brant::Map::iterator it_map = m.begin();
cout<< "map:"<< endl;
while (it_map != m.end())
{
cout<< (*it_map).first
<< "："<< (*it_map).second<< endl;
++it_map;
}
}
void test_map_()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜",
"苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
brant::MapcountMap;
for (auto& str : arr)
{
countMap[str]++;
}
brant::Map::iterator it = countMap.begin();
while (it != countMap.end())
{
cout<< it->first<< ":"<< it->second<< endl;
++it;
}
cout<< endl;
for (auto& kv : countMap)
{
cout<< kv.first<< ":"<< kv.second<< endl;
}
}
3.4 红黑树
只截取了改动和增添的部分。原来的红黑树在这.
templateclass RBTree
{
typedef RBTreeNodeNode;
public:
typedef __RBTreeIteratoriterator;
typedef __RBTreeIteratorconst_iteraotr;
iterator begin()
{
//找最左节点
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
//用一个节点构造迭代器
return iterator(left);
}
iterator end()
{
//因为没有哨兵节点，直接使用空进行返回
return iterator(nullptr);
}
pairInsert(const T& data)
{
KeyOfvalue kovalue;
if (!_root)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node* parent = nullptr;
Node* cur = _root;
//找插入的位置
while (cur)
{
if (kovalue(cur->_data) >kovalue(data))
{
parent = cur;
cur = cur->_left;
}
else if (kovalue(cur->_data)< kovalue(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur),false);
}
}
cur = new Node(data);
//插入成功，返回新增节点
//注意：cur 可能会改变(情况1变色处理,cur指向可能会改变)
//使用newnode记录新创建节点的地址
Node* newnode = cur;
if (kovalue(parent->_data) >kovalue(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);
if (grandfater->_left == parent)
{
Node* uncle = grandfater->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
};
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站名称：红黑树封装map/set及其迭代器(C++)-创新互联
网站网址：
http://cdkjz.cn/article/pijhh.html
