第九章 顺序容器

1. 顺序容器包括

      接受容器大小做形参的构造函数只是用于顺序容器,而关联容器不支持这种初始化.

2.C++中,大多数类型都可用作容器的元素类型.容器元素类型必须满足以下两个约束:

      1).元素类型必须支持赋值运算

      2).元素类型的对象必须可以复制

注:没有元素是引用类型的容器,也没有元素是IO类型的容器

3.使用迭代器编写程序时,必须留意那些操作会使迭代器失效.使用无效的迭代器将会导致严重的运行错误.(在使用迭代器时,通常可以编写程序使得要求迭代器有效的代码范围相对较短,然后,在该范围内,严格检查每一条语句,判断是否有元素添加或删除,从而相应的调整迭代器的值.

关于容器大小比较,其原理与泛型算法一样.需要支持原子的大小比较操作符.

#include <iostream>
    #include <vector>
    #include <set>
    #include <list>
    #include <string>
    #include <bitset>
    #include <algorithm>

    using namespace std;

    struct Usr
    {
        int i;
        string strUiD;          //用户标示ID
        string strSrnName;      //用户名称
        string strNickName;     //昵称
        string strDesc;         //个人简介
        string strGender;       //性别
        string strIcon;         //头像图片
        string strVtitle;       //暂时不知
        string strVType;        //用户是够通过真实身份验证(0未通过)

        Usr( string strUiD )
        {
            this->strUiD = strUiD;
        }
    };
    inline bool operator== ( const Usr& usrOne,const Usr& usrTwo )
    {
        if ( usrOne.strUiD == usrTwo.strUiD  )
        {
            return true;
        }
        return false;
    }
    void main()
    {
        vector<Usr> vecUsr;
        Usr usr( "ysl" );
        vecUsr.push_back( usr );

        usr.strUiD = "abc";
        usr.strVtitle = "初级";
        vecUsr.push_back( usr );

        usr.strUiD = "abc";
        vector<Usr>::const_iterator cIter= find( vecUsr.begin(),vecUsr.end(),usr );
        if ( cIter != vecUsr.end() )
        {
            cout<<cIter->strVtitle<<endl;
        }
        system( "pause" );
    }

4.顺序容器的操作

●顺序容器库中添加元素的操作

c.push_back(t)      在容器c的尾部添加值为t的元素,返回void

c.push_front(t)      在容器c的前端添加值为t的元素,返回void(只适用list和deque容器类型)

c.insert(p,t)                   再迭代器p所指向的元素前插入值为t的新元素.返回指向新添加元素的迭代器

c.insert(p,n,t)                添加n个值为t的新元素,返回void类型

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

注:不要存储end操作迭代器,添加或删除deque和vector容器的元素都会导致存储的迭代器失败.

●顺序容器大小的操作

c.maxsize()                   返回容器c可容纳的最多元素个数

c.resize(n)                     调整容器c的大小,如果n则删除多出来的元素,否则使用默认初始化多余的元素

c.resize(n,t)                   调整c的大小,如果n添加元素t

●访问顺序容器的元素

c.back()                        返回容器c的最后一个元素的引用

c.front()                        返回容器c的第一个元素的引用

●删除顺序容器内元素的操作

c.erase(p)                      删除p所指的元素

c.erase(b,e)                   删除b-e之间的元素

c.clear()                        删除容器的所有元素

c.pop_back()                删除容器的最后一个元素

c.pop_front()                删除容器的第一个元素(仅适合list和deque)

注意:pop_front和pop_back函数的返回值并不是删除的元素的值,而是void

●赋值与swap

c1 == c2                       删除容器c1的所有元素,然后将c2的元素复制给c1

c1.swap(c2)                  交换内容:调用玩该函数后,c1中存放的是c2原来的元素.c1存放的是c2原来的元素,该函数的执行速度通常要比将c2复制到c1的操作快

c.assign(b,e)                 重新设置c的元素:将迭代器b和e标志的范围内所有元素复制到c中(它也是先清空c)

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

注意:关于swap的一个重要的问题在于:该操作不会删除或插入任何元素,而且保证在正常时间内实现交换.由于容器内没有移动任何元素,因此迭代器不会失效

举例如下:

            vectorvec1;

            vectorvec2;

            for (inti = 0;i<10;i++)

            {

                   vec1.push_back(i);

            }

 

            for (intj = 0;j<5;j++)

            {

                   vec2.push_back(j+20);

            }

            std::vector::iteratoriter1 =vec1.begin();

            std::vector::iteratoriter2 =vec2.begin();

      

            vec1.swap(vec2);

            cout<<"vec1.begin= "<<*iter1<<"/nvec2.begin= "<<*iter2<<endl;

5.对于vector容器,系统在分配容量时要比当前所需的空间多一些.vector容器预留了这些额外的储存区,用于存放新添加的元素.

      size和capacity的区别:前者值容器当前拥有的元素个数,后者值容器在必须分配新存储空间之前可以存储的元素的总数.

reserve(n)    设置vector应该预留多少个元素的存储空间

capacity()    返回分配新存储之前可以存储空间之前可以存储的元素总数

      当vector容器不得不分配新的存储空间时,以加倍当前容量的分配策略实现重新分配

6.使用容器类型的法则:

1).如果程序要求随机访问元素,则应该使用vector或者deque容器;

