C++ 标准模板库组件介绍

12年前

在前几天的阿里面试过程中，问到了我标准模板库的继承体系。平时开发对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;      ......  }

这里很明显的是通过宏定义将指针定义为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;  }

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