C++泛型编程，及STL源码入门

速刷知识点，可用来查漏补缺

泛型编程

c++模板类分为class template 和 function template。

特化分为特例化（全特化）和部分特例化（偏特化）

模板和特例化版本应该声明在同一头文件，所有同名模板的声明应该放在前面，接着是特例化版本。
一个模板全特化的条件：（1）必须有一个主模板类（2）模板类型全部明确化。

模板函数

template<typename T1, typename T2>
void fun(T1 a, T2 b)
{
    cout<<"模板函数"<<endl;
}
template<>
void fun<int , char >(int a, char b)
{
    cout<<"全特化"<<endl;
}

类模板

template<typename T1, typename T2>
class Test
{
public:
    Test(T1 i,T2 j):a(i),b(j){cout<<"类模板"<<endl;}
private:
    T1 a;
    T2 b;
};

template<>
class Test<int , char>
{
public:
    Test(int i, char j):a(i),b(j){cout<<"全特化"<<endl;}
private:
    int a;
    char b;
};


template <typename T2>
class Test<char, T2>
{
public:
    Test(char i, T2 j):a(i),b(j){cout<<"偏特化"<<endl;}
private:
    char a;
    T2 b;
}

STL

六大组件：容器、算法、迭代器、仿函数、适配器、空间配置器

关系：

容器通过空间配置器获得存储空间
算法通过迭代器访问空间中的内容
仿函数增加算法的通用性
适配器可以修饰仿函数

STL将数据和操作分离，由迭代器充当交互的中间人。

关于容器的接口函数，建议在需要用到的时候，直接查看cplusplus的文档，里面介绍的很详细，不推荐死记硬背。在刚开始接触容易的时候，只要知道有哪些容器，大致是什么用途就好了。

以下是简要介绍

pair

作用：将两个数据成员进行组合，通常和map一起进行使用，作为map的元素。

在map中插入（insert）时，返回值为<迭代器， bool>，迭代器指向插入的元素，bool指示插入是否成功。

map.insert({a, b});
map.insert(pair<string, string>(a, b));

vector

作用：动态数组

底层实现：堆中的连续内存。如果当前空间已经用完，则在新增数据时，分配一块更大的内存（通常是翻倍），将原来的数据复制过来。

扩容机制：（1）固定扩容（2）加倍扩容

迭代器：由于vector是线性空间，所以普通指针具备作为vector迭代器的所有条件。

数据结构：线性空间

源码的大致思路（注意，实际的源码要复杂得多）

templeta<class T,class Alloc=alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type *pointer;
    typedef value_type &reference;
    typedef value_type *iterator;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type
    //类型定义
protected:
    typedef simple_alloc <value_type, Alloc> data_alloctor
    //空间配置器
    iterator start;
    iterator finish;
    iterator end_of_storage;
    //3个指针，作为迭代器，指向start，end， end_of_storage
    
    //自动扩充内存
    void insert_aux(iterator position, const T &x);
    //取消分配内存，用于析构函数
    void deallocate() {
        if (start)
            data_allocator::deallocate(start, end_of_storage);
    }
    
    //初始化填充，用于构造函数
    void fill_initialize(size_type n, const T &value) {
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }

public:
//容器接口
    iterator begin() { return start; };
    iterator end() { return finish; };
    size_type size() const { return size_type(end() - begin()); };
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); };
    
//constructor
    vector() : start(0), end(0), end_of_storage(0) {};
    vector(size_type n, const T &value)(fill_initialize(n, value););
    vector(long n, const T &value)(fill_initialize(n, value););
    vector(int n, const T &value)(fill_initialize(n, value););
    explicit vector(size_type n) { fill_initialize(n, T()); };
    
//析构
~vector() {
    destory(start, finish);//全局函数，析构对象
    deallocate();//成员函数，释放空间
}

//member function
    reference front() { return *begin(); };
    
    reference back() { return *(end() - 1); };
    
    void push_back(const T &x) {
        if (finsih != end_of_storage) {
            construct(finish, x);
            ++finish;
        } else insert_aux(end(), x);
    //扩充后添加
    }
    
    void pop_back() {
        --finish;
        destory(finish);
    }
    
    iterator erase(iterator position) {
        if (position + 1 != end())
            copy(position + 1, finish, position);
        --finish;
        destory(finish);
        return position;
    }
    
    void resize(size_type new_size, const T &x) {
        if (new_size() < size())
            erase(begin() + new_size, end());
        else
            insert(end(), new_size - size(),x);
    }
    
    void resize()(size_type new_size) { resize(new_size, T()); }

    void clear() { erase(begin(), end()); }