2).如果程序必须在容器的中间位置插入或删除元素,则应采用list容器

3).如果程序不是在容器的中间位置,而是在容器的首部或者尾部插入或删除元素,则应采用deque容器

4).如果只需在读取输入时在容器的中间位置插入元素,然后随机访问元素,则可考虑在输入时将元素读入到一个list容器,接着对此容器重新排序,以适应其顺序访问,然后将其复制到vector容器.

注意:通常来说,除非找到选择使用其他容器的更好的理由,否则vector容器都是最佳选择,并建议多使用迭代器而非下标

7.string不支持带有单个容器长度作为参数的构造函数(其函数很多,而且在实际上用不了那么多,所以在此偷下懒,省略,如果需要用到它则可查阅MSDN).

8.除了顺序容器,标准库还提供了=三种顺序容器适配器:queue,priority_queue和stack:需要包含的相关头文件:#include

                                                #include

stack适配器所关联的基础容器可以是任意一种顺序容器,而queue适配器要求其关联的基础容器必须提供push_front操作,因此只能建立在list上,而不能建立在vector上

●栈适配器:

      s.empty()     如果栈为空

      s.size()         返回栈种元素的个数

      s.pop()         删除栈顶元素,但不返回其值

      s.top()          返回栈顶元素的值,但不删除它

      s.push()        在栈顶压入新元素

●队列和优先级队列支持的操作

      q.empty()     如果队列为空

      q.size()         返回队列中元素的个数

      q.pop()         删除队首元素,但不删除其值

      q.front()       返回队首元素的值(只是用于队列)

      q.back()       返回队尾元素的值,但不删除它(只是用于队列)

      q.top()         返回具有最高有优先级的元素值(该操作只适于优先级队列)

      q.push()       对于queue,在队尾压入一个新元素

                           对priority_queue,在基于优先级的适当位置插入新元素                 

常见问题列举:

error C2653: 'vector >' : is not a class or namespace name

error C2065: 'size_type' : undeclared identifier

error C2146: syntax error : missing ';' before identifier 'ix'

error C2065: 'ix' : undeclared identifier

error C2143: syntax error : missing ')' before '++'

warning C4552: '!=' : operator has no effect; expected operator with side-effect

error C2059: syntax error : ';'

error C2059: syntax error : ')'

error C2143: syntax error : missing ';' before '{'

处理方法:在vector前加上std::

标准库定义了三种顺序容器类型：vector、list

和 deque（是双端队列“double-ended queue”的简写，发音为“deck”）。

    它们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。

    标准库还提供了三种容器适配器（adaptors）。

    实际上，适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。顺序容器适配器包括 stack、queue 和 priority_queue 类型 

