关联式容器

关联式容器

所谓关联式容器，观念上类似于关联式数据库，每个元素都有一个键值key和一个实值value。当向容器插入元素时，容器根据其key值将实值放到适当的位置。关联式容器没有头尾的概念，所以也不会有push_front()，push_back()等操作函数。

STL关联容器分为set（集合）和map（映射表）两大类，及其衍生体multiset和multimap。这些容器的底层机制均以RB-tree（红黑树）实现。RB-tree也是一个独立容器，但并不开放使用。

SGI STL还提供一个不在标准规格的关联式容器 hash_table（散列表），以及以 hash_table 为底层机制而完成的 hash_set散列集合、hash_map散列映射表、hash_multiset散列多键集合、hash_multimap散列多键映射表。

红黑树

红黑树的源码这里不完整给出，感兴趣可以看原书或者其他的实现，这里只给出核心的数据结构。

struct __rb_tree_node_base {
    typedef __rb_tree_color_type  color_type;
    typedef __rb_tree_node_base*  base_ptr;

    color_type color;
    base_ptr parent;
    base_ptr left;
    base_ptr right;
};

template<class Value>
struct __rb_tree_node : public __rb_tree_node_base {
    typedef __rb_tree_node<Value>* link_type;
    Value value_filed;
};

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc> 
class rb_tree {
public:
    typedef __rb_tree_node<Value> rb_tree_node;
    typedef rb_tree_node* link_type;
    ....  // 迭代器相关的typedef
};

为什么红黑树节点中只存储Value，却需要模板函数中传入Key。

• 对于set来说，Value和Key是恒等映射，通过keyOfValue这个函数进行的。在某些场景下，我们需要获取value对应的key，用key来进行排序。
• 对于map来说，Value和Key也是一种映射，这里的Value是一个pair，存储的是KV，我们也可以通过KeyOfValue获取到Key。

set

标准的STL set使用RB-tree为底层机制，几乎所有的set操作行为，都只是转调用RB-tree的操作行为而已。
set拥有与list相同的某些性质：当客户端对他进行元素新增或者删除操作时，操作之前的迭代器，在操作完成后都依然有效。
我们不能通过set的迭代器改变set的元素值，因为set的元素值就是键值，如果任意改变set的元素值，会破坏set元素的排列规则。所以,set<T>::iterator被定义为底层RB-tree的const_iterator，杜绝写入操作。
下面是set的源码摘录：

// 定义位于 <stl_function.h>
template<class T>
struct identity : public unaru_function<T, T> {
    const T& operator()(const T& x) const {return x;}
};

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;
};

在set中，由于插入的元素既是value值，也是key值，我们没有必要用一个pair存起来，而是之存入value，然后用identity这个函数对象通过value转成key，也就是一个恒等映射(在set里面是，但在map里面就是不是)。

map

map的所有元素都是pair，这些pair被存储在rb_tree的节点中作为Value。pair的第一个元素被视为键值，第二个元素被视为实值。
我们来看map的源码摘录。

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 maped_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;
    repe_type t;
};

我们可以通过map的得带器改变map的元素内容吗?如果想修正元素的键值，答案是不行，因为map元素的键值关系到map元素的排列顺序。任意改变map元素键值会破坏map的组织。如果想修正元素的实值，答案是可以，因为map元素的实值并不影响map的元素排列规则。因此,map iterators并不是一种constant iterators，也不是一种mutable iterators。
map拥有和list相同的某些性质：当客户端对它进行元素新增或者删除操作的时候，操作前的所有迭代器，在操作完成后都依然有效。当然，被删除元素的那个迭代器除外。

再说一下map中insert的返回值。

pair<iterator, bool> insert(const value_type& x) { // const value_type& 可以接受右值
    return t.insert_unique(x);
}

返回一个pair，其中第一个元素是迭代器，第二个表示插入成功与否。
然后看看map重载的下标([])运算符，它实际就是调用了insert函数,所以map["A"] = "B"可以实现元素插入。

T& operator[](const key_type& k) {
    return (*((insert(value_type(k, T()))).first)).second;
}

multi_set和multi_map

multiset用法和set完全相同，但容器可以存储多个值相同的元素。因此它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()。
multimap用法和map完全相同，蛋挞允许键值重复，它的底层也是调用insert_equal()。

hashtable

可以先复习一下一次探测和二次探测以及开链的知识点。
这里我们采取开链的实现方式，一个hashtable的节点定义如下:

template <class Value>
struct __hashtable_node {
    __hashtable_node* next;
    Value val;
};

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class 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;
    vector<node*, Alloc> buckets;
    size_type num_elements;
}

hashtable也实现了insert_equal()和insert_unique()函数。

hash_set & hash_multiset

设计和set大致一样，比如说set和multiset的键值就是实值，实值就是键值。调用的是insert_unique()。

template<class Value, class HashFcn = hash<Key>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
    typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
    ht rep;

};

multiset调用的是insert_equal(),元素key可以重复。
同理，hash_map和hash_multimap也是一样。

实际上：
hash_set 约等于 unordered_set(key都不重复，都是哈希实现)
hash_map 约等于 unordered_map
此外还有unordered_multiset(key可以重复，哈希实现)