红黑树封装map/set及其迭代器(C++)-创新互联
目录
一、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能否正常的插入数据。
// 节点数据 引用/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;
}成员访问操作符即返回该节点的地址，主要用于 map 中，方便访问 pair 中的first以及second。
Ptr operator->()
{
return &(_node->_data);
}bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}迭代器常用成员函数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;
}有了前面++的模拟实现，实现 --就是反着遍历即可。
- 左子树不为空，进行 -- 则是指向左子树中序的最后一个(最右节点)。
- 左子树为空，-- 找孩子不是父亲左节点的祖先。
代码如下:
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;
}我们来看 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;
};
} 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;
}
}; 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;
}
} 只截取了改动和增添的部分。原来的红黑树在这.
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://pwwzsj.com/article/pijhh.html
