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

迭代器

  1. begin() 返回第一个元素的迭代器;
  2. end() 返回最后一个元素后面的迭代器(而不是最后一个元素);
  3. rbegin() 返回最后一个元素的反向迭代器;
  4. rend() 返回第一个元素前面的迭代器;
  5. 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
*/

容量相关

  1. size() 获取容器中元素个数;
  2. max_size() 返回在当前的系统环境下,容器最多可以容纳的元素个数,但并不一定可以达到这么多;
  3. resize(size_type n, value_type val) 将容器元素个数置为n,若当前个数大于n,则多余的元素被删去;若当前个数小于n,其余位置使用val填充;
  4. empty() 若容器为空则返回true,否则返回false;
  5. reserve(size_type n) 改变容器容量,使得在不重新分配内存的情况下至少可以容纳n个元素(这并不改变当前容器中元素的个数);
  6. shrink_to_fit() (C++11)减少预留在尾部的空间,具体与标准库的实现有关;
  7. 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
*/

元素访问

  1. operator[] 访问某个位置的元素,若位置无效则产生未定义行为;
  2. at() 访问某个位置的元素,若位置无效则抛出异常;
  3. front() 返回第一个元素的引用;
  4. back() 返回最后一个元素的引用;
  5. 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
*/

增删元素

  1. assign(…) 为容器重新赋值;
  2. push_back(value_type val) 在尾部追加元素;
  3. pop_back() 删除最后一个元素;
  4. insert(…) 在某个位置插入元素,若这个位置及之后有元素,则这些元素依次后移;
  5. erase(…) 删除元素;
  6. swap(vector<value_type> &v) 交换两个容器的内容;
  7. clear() 清空容器;
  8. emplace(…) (C++11)在某个位置构造元素,不会产生拷贝;
  9. 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>。

0

发表评论

邮箱地址不会被公开。 必填项已用*标注