C++常见问题总结_顺序容器

╰+攻爆jí腚メ 2022-05-24 12:43 265阅读 0赞

## 顺序容器 ##

一个容器就是一些特定类型对象的集合。顺序容器的顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

**顺序容器类型**

vector;// 支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢。
    deque; // 双端队列。支持快速随机访问。在头尾位置插入删除速度很快。
    list; // 双向链表。只支持双向顺序访问。在list中任何位置进行插入或删除元素的速度都很快。
    forward_list;// 单向链表。只支持单向顺序访问。在任何位置插入删除都很快。
    array; //固定大小数组。支持快速随机访问，不能添加或删除元素。
    string;// 与vector相似的容器，但专门用于保存字符，随机访问快，在尾部插入/删除速度快。

**容器类型公共操作**  
这一部分介绍所有容器类型都提供的操作。

*  *容器类型成员*
    
    每个容器都定义了多个类型（类型别名）：

iterator // 容器类型的迭代器类型  vector<int>::iterator it=c.begin();
    const_iterator
    
    size_type //无符号整数类型，足够保存最大可能的容器大小 下表运算符接收的参数类型[] 标准库类型中定义体现于机器无关
    vector<int> :: size_type i;
    
    difference_type//带符号整数类型 ，足够保存两个迭代器之间的距离
    
    value_type//元素类型
    
    reference// 元素左值类型，与value_type&含义相同。
    const_reference//元素的const左值类型。

通过类型别名，我们可以在不了解容器中元素类型的情况下使用它。

list<string>::iterator iter;
    vector<int>::difference_type count;

*  *容器定义和初始化*

C c;//默认构造函数 （如果c是一个array，其中元素按默认初始化）否则为空。
    
    C c1(c2);//c1初始化为c2的拷贝。c1和c2元素类型必须相同（容器类型相同，保存类型相同） 对于array大小相同
    C c1=c2;
    
    C c{a,b,c,....};//初始化为列表中元素的拷贝，类型必须相容，对于array元素数目小于等于其大小，任何遗漏的元素进行值初始化
    C c={a,b,c,....};
    
    C c(b,e);//迭代器之间的内容，元素必须相容，初始化为迭代器指定范围中元素的拷贝。（array不适用）
    
    //只用顺序容器（不包括array）的构造函数才能接受大小参数
    C seq(n);//n个元素进行值初始化 ；这些构造函数是explicit的。（string不适用）
    C seq(n,t);//n个初始值为t的元素
    
    //array初始化（要指定大小）
    array<int,42>;
    array<string,10>;

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。不过当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，只要能将要拷贝的元素转换为要初始化的元素类型即可。

list<string> authors={
       "milton","shakespeare","austen"};
    vector<const char*>articles={
       "a","an","the"};
    
    list<string> lists(authors);//正确 类型匹配
    deque<string> authlist(authors);//错误：容器类型不匹配
    vector<string>words(articles); //错误：容器类型必须匹配
    
    //正确const char*元素转换为string
    forward_list<string> words(articles.begin(),articles.end());

1、与顺序容器大小相关的构造函数  
顺序容器（array除外）还提供另一个构造函数，他接受一个容器大小和一个（可选的）元素初始值，这些元素进行值初始化。（标准库创建一个值初始化器）

vector<int> ivec(10,-1);
    list<string> svec(10,"hi!");
    forward_list<int> ivec(10); //10个元素每个都初始化为0；
    deque<string> svec(10); //10个元素，每个都是空string。

**如果元素类型是内置类型或者具有默认构造函数的类类型，可以只为构造函数提供一个容器大小的参数。没有默认构造函数时，还必须显示指定一个元素初始值**

2、标准库array  
标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，还要指定容器的大小。

array<int,42>  //类型为：保存42个int的数组。
    array<string,10> //类型为：保存10个string的数组
    
    //使用时，必须同时指定元素类型和大小
    array<int,10>::size_type i; 
    array<int>::size_type i;//错误 array<int> 不是一个类型

由于大小固定的特性，它的构造函数都会确定容器的大小，与其他容器不同，一个默认构造的array是非空的，他包含了与其大小一样多的元素。这些元素都被默认初始化。

array<int,10> ia1; //10个默认初始化的int。
    array<int,10>ia2={
       1,2,3,4,5,6,7,8,9,10};//列表初始化
    array<int,10>ia3={
       42};//ia3[0]为42，其余元素值初始化为0。
    
    int digs[10]={
       0,1,2,3,4,5,6,7,8,9};
    int cpy[10]=digs;  //错误内置数组不支持拷贝或赋值
    array digits<int,10>={
       0,1,2,3,4,5,6,7,8,9};
    array<int,10>copy=digits;

*  *赋值和swap*

容器赋值运算

