《STL 六大组件之容器探秘：深入剖析 vector》

一、vector 简介

  vecotr 是 C++ STL 中的容器之一，用来存储同类型的多个变量，与数组很相似。但其与数组又有许多不同，vector 是一个类模版，而数组的本质是指针。且使用数组时申请多少空间则只能使用多少空间；而 vector 可以动态增容，空间随着元素的增多而增大。

二、vector 的常用接口

  下面从各个方面介绍一下 vector 容器的常用接口，并展示其用法。

1. 构造函数（constructor function）

  下面介绍 vector 常用的四个构造函数

（1）函数原型

// 1. 默认构造函数，构造一个空的 vector 对象
vector();  
// 2. 构造一个包含 n 个值为 val 的vector 对象
vector(size_type n, const value_type& val = value_type());  
// 3. 复制构造函数，构造一个和 v 一样的 vector
vector(const vector& v);
// 4. 该构造函数是一个函数模版，使用一段迭代器来构造该 vector，迭代器可以是任意类型的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last);

（2）使用演示

// 1. constructor function
void test1()
{// 1. 默认构造函数vector<int> vt_i;cout << "size_1: " << vt_i.size() << endl;cout << "capacity_1: " << vt_i.capacity() << endl;// 2. n 个 valvector<char> vt_c(5, 'x');for (const auto& e : vt_c)cout << e;cout << endl;// 3. 复制构造函数vector<double> vt_d;// 插入数据for (int i = 0; i < 10; ++i)vt_d.push_back(i);// 复制构造vector<double> vt_d_cpy(vt_d);for (const auto& e : vt_d_cpy)cout << e << " ";cout << endl;// 4. 迭代器构造string str1("Go for it, everyone!");vector<char> vt_c_1(str1.begin() + 3, str1.end());for (const auto& e : vt_c_1)cout << e;cout << endl;
}

（3）运行结果

2. 与迭代器相关的接口（iterator）

  下面简单介绍 vector 常用的 4 个迭代器接口及其用法，主要分为正序迭代器和反序迭代器。

（1）函数原型

// 1. 正序迭代器
iterator begin();
iterator end();
// 2. 反序迭代器
reverse_iterator rbegin();
reverse_iterator rend();// const 迭代器
// 为 const vector 对象服务
const_iterator begin() const;
const_iterator end() const;
const_reverse_begin() const;
const_reverse_end() const;

（2）使用演示

// 2. iterator
void test2()
{vector<int> vt_i;// 插入数据for (int i = 1; i < 10; ++i)vt_i.push_back(i);// 正序遍历cout << "正序遍历: ";vector<int>::iterator it = vt_i.begin();while (it != vt_i.end()){// 打印当前迭代器cout << *it << " ";// 下一个++it;}cout << endl;// 逆序遍历cout << "逆序遍历: ";vector<int>::reverse_iterator rit = vt_i.rbegin();while (rit != vt_i.rend()){// 打印当前迭代器cout << *rit << " ";// 下一个++rit;}cout << endl;
}

（3）运行结果

3. 与容量相关的接口（capacity）

  下面介绍 vector 常用的 5 个与容量有关的接口

（1）函数原型

// 1. 返回当前 vector 对象的 size
size_type size() const;
// 2. 返回当前 vector 对象的 capacity
size_type capacity() const;
// 3. 判断当前 vector 对象是否为空
bool empty() const;
// 4. 改变当前 vector 对象的 size
// 如果 n < size，则缩减 size；如果 n > size，则把新增得元素设置为 val；
// 当然，如果 n > capacity，则会进行增容
void resize(size_type n, value_type val = value_type());
// 5. 改变当前对象的 capacity
// 重新开辟一个大小为 n 的空间，把原来的数据拷贝到新的空间（拷贝不了的数据舍弃），释放旧空间；
void reserve(size_type n);

（2）使用演示

// 3. capacity
void test3()
{vector<int> vt_i;// 插入数据，同时并观察 vector 对象在 VS 环境下 capacity 的增长情况cout << "修改前" << endl;for (int i = 0; i < 20; ++i){vt_i.push_back(i);cout << "capacity: " << vt_i.capacity() << endl;}cout << "size: " << vt_i.size() << endl << endl;// 改变当前 vector 对象的 capacitycout << "修改 capacity 后" << endl;vt_i.reserve(50);cout << "capacity: " << vt_i.capacity() << endl;cout << "size: " << vt_i.size() << endl << endl;// 改变当前对象的 sizecout << "修改 size 后" << endl;vt_i.resize(25, 0);cout << "capacity: " << vt_i.capacity() << endl;cout << "size: " << vt_i.size() << endl << endl;// 打印当前 vector 对象for (const auto& e : vt_i)cout << e << " ";cout << endl;
}

