一个博客

随便写写

0%

容器和迭代器

发表于 更新于 分类于

本文主要通过介绍C++中最重要的容器vector来让大家认识容器。

容器

容器是C++ STL（标准模板库）中的重要部分，容器实现了很多常用数据结构，而且容器全是模板类，有很强的通用性，以及提供了一套能够配合STL的算法库使用的迭代器接口。在大多数情况下STL的函数效率都优于大多数人写的等效的函数，保证了通用性的同时也保证了高效。

比赛时间有限，而且为了避免犯错，我们没有必要在比赛的时候手搓复杂的数据结构（如哈希表和红黑树等，代码可能要上百行，而且如果写的时候神智不清还容易写错的）。所以建议大家多使用标准库，使代码简洁的同时降低出错和保证高效。

vector的初始化

vector是C++中最重要的容器。vector字面意思是向量，实际使用上就相当于动态扩容的数组。

使用vector需要引入头文件#include<vector>，后面每种容器都要单独引入头文件，如果不想一个个引入，也可以使用万能头#include<bits/stdc++.h>，这样会引入标准库的所有头文件，但是会较大增加编译时间，所以大家看情况使用。

下面这段代码创建了一个有10个int元素，并且每个元素初始化为0的int类型的vector

1
vector<int> A(10,0);

vector初始化的两个参数都是可选的，第一个参数是元素个数（上面为10，默认为0），第二个参数是每个元素的默认值（上面为0，默认为类默认构造函数）。还有另一种初始化赋值为数组的方法
1
vector<int> A{1,2,3,4,5};

vector的动态扩容

之前说过vector是动态扩容的数组，vector保存的数据在内存上是连续的，是先分配了一大块内存，然后再写入数据。如果之前分配的内存写满了，会重新分配另一块内存，大小为之前的两倍，然后将原本的内存上的数据复制到新的内存上，然后再释放掉原来的内存。这样会带来不可忽视的开销，所以如果要进行可能会扩大vector容器大小的操作之前，可以手动给它分配一块较大的内存，以减少中途多次动态扩容带来的开销，一般算法题中需要用到的数据大小的范围是可以预测的。

前面我们知道可以在初始化vector的时候指定容器的大小，如果后续想要改变容器的大小可以通过.resize()，试试下面的代码

1
2
3
4
vector<int> A(5,0);
cout<<A.size()<<endl;
A.resize(10,0);
cout<<A.size()<<endl;

resize的第一个参数是新的容器大小，第二个参数是新增的元素的值，如果不指定就使用默认初始化，resize同时执行了分配内存和容器扩容。

我们也可以使用reserve来分配vector的内存大小，但是不改变容器的大小，这个一般跟emplace_back一起使用。

1
2
3
4
vector<int> A(5,0);
cout<<A.size()<<endl;
A.reserve(10);
cout<<A.size()<<endl;

vector的遍历

按照C语言的思维，遍历一个数组，需要知道它的大小，然后用for循环遍历，就像下面这样

1
2
3
for(int i=0;i!=A.size();++i)
    cout<<A[i]<<" ";
cout<<endl;

.size()是vector的一个函数，也是每个容器都有的函数，返回容器的大小。并且vector重载了[]运算符（读作“下标”运算符），可以通过下标访问vector中保存的数据。

在C++中，遍历容器有四种写法，上面是最普通的写法。最简单最优雅的写法是基于范围的for循环，

1
2
3
for(auto a:A)
    cout<<a<<" ";
cout<<endl;

a为A中的每个元素，可以使用auto自动推断a的类型，以及也可以将a声明为引用来修改A中的元素的值以及避免拷贝开销，就像下面这样
1
2
3
4
5
6
for(auto&a:A)
    cin>>a;

for(auto a:A)
    cout<<a<<" ";
cout<<endl;

最麻烦但是最实用的写法是使用迭代器的for循环，迭代器简单来说就是类似C语言中的指针的东西。重载了加减、自增自减运算符还有解引用符（就是变量名前面的星号），能够通过加减指向前面或者后面的元素，通过解引用符获取元素的引用。

1
2
for(auto it=A.begin();it!=A.end();it++)
    cout<<*it<<" ";

自己画了个图

.begin()和.end()也是每个容器都有的函数，分别返回指向容器开头和末尾的迭代器，注意末尾迭代器指向的是最后一个元素的下一个位置，以及可以使用.front()和.back()获取第一和最后一个元素的引用。

最后一种其实是我拿来凑数的，最不常用的写法，大家可以直接忽略，它的特点就是可以指定执行策略，可以并行执行，不过在蓝桥杯用处不大，所以看看就好，使用的时候需要引入算法库#include<algorithm>，下一篇文章会讲这个算法库

1
2
3
4
#include<algorithm>
/*一些代码*/
for_each(A.begin(),A.end(),[](int a){cout<<a<<" ";});
cout<<endl;

它的前两个参数是一对迭代器表示的区间，第三个参数是要对每个元素调用的函数，这里我传入了一个lambda用于输出元素。

vector的增加

我们可以使用emplace_back在vector末尾构造一个元素，注意是构造，不是插入，区别在于emplace_back的参数是对应类型的构造函数的参数，如果为相同类型的元素的话实际上是调用了它的移动构造函数（或复制构造函数）。

