C++标准库容器总结

    C++标准库顺序容器
    所有的标准库容器都是类模板，用以存储单一类型元素的集合。顺序容器按元素位置存储访问，关联容器按键存储访问。
    1 顺序容器
      将单一类型的元素按顺序存储，以下标来访问元素。标准库定义了三种顺序容器：vector，list及deque。vector支持快速随机访问；list支持快速插入删除；deque是双端队列。
      a）容器初始化：
      C c; 创建一个名为c的容器，容器类型为C，如vector或list，T为容器内元素类型。适用于所有容器；
      C c1(c); 创建容器c的副本，c1和c必须具有相同的容器类型和元素类型，适用于所有容器；
      C c(b,e); 创建容器c,元素是迭代器b,e标示范围内的副本，适用于所有容器；
      C c(n,t); 创建容器c，元素为n个值为t的值，t的类型必须是容器C的元素类型或者可以转换为该类型，只适用于顺序容器；
      C c(n); 创建具有n个值初始化元素的容器c,元素类型为值n的类型，只适用于顺序容器；
      注：* 在使用迭代器复制元素时，不要求双方容器类型相同，容器内元素类型也可以不同，只要元素类型可以相互转换即可；
          * 迭代器范围[b,e)是左闭右开区间，即e所指的元素并未被复制，e只是提供了停止复制的条件；
     
      b）元素类型约束：
      元素类型必须满足：
      元素类型必须支持赋值；
      元素类型的对象必须可以复制；
      关联容器的键类型必须且只要实现<操作符即可。
      注：*大多数类型都能满足上述最低限制的约束。例外，引用不支持一般意义上的赋值，IO库类型不支持复制或赋值，所以两者以及auto_ptr类型都不能作为容器的元素类型。
     
    2 迭代器
      一种数据类型，用于遍历容器内元素，标准库容器都有自己的迭代器，配合算法使用。迭代器是标准库容器类型的配套设施。
      a）迭代器范围是一个左闭右开的区间，即[b,e);
      b）一些容器操作会使指向容器元素的迭代器失效，要特别注意。
      c）const_iterator迭代器和const迭代器的区别；
      注：*迭代器往往和容器及泛型算法结合使用，本节仅简单描述，后面会有详尽的介绍。
     
    3 顺序容器的操作
      a）begin和end操作：
        c.begin(),c.end(),c.rbegin(),c.rend();
        非const版本：vector::iterator = c.begin();
                     vector::reverse_iterator = c.rbegin();
        const版本：  vector::const_iterator = c.begin();
                     vector::const_reverse_iterator = c.rbegin();
      b）添加操作：
         c.push_back();在容器尾部添加值为t的元素，返回void;
         c.push_front();在容器头部添加值为t的元素，返回void，
            只适用于list和deque；
         c.insert(p,t);在迭代器p所指向的元素前面插入值为t的元素，返回指向t的迭代器；
         c.insert(p,n,t);在迭代器p所指向的元素前面插入n个值为t的元素，返回void；
         c.insert(p,b,e);在迭代器p所指向的元素前面插入由迭代器b和e标记的范围内的元素，返回void；
      注：*添加元素可能会使迭代器失效，所以每次操作之后都应该及时更新迭代器；
     
      c）容器大小：
         c.size();返回容器内元素个数，返回类型为c::size_type;
         c.max_size();返回容器内最多可容纳的元素个数，返回类型为c::size_type;
         c.empty();测试容器内是否有元素；
         c.resize(n);调整容器大小，使其能容纳n个元素；
         c.resize(n,t);调整容器大小，使其能容纳n个元素，新添加元素以t初始化；
      注：*c.resize(n)中，当n < c.size(),删除多出来的元素；否则，采用值初始化添加新元素；
          *c.reserve(n);仅调整c的最大容量，并不初始化元素；
          *c.resize(n)和c.resize(n,t)可能会使迭代器失效；
     
      d）访问元素：
         c.front();返回容器内第一个元素的引用，如果c为空，该操作未定义；
         c.back();返回容器内最后一个元素的引用，如果c为空，该操作未定义；
         c[n];和c.at(n);返回下标为n的元素的引用，n越界时，该操作未定义，只用于vector和deque；
     
      e）删除元素：
         c.erase(p);删除迭代器p指向的元素，返回一个指向被删除元素后面的元素的迭代器；
         c.erase(b,e);删除迭代器b和e标记范围内的所有元素，返回一个指向被删除元素段后面的元素的迭代器；
         c.clear();删除容器内的所有元素，返回void；
         c.pop_back();删除容器的最后一个元素，返回void；
         c.pop_front();删除容器的第一个元素，返回void，只适用于list和deque；
      注：*删除元素可能会使迭代器失效，所以每次操作之后都应该及时更新迭代器；
     
      f）赋值操作：
     
         cl = c2;删除cl的所有元素，将c2的所有元素复制给c1，c1和c2的容器类型及元素类型必须相同；
         cl.swap(c2);交换c1和c2中的所有元素，c1和c2的容器类型及元素类型必须相同；
         c.assign(b,e);重新给c赋值，内容为b和e所标记范围内的元素，b和e必须不是指向c中的元素的迭代器；
         c.assign(n,t);将c中的元素重新设置为n个值为t的元素；
      注：*赋值和assign操作会使左操作数中的迭代器失效，但是swap操作后，迭代器仍然指向相同的元素；
          *swap操作在常量时间内完成，没有移动任何元素；
     
    4 vector容器的自增长
     
      vector预留了额外的存储区，用于存放新添加的元素，当现有的空间用完之后再自动重新分配存储空间。capacity()和reserve()使程序员可以和vector的内存分配的实现部分交互工作。
      a）c.capacity();获取c在要分配更多的存储空间之前所能容纳的元素总数；
      b）c.reserve(n);c应该预留n个元素的存储空间；
      注：*c.resize(n);和c.reserve(n);的区别很微妙,前者对多出来的新元素进行值初始化；后者仅仅调整存储空间，而不进行任何初始化。
          *c.max_size();和c.capacity();的区别也很微妙。简单的说，c.max_size();是c.capacity();的最大值，前者是一个常量，值取决于操作系统或C++库的实现，而后者则是一个变量。
         有例子程序。
          *c.size(); <= c.capacity(); <= c.max_size();
     
    5 顺序容器的选用
      a）顺序容器的特点：
      vector容器可以实现高效的随机访问，但是除了容器尾部外，在其他任何位置添加和删除元素却很低效；
      list容器可以实现高效的添加删除，但是随机访问的效率却很低；
      deque容器支持对所有元素的随机访问，在容器的首部和尾部可以高效地添加删除元素，但是在中间位置添加删除元素却又很低效。
      注：*应用中占优势的操作将决定使用哪种类型的容器。
     
    6 容器适配器
      适配器概念的定义：是一种标准库类型，函数或迭代器，使一种标准库类型，函数或迭代器的行为类似于另一种标准库类型，函数或迭代器。本质上，适配器是使一种事物的行为类似于另一种事物行为的机制。容器适配器在其基础容器上定义一个新的接口，使基础容器拥有另一种不同容器的工作方式。
      顺序容器适配器：stack（栈），queue（队列），priority_queue（优先级队列）。
      a）容器适配器通用的操作和类型：
         size_type 一种类型，存储此适配器类型最大对象的长度；
         value_type 元素类型；
         container_type 基础容器的类型；
         A a;创建一个新的容器适配器；
         A a(c);创建一个新的容器适配器a,初始化为c的副本；
         关系操作符：==，!=，<,<=,>,>=。

      b）适配器的初始化：
         deque deq;
         stack stk();
         stack stk(deq);
      注：*stack适配器和queue适配器的基础容器默认为deque，priority_queue的基础容器默认为vector。
     
      c）覆盖基础容器类型：
         deque deq;
         stack > stk(deq);
      注：*stack适配器关联的基础容器可以是任意一种顺序容器类型；
          *queue适配器要求基础容器必须提供push_front操作，只能建立在list容器上；
          *priority_queue适配器要求提供随机访问操作，只能建立在vector或deque容器上；
     
      d）栈适配器的操作：
         s.empty();返回栈是否为空；
         s.size();返回栈中的元素个数；
         s.pop();删除栈顶元素，返回void；
         s.top();返回栈顶元素，但不删除该元素；
         s.push(item);在栈顶压入新元素；
      注：*程序员不能直接使用栈适配器所关联的基础容器的操作。
     
      e）队列和优先级队列的操作：
         q.empty();返回队列是否为空；
         q.size();返回队列中的元素个数；
         q.pop();删除队首元素，返回void；
         q.front();返回队首元素，但不删除元素，只适用于队列；
         q.back();返回队尾元素，但不删除元素，只适用于队列；
         q.top();返回具有最高优先级的元素，但不删除该元素，只适用于优先级队列；
         q.push(item);对于queue，在队尾压入一个元素；对于priority_queue，在基于优先级的适当位置插入一个元素。

