STL

前言：一直在使用容器，但从未系统地总结，希望此次总结，能带给自己对容器更加深入的理解和使用。

一、顺序容器的定义

      *所有容器都是类模板，将单一类型元素聚集起来，然后根据位置来存储和访问这些元素的容器，就是顺序容器。

 1、容器元素的初始化

      <1>、创建一个名为c的空容器， C<T> c;

      例：vector<CString> strVector;

      <2>、创建容器的副本， C c(C2);

      注意：容器类型、元素类型必须一致

      例：list<char*> cList;

             list<char*> cCopyList(cList);

      <3>、根据迭代器范围创建容器副本， C c(b,e);

      注意：不要求容器类型，此种初始化方式间接提供了一种“不同种容器间的拷贝”的方法

            *1、容器间的拷贝

                  例：list<string> slist(5, "hello");

                         list<string>::iterator it = slist.begin();

                         vector<string> sVector(it, it+2);

            *2、用数组初始化容器，（因为指针就是迭代器，所以可以这么做）

                  例：char *words[] = {"up", "down", "left", "right"};

                         size_t words_size = sizeof(words)/sizeof(words[0]);

                         list<string> wordlist(words, words+words_size);

      <4>、创建指定元素数目的容器（仅适用于顺序容器）

            *1、指定元素数目和初始化值，（元素数目可以是常量或非常量表达式）

            例：const list<int>::size_type list_size = 64;

                   list<string> slist(list_size, "YES");// slist中含有64个元素，每个元素都被初始化为“YES”字符串；

            *2、仅指定元素数目，不指定元素的初始化值

            例：list<int> iList(list_size);//iList列表中有64个元素，每个元素值为0；

            注意：这种初始化式，容器中的元素类型必须是内置类型、复合类型或是提供了默认构造的类类型，（因为此时的元素初始化值由标准库完成）。

           注意一种特殊情况：

           例：假设类Foo没有默认构造函数，但提供了一个int型的构造函数，则下列构造合法：

           vector<Foo> ok(10, 1);

           注意：只有同时指定每个元素的初始化式，才能通过这种方式构造，如：vector<Foo> bad(10)；就是非法的。

 

2、容器内元素的类型约束

      容器元素类型需满足以下要求：

            * 元素类型必须支持赋值运算； 

            * 元素类型的对象必须可以复制。

      大多数类型满足以上要求，包括容器类型本身；但是以下类型不支持这些要求：

            *引用，（不支持一般意义的赋值运算）;

            *输入输出（IO）,（不支持复制或赋值）;

            *anto_ptr

      例子：容器的容器

      vector< vector<string> > lines;//lines中的元素类型为vector<string>;

二、迭代器与迭代器范围

      <1>、常用的迭代器运算

       *iter  ;  iter->mem;     ++iter;    iter++;     --iter;   iter--;   iter1 == iter2;  iter1 != iter2;

      <2>、vector 和 deque 容器的迭代器提供额外的运算

       注意：C++定义的容器类型中，只有vector 和 deque容器提供的运算集合是：迭代器的算术运算、所有的关系运算（适用于所有容器的关系运算只有==”和“!=”）;  

       iter + n; iter - n; //将迭代器指针位移n位

       iter1 += iter2 ; 

       iter1 -= iter2; //

       iter1 - iter2;

       >, >=, <, <= 

     注意：list容器的迭代器既不支持算术运算（加法或减法），也不支持关系运算（<=, <, >=, >）,只支持自增、自减、相等、不等运算。

       例：将一个list容器内的元素逆序输出：

       list<int> m_list;

       ...;

       list<int>::iterator it = m_list.end();

       for( ; it != m_list.begin(); )

       {

              cout<<*(--it)<<" "

       }

       cout<<endl;

      <3>、迭代器的范围：

      begin()获得容器的第一个元素， end()获得容器最后一个元素的下一个位置；

     容器元素的范围：[ xx.begin(), xx.end() );

     <4>、注意使迭代器无效的操作

     编程时要特别注意，哪些操作会使迭代器失效，使用无效迭代器将导致严重的运行时错误，例如erase函数。

     任何insert或push操作都可能导致迭代器失效，当编写循环将元素插入到vector或deque容器中时，程序必须确保迭代器在每次循环后都得到更新。

     例如以下代码：

     vector<int>::iterator first = v.begin(), last = v.end();

     while(first != last)

     {

           first  = v.insert(++first, 42);

           ++first;

     }

    注意：此处存在容器的插入操作，将导致迭代器失效，然而局部变量last既不指向容器的元素，也不指向容器末端的下一位置，所以会产生运行时错误。

     正确的循环应该是：

     while(first != v.end())

     {

           first = v.insert(++first, 42);

           ++first;

     }