//与内置数组不同，array类型允许赋值。
    C1=C2;//相同的类型（对于array大小也是其类型的一部分）
    
    c={a,b,c,.....};//array 不适用
    array<int,10>a1={
       1,2,3,4,5,6,7,8,9,10};
    array<int,10>a2={
       0};
    a1=a2;// 替换a1中的元素
    a2={
       0}; //错误：不能将一个花括号列表赋予数组，由于右边运算对象的大小可能与左边不同。所以不支持，并也不适用于assign
    
    //assign操作不适用于array 允许从类型相容进行赋值
    seq.assign(b,e);//b,e一对迭代器
    
    seq.assign(il);//il为初始化列表
    
    seq.assign(n,t);//替换n个值为t的元素

1、使用assign(仅顺序容器)  
成员assign允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值

list<string> names;
    vector<const char*>oldstyle;
    names=oldstyle;//错误容器类型不匹配
    names.assign(oldstyle.begin(),oldstyle.end());//正确
    
    list<string> slist1(1);//一个元素为空string
    slist1.assign(10,"hiya!");//10个元素每个都是hiya!

由于就元素被替代，因此传递给assign的迭代器不能指向调用assign的容器。

2、使用swap

c1.swap(c2); //交换元素，必须具有相同的类型。通常swap比从c2向c1拷贝元素快得多。
    swap(c1,c2);
    //
    vector<int>svc1(10);
    vector<int>svc2(24);
    swap(svc1,svc2);

交换后svc2包含十个元素，SVC1包含24个元素，元素本身并不交换只是交换两个容器内部的数据结构（array除外，会真正交换元素）。  
元素不会移动的事实意味着，除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍然指向操作之前的那些元素。例如：iter在swap指向是svec1\[3\]的string，那么在swap之后它指向svec2\[3\]的元素。与其他容器不同对一个string调用swap会导致迭代器、引用和指针失效。  
对于array，swap会真正交换它们的元素，因此，交换两个array的时间与array中的元素成正比。对于array，在swap操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经与另一个array中的元素对调了。

*  *容器大小操作*

除了一个例外，每个容器类型都有三个与大小相关的操作

size();
    empty();
    // 返回一个大于或等于该类型容器所能容纳的最大元素的值，forward_list不支持
    max_size();

*  *关系运算符*  
    每个容器类型都支持相等运算符（==和！=）；除了无序关联容器外的所有容器都支持关系运算符（> >= < <=）。关系运算符左右两边的运算对向必须是相同类型的容器且必须保存相同类型的元素。

--------------------

两个容器相同的大小且所有元素都两两对应相等，则这两个容器对应相等；否则不等。  
两个容器大小不同，但较小容器中的元素都等于较大容器中的对应元素，则较小容器小于较大容器。  
两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不想等的元素的比较结果。

--------------------

vector<int> v1={
       1,3,5,7,9,12};
    vector<int> v2={
       1,3,9};
    vector<int> v3={
       1,3,5,7};
    vector<int> v4={
       1,3,5,7,9,12};
    v1<v2;//true
    v1<v3;//false
    v1==v4;//true
    v1==v2;//false

容器的关系运算符使用元素的关系运算符完成比较，只有当其元素类型也定义了相应的比较运算符时，在可以使用关系运算符来比较两个容器。

**顺序容器操作**  
下面我们将介绍顺序容器所特有的操作。

*  *向顺序容器中添加元素*

//array不支持这些操作
    c.push_back(t); //返回void
    c.emplace(args);
    
    c.push_front(t);//返回void
    c.emplace(args);
    
    c.insert(p,t);// 迭代器p之前插入元素，返回指向新添加元素的迭代器
    c.emplace(p,args);
    
    c.insert(p,n,t);//在迭代器插入n个值为t的元素，返回指向新添加的第一个元素的迭代器，n=0时返回p；
    
    c.insert(p,b,e);//迭代器b和e之间的元素插入p之前 ，返回指向新添加的第一个元素的迭代器，（b,和e不能为c中的迭代器）
    
    c.insert(p,il);//il为元素值列表

1、push\_back  
除array和forward\_list之外，每个顺序容器都支持。

void pluralize(size_t cnt,string&word)
    {
        if(cnt>1)
            word.push_back('s');//等价于word+='s';
    }

**当我们用一个对象来初始化容器时，或是将一个对象插入到容器中时，实际放入到容器中的是对象值的一个拷贝，而不是对象本身**

2、push\_front  
vector和string不支持，此操作将元素插入容器的首位置。

list <int> ilist;
    for(size_t ix=0;ix!=4;++ix)
    {
        ilist.push_front(ix);
    }
    //保存序列3、2、1、0。

3、insert  
forward\_list有自己版本的insert

