前置知识:红黑树原理 【数据结构】7.平衡搜索树(AVL树和红黑树),红黑树的平衡性有利于 search 和 insert
- 红黑树的迭代器
- begin() 左侧
- end() 右侧
- 迭代顺序 5 6 7 8 10 11 12 13 15
- 不能使用迭代器修改 Key 的值,例如将 6 改成 50 会破坏红黑树的性质
1. RB-tree
在g++编译器中(4.9),rbtree在 <bits/stl_tree.h> 中定义
1 2 3 4 5 6 7 8 9 10 11 12 13
|
template <class Key, class Value, class KeyOfValue, class Compare, class Allocated = alloc> class _Rb_tree { protected: typedef __rb_tree_node<Value> rb_tree_node; public: typedef rb_tree_node* link_type; protected: size_type node_count; link_type header; Compare key_compare; };
|
- 使用案例,该rbtree的key就是value,获取key的方式就是直接返回该元素
- rbtree._M_insert_unique(5); 插入元素(无重复)
- rbtree._M_insert_equal(5); 插入元素(可以重复),可以使用 .count(5) 计算数量
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| _Rb_tree<int, int, identity<int>, less<int>, alloc> rbtree;
template <class T> struct identity : public unary_function<T, T> { const T& operator()(const T& x) const { return x; } };
template <class T> struct less : public binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x<y; } };
|
2. set / multiset
- set 提供遍历操作以及迭代器 iterator,可以使用 ++ite 进行遍历,并且得到排序后的数据
- 无法使用迭代器修改元素值,修改值会导致破坏排序
- set insert 调用无重复插入方法,multiset insert 调用可重复插入的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| template <class Key, class Compare = less<Key>, class Alloc = alloc> class set { public: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; prevate: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t; public: typedef typename rep_type::const_iterator iterator; };
|
2.1 typename
1 2
| typedef typename rep_type::const_iterator iterator; typedef rep_type::const_iterator iterator;
|
首先看类作用域下操作符 MyClass::name
调用实际上有 3 种可能:以MyClass
为例子来说,MyClass::A
静态数据成员,MyClass::B
静态成员函数,MyClass::C
嵌套类型。由于MyClass
是一个完整的定义,所以编译器完全可以推断出任意一个变量究竟是什么类型的。但还有一种可能,如果是T::name
呢?
1 2 3 4 5
| class MyClass{ static int A; static int B(); typedef int C; }
|
以foo
函数为例子,一眼看下去它的含义是定义了T
类中iterator
的指针并起名为iter
;如果传入的是ContainsAType
则完全没有问题。但如果传入的是ContainsAnotherType
则会出现问题,因为在该类中定义了静态整形变量,如果有一个全局整形变量iter
,则翻译后这里就会变成一个乘法表达式,二义性是不能被允许的,所以委员会引入了typename
关键字
模板类型实例化前,并不知道它具体是哪个类型,而使用typename
可以直接告诉编译器这是一个类型,而非成员对象。
1 2 3 4 5 6 7 8 9 10 11 12 13
| struct ContainsAType { struct iterator { } };
struct ContainsAnotherType { static int iterator; };
template <class T> void foo() { T::iterator * iter; }
|
3. map / multimap
- map 提供遍历操作以及迭代器 iterator,可以使用 ++ite 遍历排序后的数据
- 无法使用迭代器修改 key,但允许修改 data(源码实现很巧妙,借用 pair<const Key, T> 实现)
- map insert 调用无重复插入方法,multimap insert 调用可重复插入方法
- insert(pair<long, string>(1, “HelloWorld”); 插入时应该插入一个pair
- map[5] = “Hi Five”; // 插入 (5, “Hi Five”)
- map[5]; // 这个比较有趣,标准规定,如果没有 Key 5, 则创建 Key 5 和 string 的默认值
- 在multimap 不可以使用 multimap[]进行插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map { public: typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; typedef Compare key_compare; prevate: typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; public: typedef typename rep_type::iterator iterator; };
|
Author:
mxwu
Permalink:
https://mingxuanwu.com/2024/02/29/202402290956/
License:
Copyright (c) 2023 CC-BY-NC-4.0 LICENSE