三、顺序容器的操作

      <1>、容器定义的类型

      size_type；无符号整型，足以存储该容器类型的最大可能容器长度

      iterator;迭代器

      const_iterator;只读迭代器

      reverse_iterator;逆序迭代器

      const reverse_iterator;只读逆序迭代器

      difference_type;有符号整型，足以存储两个迭代器的差值，可以为负

      value_type;元素类型

      reference;元素引用类型，等价于 value_type&;

      const_reference;元素的常量引用类型，等价于 const value_type&;

 

     <2>、begin和end操作

     c.begin();返回一个迭代器，它指向容器c的第一个元素；

     c.end(); 返回一个迭代器，它指向容器c最后一个元素的下一个位置；

     此外，还有c.rbegin(); c.rend();

     以上操作都有两个版本：一个是const成员、另一个是非const成员；如果容器是const类型，这些操作返回const iterator或const reverse_iterator类型；如果容器类型不是const类型，返回iterator或reverse_iterator类型。

   

    <3>、向顺序容器中添加元素

     c.push_back(t);返回void

     c.push_front(t);//仅适用于list和deque容器类型；返回void

     c.insert(p,t);//在迭代器p所指向的元素前面插入值为t的新元素；返回指向新元素的迭代器；

     c.insert(p, n, t);//在迭代器p所指向的元素的前面插入n个值为t的新元素;返回void

     c.insert(p,b,e);//在迭代器p所指的元素的前面插入由迭代器b和e标记的范围内的元素，返回void;

     特别注意：在向容器中添加元素时，系统是将元素值复制到容器中，容器中存放的是元素的副本，与元素原始值互不相关。

     注意：c.insert(p,t);的返回值是指向新元素的迭代器，因此可以利用该迭代器重复插入元素：如下

            list<string> lst;

            list<string>::iterator iter = lst.begin();

            while(cin>> word)

                  iter = lst.insert(iter, word);

     <4>、容器类型的比较

     所有的容器类型都支持用关系运算符来实现两个容器的比较。比较的容器必须是同一类型，元素类型也相同。

     注意，容器的比较是基于容器内元素的比较。容器的比较使用元素类型定义的同一关系运算符，如果容器的元素类型不支持这种操作符，那么容器就不能使用这种操作符比较。

     类似于字符串的比较：

     *** 两个容器长度相等且元素都相等，那么两个容器相等；

     *** 两个容器长度不等，且较短的容器中每个元素都等于较长容器中的元素，那么较短容器小于较长容器；

     *** 两个容器都不是对方的初始化子序列，那么容器比较结果取决于所比较的第一个不相等的元素。

     <5>、容器大小的操作

     c.size() ;      c.empty();

     c.max_size();//返回容器c可容纳的最多元素个数；

     c.resize(n);//调整容器c的长度大小，使其能容纳n个元素，如果n<c.size()，则删除多出来的元素；

     c.resize(n,t);//调整容器c的大小，使其能容纳n个元素，所有新添加的元素值都为t;

     <6>、访问元素

     c.back();   c.front();

     c[n]://返回下标为n的元素的引用，只适用于vector和deque容器；

     c.at(n);//返回下标为n的元素的引用，只适用于vector和deque容器；

     注意：使用越界的下标，或调用空容器的front或back函数，都将导致程序出现严重的错误。

            at(n)成员函数，在给出的下标无效时，会抛出异常，建议使用。

     <6>、删除元素

     c.erase(p);//删除迭代器p所指向的元素。

     c.erase(b,e);//删除迭代器b和e所标记的范围内的所有元素。

     c.clear(); //删除容器c中的所有元素。

     c.pop_back();//删除容器中的最后一个元素，返回void，如果为空容器，则该函数未定义。

     c.pop_front();//删除容器中的第一个元素u，返回void，如果为空容器，则该函数未定义。只适用于list或deque容器。

     <7>、容器的赋值操作

     c1 = c2；等价于

     c1.erase(c1.begin(), c2.end());  c1.insert(c1.begin(), c2.begin(), c2.end());

     顺序容器的操作：

           c1.swap(c2)；//交换内容，调用函数后，c1中存放的是c2原来的元素，c2中存放的是c1原来的元素。c1和c2的类型必须相同。

     c.assign(b,e)；//重新设置c的元素，将迭代器b和e标记的范围内所有的元素复制到c中，b和e必须不是指向c中的元素的迭代器。

     c.assign(n,t);//将容器c重新设置为存储n个值为t的元素。

 

