C++容器：vector – kedixa的博客

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/

构造与析构

迭代器

容量相关

元素访问

增删元素

总结

发表回复 取消回复

发表回复取消回复