我們知道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 = https://www.cnblogs.com/sandychn/p/" << *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 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 = https://www.cnblogs.com/sandychn/p/{1,2}
insert result = false
size = 2
address = 0xf91be0, value = {1,2}
address = 0xf91c10, value = {1,3}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61741.html
標籤：C++
上一篇：序列歸并