1 关联容器定义
  存储对象集合的类型，支持通过键的高效访问。和顺序容器的本质差别在于：顺序容器通过元素在容器中的位置顺序存储和访问元素，而关联容器却是依靠键。map和set是两个基本的关联容器类型，map以键值对的形式组织存储元素，而set仅存储键。
2 pair类型（在utility头文件中定义）
  a）pair类型的操作：
     pair p1;创建一个空的pair对象，两个元素类型分别是T1和T2，值初始化；
     pair p1(v1,v2);创建一个pair对象，具有两个元素v1和v2，类型分别是T1和T2；
     make_pair(v1,v2);以v1和v2作为值创建一个pair对象，元素类型分别是v1和v2的类型；
     p1.first;返回值为v1；
     p1.second;返回值为v2；
     p1 < p2;小于运算遵循字典次序；
     p1 == p2;如果两个pair对象的first成员和second成员依次相等，则两个pair对象相等；
  注：*pair类型属于类模板。
3 关联容器和顺序容器的操作区别
  a）共有的操作：
     C c;
     C c(c2);
     C c(b,e);
     关系操作符；
     c.begin();
     c.end();
     c.rbegin();
     c.rend();
     size_type
     iterator
     const_iterator
     reverse_iterator
     const_reverse_iterator
     difference_type 存储两个迭代器差值的有符号整型，可为负数
     value_type 对于map，是pair 类型
     reference value_type& 的同义词
     const_reference 等效于 const value_type&
     swap和赋值操作；
     clear和erase操作；
     容器大小的操作（resize除外）；
  b）关联容器不提供的操作：
     front，push_front，pop_front，back，push_back，pop_back
