简介

set, map是C++标准库的一种容器。底层实现都是采用红黑树的数据结构。这里要注意和unordered_set、unordered_map的本质区别，它们利用的是hash_table。set和map由于底层是红黑树，因此查找的速度很快，虽然hash_table的查找时间也很短，但是需要额外的存储空间。红黑树的具体实现还是比较复杂，需要先从2-3-4树学起，然后弄懂其原理。最简单的理解是在普通的二叉查找树基础上规避了其极端情况而出现的一种数据结构，它看重的是树的平衡性，下图是红黑树的简单示意图。
rb_tree

红黑树模板

下面是红黑树的模板代码，注释中写到rb_tree的对象所占空间是12字节。简单分析下就是header是一个指针占4个字节，node_count应该是unsigned_int占4字节，key_compare是function object，本身是没有存储空间的，但是为了进行区分它们，编译器会为其分配一个字节的存储空间，这样就可以通过存储地址来识别出不同的object。因此总共大小应该是9个字节，但是由于存在内存对齐机制，默认是4字节对齐的，因此最后的1其实是占用了4个字节。所以，最后是占用了12字节。

// rb_tree code
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;
        link_type header;
        Compare key_compare; //function object 大小为0，因为没有数据，但是编译器实现大小为1，总共大小是9-->12
        // 空class都会占据一个byte，因为这样就可以为其提供一个唯一的存储地址，以此来区分不同的对象。
}

set、map源码分析

set、map的key值都不能随意改变，因为这会破坏红黑树的结构，因此在源码中都在key前加上了const限制。另外，set的key和value其实是同一个，而map中key、data却是分开的。侯老师在视频中说set、map更像是适配器，其实很形象，因为两者都是借助红黑树完成了所有功能，套了个壳而已。

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_type;
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;
}
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; //key 是 const的不能修改;
    typedef Compare key_compare;
private:
    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;
    ...
}

总结

这篇文章可以说是相当简单的介绍了set、map的结构，其实最难的部分在于红黑树的学习理解上，有机会把红黑树简单梳理下。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。