STL容器源码剖析

std::vector

# Vector数据结构 
template<class T, class Alloc =alloc>
class vector
{
...
protected:
    iterator start; //表示目前使用空间的头    
    iterator finish; //表示目前使用空间的尾
    irterator end_of_storage; //表示目前可用空间的尾  
    
}
# vector::iterator数据结构
template<class T, class Alloc =alloc>
class vector
{
...
public:
    typedef T  value_type;  
    typedef *value_type  iterator; //即vector::iterator是一个普通类型指针
public:
    iterator begin()    { return start; }
    iterator end()  {return finish;}
    size_type size()    {return size_type(end() - begin());}
    size_type capacity()    {return size_type(end_of_storage - begin());}
}

image.png

std::list

# SGI STL List源码
template<class T, class Alloc =alloc>
class list
{
...
protected:
    typedef __list_node<T> list_node;
    
...
public:
    typedef list_node* link_type;
    
... 
protected:
    link_type node; //只要一个指针，便可表示整个环形双向链表
...
public:
    iterator begin() {return (link_type)(node->next);}
    //环形链表的尾部加上一个空白节点（即node），便符合STL规范之“前闭后开”区间  
    iterator end() {return node;}   
    bool empty() {return node->next == node;}
...
    reference front() {return *(begin()); }
    reference back() {return *(--end()); }
...
public:
    list() { empty_initialize(); }
protected
    void empty_initialize() {
        node = get_node();  //配置一个节点空间，另node指向它
        node->next = node;  //另node头和尾都指向它自己
        node->prev = node;
    }
}

# list::iterator的数据结构
template<class T, class Ref, class Ptr>
class __list_iterator
{
    typedef __list_node<T>* link_type;  
    link_type node; //即list::iterator中拥有一个普通指针，指向list的节点
}

# SGI STL List数据结构展示
template<class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data; //list<T>()容器中真正存储T元素的位置；
}

# 测试代码
int main()
{
    list<int> ll;
    ll.push_back(0);
    ll.push_back(1);
    ll.push_back(2);
    ll.push_back(3);
}

image.png

std::map

# SGI STL Map源码
template<class key, class T,
    class Compare = less<key>,  //缺省采用递增排序
    class Alloc =alloc>
class map
{
...
public:
    //typedefs
    typedef pair<const key, T> value_type; //元素型别（key/value）
    typedef Compare key_compare;            //key比较函数

    class value_compare : public binary_function<value_type, value_type, bool> {
    friend class map<key, T, Compare, Alloc>;
    protected:
        Compare com;
        value_compare(Compare c): com(c) {}
    };
...
//核心数据
private:
    typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t; //map底层以红黑树表现
... 
public:
    map(): t(Compare()) {}
    map(const map<key, T, Compare, Alloc>& x): t(x.t) {}
...
    //map对外的所有操作， RB-Tree都已提供，map只需转调用即可
    size_type size() const { return t.size(); }
    iterator begin() { return t.begin(); }
...
}

# SGI STL RB-Tree源码
template<class key, class value, class keyOfValue, class Compare, class Alloc>
class rb_tree
{
protected:
    typedef __rb_tree_node_base* base_ptr;
    typedef __rb_tree_node<value> rb_tree_node;
    typedef __rb_tree_color_type color_type;
...
public:
    rb_tree_node* link_type;
    
protected:
    //RB_tree只以3笔数据表现
    size_type node_count;   //追踪记录数的节点的数量
    link_type header;   //特殊定义的节点， header->parent == (link_type&)root
    Compare key_compare;   //function object，节点间key的大小比较准则

    link_type& root() const  { return (link_type&)header->parent; }
    link_type& leftmost() const { return (link_type&)header->left; }
    link_type& rightmost() const { return (link_type&) header->right; }
...
private:
    void init() {
        header = get_node(); //创建一个rb_tree_node，令header指向它
        root() = 0;
        leftmost() = header;
        rightmost() = header;
    }   
...
public:
    iterator begin() { return leftmost(); } 
    iterator end() { return header; }
    size_type size() { return node_count; }
    //allocation/deallocation
    rb_tree(const Compare& comp = Compare() ): node_count(0), key_compare(comp)
    {
        init();
    }
}

# rb_tree双层节点设计
## __rb_tree_node_base
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data; //list<T>()容器中真正存储T元素的位置；
}

# 测试代码
int main()
{
    list<int> ll;
    ll.push_back(0);
    ll.push_back(1);
    ll.push_back(2);
    ll.push_back(3);
}

std::deque

# deque数据结构 
template<class T, class Alloc =alloc, size_t BufSize = 0>
class deque
{
...
public:
    typedef T value_type;
    typedef value_type* pointer;
    
...
protected:
    typedef pointer* map_pointer;
... 
protected:
    map_pointer map; //deque的中控，map指向一块连续的空间，每个元素都是一个指针，指向一块缓冲区；
    size_type map_size; 
    pointer start; //指向deque容器中的第一个节点       
    pointer finish;//指向deque容器中的最后一个节点      
}
# deque::iterator的数据结构
template<class T, class Alloc =alloc>
class __deque_iterator
{
...
public:
    
}

image.png image.png