（3）运行结果

4. 与访问和修改有关的接口（access、modify）

  下面介绍 vector 的 6 个与访问和修改有关的接口

（1）函数声明

// 1. 下标运算符重载（分普通 vector 对象和 const vector 对象）
reference operator[](size_type n);
const reference operator[](size_type n) const;
// 2. 尾插、尾删
void push_back(const value_type& val);
void pop_back();
// 3. 插入、删除
iterator insert(iterator position, const value_type& val);
iterator erase(iterator position);
// 4. 交换两个 vector 对象
void swap(vector& v);

（2）使用演示

// 4. access、modify
void test4()
{vector<int> vt_i;// 使用尾插插入数据插入数据for (int i = 1; i <= 10; ++i)vt_i.push_back(i);// 使用下标运算符访问 vector 对象中的元素for (int i = 0; i < 10; ++i)cout << vt_i[i] << " ";cout << endl;// 使用尾删删除数据for (int i = 0; i < 5; ++i)vt_i.pop_back();// 打印尾删后的 vector 对象for (int i = 0; i < 5; ++i)cout << vt_i[i] << " ";cout << endl;// 插入数据vt_i.insert(vt_i.begin(), 0);vt_i.insert(vt_i.end(), 6);vt_i.insert(vt_i.begin() + 3, 99);for (const auto& e : vt_i)cout << e << " ";cout << endl;// 删除数据vt_i.erase(vt_i.begin() + 3);vt_i.erase(vt_i.end() - 1);vt_i.erase(vt_i.begin());for (const auto& e : vt_i)cout << e << " ";cout << endl;
}

（3）运行结果

三、与 vector 相关的精选习题

1. 只出现一次的数字

题目链接：link

题目描述：

1. 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

2. 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例：

提示：

（1）解题思路
  两个相同的数异或为 0，而任何数与 0 异或不变。把 vector 中的所有数异或，则最终的结果就是 vector 中只出现一次的数。

（2）解题代码

