深入理解C++系列（09）——vector

⭐️博主： 此生决int-@CSDN博客

 速胜派就是最大的投降派！！！

         🔥热门专栏🔥

      深入理解 C++ 系列 ｜ 算法系列

      快速复习系列 ｜ Java 速通系列

文章目录

• • 上期回顾
• C++ vector 复习总结
• • 一、vector 的使用
  • • 1. vector 是什么？
    • 2，vector的构造、遍历、
    • • vector 的常见构造
      • 迭代器与遍历
      • • 1， 迭代器遍历
        • 2. 下标遍历
        • 3. 范围 for 遍历
    • 3，vector 常用接口⭐️⭐️⭐️
    • 4，vector二维数组⭐️⭐️
    • • 二维数组练习题：杨辉三角⭐⭐
      • • 题目链接
        • 题目描述
        • 解题思路
        • 解题代码
        • 大神解题代码
  • 二，vector 模拟实现——知识点 & 易错点总结⭐️⭐️⭐️
  • • 一、vector 底层结构
    • 二、关于模板
    • 三，重要接口实现
    • • 1、reserve()⭐️⭐️⭐️
      • 2、resize()
      • 3、push_back()
      • 4、pop_back()
      • 5、operator[]⭐️⭐️
      • 6、insert()⭐️⭐️⭐️
      • 7、erase()⭐️⭐️
      • 8、拷贝构造 ⭐️⭐️
      • 9、operator=
      • 10、swap()
      • 11、构造函数⭐️⭐️⭐️
      • • 1，模版函数
        • 2， `vector<int> v(10,1)` 容易产生歧义的问题
      • 12、迭代器
      • 13、模板实现
    • 实现的所有坑点总结：
  • 三、总结（复习时直接看）
  • 下期预告
  • 结语

上期回顾

上一篇我们主要学习了 string，重点掌握了 string的使用，相关接口，以及底层实现！以及·练习了几道string相关的算法题。但是，string并不属于STL的一部分，但是它与STL有比较相似的地方，那么我们今天就来学习真正的STL的第一位成员：vector——顺序表，让我们来看看，真正的STL是怎么设计的，也为我们后面学习其他STL容器打好基础！

C++ vector 复习总结

本节主要围绕两个层面展开：

一、vector 的使用

1. vector 是什么？

一句话概括：vector 就是支持动态扩容的数组。

1，vector 本质：vector 是一种动态顺序表（动态数组），底层使用连续内存存储元素，支持随机访问和自动扩容。 2，与 我们上一期学的string 的关系：两者设计思想高度一致，都具有 size()、capacity()、reserve()、resize()、push_back() 等接口，可以将 string 看作是面向字符的特殊动态序列，但二者也有很多不同！

2，vector的构造、遍历、

vector 的常见构造

构造方式：支持默认构造、指定元素个数和值构造、区间构造，其中 STL 的区间均遵循 左闭右开 [first, last) 的规则。

示例：

vector<int> v1;
vector<int> v2(5, 1);
vector<int> v3(v2);
int a[] = {1, 2, 3, 4};
vector<int> v4(a, a + 4);

重点：

• vector<int>(5, 1) 表示 5 个元素，每个值是 1。
• 迭代器区间构造非常常用，尤其在数组、字符串、其他容器之间转换时。

迭代器与遍历

• 遍历方式：支持下标遍历、迭代器遍历和 C++11 范围 for 遍历，其中迭代器是 STL 的统一访问方式，后续所有容器和算法都会大量使用！

1， 迭代器遍历

vector<int> v{1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}

for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
{
cout << *rit << " ";
}

含义：

• begin()：指向第一个元素。
• end()：指向最后一个元素的下一个位置。
• rbegin()：最后一个元素。
• rend()：第一个元素前一个逻辑位置。

注意：

end() 不是有效元素位置，不能解引用。

2. 下标遍历

vector 最常用的遍历方式之一：

for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}

3. 范围 for 遍历

