**侯捷老师的C++笔记3--STL**
rb_tree && set/map && hash_set/hash_map
rb_tree
- red-black tree(红黑树): balanced binary search tree(平衡二叉搜索树)
- 中序遍历则为有序
- 不应该使用rb_tree的iterator来改变元素的值
- rb_tree提供两种insertion, insert_unique() –> key不可重复(set/map), insert_equal() –> key可重复(multiset/multimap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15rb_tree<int, int, identity<int>, less<int>, alloc> myTree;
// set, key = value, so use identity
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node<Value> rb_tree_node; // left, right, parent
...
public:
typedef rb_tree_node* link_type;
...
protected:
size_type node_count; // rb_tree的大小, 节点数量
link_type header; // 指向root,
Compare key_compare; // function object, 比较函数
};set/ multiset
- 以rb_tree为底层结构,有元素自动排序的特性(key)
- (++ite)即可获得sorted
- 无法使用iterator改变元素值,底部为const iterator
1
2
3
4
5
6
7
8
9
10
11
12
13template <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;
private:
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; // const, 不能改变元素值
};map/ multimap
- 以rb_tree为底层结构,有元素自动排序的特性(key)
- (++ite)即可获得sorted
- 无法使用iterator改变key值,底部key type为const,无法改变
- 有operator[]重载
1
2
3
4
5
6
7
8
9
10
11
12
13
14template <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; // vaule = key | data
typedef Compare key_compare;
private:
typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; // key为const,不能改变
rep_type t;
public:
typedef typename rep_type::iterator iterator;
};
hash_table
- hash到同一个值之后用list连接起来
- 如果element的个数大于bucket数量时,会进行rehashing, bucket的数量会变为二倍最近的素数
- 可以使用hashtable iterator来改变元素的data, 但不能改变key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable {
public:
typedef HashFcn hasher;
typedef EqualKey key_equal;
typedef size_t size_type;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node; // list_node
/* template<class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
}; */
vector<node*, Alloc> buckets; // buckets
size_type num_elements;
public:
size_type bucket_count() const {return buckets.size();}
};