STL中_Rb_tree的探索
2024-10-08 09:30:51
我们知道STL中我们常用的set
与multiset
和map
与multimap
都是基于红黑树。本文介绍了它们的在STL中的底层数据结构_Rb_tree
的直接用法与部分函数。难点主要是_Rb_tree
的各个参数的确定。
特别注意在如下代码的Selector
类用于从Node
中选出用于排序的key值,这个仿函数必须返回const int&
而不能是int
,否则less<int>::operator(const int&, const int&)
会抛出segmentation fault
。由于源码中逻辑比较复杂,但是可以观察到内部涉及这方面的地方经常使用到指针。所以可以推测是因为引用了已经释放的局部变量所以才抛出的segmentation fault
。一开始写成int
,看了很多源码才发现是这个原因,一定要注意。
接下来是样例代码,里面都有注释了。
#include <iostream>
#include <iomanip>
// 原则上不要直接引用这个头文件,这里只是为了测试
#include <bits/stl_tree.h>
using namespace std;
struct Node {
int first, second;
Node(int _first, int _second) : first(_first), second(_second){};
friend ostream& operator<<(ostream& outs, const Node& node) {
outs << '{' << node.first << ',' << node.second << '}';
return outs;
}
};
template <class T>
struct Selector {
// MUST return const int&, not int.
// if return int, segmentation fault will occur.
// I have spent much time because of this.
const int& operator()(const T& obj) const {
return obj.first;
}
};
int main() {
// _Rb_tree: red-black tree in STL.
using tree_type = _Rb_tree<int, Node, Selector<Node>, less<int>>;
using iterator_type = tree_type::iterator;
using result_pair_type = pair<tree_type::iterator, bool>;
tree_type tree;
// 插入元素Node(1, 2)
result_pair_type res = tree._M_insert_unique(Node(1, 2));
cout << "insert address = " << res.first._M_node << endl;
cout << "insert result = " << boolalpha << res.second << endl; // true
iterator_type it = tree.begin();
cout << "begin address = " << it._M_node << endl;
it = tree.find(1);
cout << "address = " << it._M_node << ", value = " << *it << endl;
// 再插入元素Node(1, 2)但是因为调用的是insert_unique
// 它不会添加重复值,所以插入会被拒绝
res = tree._M_insert_unique(Node(1, 2));
cout << "insert result = " << boolalpha << res.second << endl; // false
// 再插入元素Node(1, 2)但这次调用insert_equal
// multiset和multimap就是利用这个函数来插入重复值
// 也就是这个函数允许重复值,所以插入成功
tree._M_insert_equal(Node(1, 3));
cout << "size = " << tree.size() << endl; // 大小就变为2
pair<iterator_type, iterator_type> result = tree.equal_range(1);
for (iterator_type ite = result.first; ite != result.second; ++ite) {
cout << "address = " << ite._M_node << ", value = " << *ite << endl;
}
return 0;
}
程序的输出为(内存地址不定):
insert address = 0xf91be0
insert result = true
begin address = 0xf91be0
address = 0xf91be0, value = {1,2}
insert result = false
size = 2
address = 0xf91be0, value = {1,2}
address = 0xf91c10, value = {1,3}
最新文章
- Lambert(朗伯)光照模型 和Half Lambert的区别
- 后台返回国标码,怎么转化为JSON
- ListView 重设Adapter后的动作,remove/add ListView 的动作
- jython 2.7 b3发布
- 协议(Protocol)---实例
- [转]World Wind学习总结一
- 小白学习mysql之函数
- YUM安装提示PYCURL ERROR 6 - "Couldn&#39;t错误的解决办法
- 有关<;table>;的几个问题
- iframe替代方案
- swift:入门知识之控制流
- vpn局域网共享
- jquery实现视觉滚动--fullpage
- 常用SQL语句(增删查改、合并统计、模糊搜索)
- 计算机网络-ip地址聚合后可用的地址数
- poj3348 Cows 凸包+多边形面积 水题
- MySQL中删除重复数据只保留一条
- 【转】【经典算法】——KMP,深入讲解next数组的求解
- hdu_2222: Keywords Search(AC自动机模板题)
- [BZOJ]1089 严格n元树(SCOI2003)