C_stl_notes3

**侯捷老师的C++笔记3--STL**

rb_tree && set/map && hash_set/hash_map

rb_tree

  • avatar
  • 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
    15
    rb_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
    13
    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;
    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
    14
    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; // 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

avatar

  • 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
    21
    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;
    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();}
    };
0%