class Solution {
public:int singleNumber(vector<int>& nums) {// 把 vector 对象 nums 中的所有元素异或// 最终的结果为 nums 中只出现一次的数int ret = 0;for (const auto& e : nums)ret ^= e;// 返回return ret;}
};

2. 杨辉三角

题目链接：link

题目描述：

示例：

提示：

（1）解题思路
  把每一行的第一个元素对齐成一列，则所求杨辉三角其实是一个等腰三角形。第一列的元素和正对角线的元素均为 1，其他元素均为其正上方的元素和左上角的元素之和。
注意：这里需要使用 resize 来调整 vector 的 size，这样可以使用下标运算符来访问每个元素。

（2）解题代码

class Solution {
public:vector<vector<int>> generate(int numRows) {// 创建二维 vectorvector<vector<int>> vv_i;// 根据输入的行数确定二维 vector 的大小vv_i.resize(numRows);// 给二维 vector 中的每个一维 vector 确定大小// 并设置每个一维 vector 中元素的值for (int i = 0; i < numRows; ++i){// 设置每行的大小vv_i[i].resize(i+1);// 设置每行的数据for (int j = 0; j < i + 1; ++j){if (0 == j || i == j)vv_i[i][j] = 1;elsevv_i[i][j] = vv_i[i-1][j-1] + vv_i[i-1][j];}}// 返回return vv_i;}
};

3. 删除有序数组中的重复项

题目链接：link

题目描述：

示例：

提示：

（1）解题思路
  使用前后指针法（pre 和 cur），pre 不动，cur 往后走，当 cur 和 pre 所指对象不同时，++pre 后与 cur 交换。重复上面的步骤，直到 cur 走到末尾。最终 pre 所在位置减去 nums 的初始位置的差值即所求 k 值。

（2）解题代码

class Solution {
public:int removeDuplicates(vector<int>& nums) {// 前后指针int pre = 0, cur = 0;// cur 往前走，当 cur 和 pre 所指对象不同时交换while (cur < nums.size()){if (nums[cur] != nums[pre])swap(nums[cur], nums[++pre]);// 下一个++cur;}// 返回return pre + 1;}
};

4. 只出现一次的数字ii

题目链接：link

题目描述：

示例：

提示：

（1）解题思路
  由于除了一个数之外，其他的数都出现三次。那么在 32 位的 int 中，为 1 的位出现的次数应该为 3n 或者 3n+1，当出现次数为 3n+1 时，则该位就是只出现一次的数字的为 1 位。当然，有可能为 0，所以最后还原的时候使用数字 0 来还原该数。

（2）解题代码

class Solution {
public:int singleNumber(vector<int>& nums) {// 存储 1 出现的次数int times_one[32] = {0};for (const auto& e : nums){for (int i = 0; i < 32; ++i){if ((e >> i) & 1)++times_one[i];}}// 根据为 1 位的出现次数还原该数int target = 0;for (int i = 0; i < 32; ++i){if (times_one[i] % 3)target |= (1 << i);}// 返回return target;}
};

5. 只出现一次的数字iii

题目链接：link

题目描述：

示例：

提示：

（1）解题思路
  把数组中的数全部异或，出现两次的数全部异或为 0，得到的结果就是只出现一次的两个数异或的结果。异或的规则是相同为 0，相异为 1，找出异或结果中为 1 的位，根据该位为 0 还是为 1 分成两组数，这两组数分别异或得到的结果就是只出现一次的两个数。

（2）解题代码

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {// 所有元素异或，得到的结果是两个只出现一次的数的异或int result = 0;for (const auto& e : nums)result ^= e;// 找出异或结果中为 1 的位int i = 0;for (i = 0; i < 32; ++i){if ((result >> i) & 1)break;}// 以该位为分界线，为 1 一组，为 0 一组// 分别异或，最终的结果就是所求的两位只出现一次的数int ret1 = 0, ret2 = 0;for (const auto& e : nums){if ((1 << i) & e)ret1 ^= e;elseret2 ^= e;}// 把结果插入 vector 对象vector<int> ret;ret.push_back(ret1);ret.push_back(ret2);// 返回return ret;}
};

6. 数组中出现次数超过一半的数字

题目链接：link

题目描述：

示例：

（1）解题思路
  由于目标数字的出现次数超过该数组长度的一般，那么把该数组进行排序，排序过后的数组的中间元素就是目标数字。

（2）解题代码

class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {// 调用标准库中的 sort 函数进行排序sort(numbers.begin(), numbers.end());// 返回该数组的中间元素return numbers[numbers.size() / 2];}
};

7. 电话号码字母组合

题目链接：link

题目描述：

示例：

提示：

（1）解题思路

1. 本题需要先创建一个字符串数组 digit_to_str，对应数字 2-9 所对应的字符组合；
2. 根据输入的数字组合获得对应的字母组合，并尾插到一个空的 vector<string> cur_combi中；
3. 重新设计一个递归函数，该函数中包含一个循环，该循环遍历 cur_combi 中的第一个 string 的所有字符，然后递归遍历第二个 string 的所有字符并和第一个 string 中的字符拼接，直到达到 cur_combi 的末尾，最后把拼接好的字符串存放到需要返回的 vector<string> ret 中。
4. 本题的解题思路作者描述的不是很好，大家结合着解题代码一起看基本上应该就能看懂，实际上就是 for 循环里放了个递归

（2）解题代码

// 创建一个全局的字符串数组
const char char_combi[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};class Solution {
public:void recursion(vector<string>& ret, const vector<string>& cur_combi, int i, int end, string cur){if (i < end){// 遍历当前 string 的每个字符for (const auto& e : cur_combi[i]){// 递归recursion(ret, cur_combi, i+1, end, cur + e);}}else  // 尾插到 ret 中{ret.push_back(cur);}}vector<string> letterCombinations(string digits) {// 如果输入数字组合为空if ("" == digits)return vector<string>();// 获得当前数字组合对应的字母组合vector<string> cur_combi;for (const auto& e : digits)cur_combi.push_back(char_combi[e-'0']);// 通过递归函数进行递归获取字符串组合vector<string> ret;recursion(ret, cur_combi, 0, cur_combi.size(), "");// 返回return ret;}
};