顺序容器
vector	支持快速随机访问
list	支持快速插入/删除
deque	双端队列
顺序容器适配器
stack	后进先出（LIFO）堆栈
queue	先进先出（FIFO）队列
priority_queue	有优先级管理的队列

    三种容器均支持 resieze() 操作，重新划定容器大小，且此函数有重载。

 

    vector : vector和built-in数组类似，是一个在堆上建立的一维数组，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符。vector因为存储在堆上，所以支持erase(
), resieze()（重新划分容器容量）等操作； vector不用担心越界当空间不够用的时候，系统会自动按照一定的比例（对capacity( )大小）进行扩充。在vector序列末尾添加(push_back( ))或者删除(pop_back(
))对象效率高，在中间进行插入或删除效率很低，主要是要进行元素的移动和内存的拷贝，原因就在于当内存不够用的时候要执行重新分配内存，拷贝对象到新存 储区，销毁old对象，释放内存等操作，如果对象很多的话，这种操作代价是相当高的。为了减少这种代价，使用vector最理想的情况就是事先知道所要装 入的对象数目，用成员函式 reserve( ) 预定下来；vector最大的优点莫过于是检索（用operator[ ]）速度在这三个容器中是最快的。

 

    list : list的本质是一个双向链表(根据sgistl源代码)，内存空间不连续，通过指针进行操作。说道链表，它的高效率首先表现是插入，删除元素，进行排序 等等需要移动大量元素的操作。显然链表没有检索操作operator[ ], 也就是说不能对链表进行随机访问，而只能从头至尾地遍历，这是它的一个缺陷。list有不同于前两者的某些成员方法，如合并list的方法splice( ), 排序sort( ),交换list 的方法swap( )等等。

    deque : deque是一个double-ended。queue是由多个连续内存块构成，deque是list和vector的兼容，分为多个块，每一个块大小是 512字节，块通过map块管理，map块里保存每个块得首地址。因此该容器也有索引操作operator[ ]，效率没vector高。另外，deque比vector多了push_front( ) & pop_front( )操作。在两端进行此操作时与list的效率 差不多。

  

    下面是选择顺序容器类型的一些准则 

    1. 如果我们需要随机访问一个容器则vector要比list好得多

    2. 如果我们已知要存储元素的个数则vector 又是一个比list好的选择。

    3. 如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector好 

    4. 除非我们需要在容器首部插入和删除元素否则vector要比deque好

    5. 如果只在容易的首部和尾部插入数据元素，则选择deque

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

 

    学习顺序容器最重要的是了解每种容器的结构原理进而在实际应用中选择最合适的容器。  

 

    三种容器都是范型类型，可以定义不同的类型容器。

    容器元素类型必须满足以下两个约束：

      - 元素类型必须支持赋值运算。

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

  

    顺序容器有大量的属性和操作，最常用的是迭代器，增加，删除元素。

    常用迭代器运算

*iter	返回迭代器 iter 所指向的元素的引用
iter->mem	对 iter 进行解引用，获取指定元素中名为 mem 的成员。等效于 (*iter).mem
++iter iter++	给 iter 加 1，使其指向容器里的下一个元素
--iter iter--	给 iter 减 1，使其指向容器里的前一个元素
iter1 == iter2 iter1 != iter2	比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等
iter + n iter - n	在迭代器上加（减）整数值 n，将产生指向容器中前面（后面）第 n 个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置
iter1 += iter2 iter1 -= iter2	这里迭代器加减法的复合赋值运算：将 iter1 加上或减去 iter2 的运算结果赋给 iter1
iter1 - iter2	两个迭代器的减法，其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置   只适用于 vector 和 deque 容器
>, >=, <, <=	迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前，则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置   只适用于 vector 和 deque 容器

    最重要的迭代器begin() 和end() 。

 

    顺序容器添加元素操作

