在前几天的阿里面试过程中，问到了我标准模板库的继承体系。平时开发对vector,list, map,set ,stack等容器用的比较多，但是没有深入研究过。经历过面试，发现了很多需要完善和提高的地方。
但是有个问题哦，标准模板库中得几大组件没有啥继承关系，只是说有某些容器之间有适配关系。

Container(容器):

所谓容器，就是存放数据的仓库，定义了数据在内存中的组织方式，

主要：有序列式容器（线性数据结构）、关联连式容器（非线性数据结构：树结构）

序列容器，典型的容器vector，相对于C++内嵌的数组，vector的优点是支持数据的动态扩展。

而空间的动态扩展，有空间配置器配置。它会为容器提供空间分配的策略，比如空间不够时增长的幅度。

关联式容器：关联式容器的思想类似于关系数据库，由key-value组成。 主要分为map和set，hash及其相关衍生.

Iteraotrs(迭代器)：

迭代器统一了容器的访问操作，很好的东西。想到了迭代器模式

Container<Type> cons; 
for (Container<Type>::iterator iter = cons.begin();  
     iter != cons.end(); iter++) 
{ 
    visit(iter); 
} 

看看《STL源码分析》中关于vector的定义

template<class T, class Alloc = alloc> 
class vector 
{ 
    typedef T value_type; 
    typedef value_type* pointer; 
    typedef value_type* iterator; 
    ...... 
} 

这里很明显的是通过typedef定义将指针定义为vector的迭代器，提供统一访问，但是本质上还是指针哈。

VC的vector的迭代器定义：是一个类哈，有许多数据组成了迭代器的定义，其中有指针，有引用。

template<class _Myvec> 
    class _Vector_iterator 
        : public _Vector_const_iterator<_Myvec> 
    {   // iterator for mutable vector 
public: 
    typedef _Vector_iterator<_Myvec> _Myiter; 
    typedef _Vector_const_iterator<_Myvec> _Mybase; 
    typedef random_access_iterator_tag iterator_category; 
 
    typedef typename _Myvec::value_type value_type; 
    typedef typename _Myvec::difference_type difference_type; 
    typedef typename _Myvec::pointer pointer; 
    typedef typename _Myvec::reference reference; 
        ...... 
} 

pointer定义，就是某个数据类型的指针

typedef value_type _FARQ *pointer; 

再看下hashtable中的迭代器的定义：

...... 
struct _hashtable_iterator 
{ 
    ...... 
    node* cur; 
    hashtable* ht; 
    ..... 
} 

在hashtable迭代器中，有两个指针，一是当前节点的指针，二是buckets vector的指针。

综上所述，所谓迭代器，就是对指针以及其他辅助信息的一个封装。对数据的访问一定是通过地址访问，地址是必须的，所以地址是迭代器中不可缺少的信息。
在迭代器的使用中，常常遇到的一个问题就是，在进行数据的插入删除时的失效问题！其实就是指针的问题哈

Allocator(空间配置器)：

空间配置器用于屏蔽容器关于内存管理的细节。比如容器内存的申请释放，当内存不够时采用怎样的一种策略。在我们平常的使用中，

vector<strudent> stus; 

并没有制定容器的空间配置方案，于是采用默认的配置方案，其实我们是可以自己编写空间配置方案，并将该方案实施于某个容器。(CustomAlloc是自定义的命名空间，并实现了空间配置方案allocator)

vector<int, CustomAlloc::allocator<int>> datas; 

可以在自定义的方案中进行内存管理。

Algorithms(算法)：

提供了大量常用、通过的算法，比如比较、查询、数据移动、复制、交换等等。
基础算法：min, max, swap
排序：sort
替换：replace
查找：find
此处不一一列举

Function Objects（函数对象）：

函数对象，简单的理解就是将一个函数封装为对象，但是它的作用是为容器的操作提供依据。我进行比较大小，根据什么比，函数对象提供，查询，匹配的规则是什么，函数对象提供。

例如：

1. 对vector容器进行排序，排序的标准是？

2. 对容器中得数据进行查询，查询的标准是？

通过函数对象，可以灵活的编写操作依据，并注入到操作函数中。

为sort函数编写Compare()

为find_if编写Query()

此处写了个实例，说明一下用法：
业务对象定义：

class student 
{ 
public: 
        string name; 
        int age; 
 
        student(string name, int age) 
        { 
             this->name = name; 
             this->age = age; 
        } 
 
        student(const student &stu) 
        { 
                *this = stu; 
        } 
 
        student& operator=(const student &stu) 
        { 
            this->name = stu.name; 
            this->age = stu.age; 
            return *this; 
        } 
}; 

函数对象定义，说明对象之间比较的依据，此处依据是年龄

struct Compare : public std::binary_function<student, student, bool> 
{ 
    bool operator()(const student stu1, const student stu2) const 
    { 
            if (stu1.age < stu2.age) 
                return true; 
            else  
                return false; 
    } 
}; 

测试程序：

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    vector<student> stus; 
    srand((unsigned int)time(NULL)); 
    string strName = "student"; 
    for (int i = 0; i < 10; i++) 
    { 
        int val = rand()/10; 
        char dataBuf[20]; 
        memset(dataBuf, 0, 20); 
        itoa(val, dataBuf, 10); 
        student stu(dataBuf, val); 
        stus.push_back(stu); 
    } 
 
    for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++) 
        cout<<iter->name<<"--"<< iter->age<<endl; 
    cout<<"-----------------------------"<<endl; 
    sort(stus.begin(), stus.end(),  Compare()); 
    for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++) 
        cout<<iter->name<<"--"<< iter->age<<endl; 
 
    getchar(); 
    return 0; 
} 

测试结果：将原本随机插入的数据根据年龄进行了排序

注：此处是对几个组件的简要说明，并未详细深入