for (auto e : v)
{
cout << e << " ";
}

修改元素时要传引用！

for (auto& e : v)
{
e *= 2;
}

3，vector 常用接口⭐️⭐️⭐️

常用接口：

部分不常用接口

细节补充

不能完全用 vector 替代 string： vector 可以存放字符，但不会自动维护 ‘\\0’，缺少丰富的字符串操作接口，也没有许多 string 实现中的专门优化（如 SSO），因此string 更适合表示和处理文本。

4，vector二维数组⭐️⭐️

caige::vector<int> v1(10, 1);
caige::vector<caige::vector<int>> v2(5, v1);

vector<vector> 本质是 外层 vector 存放多个 vector 对象，并不是一整块连续的二维内存。模板会实例化两个类：vector 和 vector<vector>。

caige::vector<int> v1(10, 1);
caige::vector<caige::vector<int>> v2(5, v1);
v2[0][0] = 2;
for (int i = 0; i < v2[0].size(); i++)
for (int j = 0; j < v2.size(); j++)
v2[i][j] = 10086;

vv[i] 返回 vector&，vv[i][j] 再调用一次 operator[]，最终返回 int&，因此支持直接赋值。 vv[i][j] 等价于 vv.operator.operator。

二维数组练习题：杨辉三角⭐⭐

题目链接

杨辉三角

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在杨辉三角中，每个数等于它左上方和右上方两个数之和。

解题思路

利用杨辉三角的性质逐行构造。前两行固定，从第三行开始，首尾元素为 1，中间元素等于上一行相邻两个元素之和，直到生成 numRows 行即可。

解题代码

class Solution {
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// 1 4 6 4 1
public:
vector<vector<int>> generate(int numRows) {

vector<vector<int>> ret;

// 第一行
vector<int> tmp1(1, 1);
ret.push_back(tmp1);

if (numRows == 1)
return ret;

// 第二行
vector<int> tmp2(2, 1);
ret.push_back(tmp2);

if (numRows == 2)
return ret;

// 从第三行开始逐行构造
for (int i = 3; i <= numRows; i++)
{
vector<int> tmp(i);

// 每一行首尾都为 1
tmp[0] = 1;
tmp[i – 1] = 1;

// 中间元素等于上一行相邻两个元素之和
for (int j = 1; j < i – 1; j++)
{
// 注意这里访问的是上一行，即 i-2
tmp[j] = ret[i – 2][j] + ret[i – 2][j – 1];
}

ret.push_back(tmp);
}

return ret;
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
vector<vector<int>> generate(int numRows) {

// 先创建 numRows 行，每行长度分别为 1~numRows
vector<vector<int>> ret(numRows);

for (int i = 0; i < numRows; i++)
{
ret[i].resize(i + 1);

// 每行首尾元素都是 1
ret[i][0] = ret[i][i] = 1;

// 中间元素由上一行两个元素相加得到
for (int j = 1; j < i; j++)
{
ret[i][j] = ret[i – 1][j – 1] + ret[i – 1][j];
}
}

return ret;
}
};

二，vector 模拟实现——知识点 & 易错点总结⭐️⭐️⭐️

具体实现见博主的Gitee仓库，博主的Gitee链接：财哥

一、vector 底层结构

• vector 底层采用一块连续的动态数组实现。
• vector 维护三个迭代器（指针）：_start（指向数据起始位置）、_finish（指向最后一个元素的下一个位置（end））、_end_of_storage（指向整块空间末尾的下一个位置）。

二、关于模板

• template<class T> 决定容器中存储的数据类型。
• 类模板中还可以继续定义函数模板，（具体见下面的template<class InputIterator>实现部分）。
• 下面的区间构造体现了 STL 泛型思想，只要求支持 *、++、!= 等迭代器操作即可。

三，重要接口实现

1、reserve()⭐️⭐️⭐️

首先，我们要知道：reserve() 只扩容，不改变 size()。

坑：

void reserve(size_t n)
{
if (n >capacity())
{
size_t old_size = size();
// T tmp = new T[n];,注意new出来的要用指针接收
T* tmp = new T[n];
// memcpy(tmp, _start,old_size);注意第三个参数是字节数而不是大小！！
// memcpy(tmp, _start, old_size*sizeof(T));不能用memcpy，因为如果是string等类就会发生浅拷贝，拷贝地址！！
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
// _finish = tmp + size();这样的话，finsh就一定为空了
_finish = tmp + old_size;
_end_of_storage = tmp + n;
// delete[] tmp;不可以delete 因为这块空间已经是_start指向的了
}
}

2、resize()

坑：

void resize(size_t n, const T& value = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish–_start<n)
{
*(_finish++) = value;
}
}
}