4 map类型
  map类型可理解为关联数组，关联的本质在于元素的值与某个特定的键相关联，而与元素的位置无关。
  a）map对象的定义：
     map m;创建一个空的map对象m，其键和值的类型分别为k，v；
     map m(m2);创建m2的副本m，m必须具有和m2相同的键类型和值类型；
     map m(b,e);创建一个map对象m，存储迭代器[b,e)标记范围内的所有元素的副本，元素类型必须能转换为pair；
  注：*键类型必须能够定义<操作符。
  b）map定义的类型：
     map::key_type;键的类型
     map::mapped_type;元素的类型
     map::value_type;pair::key_type,map::mapped_type>
  注：*map迭代器解引用生成pair::key_type,map::mapped_type>类型的对象，pair对象的值成员可以修改，但键成员不能修改；
5 map容器的操作
  a）添加元素：
     m.insert(e);e为map的value_type类型的值。如果键e.first不存在，则添加一个值为e.second的值，如果存在，则m不变。该操作返回一个pair类型的对象，包含一个指向新添加元素的map迭代器，以及一个bool值，表示插入是否成功；
     m.insert(b,e);将迭代器b和e标示区间内的所有元素插入到m中，所插入的元素必须为m.value_typpe类型，返回void；
     m.insert(iter,e);如果m中不存在键e.first，则在m中以iter为起点搜索新元素的位置并插入，返回一个指向新添加元素的迭代器。
     m["zhu"] = 1;在map中查找键为"zhu"的元素，如果没有，则插入一个新的键值对，键为"zhu"，值采用初始化，再将1赋给元素的值；
  b）查询元素：
     m.count(k);返回m中k键出现的次数，返回值只能是0或1；
     m.find(k);如果m中存在键为k的元素，则返回指向该元素的迭代器，否则，返回m.end()；
  c）删除元素：
     m.erase(k);删除m中键为k的元素，返回值为所删除元素的个数，只能是0或1，类型为size_type；
     m.erase(p);删除m中迭代器p所指向的元素，p所指向的元素必须存在，返回void；
     m.erase(b,e);删除m中由迭代器[b,e)标示范围内的元素，[b,e)必须是有效范围，返回void。
6 set类型
  set容器单单存储键的集合。
  a）set容器不支持的操作：
     set不支持下标操作；
     没有定义mapped_type，value_type对应的是key_type，即元素的类型；
     与map一样，set容器中的键也必须唯一，而且不能修改。
  注：*set容器支持map的大部分的操作。
7 multimap和multiset
  a）元素的添加删除：
     insert 操作每次都会添加一个元素；
     erase 带有一个键参数的该操作将删除拥有该键的所有元素，返回删除的元素个数，而带有一个或一对迭代器参数，则只删除指定的元素，返回void。
  b）查找元素：
     m.count，m.find()
     m.lower_bound(k) 返回一个指向键不小于k的元素的迭代器；
     m.upper_bound(k) 返回一个指向键大于k的第一个元素的迭代器；
     m.equal_range(k) 返回一个pair对象，first成员等价于m.lower_bound(k);second成员等价于m.upper_bound(k);
  注：*三种查找方法都基于一个事实，在multimap中，同一个键所关联的元素必然相邻存放。