1
2
3
4
5
6
7
8
vector<int> A;
A.reserve(10);
cout<<A.size()<<endl;
for(int i=0;i!=10;++i)
    A.emplace_back(i);
cout<<A.size()<<endl;
for(auto a:A)
    cout<<a<<" ";

运行上面的代码可以看到在reserve之后A的size还是0，在用emplace_back插入元素之后大小为10，并且每次都是在vector的末尾插入元素。

跟它类似的还有个不带_back的emplace，这个可以在任意位置前添加新元素。

1
2
3
4
5
6
7
8
9
vector<int> A{0,1,2,3,4,6,7,8,9};
for(auto it=A.begin();it!=A.end();it++){
    if(*it>5){
        A.emplace(it,5)
        break;
    }
}
for(auto a:A)
    cout<<a<<" ";

emplace的第一个参数是要插入到的位置的迭代器，所以要使用迭代器遍历。在上面的代码中是遍历A找到第一个大于5的位置，在它前面插入5，然后中断循环。

但是大部分情况下不建议使用emplace。写过顺序表插入的应该都知道，在中间插入元素之后，后面每个元素都要往后移，时间复杂度为O(N)，而末尾插入元素为常数时间，所以使用vector应该尽量只在末尾插入元素，如果一定需要在其他位置插入，可以选择其他容器。

vector的删除

删除的话其实我用得很少，所以我也不太熟悉，引用某句很有哲理的话，“如何删除数组中最后一个元素？”，“你不去使用它就删除了”，本节完。

最简单的删除最后一个元素的方法就是pop_back，

1
2
3
4
5
6
7
8
vector<int> A{0,1,2,3,4,5,6,7,8,9};
for(auto a:A)
    cout<<a<<" ";
cout<<endl
A.pop_back();
for(auto a:A)
    cout<<a<<" ";
cout<<endl

运行上面的代码可以发现9被删除了，并且容器大小减1。

如果想删除指定值，也可以使用remove来将所有符合的元素移动到vector末尾，再使用erase删除指定区间的元素。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> A{0,1,2,3,4,5,6,7,8,9};
for(auto a:A)
    cout<<a<<" ";
cout<<endl
auto it=A.remove(A.begin(),A.end(),5);
for(auto a:A)
    cout<<a<<" ";
cout<<endl
A.erase(it,A.end());
for(auto a:A)
    cout<<a<<" ";
cout<<endl

remove接受3个参数，分别是两个迭代器表示的范围，和要移动到末尾的值。返回被移动到末尾的元素中的第一个的迭代器（也可以理解为新的末尾）。下面是执行it=A.remove(A.begin(),A.end(),5);之后的样子

erase接受两个参数，分别是两个迭代器表示的范围，删除范围内的元素，并缩小vector的大小（不改变内存大小）。显然如果删除的不是在末尾，也会产生元素向前移动，造成额外开销，为了避免这部分开销，erase尽量在末尾使用。下面是执行A.erase(it,A.end());之后的样子

然后可以思考一下下面的代码

1
2
3
4
5
6
7
8
vector<int> A{0,1,2,3,4,5,6,7,8,9};
for(auto a:A)
    cout<<a<<" ";
cout<<endl;
auto end=A.remove(A.begin(),A.end(),5);
for(auto it=A.begin();it!=end;it++)
    cout<<*it<<" ";
cout<<endl;

可以看到如果我们使用end标记末尾，我们就访问不到后面的元素了，end后面有没有元素都没有影响，所以刷算法题用的这种一次性代码其实不需要专门去删除元素还有维护内存。

容器的通用方法

vector的常用方法应该都说完了，之后就是多使用和习惯了。通过上面vector的介绍，大家对容器应该有了一些认识，接下来说一些几乎每种容器都有的函数。

首先是迭代器系列，之前我们已经用过了begin和end，这两个迭代器分别为容器的开始与末尾，能够从begin通过自增迭代到end，标志了容器的范围，也叫正向迭代器，因为是从头到尾的顺序。

然后是反向迭代器，rbegin和rend，其实就是在begin和end前面加上了r，表示反向。使用这两个迭代器可以从尾到头迭代容器，可以试一下下面的代码，

1
2
3
4
5
6
7
vector<int> A{0,1,2,3,4,5,6,7,8,9};
for(auto it=A.begin();it!=A.end();it++)
    cout<<*it<<" ";
cout<<endl;
for(auto it=A.rbegin();it!=A.rend();it++)
    cout<<*it<<" ";
cout<<endl;

就像这样

另外还有在开头加上了c的cbegin和cend，表示常量，既通过对迭代器解引用得到的是常量引用，不能对其进行修改，这个在竞赛中很少用到，知道有这个东西就行。

另外还有前面一直用到的.size()也是一个通用的方法，返回容器的大小，还有.empty()返回容器是否为空。

总结

至此我们已经知道了容器是什么，以及知道了vector的使用。在刷题的时候我们尽量使用vector来作为数组，而不是C语言风格的数组，使用STL容器和迭代器可以配合STL中的算法库的函数使用，下一篇文章就说说STL中的算法库。