protected:
//分配空间并初始化
    iterator allocate_and_fill(size_type n, const T &x) {
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, x);//全局函数
    }
}

构造和内存管理：在末尾插入元素时，有空间则插入，无空间则扩容后再插入。

template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T &x) {
    if (finish != end_of_storage) {
        //有空余空间则直接构造，注意allocate, deallocate, construct, destory, max_size为库函数，可直接调用。
        //在alloc_traits.h头文件中
        consruct(finish, *(finish - 1));
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    } else {
        //否则，翻倍申请新空间，并将原空间的元素拷贝过来
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size() : 1;
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            //尝试拷贝原有元素，失败则抛出异常
            new_finish = uninitialized_copy(start, position, new_start);
            construct(new_finish, x);
            ++new_finish;
            new_finish = uninitialized_copy(position, finish, new_finish);
        }catch () {
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //删除原vector
        destory(begin(), end());
        deallocate();
        //更新指针
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

list

作用：双向链表

迭代器：迭代器是泛化的指针，重载了->, --, ++, * ()等运算符，迭代器也是算法与容器之间的桥梁，算法需要了解容器的方方面面，于是就有了5种关联类型。我们通过萃取器（iterator traits类）来提供关联类型值。具体细节参阅c++primer相关章节。

template<class T, class Alloc = alloc>
class list {
protected:
    typedef listnode <T> listnode;
public:
    typedef listnode link_type;
    typedef listiterator<T, T &, T> iterator;
protected:
    link_type node;
};

迭代器的5种关联类型

value_type
difference_type
pointer
reference
iterator_vategory

// 迭代器内定义的关联类型
template<class I>
struct iterator_traits {
    typedef typename I::iteratorcategory iteratorcategory;
    typedef typename I::valuetype valuetype;
    typedef typename I::differencetype differencetype;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};
•// 指针类型的迭代器
template<class T>
struct iteratortraits<T> {
    typedef randomaccessiteratortag iteratorcategory;
    typedef T value_type;
    typedef ptrdifft differencetype;
    typedef T *pointer;
    typedef T &reference;
};
// 指针常量类型的迭代器
template<class T>
struct iteratortraits<const T> {
    typedef randomaccessiteratortag iteratorcategory;
    typedef T valuetype; 
    typedef ptrdifft differencetype;
    typedef const T *pointer;
    typedef const T &reference;
};

deque

作用：双端数组

底层实现：分段连续的空间，随时可以增加一段新空间并链接。效率显著低于vector，为了提高效率，在对deque进行排序时，可以先把deque复制到vector中排序，再复制回去。

中控器：一段一段的定量连续空间组成

数据结构：一个map，first和finish两个迭代器，map的大小

template<class T, class Alloc=alloc, size_t Bufsize = 0>
class deque {
public:
    typedef T value_type;
    typedef value_type pointer*;
    typedef size_t size_type;
    // ...
public:
    typedef _deque_iterator<T, T &, T *, BufSiz> iterator;
protected:
    typedef pointer *map_pointer;
protected:
    iterator start;
    iterator finish;
    map_pointer map;//指向map
    size_type map_size;//map可以容纳的指针数
}

迭代器

template<class T, class Ref, class Ptr, size_t BufSiz>
struct _deque_iterator {
    typedef _deque_iterator<T, T &, T *, BufSiz> iterator;
    typedef _deque_iterator<T, cosnt T &, const T *, BufSiz> const_iterator;
    static size_t buffer_size() { return _deque_buf_size(BufSiz, sizeof(T)); };
    typedef randem_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T **map_pointer;
    typedef _deque_iterator self;
    T *cur;
    T *first;
    T *last;
    map_pointer node;
    // ...
    //指定缓存区的大小
    inline size_t _deque_buf_size(size_t n, size_t sz) {
        return n != 0 ? n :
        (sz < 512 ? size_t(512 / sz) : size_t(1));
    }
}