c.push_back(t)	在容器 c 的尾部添加值为 t 的元素。返回 void 类型
c.push_front(t)	在容器 c 的前端添加值为 t 的元素。返回 void 类型   只适用于 vector 和 deque 容器
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.size()	返回容器 c 中的元素个数。返回类型为 c::size_type
c.max_size()	返回容器 c 可容纳的最多元素个数，返回类型为 c::size_type
c.empty()	返回标记容器大小是否为 0 的布尔值
c.resize(n)	调整容器 c 的长度大小，使其能容纳 n 个元素，如果 n < c.size()，则删除多出来的元素；否则，添加采用值初始化的新元素
c.resize(n,t)	调整容器 c 的长度大小，使其能容纳 n 个元素。所有新添加的元素值都为 t

    看下面例子：

    list ilist(10, 42); //  定义10个值为 42 的的list
    ilist.resize(15);           //  增加了5个 0值项
    ilist.resize(25, -1);      // 增加 10 个-1值项
    ilist.resize(5);             // 删除了20个项
   

    resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。

    对于所有的容器类型，如果 resize 操作压缩了容器，则指向已删除的元素迭代器失效。    

 

    vector 预分配机制: 可以在元素不存在的情况下预分配一段空间，为以后的存储做准备。这段空间可以用reserve()调节。capacity()返回的值就是可以存放元素的个数。capacity() - size()就是下次重新进行空间分配前的预留元素个数。至于max_size() 指的是一个vector结构可供储存元素的个数的上线，通常是由于寻址空间决定的。  

 

    访问顺序容器内元素的操作

c.back()	返回容器 c 的最后一个元素的引用。如果 c 为空，则该操作未定义
c.front()	返回容器 c 的第一个元素的引用。如果 c 为空，则该操作未定义
c[n]	返回下标为 n 的元素的引用 如果 n <0 或 n >= c.size()，则该操作未定义   只适用于 vector 和 deque 容器
c.at(n)	返回下标为 n 的元素的引用。如果下标越界，则该操作未定义 只适用于 vector 和 deque 容器

 

使用下标运算的另一个可选方案是 at 成员函数。这个函数的行为和下标运算相似，但是如果给出的下标无效，at 函数将会抛出 out_of_range 异常：

vector svec;   // 空容器
cout << svec[0];    // run-time error: There are no elements in svec!
cout << svec.at(0); // throws out_of_range exception
   

顺序容器有大量的成员可用，学习容器不需要记住所有成员操作时可查阅相关文档。

 

顺序容器还有三种适配器，主要作用是包装其它容器使之具有某种操作特征。

1 stack 堆栈适配器             ( 可用的容器类型 vector deque list)
2 queue 队列适配器             ( 可用的容器类型 deque list)
3 priority_queue 优先级队列   (可用的容器类型 deque vector)

 

下面的例子用三种适配器将顺序容器 list 分别包装成 堆栈，队列，具有优先级的队列

stack 用法：
#include <iostream>
#include <stack> //堆栈适配器头文件
#include <list>
using namespace std;

int main(void)
{
    std::stack< int,std::list<int> > charStack;
    cout << "入栈:" << endl;
    for(int i=0;i<10;i++)
    {
       cout<<i+66<<endl;
       charStack.push(66+i);
    }
    cout<<"出栈:"<<endl;
    int size=charStack.size();
    for (i=0;i<size;i++)
    {
       cout<<charStack.top()<<endl;
       charStack.pop();
    }
    cout<<endl;
    return 0;
}

queue用法：
#include <iostream>
#include <queue>
#include <list>
using namespace std;

int main()
{
    std::queue< int,list<int> > intQueue;
    cout << "入队:" << endl;
    for(int i=1;i<=10;i++)
    {
       intQueue.push(i*100);
       cout<<i*100<<endl;
    }
    cout<<"出队:"<<endl;
    int size=intQueue.size();
    for(i=0;i<size;i++)
    {
       cout<<intQueue.front()<<endl;
       intQueue.pop();
    }
    return 0;
}

priority_queue 用法：
#include <iostream>
#include <queue>
#include <list>
using namespace std;

int main()
{
    std::priority_queue< int,vector<int>,std::greater<int> > intPQueue; //优先级greater<type> 可换成 less<type>
    intPQueue.push(100);
    intPQueue.push(500);
    intPQueue.push(600);
    intPQueue.push(200);
    intPQueue.push(300);
    intPQueue.push(400);
    int size=intPQueue.size();
    for(int i=0;i<size;i++)
    {
       cout<<intPQueue.top()<<endl;
       intPQueue.pop();
    }
    return 0;
}