四、vector容器的自增长

      由于vector容器要分配连续的存储空间，list分配不连续的存储空间，一般而言，使用list容器优于vector容器，但是实际情况却是，比起list和dqeue容器，vector的增长效率通常会更高。因为，标准库的实现者使用“以最小的代价连续存储元素”的内存分配策略，由此带来的访问元素的便利弥补了其存储的代价。

     <1>、capacity和reserve成员

     capacity成员的功能：获取容器需要分配更多的存储空间之前能够存储的元素总数；（vecotr的size与“不用再开辟空间之前，还能存储的元素个数”之和）

     reserve成员的功能：设置vector容器应该应该预留多少个元素的存储空间。（vector每次重新分配空间时，空间大小（元素）的增量）

     <2>、capacity与size的区别

      size指的是容器当前拥有的元素个数；而capacity则指的是容器在必须分配新存储空间之前可以存储的元素总数。

五、容器的选用

      <1>、vector和deque容器提供了对元素的快速随机访问，但是付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大。

      list类型在任何位置都能快速插入和删除，但付出的代价是元素的随机访问的开销较大。

      注：通常来说，除非找到选择使用其他容器的更好理由，否则vector容器都是最佳选择。

     <2>、选择容器的原则

     **1、 如果程序要求随机访问元素，则应使用vector或deque容器。

     **2、如果要求在容器的中间插入、删除元素，首选list。

     **3、如果要求在容器的首尾插入或删除元素，首选deque。

     **4、如果只在读取输入的时候在容器的中间插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个list容器中，接着对此容器重新排序，使其适合顺序访问，然后将排序后的list容器复制到一个vector容器。

     **5、在选择vector或list时，不能确定要选哪一种，可以先选vector，然后使用vector和list都有的操作，使用迭代器而不是下标，并且避免随机访问元素。这样写代码，必要时，可很方便地将程序从使用vector容器修改为使用list容器。

    

六、容器适配器

       适配器（adaptor）:就是接口转换器，信息接口、如笔记本的电源适配器，就是将220v电压转换为19v电压。其本质是使一种事物的行为类似于另一种事物的行为的机制。

       容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如stack(栈)适配器可以使任何一种顺序容器以栈的方式工作。

       在标准库中适配器，包含容器适配器、迭代器适配器和函数适配器；

      标准库提供三种顺序容器适配器：queue、priority_queue和stack。

      <1>、默认的stack和queue都是基于deque容器实现的，而priority_queue则是在vector容器上实现的。

      例如：stack<int> stk(m_container);//这里的m_container只能是deque类型。

      但是，在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型实参，可覆盖其关联的基础容器类型。

      例如：stack< string, vector<string> > str_stk(svec);//这里的svec只能是vector容器。

      注意：stack栈可以建立在vector、list或deque容器之上；

                 queue适配器要求其关联的基础类型必须提供push_front运算，因此只能建立在list容器之上。

                 priority_queue适配器要求提供随机访问功能，因此可以建立在vector或deque容器上，但不能建立在list容器上。

     <2>、适配器的关系运算

     两个相同类型的适配器可以做关系运算，（只要基础元素类型支持关系运算即可）。关系运算的结构取决于第一个不相等的元素。