顺序容器

╰半橙微兮° 2022-08-24 05:25 146阅读 0赞

容器容纳特定类型对象的集合。前面已经用过一种容器类型：标准库vector类型，这是一种顺序容器。它将单一类型的元素聚集起来成为容器，然后根据位置来存储和访问这些元素，这就是顺序容器。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。在顺序容器中，所有的元素根据其位置排列和访问。顺序容器共享一组通用的已标准化的接口：如果两种顺序容器都提供某种操作，那么该操作具有接口和含义。

vector是最常用的容器类型，它支持对元素的快速随机访问。可以高效地在vector容器尾部添加和删除元素，而在其他位置上的插入和删除运算则要付出比较昂贵的代价。deque类与vector相似，但它还支持在deque首部的快速插入和删除运算。list类只支持元素的顺序访问，但在list的内部任何位置插入和删除元素都非常快。

容器定义的操作非常少，只定义了构造函数，添加和删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器操作。其他的一些有用的操作，如 排序，查找等则不是有容器类型定义，而是由标准算法定义的。

顺序容器的种类有：

vector，支持快速随机访问（vector元素是连续存放的）

list，支持快速插入/删除

deque，双端队列

顺序容器适配器：

stack，后进先出栈

queue，先进先出队列

priority\_queue ，有优先级管理的队列

**迭代器**：所有的迭代器都有相同的借口(其实就是有相同的成员函数)，都支持==和!=的关系操作符，但是对于vector和deque这两个容器却提供了额外的关系操作符，他们支持(假设迭代器对象为iter)的额外操作有：iter+n，iter1 += iter2，>，>=，<，<=。

向容器内添加元素的方法有通用的insert接口和push\_back接口，同时，对于list和deue而言还有push\_front接口，需要注意的是，当修改了容器之后，原先的容器的迭代器可能会失效，最好的例子就是，如果在修改或者删除容器内的元素之前存储了end返回的迭代器，那么当修改完容器之后，这个迭代器会失效，所以在代码中应该尽量避免存储end返回的迭代器。

**容器的大小操作**：resize(int )和resize(int, T),max\_size()。resize用来改变容器所包含的元素个数，如果当前容器的长度比resize给出的长度要大，那么容器就会将容器的多出来的后面部分从容器中删除，若当前容器的大小小于resize给出的 长度，则系统就会在容器的后部添加元素。

赋值(asign)和交换(swap)，asign首先会将原先容器内的所有元素删除，然后再将新的值复制到容器内，li = li1相当于：

li.erase(li.begin(), li.end());//删除

li.insert(li.begin(),li1.begin(),li1.end());

swap操作是一个常量级的函数调用，不会删除和插入任何元素，因此迭代器不会失效。(我觉得这swap操作相当于换名，操作的对象相互换名字)

# 1 顺序容器的定义 #

为了定义一个容器类型的对象，必须包含相关的头文件，即下列头文件之一：

\#include<vector>

\#include<list>

\#include<deque>

例：

vector<string> svec;//empty vector that can hold strings

list<int> ilist;//empty list that can hold int

deque<A> a\_item;//empty deque that can hold A

# 2 容器元素的初始化 #

除了默认构造函数外，容器类型还提供其他的构造函数，使程序员可以指定元素的初值。

C<T> c; 创建一个名为c的空容器。C是容器类型名，如vector，T是元素类型，如int string。使用于所有容器；

C c(c2); 创建容器c2的副本c；c和c2必须具有相同的容器类型，并存放相同类型的元素。使用于所有的容器；

C c(b,e);创建c，其元素是迭代器b和e标示的范围内元素的副本。适用于所有的容器；

C c(n,t)；用n个值为t的元素创建容器c，其中值t必须是容器类型C的元素类型的值，或者是可以转换为该类型的值。只适用于顺序容器。

C c(n);创建有n个值初始化元素的容器c。只适用与顺序容器。

# 示例： #

vector<int> ivec;
    vector<int> ivec2(ivec);//将一个容器初始化为另一个容器的副本
     
    //初始化为一段元素的副本
    //initialize slist with copy of each element of svec
    list<string> slist(svec.begin(),svec.end());
    //find midpoint int the vector
    vector<string>::iterator mid=svec.begin()+svec.end()/2;
    //initialize front with first half of svec:The elements up to but not including *mid
    deque<string> front(svec.begin(),mid);
    //initialize back with second half of svec:The elements *mid through end of svec
    deque<string> front(mid,svec.end());
    我们知道：指针就是迭代器，因此允许通过使用内置数组中的一对指针初始化容器也就不奇怪了：
    char *words[] ={"a","b","c","d"};
    //calculate how many elements in word
    size_t words_size=sizeof(words)/sizeof(char *);
    将数组长度加到指向第一个元素的指针上就可以得到指向超出数组末端的下一位置的指针。通过指向第一个元素的指针words和指向数组中最后一个元素的下一位置的指针，实现了words2的初始化。其中第二个指针提供停止复制的条件，其所指向的位置上存放的元素并没有复制。
    //use entire array to initialize words2
    list<string> words2(words,words+words_size);
     
    //分配和初始化指定数目的元素
    const list<int>::size_type list_size =64;
    list<string> slist(list_size,"eh?");
    这段代码表示slist含有64个元素，每个元素都被初始化为“eh?”字符串。

