【琢磨 STL】关联式容器
2021-04-03 08:06:19 #CPP  #CPP  #STL 

image-20210321140203146

RBT

  1. Red-Black Tree，红黑树，平衡二分搜寻树。排列规则有利search和insert，并保持平衡，防止任何结点过深
  2. RBT 提供遍历操作以及 iterator。通过 iterator 操作重载的++item，遍历得到排序状态的元素值
  3. 可以但非常不提倡通过 iterator 改变元素值，会破坏 RBT 的排列顺序
  4. 提供两种insert操作：insert_unique()表示key值独一无二；insert_equal()表示key值可以重复。如果调用insert_unique()重复放入key，不会发生异常或崩溃，只是单纯的没有把值放入 RBT
  5. 相关源码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = 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;   // rb_tree的大小，即结点数量
        link_type header;
        Compare key_compare;
    };
  6. 五种模板参数的作用

    Key：元素的类型

    Value：key|data，由两者合成为 value。set 中 key 就是 value，map 中 value 就是键值对

    KeyOfValue：如何从 Vlaue 中获得 key。

    Compare：key 比较大小的方法

    Alloc：分配器，默认是 alloc

  7. 在 GCC 中，KeyOfValue默认使用identity<> 
    1
    2
    3
    4
    template<class T>
    struct identity : public unary_function<T, T> {
        const T &operator()(const T &x) const { return x; }
    };
    由此可以看出，默认将 vlaue 视为 key

8.Compare默认使用less<>

1
2
3
4
template<class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T &x, const T &y) const { return x < y; }
};

less<>针对例如 int，double 等类型，如果Key是自己写的类型，需要传入相关的用来比较的类成员函数

有序

set/multiset

  1. 以 RBT 为底层结构，通过调用 RBT 的功能来实现所有的操作，元素自动排序，排序依据是 key
  2. key 即 vlaue
  3. set 的 key 独一无二，set.insert()的底层实现是 RBT 的insert_unique()；multiset 的 key 可以重复，multiset.insert()的底层实现是 RBT 的insert_equal()
  4. 相关源码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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;

    private:
        typedef rb_tree <key_type, value_type,
                        identity<value_type>, key_compare, Alloc> rep_type;
        rep_type t;     // 以RBT作为底层结构

    public:
        typedef typename rep_type::const_iterator iterator;
    };
  5. 通过第 10 行，可以看一下模板参数

    Value：默认为 Key 的类型

    KeyOfValue：使用 RBT 默认的 identity<>

    Compare：使用 RBT 默认的 less<>，也可以传入自写的

  6. 不可以通过 iterator 更改元素的值。通过 typedef 底层 RBT 的 const_iterator 为自己的 iterator，第 14 行

map/multimap

  1. 以 RBT 为底层结构，通过调用 RBT 的功能来实现所有的操作，元素自动排序，排序依据是 key
  2. value 分为 key 和 data
  3. map 的 key 独一无二，map.insert()的底层实现是 RBT 的insert_unique()；multimap 的 key 可以重复，multimap.insert()的底层实现是 RBT 的insert_equal()
  4. 相关源码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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;

    private:
        typedef rb_tree <key_type, value_type,
        				select1st<value_type>, key_compare, Alloc> rep_type;
        rep_type t;     // 以RBT作为底层结构

    public:
        typedef typename rep_type::iterator iterator;
    };
  5. 不可以通过 iterator 更改元素的 key，但是可以更改 data。
    在第 15 行，可以看出 iterator 并不是 const 类型。
    在第 7 行，可以看出 value 实际上是一个 pair 对象，通过构建时传入 const 类型的 Key，来保证用户无法修改 key，但是可以修改 data
  6. 通过第 11 行，模板参数中的KeyOfValue使用的是select1st，用来获得pair.first作为 key 
    1
    2
    3
    4
    5
    6
    template<class Pair>
    struct select1st :
            public unary_function<Pair, typename Pair::first_type> {
        const typename Pair::first_type &
        operator()(const Pair &x) const { return x.first; }
    };

HashTable

  1. HT 原理

    image-20210404172655538

    1. 对bucket设定固定大小 M，一般设定 53
    2. 对需要存入 HT 的对象，获取其特定值 H（例如学生对象的班内编号，货物对象的生产编号，这种可以具象出来的数字），用以编组
    3. 以 M 对 H 取余，存入对应的位置（如编号 53，取余后为 0，编号 54，取余后为 1，分别放入 0 和 1）
    4. 取余相同的对象以链表的形式存入对应位置（编号 106，取余后也为 0，存入 53 后面）
    5. 一般来说，当元素总量超过bucket的固定大小 M 时，对bucket做 rehash 操作。以__stl_prime_list中的值依次取（GCC2.9 版本，其他版本的值可能会有变化）
    6. rehash 后对所有元素根据新的 M，再做取余运算，并以此存入相应位置

  2. C++ 中实现源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 结点
template<class Value>
struct hashtable_node{
    hashtable_node* next;	// 指向下一个结点
    Value val;	// 记录数据
};

template<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;    // 实现HashFcn
    key_equal equals;   // 实现对key的比较
    ExtractKey get_key;     // 实现对key的获取

    typedef hashtable_node <Value> node;

    std::vector<node *, Alloc> buckets;
    size_type num_elements;

public:
    size_type bucket_count() const { return buckets.size(); }
};

// 迭代器
template<class Value, class Key, class HashFcn,
        class ExtractKey, class EqualKey, class Alloc=alloc>
struct hashtable_iterator {
    hashtable_node<Value> *cur;	// 指向对象链表中的结点
    hashtable<Value, Key, HashFcn,
    		  ExtractKey, ExtractKey, Alloc> *ht;	// 指向buckets
};
  1. 模板参数HashFcn用来获取对象的特定值 H（用来确定在bucket中的位置，不会面向用户）
  2. 模板参数ExtractKey用来获取对象的 key（用来表示这个对象的值，面向用户）
  3. 模板参数EqualKey用来对对象的 key 做比较（使用insert_unique()插入时做判断）
  4. 一个hashtable对象的大小为：三个仿函数大小为 1（理论上为 0，实际为 1），合 3；vector 类型的 buckets 大小为 12；size_type 类型的 num_elements 大小为 4。总共为 19 个字节，调整为 20 个字节
    7.buckets的大小永远大于size()

无序

unordered_set/unordered_multiset

  1. 以 HT 为底层结构，通过调用 HT 的功能来实现所有的操作，元素乱序
  2. key 即 vlaue
  3. unordered_set 的 key 独一无二，set.insert()的底层实现是 HT 的insert_unique()；unordered_multiset 的 key 可以重复，multiset.insert()的底层实现是 HT 的insert_equal()
  4. 不可以通过 iteratpr 更改元素的 key

unordered_map/unordered_multimap

  1. 以 HT 为底层结构，通过调用 HT 的功能来实现所有的操作，元素乱序
  2. value 分为 key 和 data
  3. unordered_map 的 key 独一无二，set.insert()的底层实现是 HT 的insert_unique()；unordered_multimap 的 key 可以重复，multiset.insert()的底层实现是 HT 的insert_equal()
  4. 不可以通过 iteratpr 更改元素的 key，但是可以更改 data