//特定位置添加元素
    vector<string> svec;
    list<string> slist;
    //等价于调用slist.push_front("hello!");
    slist.insert(slist.begin(),"hello!");
    //vector 不支持push_front操作，但我们可以插入到begin()之前
    svec.insert(slist.begin(),"hello!");
    
    
    //插入范围内的元素
    svec.insert(svec.end(),10,"Anna");//10个元素插入到svec末尾
    
    vector <string> v={
       "quasi","simab","frollo","scar"};
    slist.insert(slist,begin(),v.end()-2,v.end());
    slist.insert(slist.end(),{
       "asd","ad","asda"});
    
    //运行时错误，迭代器表示要拷贝的范围时，不能指向与目的位置相同的容器。
    slist.insert(slist.begin(),slist.begin(),slist.end());
    
    
    //使用insert的返回值
    list<string> lst
    list<string> ::iterator iter=lst.begin();
    while(cin>>word)
        iter=lst.insert(iter,word);//等价于调用push_front

4、使用emplace  
当我们调用一个emplace成员函数时，是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

//必须与元素的构造函数向匹配
    c.emplace_back("asdasd",25,19.0);
    c.push_back(sales_data("asdasd",25,19.0));

在调用empalce\_back时是在容器管理的内存空间中直接创建对象，而使用push\_back则会创建一个局部临时对象，并将其压入容器中。

*  *访问元素*

c为空时，函数行为未定义
    c.back()；//返回尾元素的引用
    c.front();//返回首元素的引用
    
    c[n];//返回对应元素的引用
    c.at(n);//返回引用，下表越界时会抛出out_of_range异常

在容器中访问元素的成员函数返回的都是引用，如果容器中保存的对象是一个const对象，则返回值是const的引用。

if(!c.empty())
    {
        c.front()=42;
        auto &v=c.back();
        v=1024;
        auto v2=c.back();
        v2=0; //未改变c中的元素，它是c.back()的一个拷贝
    }
    
    vector<string> svec;
    cout<<svec[0];    //运行时错误，svec中没有元素。
    cout<<svec.at(0); //抛出一个out_of_range异常

*  *删除元素*

c.pop_back(); //返回void
    c.pop_front();
    
    c.erase(p);   //返回被删除元素之后的迭代器
    c.erase(b,e);// 返回最后一个被删除元素之后的迭代器
    
    c.clear();

**删除deque中除收尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector和string中删除点之后未知的迭代器、引用和指针都会失效。**

1、pop\_back和pop\_front  
vector和string不支持pop\_front，forward\_list不支持pop\_back。与元素访问成员函数类似，我们不能对一个空容器执行弹出操作。

2、erase

//从容器内部删除一个元素
    //删除list中的所有奇数
    list<int> lst={
       0,1,2,3,4,5,6,7,8,9};
    auto it=lst.begin();
    while(it!=lst.end())
    {
        if(*it%2)
            it=lst.erase(it);
        else
            ++it;
    }
    
    //删除多个元素,删除两个迭代器表示的范围内的元素 左闭右开区间
    //返回指向最后一个被删除元素值后位置的迭代器
    elem1=slist.erase(elem1,elem2);//调用后elem1==elem2

*  *改变容器的大小*

//array不支持
    
    c.resize(n);
    //调整c的大小为n，多出的元素被丢弃，添加的新元素进行值初始化 由于进行值初始化所以要求其中元素的类型有默认构造函数
    c.resize(n,t);
    // 调整c的大小为n，任何被新添加的元素初始化为值t
    
    list<int> ilist(10,42);   //10个int，每个都是42
    ilist.resize(15);        //末尾加5个0
    ilist.resize(25,-1);    // 末尾加10个-1
    ilist.resize(5);       // 末尾删除20个元素

**vector对象如何增长**  
当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。这样就不需要每次台南佳新元素都重新分配容器的内存空间。（在每次重新分配内存空间时都要移动所有元素）

//shrink_to_fit()适用于vector string 和deque
    //capacity和reserve只适用于vector string
    
    c.shrink_to_fit();//将capacity()减少与其size()相同大小 
    
    c.capacity();//不重新分配内存的话 c可以保存多少元素 
    
    c.reserve(n);//分配至少能容纳n个元素的空间

只有当内存空间超过当前的容量时，reverse()调用才会改变vector的容量。如果需求大小大于当前容量，reserve至少分配与需求一样大的内存空间。  
如果需求大小小于当前容量 ，reserve什么也不做。  
调用reserve永远也不会减少容器占用的内存空间。类似的resize成员函数只改变容器中元素的数目，而不是容器的容量。  
在新标准中，我们可以调用shrink\_to\_fit来要求容器退回不需要的内存空间。只是一个请求 标准库不保证退还。  
容器的size是指他已经保存元素的数目；而capacity实在不分配新的内存的前提下他最多可以保存多少元素。  
**每个vector实现都可选择自己的内存分配策略。但是必须遵守一条原则是：只有当迫不得已时才可以分配新的内存空间**