3、push_back()

坑：

void push_back(const T& x)
{
if (capacity() == size())
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}

4、pop_back()

坑：

• pop_back() 前必须判空。
• 删除元素本质上就是 _finish–。
• 不需要真正释放空间。

void pop_back()
{
//要判空
if (size() == 0)
return;
_finish—;
}

5、operator[]⭐️⭐️

// 元素访问
T& operator[](size_t i)
{
assert(i < size());
// return _start + size();为什么这里错了，这里返回的是什么？
//_start是首元素的地址，_start+1是指针运算，*(_start+1)=_start[1]
return _start[i];//为什么可以用[]?哦，因为_start是T*,T*类型就是T指针，那么，_start就是T类型数组的数组名（不准确），可以通过[]访问
//还要注意，这里的T不能默认是内置类型，还可能是string等类型，

// _start 是 T*，指向动态数组的首元素。
// 指针也可以使用 [] 运算符，因为 p[i] 本质上等价于 *(p + i)。
// 返回 T& 而不是 T，这样既避免拷贝，又可以支持 v[i] = x 的修改操作。
// 注意：T 不一定是内置类型，还可能是 string、vector 或自定义类型，
// 所以这里不能假设 T 是 int、char 等基本类型。
}

6、insert()⭐️⭐️⭐️

坑：

iterator insert(iterator pos, const T& x)//注意这里的pos是迭代器不是下标！！！
{
assert(pos>=_start&&pos <= _finish);
size_t index = pos – _start;//扩容后pos不可用了！！！！！！！
if (_finish ==_end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}

iterator tmp = _finish;
while (tmp >_start+index)
{
*(tmp) = *(—tmp);
// *(tmp) = *(tmp – 1);
}
// _start[pos] = x;
*(_start+index) = x;
_finish++;
//return this;返回迭代器啊喂！！！
return _start + index;//返回插入的元素的迭代器！！
}

7、erase()⭐️⭐️

坑：

iterator erase(iterator pos)//删除当前元素
{
assert(pos < _finish && pos >= _start);
/* for (size_t i = pos; i < size(); i++)
{
_start[i – 1] = _start[i];
}*/
iterator tmp = pos;
while (tmp < _finish–1)
{
*(tmp) = *(++tmp);
}
_finish—;
//return this;返回迭代器啊喂！！！
return pos;
}

8、拷贝构造 ⭐️⭐️

vector(const vector<T>& v)//注意这里是const，不能用swap
{
T* tmp = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++)
{
tmp[i] = v[i];
}
_start = tmp;
_finish = tmp + v.size();
_end_of_storage = tmp + v.capacity();
}

9、operator=

vector<T>& operator=(const vector<T>& v)
{
vector<T> tmp(v);
swap(tmp);
return *this;
}

10、swap()

• swap() 参数必须是引用。因为要修改变量的值。
• swap() 只交换三个指针。
• 注意：同一个类的成员函数可以访问其他对象的私有成员。不需要通过 begin() 等接口交换。

//类成员函数可以访问类的私有变量！！！，不需要接口
/* iterator _capacity()
{
return _end_of_storage;
}
void swap(vector<T>&v)
{
std::swap(_start , v.begin());
std::swap(_finish , v.end());
std::swap(_end_of_storage , v._capacity());
}*/
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}

