目录

• 容器结构分类
• 通过萃取机traits萃取迭代器的型别
• 容器list
  • list的定义
  • list的node定义
  • list的iterator
• 容器vector
  • vector的定义
  • vector的iterator
  • vector 的大小
• array
  • array的定义
• forward_list
  • forward_list与list的区别
• deque
  • deque的定义
  • deque的iterator

容器结构分类

这里的衍生，并非继承关系，而是一种包含关系。
例如heap中包含一个vector。

通过萃取机traits萃取迭代器的型别

template <class I>
struct iterator_traits { //traits是特性之意
    typedef typename I::value_type value_type;
};
//两个偏特化(partial specialization)
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type; //注意是T而不是const T,因为value_type的主要目的是用来声明变量，而声明一个无法被赋值的变量是没有什么用的（const T）,所以要去掉const
};
//于是当需要知道I的value_type时，便可以这么写：
template<typename I>
void algorithm(...) {
    typename iterator_traits<I>::value_type v1;
}

容器list

list在要内存时，不光需要一个指针，还需要指向前后的两个指针。

list的定义

//list的定义
    template<class T, class Alloc = alloc>
    class list {
    protected:
        typedef __list_node<T> list_node;
    public:
        typedef list_node* link_type;
        //G2.9编译器的iterator
        typedef __list_iterator<T, T&, T*> iterator;
        //G4.9编译器的iterator
        typedef _List_iterator<_Tp> iterator;
    portected:
        link_type node;
    };

list的node定义

G2.9编译器的设计是如下所示：其中前向指针和后向指针，指向的都是void类型，所以sizeof(list)是4个字节，就是一个指向数据的指针。

//list节点的定义
    template <class T>
    struct __list_node {
        typedef void* void_pointer;
        void_pointer prev;
        void_pointer next;
        T data;
    };

G4.9版本在G2.9版本的基础之上，将node部分拆分成了两个部分，一个是_list_node_base，改变了G2.9版本的前向和后向指针的指向类型，另外node是继承_List_node_base后，再加上数据部分，如下所示：