STL中_Rb_tree的探索
2020-02-20 16:00:56来源:博客园 阅读 ()
STL中_Rb_tree的探索
我们知道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}
原文链接:https://www.cnblogs.com/sandychn/p/12334194.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash