C 的顺序容器

标准库定义的顺序容器类型有：vector、list、deque

   

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

顺序容器的定义

1、包含头文件：#include、#include、#include

2、格式：顺序容器名<类型> 变量名

3、容器元素的初始化

容器的构造函数
1、C c; 创建一个名为c的空容器。C是容器的类型名。
2、C c(c2) 创建容器c2的副本c；c与c2必需有相同的容器类型、相同类型的元素
3、C c(b,e) 创建c，其元素是迭代器b、c标志范围内元素的副本，适用于所有容器
4、C c(n,t) 用n个值为t的元素创建容器c，其中t必须为容器类型C的元素类型的值，或者是可转换为该类型的值 只适用于顺序容器
5、C c(n) 创建n个值初始化元素的容器C 只适用于顺序容器

程序

#include<iostream>
#include<list>
#include<vector>
#include<deque>
#include<string>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::list;
using std::deque;
using std::string;

int main()
{
    vector<int> c;
    vector<int>::iterator intr;
    if(c.empty())
        cout<<"the vector c is empty"<<endl;
    else
    {
        vector<int>::iterator in;
        for(in=c.begin();in!=c.end();in  )
            cout<<*in<<" ";
        cout<<endl;
    }

    vector<string> stv(6,"i am gyeve");
    vector<string>::iterator str;
    for(str=stv.begin();str!=stv.end();str  )
            cout<<*str<<" ";
    cout<<endl;

    stv.resize(8,"ok");
    vector<string> stv2(stv);
    for(str=stv2.begin();str!=stv2.end();str  )
            cout<<*str<<" ";
    cout<<endl;

    vector<int> num(4,3);
    vector<int> num1(  num.begin(),--num.end());
    for(intr=num1.begin();intr!=num1.end();intr  )
            cout<<*intr<<" ";
    cout<<endl;


    return 0;
}

结果

迭代器、迭代器的范围和迭代器失效的操作

1、在每个容器中都提供了共同工作的迭代器类型，与容器类型一样，所有迭代器提供了相同的接口

常用的迭代器运算
*iter 返回迭代器iter所指向的元素的引用
iter->mem 对iter进行解引用，获取其指定元素中名为mem的成员
iter 给iter加一，使其指向容器的下一个元素
iter
--iter 给iter减一，使其指向容器的上一个元素
iter--
iter1==iter2 比较两个迭代器是否相等，当两个迭代器指向同一个容器中的同一个元素时相等，或者当他们指向同一个容器的超出末端的下一个位置时，两个迭代器相等
iter1!=inter2

2、在C 中使用一对迭代器表示迭代器的范围，这两个迭代器分别指向同一个容器的两个元素或者超出末端的下一个位置。通常用beg、end 和 first 、last表示。具体表示的范围： [first,last)

：当first与last相等时，迭代器为空-------那么就必须要使用  c.empty()

：当first与last不等时，迭代器至少含有一个元素------迭代器和指针扮演相同的角色，因此没有明显的大小关系，在循环中判断结束的条件是   first != last

3、当对容器进行某些操作时，可能会引起该容器相应的迭代器失效。例如erase（）---该函数的作用是删除容器中的一个或几个元素，那么已经删除的元素的迭代均无效。当引用的操作可能引起迭代器无效时，此时对于表示的迭代器范围要及时进行更新.

list ok;
list::iterator first= ok.begin();
list::iterator last=ok.end();
list::iterator in;
for(in=first,in!=last;in  )
;
更改 :
for(in=first,in!=ok.end();in  )
;

顺序容器的操作

1、在顺序容器中提供了：在容器中添加元素、删除元素、改变大小……操作

2、容器中定义的类型别名------typedef

size_type 无符号整型，足以存储此容器的最大可能的容器长度
iterator 此容器类型的迭代容器类型
const_iterator 元素只读迭代器类型
reverse_iterator 按照逆序寻址单元的迭代器
const_reverse_iterator 元素为只读的逆序迭代器
difference_type 足够存储两个迭代器差值的有符号整型，可为负数
value_type 元素类型
reference 元素的左值类型，是value_type&的同义词
const_reference 元素的常量左值类型，等价于const value_type&

3、begin、end、在容器中添加元素

c.begin() 返回一个迭代器，它指向容器c的第一个元素
c.end() 返回一个迭代器，他指向容器c的最后一个元素的下一个元素
c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前的位置
-----------------------------------------------------------
c.push_back(t) 在容器的尾部添加一个值为t的元素，返回void类型
c.push_front(t) 在容器的头部添加一个值为t的元素，返回void类型，只适用于list、deque容器
c.insert(p,t) 在迭代器p所指向的元素前面插入值为t的新元素，返回指向新添加的元素的迭代器
c.insert(p,n,c) 在迭代器p指向的元素前面插入n个值为t新元素，返回void类型
c.insert(p,b,e) 在迭代器p指向的元素前面插入由迭代器b和e标记的范围内的元素，返回void

批注：添加元素可能使得迭代器失效。因此要及时更新迭代器：end

程序

#include<iostream>
#include<list>
#include<string>
#include<deque>
using std::cout;
using std::cin;
using std::endl;
using std::list;
using std::string;
using std::deque;
int main()
{
    list<int> ilist;
    for(size_t ix =0; ix!=4;ix  )
        ilist.push_back(ix);
    for(size_t ix=0; ix!=4;ix  )
        ilist.push_front(ix);
   for(list<int>::iterator it = ilist.begin();it!=ilist.end();it  )
       cout<<*it<<" ";
   cout<<endl;

    deque<string> sdeque(5,"deque");
    sdeque.insert(sdeque.begin(),"using");
    sdeque.insert(sdeque.end(),"end");

   for(deque<string>::iterator it = sdeque.begin();it!=sdeque.end();it  )
       cout<<*it<<" ";
   cout<<endl;
    return 0;
}

结果

4、容器的大小操作

c.size() 返回容器c中元素的个数，返回值的类型是c::size_type
c.max_size() 返回容器c中可容纳的最多元素的个数
c.empty() 判断容器c是否为空
c.resize(n) 改变容器c的大小，如果n
c.resize(n,t) 改变容器c的大小，如果n

批注：resize操作可能会使迭代器失效，在vector或者deque容器上做resize操作有可能使其所有的迭代器失效，对于所有类型的容器类型，如果resize()压缩了容器，使得已删除的元素迭代器失效

5、访问元素

：如果容器非空，那么容器类型的front和back成员将返回容器内部第一个元素和最后一个元素的引用；

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

在使用下标操作函数时必须保证在指定的下标位置上的元素确实存在

6、删除元素

：容器类型提供了同样的erase和特定的pop_front、pop_back操作来删除容器的元素

c.erase(p) 删除迭代器p指向的元素，返回删除元素的下一个元素
c.erase(b,e) 删除迭代器b、e标志的元素范围，返回被删除元素段的下一个元素
c.clear() 将容器c清空
c.pop_back() 将容器c的最后一元素删除，返回void
c.pop_front() 将容器c的第一个元素删除，返回void，只适用于list、deque

：对于要删除某个指定的元素时，需要找到该元素相应的迭代器----find（beg,end，search）

其中find函数在头文件algorithm中

7、赋值和swap

：c1=c2 对于赋值操作首先是删除左操作容器中的所有元素，然后将右操作数容器的所有元素插入到左边容器中，赋值后左右两边的容器相等，尽管赋值前两个容器的值可能不相等，但是赋值后两个容器都具有右操作数的长度

：assign 操作首先删除容器的所有元素，然后将其参数所指定的新元素插入到该容器中----因为assign操作首先会先删除容器中原有的存储的元素，因此，传递给assign函数的迭代器不能指向该函数的容器内的元素----c.assign(b,e)[重置c中的元素，将迭代器b、e标记的元素赋值给c]------c.assign(n,t)[重置c中的元素，将n个值为t的元素赋值给c]

：swap操作实现交换两个容器内部的所有元素的功能。要交换的类型必须匹配。对于swap函数它不会删除或插入任何元素，而是保证在常量时间内进行交换，并且迭代器也没有失效
程序

#include<iostream>
#include<algorithm>
#include<list>
#include<string>
#include<vector>
using std::cout;
using std::cin;
using std::vector;
using std::list;
using std::endl;
using std::string;
int main()
{
    vector<int> ok1(3,5);
    list<int> ok2(5,5);
    list<string> stringlist(3,"I am gyeve");

    vector<int>::iterator iter_vector = ok1.begin();
    list<int>::iterator iter_list = ok2.begin();
    list<string>::iterator lists, list_string ;


    cout<<"max_size " <<ok1.max_size()<<"  size:"<<ok1.size()<<" capacity: "<<ok1.capacity()<<endl;
    ok1.reserve(50);
    cout<<"max_size " <<ok1.max_size()<<"  size:"<<ok1.size()<<" capacity: "<<ok1.capacity()<<endl;
    /*对于capacity来讲通常比size要大于等于*/
    for(  ; iter_list !=ok2.end()&& iter_vector!=ok1.end();iter_list  ,iter_vector  )
    {
        if(*iter_list==*iter_vector)
            continue;
        else
            break;
    }
    if(iter_list==ok2.end()&&iter_vector==ok1.end())
        cout<<"equal "<<endl;
    else
        cout<<"not euqal "<<endl;

    ok1.resize(6,-1);
    cout<<"max_size " << ok1.max_size()<<"  size:"<<ok1.size()<<endl;
    for(iter_vector=ok1.begin(); iter_vector < ok1.end(); iter_vector  )
        cout<<*iter_vector<<" ";
    cout<<endl;

    if(!ok1.empty())
    {
        vector<int>::reference val = *ok1.begin();/*指向的是一个迭代器*/
        vector<int>::reference val1 = ok1.front();/*返回的直接是该类型的引用*/
        vector<int>::reference last = *--ok1.end();
        vector<int>::reference last1 = ok1.back();
        cout<<"ok1.begin "<<val<<" ok1.front "<<val<<"  ok1.end "<<last<<" ok1.back "<<last1<<endl;
    }
    cout<<"ok1[0] " << ok1[1]<<endl;/*只适用于vector 和 deque */
    cout<<"ok1.at(4) "<<ok1.at(4)<<endl;
    ok1.erase(ok1.begin(),ok1.end());
    if(ok1.empty())
        cout<<"ok1 empty ";
    else
        cout<<"ok1 not empty ";
    cout<<endl;

    ok2.clear();

    if(ok2.empty())
        cout<<"ok2 empty ";
    else
        cout<<"ok2 not empty ";
    cout<<endl;

    cout<<"before earse the string list : " ;
    for(lists=stringlist.begin(); lists!=stringlist.end(); lists  )
        cout<<*lists<<" ";
    cout<<endl;

    string search("I am gyeve");
    list_string=find( stringlist.begin(),stringlist.end(),search);

    if(list_string != stringlist.end())
        stringlist.erase(list_string);

    cout<<"after erase the string list : " ;

    for(lists=stringlist.begin(); lists !=stringlist.end(); lists  )
        cout<<" "<<*lists;
    cout<<endl;
    return 0;
}

结果

vector容器的自增长

：对于vector是已连续的空间进行存储的方便随机进行访问，如果要添加一个元素是vector容器没有预留的空间，那么必须将vector进行重新分配空间，，接着插入新元素，删除旧的存储空间。这样该容器的性能将会很慢，因此对于vector会预留一些空间------通过capacity、reserve进行操作

：capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素的总是

：reserve操作则告诉vector容器应该预留多少个元素存储空间