C++中的vector是一种像数组一样的序列容器,它使用连续的存储空间来保存元素。当需要保存的元素增多时,容器通过分配更多的空间来保存更多的元素。通常来说,vector不会在每次增加元素时都去重新分配内存,而是预先在尾部预留出一部分空间来容纳新放入的元素。对于随机访问以及在尾部增加或删除元素的操作,其效率是很高的。
vector类包含在vector头文件中,它是一个类模板,因此在定义vector类的对象时,需要指明容器需要保存的对象的类型(除特殊情况外,本文均以int类型为例)。对于标注C++11的内容,需要支持C++11标准的编译器来编译。
#include <vector> // 包含vector头文件
using std::vector; // vector位于std命名空间中
vector<int> vec; // 定义一个包含int类型的vector容器
构造与析构
- 默认构造函数:构造一个空的容器,不包含任何元素;
// vector()
vector<int> vec; // 构造空容器
- 填充构造函数:构造一个含有n个元素的容器,每个元素是val的一个拷贝;
// vector(size_type n, value_type& val)
vector<int> vec(10, 1); // 含有10个1的容器
- 范围构造函数:构造包含[first, last)中元素的容器;
// vector(InputIterator first, InputIterator last)
vector<int> v(10, 1);
vector<int> vec(v.begin(), v.begin() + 3); // 包含3个1
- 复制构造函数:构造另一个vector的拷贝;
// vector(const vector &x)
vector<int> v(10, 1);
vector<int> vec(v); // 包含10个1的容器
- 移动构造函数(C++11):将另一个vector的内容移动到新的vector中,而不是逐个复制;
// vector(vector &&x)
vector<int> v(10, 1);
vector<int> vec(std::move(v)); // 包含10个1的容器
- 初始化列表构造函数(C++11):通过初始化列表构造vector对象;
// vector(initializer_list<value_type> il)
auto il = {1, 2, 3};
vector<int> vec1(il); // 1, 2, 3
vector<int> vec2{1, 2, 3};
- 析构函数:析构容器中的每个元素,并释放内存;
// ~vector()
- 赋值运算符(operator =):销毁容器中的元素,并将x中的所有元素复制到容器中。
vector<int> vec1(10, 1);
vector<int> vec2(20, 1);
vec2 = vec1; // vec2中有10个1
迭代器
- begin() 返回第一个元素的迭代器;
- end() 返回最后一个元素后面的迭代器(而不是最后一个元素);
- rbegin() 返回最后一个元素的反向迭代器;
- rend() 返回第一个元素前面的迭代器;
- cbegin()、cend()、crbegin()、crend()(C++11) 表示对应的常量(const)迭代器。
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector<int> vec({1, 2, 3, 4});
cout << "The vector contains:";
for(auto it = vec.begin(); it != vec.end(); ++it)
cout << ' ' << *it;
cout << endl;
cout << "The reversed vector contains:";
for(auto it = vec.rbegin(); it != vec.rend(); ++it)
cout << ' ' << *it;
cout << endl;
return 0;
}
/*
The vector contains: 1 2 3 4
The reversed vector contains: 4 3 2 1
*/
容量相关
- size() 获取容器中元素个数;
- max_size() 返回在当前的系统环境下,容器最多可以容纳的元素个数,但并不一定可以达到这么多;
- resize(size_type n, value_type val) 将容器元素个数置为n,若当前个数大于n,则多余的元素被删去;若当前个数小于n,其余位置使用val填充;
- empty() 若容器为空则返回true,否则返回false;
- reserve(size_type n) 改变容器容量,使得在不重新分配内存的情况下至少可以容纳n个元素(这并不改变当前容器中元素的个数);
- shrink_to_fit() (C++11)减少预留在尾部的空间,具体与标准库的实现有关;
- capacity() 获取容器的容量,包含预留在尾部的空间。
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector<int> vec({1, 2, 3, 4});
cout << "The size of vec is: " << vec.size() << endl;
cout << "resize(6, 0)" << endl;
vec.resize(6, 0);
cout << "The size of vec is: " << vec.size() << endl;
cout << "The capacity of vec is: " << vec.capacity() << endl;
cout << "reserve(100)" << endl;
vec.reserve(100);
cout << "The size of vec is: " << vec.size() << endl;
cout << "The capacity of vec is: " << vec.capacity() << endl;
cout << "shrink_to_fit()" << endl;
vec.shrink_to_fit();
cout << "The size of vec is: " << vec.size() << endl;
cout << "The capacity of vec is: " << vec.capacity() << endl;
return 0;
}
/*
The size of vec is: 4
resize(6, 0)
The size of vec is: 6
The capacity of vec is: 8
reserve(100)
The size of vec is: 6
The capacity of vec is: 100
shrink_to_fit()
The size of vec is: 6
The capacity of vec is: 6
*/
元素访问
- operator[] 访问某个位置的元素,若位置无效则产生未定义行为;
- at() 访问某个位置的元素,若位置无效则抛出异常;
- front() 返回第一个元素的引用;
- back() 返回最后一个元素的引用;
- data() (C++11)返回vector用于保存元素的内存的首地址。
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector<int> vec({1, 2, 3, 4});
vec[1] = 6;
vec.front() = 5;
vec.back() = 8;
vec.at(2) = 7;
cout << "The vec contains:";
for(auto &i : vec) cout << ' ' << i;
cout << endl;
return 0;
}
/*
The vec contains: 5 6 7 8
*/
增删元素
- assign(…) 为容器重新赋值;
- push_back(value_type val) 在尾部追加元素;
- pop_back() 删除最后一个元素;
- insert(…) 在某个位置插入元素,若这个位置及之后有元素,则这些元素依次后移;
- erase(…) 删除元素;
- swap(vector<value_type> &v) 交换两个容器的内容;
- clear() 清空容器;
- emplace(…) (C++11)在某个位置构造元素,不会产生拷贝;
- emplace_back(…) (C++11)在最后一个元素后面构造元素。
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
class R {
int x, y;
public:
R(int x = 0, int y = 0) {
this->x = x;
this->y = y;
cout << "Constructor called.\n";
}
R(const R &r) {
x = r.x;
y = r.y;
cout << "Copy constructor called.\n";
}
};
int main()
{
vector<int> v(4, 7);
// assign
vector<int> vec({1, 2, 3, 4});
// assign(InputIterator first, InputIterator last);
vec.assign(v.begin(), v.begin() + 3); // v的前三个元素
// assign(size_type n, const value_type &val)
vec.assign(6, 2); // 6个2
// assign(initializer_list<value_type> il) C++11
vec.assign({2, 3});
vec.push_back(9); // vec: 2 3 9
cout << "The vec contains:";
for(auto &i : vec) cout << ' ' << i;
cout <<endl;
// insert
vector<int>::iterator it;
it = vec.begin() + 2;
// insert(iterator it, const value_type &val)
// 在位置it插入元素val
vec.insert(it, 8); // vec: 2 3 8 9
// insert(iterator it, size_type n, const value_type &val)
// 在位置it插入n个元素val
it = vec.begin() + 2; // 若容器重新分配内存,则迭代器失效,须重新获取
vec.insert(it, 2, 8); // vec: 2 3 8 8 8 9
// insert(iterator it, InputIterator first, InputIterator last)
// 在位置it插入[first, last)中的内容
it = vec.begin() + 2;
vec.insert(it, v.begin(), v.begin() + 2); // vec: 2 3 7 7 8 8 8 9
// insert(iterator it, value_type &&val) C++11
// 将val移动(move)到it位置,关于移动语义暂不讨论,省略样例
// insert(iterator it, initializer_list<value_type il) C++11
// 在it位置插入il中的内容
it = vec.begin() + 2;
vec.insert(it, {4, 5, 6});
cout << "The vec contains:";
for(auto &i : vec) cout << ' ' << i;
cout <<endl;
// erase
// erase(iterator it)
// 删除位于迭代器it处的值
vec.erase(vec.begin()); // 删除第一个元素
// erase(iterator first, iterator last)
// 删除[first, last)中的内容
vec.erase(vec.begin(), vec.end() - 1); // vec: 9
vec.clear(); // 清空容器
// emplace, emplace_back
// 在指定位置直接构造元素,而不是先构造,再拷贝到指定位置
vector<R> vecR;
vecR.reserve(4); // 防止重新分配内存
cout << "vecR.push_back:\n";
vecR.push_back(R(0, 0));
cout << "vecR.emplace:\n";
// 在第一个位置构造,容器中的内容后移
vecR.emplace(vecR.begin() + 1, 1, 2);
cout << "vecR.emplace_back:\n";
// 在尾部构造
vecR.emplace_back(1, 2);
return 0;
}
/*
The vec contains: 2 3 9
The vec contains: 2 3 4 5 6 7 7 8 8 8 9
vecR.push_back:
Constructor called.
Copy constructor called.
vecR.emplace:
Constructor called.
vecR.emplace_back:
Constructor called.
*/
总结
vector适用于频繁读写但较少增删或仅在尾部增删的操作,当向容器中插入元素时,所有位于插入元素后面的元素都将被依次向后移动,若多次插入元素则效率很低。即使是在尾部插入,当由于空间不足引起内存重新分配的时候,所有的元素也将被依次拷贝或移动(move)到新的位置。因此,若在使用前已知数据量的大小,可以先使用reserve分配恰当的内存空间,避免拷贝引起的效率损失。
vector有很高的随机存取效率,如果不想使用new、delete手动分配数组,可以使用vector来方便地管理内存。同时,还可以“嵌套”地使用vector来获得二维数组vector<vector<int>>、三维数组vector<vector<vector<int>>>等等,原则上可以实现高维数组,但由于维数增加时书写起来不容易理解,因此不建议使用三维以上的嵌套,高手随意。
需要注意的是,vector<bool>是vector类的模板特化,它采用一个bit来保存一个bool值。vector<bool>不包含vector类中的data()、emplace()以及emplace_back()成员函数,增加了flip()函数用于将所有的bool值取反。当需要一个较大的bool数组而又不想浪费空间的时候,可以考虑vector<bool>。
本文由kedixa发表于个人博客,
转载请注明作者及出处。
本文链接:https://blog.kedixa.top/2016/cpp-container-vector/