# 3 容器内元素的类型约束 #

C++语言中，大多数类型都可以用作容器的元素类型。容器元素类型必须满足下面两个约束：

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

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

此外，关联容器的键类型还需满足其他的约束，后续再关联容器中再介绍。

# 4 容器的内存管理 #

所有的容器都提供（有效的）动态内存管理。程序员在容器中添加元素时，不必操心元素存放在哪里。容器自己实现其存储管理。vector的元素是连续存放的，而其他的则相当于链表的内存结构。容器的max\_zise(0是和平台相关的，是说容器最大是多少，而capacity()则是相对于特定的容器在不需要重新分配内存的情况下所能容纳的最大元素个数。举个例子，对于局部数组而言(windows下面的),由于栈的最大值为1M，所以在数组最大只能声明为1M大小，这个相当于max\_size，但是特定的数组，比如你声明了数组int a\[20\]，这个数组最大能够容纳20个元素，此即为capacity()。

vector<int> vec(5,10);
    vector<int> vec1(2,1);
    vector<char> vec2(4,'2');
     
    //查看capacity 
    cout << "vec的capacity:" << vec.capacity() << endl;//输出5 
    cout << vec.max_size() << endl; 
    cout << vec1.max_size() << endl; 
    cout << vec2.max_size() << endl; 
    //插入一个元素后 ,超过capacity，所以需要重新分配内存
    //capacity变大 
    vec.push_back(13); 
    cout << "vec的capacity:" << vec.capacity() << endl;
    cout << vec.max_size() << endl; 
    //删除一个元素后，不需要重新分配内存，所以capacity不变 
    vec.pop_back(); 
    cout << "vec的capacity:" << vec.capacity() << endl;
    cout << vec.max_size() << endl;

对于上述代码的运行结果发现，vec和vec1的max\_size是相同的，而vec2大约是vec的4倍，可以想象，编译器会给一个容器对象固定的大小，但是因容器内的元素类型不一样，所以会产生max\_size不一样，但是对于相同的元素类型的容器，其大小是一样的。对于上述代码中的vec1和vec2，如果对vec1的max\_size结果成衣4，那么就会发现此时他们几乎就相等了。如下图所示：

从结果可以看出，就是数学中所说的约等于。

#include <iostream>
    #include <vector>
    #include <list>
    #include <deque>
    #include <string>
     
    using namespace std;
    int main(int argc, char *argv[])
    {
    //定义一个1长度为10的list容器 
    list<string> li(2,"init_data");
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //push_front 
    li.push_front("push_front");
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //push_back 
    li.push_back("push_back");
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //insert 
    li.insert(++li.begin(),"insert(p,t)");
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    li.insert(--li.end(),2,"insert(p,n,t)");
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl << endl;
    //insert
    /******************************************************** 
     *li.insert(li.end(),li.begin(),--li.end());
     *上面的这一句有问题，修改了容器，所以两处使用end会出错 ，
     *该语句原本想把原容器内的内容复制一遍到后面，可是不成功，
     *我的运行结果是容器内剩最后的一个元素没有复制，所以下
     *面的resize不能回复容器
     ********************************************************/ 
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //resize
    //容器大小减半 
    cout << "容器大小减半:" << endl;
    li.resize(li.size()/2); 
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //删除容器的元素,clear可以删除所有元素， 
    //当然也可以通过pop_front和pop_back删除元素 
    cout << "删除首元素:" << endl; 
    li.erase(li.begin()); 
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl; 
    //容器大小再减半 
    cout << "容器大小减半:" << endl;
    li.resize(li.size()/2); 
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << endl;
    //容器大小翻倍 
    cout << "容器大小翻倍:" << endl;
    //resize变大的话，若不指定增加元素值，采用值初始化(初始化为对应的数据类型的默认值)
    li.resize(li.size()*2,"resize_add"); 
    for(list<string>::const_iterator i=li.begin(); i!=li.end(); i++)
    cout << *i << "  ";
    cout << "大小为" << li.size() << endl;
    //back和font的使用
    //back为*--end()，front为*begin() 
    cout << "front:" << li.front() << "  back:" << li.back() << "  \n" << endl;
    vector<int> vec(5,10);
    vector<int> vec1(2,1);
    vector<char> vec2(4,'2');
    //查看capacity 
    cout << "vec的capacity:" << vec.capacity() << endl;//输出5 
    cout << vec.max_size() << endl; 
    cout << "vec1.max_size()*4:" << vec1.max_size()*4 << endl; 
    cout << "vec2.max_size():" << vec2.max_size() << endl; 
    //插入一个元素后 ,超过capacity，所以需要重新分配内存
    //capacity变大 
    vec.push_back(13); 
    cout << "vec的capacity:" << vec.capacity() << endl;
    cout << vec.max_size() << endl; 
    //删除一个元素后，不需要重新分配内存，所以capacity不变 
    vec.pop_back(); 
    cout << "vec的capacity:" << vec.capacity() << endl;
    cout << vec.max_size() << endl; 
    return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220823/f187e698cf574cc596c735a562555e07.png