11、构造函数⭐️⭐️⭐️

// 构造/析构
vector()
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{

}
vector(size_t n, const T& value = T())
{
T* tmp = new T[n];
for (int i = 0; i < n; i++)
{
tmp[i] = value;
}
_start = tmp;
_finish = _start + n;
_end_of_storage = _finish;
}
vector(int n, const T& value = T())
{
T* tmp = new T[n];
for (int i = 0; i < n; i++)
{
tmp[i] = value;
}
_start = tmp;
_finish = _start + n;
_end_of_storage = _finish;
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}

1，模版函数

template<class InputIterator>
vector(InputIterator first, InputIterator last);

InputIterator 不是 STL 提供的类，也不是关键字，它只是一个普通的模板参数名，可以任意修改，例如：

template<class It>
vector(It first, It last);

template<class Iterator>
vector(Iterator first, Iterator last);

都完全合法。

之所以命名为 InputIterator，是因为 STL 中规定了 Input Iterator（输入迭代器） 这一类迭代器，属于一种语义化命名。

模板实例化时：

• 数组：InputIterator → int*
• vector：InputIterator → vector<int>::iterator
• list：InputIterator → list<int>::iterator
• string：InputIterator → string::iterator

因此，只要支持 *、++、!= 等迭代器操作，就可以传入这个函数做参数，就可以作为区间构造的参数。

2， vector<int> v(10,1) 容易产生歧义的问题

类中同时存在：

vector(size_t n, const T& value = T());

template<class InputIterator>
vector(InputIterator first, InputIterator last);

当写：vector v(10,1);时，编译器既可以理解为：

vector(size_t, const int&)

表示 创建 10 个值为 1 的元素；

也可以把模板推导为：InputIterator = int从而vector(int, int)，误认为这是区间构造。 为了减少这种匹配歧义，一些实现会额外提供：

vector(int n, const T& value = T());

让 vector(10,1) 优先匹配普通构造函数。

12、迭代器

• begin() 返回首元素位置。
• end() 返回最后一个元素的下一个位置。
• const 对象会调用 const 版本。

// 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}

13、模板实现

实现的所有坑点总结：

• 把 迭代器当成下标 使用。
• 忘记 扩容后迭代器失效。
• operator[] 返回了指针而不是引用。
• 忘记保存扩容前的 size()。
• resize() 新元素固定赋值 0，没有使用 value。
• insert() 返回 this 而不是插入位置迭代器。
• 想在拷贝构造中直接使用 swap()。
• swap() 参数没有使用引用。
• 误认为成员函数不能访问其他对象的私有成员。
• 在模板代码中使用 memcpy 拷贝对象。
• 忘记模板不能分离编译。
• 对 InputIterator 的理解停留在"某种固定类型"，而实际上它只是模板参数名。

三、总结（复习时直接看）

• vector = 支持动态扩容的顺序表 / 动态数组。
• 最常用遍历方式：下标、迭代器、范围 for。
• size() 表示元素个数，capacity() 表示容量。
• reserve() 预留容量，不改元素个数。
• resize() 改元素个数，必要时扩容并初始化。
• push_back() 尾插，容量不够时可能扩容。
• 扩容后旧空间释放，旧迭代器全部可能失效。
• erase() 返回删除位置之后的新迭代器。
• 删除过程中遍历，标准写法是 it = v.erase(it)。
• 二维 vector 本质是“元素是 vector 的 vector”。
• 资源管理类不能用 memcpy 做扩容拷贝。
• 扩容策略不是标准固定的，不同 STL 实现可能不同。

下期预告

深入理解C++——list链表

结语

  本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。   也欢迎订阅我的深入理解 C++系列专栏、快速复习系列专栏 、算法系列专栏。

  愿每一次敲下键盘，都比昨天更进一步！

  愿每一行代码落下，都让未来多一种可能！