跳到主要内容C++ vector 深度解析:从使用到模拟实现 | 极客日志C++算法
C++ vector 深度解析:从使用到模拟实现
C++ STL 容器 vector 的核心机制涉及基础用法、空间增长策略差异及迭代器失效原理。内容涵盖 resize 与 reserve 对容量的影响,insert 和 erase 操作引发的迭代器失效陷阱,并通过模拟实现剖析底层内存管理细节。结合代码示例提供避坑指南,帮助理解动态数组在内存中的映射逻辑。
草莓泡芙1 浏览 vector 的介绍及使用
vector 的介绍
STL 容器的学习通常分为三个境界:能用、明理、能扩展。下面我们以 vector 为例,按照这个思路展开。
vector 的使用
在实际开发中,熟悉常用接口即可。以下是需要重点掌握的构造函数:
| 构造函数声明 | 接口说明 |
|---|
vector() | 无参构造 |
vector(size_type n, const value_type& val) | 构造并初始化 n 个 val |
vector(const vector& x) | 拷贝构造 |
vector(InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
vector iterator 的使用
| iterator 的使用 | 接口说明 |
|---|
begin + end | 获取第一个数据位置的 iterator / const_iterator,获取最后一个数据的下一个位置的 iterator / const_iterator |
rbegin + rend | 获取最后一个数据位置的 reverse_iterator,获取第一个数据前一个位置的 reverse_iterator |
迭代器并非简单的指针,其内部实现较为复杂。但在存储数据的一片连续空间中,我们可以用指针先简单模拟着理解。
vector 空间增长问题
| 容量空间 | 接口说明 |
|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize | 改变 vector 的 size |
reserve | 改变 vector 的 capacity |
关于扩容机制,不同编译器实现可能不同。例如 VS 下的 STL 基本按 1.5 倍增长,而 g++ 下通常是 2 倍。具体增长倍数取决于具体需求定义,不要固化认为都是 2 倍。reserve 只负责开辟空间,如果确定知道需要用多少空间,提前调用可以缓解增容代价;resize 在开空间的同时还会进行初始化,会影响 size。
void TestVectorExpand() {
size_t sz;
std::vector<int> v;
sz = v.();
std::cout << ;
( i = ; i < ; ++i) {
v.(i);
(sz != v.()) {
sz = v.();
std::cout << << sz << ;
}
}
}
capacity
"making v grow:\n"
for
int
0
100
push_back
if
capacity
capacity
"capacity changed: "
'\n'
如果已经确定 vector 中要存储元素大概个数,可以提前将空间设置足够,避免边插入边扩容导致效率低下:
void TestVectorExpandOpt() {
std::vector<int> v;
size_t sz = v.capacity();
v.reserve(100);
std::cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i) {
v.push_back(i);
if (sz != v.capacity()) {
sz = v.capacity();
std::cout << "capacity changed: " << sz << '\n';
}
}
}
vector 增删查改
| vector 增删查改 | 接口说明 |
|---|
push_back | 尾插 |
pop_back | 尾删 |
find | 查找(注意这个是算法模块实现,不是 vector 的成员接口) |
insert | 在 position 之前插入 val |
erase | 删除 position 位置的数据 |
swap | 交换两个 vector 的数据空间 |
operator[] | 像数组一样访问 |
vector 迭代器失效问题
迭代器的主要作用是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了。使用一块已经被释放的空间,造成的后果是程序崩溃。对于 vector 可能会导致其迭代器失效的操作有:会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back 等。
#include<iostream>
#include<vector>
using namespace std;
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto it = v.begin();
v.assign(100, 8);
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int a[] = {1, 2, 3, 4};
std::vector<int> v(a, a + sizeof(a) / sizeof(int));
std::vector<int>::iterator pos = find(v.begin(), v.end(), 3);
v.erase(pos);
cout << *pos << endl;
return 0;
}
erase 删除 pos 位置元素后,pos 位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效。但是,如果 pos 刚好是最后一个元素,删完之后 pos 刚好是 end 的位置,而 end 位置是没有元素的,那么 pos 就失效了。因此删除 vector 中任意位置上元素时,vs 就认为该位置迭代器失效了。但是 Linux 下不会挂掉。可以看出不同平台的编译器的设计在文档不做要求的情况下设计可能是不同的。
以下代码的功能是删除 vector 中所有的偶数,请问哪个代码是正确的?
std::vector<int> v{1, 2, 3, 4};
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) v.erase(it);
++it;
}
std::vector<int> v{1, 2, 3, 4};
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) it = v.erase(it);
else ++it;
}
第二个正确。注意:Linux 下,g++ 编译器对迭代器失效的检测并不是非常严格,处理也没有 vs 下极端。
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " ";
cout << endl;
auto it = v.begin();
std::cout << "扩容之前,vector 的容量为:" << v.capacity() << std::endl;
v.reserve(100);
std::cout << "扩容之后,vector 的容量为:" << v.capacity() << std::endl;
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
从上述例子可以看到:SGI STL 中,迭代器失效后,代码并不一定会崩溃,但是运行结果肯定不对。如果 it 不在 begin 和 end 范围内,肯定会崩溃的。在设计上,直接崩溃比较好,因为规避了越界问题。
#include<string>
void TestString() {
std::string s("hello");
auto it = s.begin();
while (it != s.end()) {
cout << *it;
++it;
}
cout << endl;
it = s.begin();
while (it != s.end()) {
it = s.erase(it);
}
}
所以为了使得咱们的代码可以在各个平台都能跑,在使用前,对迭代器重新赋值即可。
vector 在 OJ 中的使用
class Solution {
public:
int singleNumber(std::vector<int>& nums) {
int value = 0;
for (auto e : nums) {
value ^= e;
}
return value;
}
};
补充位运算小知识:0^任何数字 都是这个数字本身;相同的两个数按位^ 等于 0。
class Solution {
public:
std::vector<std::vector<int>> generate(int numRows) {
std::vector<std::vector<int>> vv(numRows);
for (int i = 0; i < numRows; ++i) {
vv[i].resize(i + 1, 1);
}
for (int i = 2; i < numRows; ++i) {
for (int j = 1; j < i; ++j) {
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
return vv;
}
};
总结:通过上面的练习我们发现 vector 常用的接口更多是插入和遍历。遍历更喜欢用数组 operator[] 的形式访问,因为这样便捷。希望大家自己实现一遍上面讲解的 OJ 练习,然后请自行完成下面题目的 OJ 练习,以此增强学习 vector 的使用。
vector 深度剖析及模拟实现
std::vector 的核心框架接口的模拟实现 bit::vector
#pragma once
#include<iostream>
#include<assert.h>
namespace twg {
template<class T>
class vector {
typedef T* iterator;
typedef const T* const_iterator;
public:
vector() {}
vector(const vector<T>& s) {
T* tmp = new T[s.capacity()];
for (int i = 0; i < s.size(); i++) {
tmp[i] = s[i];
}
_start = tmp;
_finish = tmp + s.size();
_end_of_storage = tmp + s.capacity();
}
template<class InputIterator>
vector(InputIterator first, InputIterator last) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
while (first != last) {
push_back(*first);
++first;
}
}
~vector() {
if (_start != nullptr) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
vector<T>& operator=(vector<T> s) {
swap(s);
return *this;
}
T& operator[](size_t n) {
assert(n < size());
assert(n >= 0);
return *(_start + n);
}
const T& operator[](size_t n) const {
assert(n < size());
return _start[n];
}
void swap(vector<T>& s) {
std::swap(_start, s._start);
std::swap(_finish, s._finish);
std::swap(_end_of_storage, s._end_of_storage);
}
void reserve(size_t n) {
if (n <= capacity()) return;
else {
int oldsize = size();
T* tmp = new T[n];
for (int i = 0; i < oldsize; i++) {
tmp[i] = *(_start + i);
}
delete[] _start;
_start = tmp;
_finish = tmp + oldsize;
_end_of_storage = tmp + n;
}
}
void push_back(const T& x) {
if (_finish == _end_of_storage) {
size_t newsize = _finish == nullptr ? 4 : capacity() * 2;
reserve(newsize);
}
*_finish = x;
++_finish;
}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
const iterator begin() const { return _start; }
const iterator end() const { return _finish; }
void print() {
auto it = begin();
while (it != end()) {
*it++;
}
std::cout << std::endl;
for (int i = 0; i < size(); i++) {
std::cout << *(_start + i) << " ";
}
std::cout << std::endl;
}
void resize(size_t n, T x) {
if (n <= size()) {
_finish = _start + n;
}
else if (n > size() && n < capacity()) {
int num = n - size();
while (num--) {
push_back(x);
}
}
else {
reserve(n);
int num = n - size();
while (num--) {
push_back(x);
}
}
}
void insert(iterator pos, const T& x) {
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
size_t pos_index = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + pos_index;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
void erase(const iterator& pos) {
auto it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
_finish--;
}
void pop_back() {
assert(_finish > _start);
--_finish;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
使用 memcpy 拷贝问题
假设模拟实现的 vector 中的 reserve 接口中,使用 memcpy 进行的拷贝,以下代码会发生什么问题?
int main() {
twg::vector<std::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
问题分析:memcpy 是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。如果拷贝的是自定义类型的元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为 memcpy 的拷贝实际是浅拷贝。
结论:如果对象中涉及到资源管理时,千万不能使用 memcpy 进行对象之间的拷贝,因为 memcpy 是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。
动态二维数组理解
void test2vector(size_t n) {
std::vector<std::vector<int>> vv(n);
for (size_t i = 0; i < n; ++i) vv[i].resize(i + 1, 1);
for (int i = 2; i < n; ++i) {
for (int j = 1; j < i; ++j) {
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
std::vector<std::vector<int>> vv(n); 构造一个 vv 动态二维数组,vv 中总共有 n 个元素,每个元素都是 vector 类型的,每行没有包含任何元素。使用标准库中 vector 构建动态二维数组时与上图实际是一致的。
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online