跳到主要内容C++ vector 类常用接口及模拟实现 | 极客日志C++算法
C++ vector 类常用接口及模拟实现
综述由AI生成C++ vector 是 STL 中的顺序容器,支持动态扩容。 vector 的构造方式、遍历方法(下标、迭代器、范围 for)、容量管理接口(size、capacity、resize、reserve)以及增删查改操作(push_back、insert、erase 等)。重点讲解了 vector 迭代器失效的场景,包括底层空间改变(扩容、resize)和元素删除导致的失效问题,并提供了相应的解决思路。最后通过代码示例展示了 vector 的基本模拟实现,涵盖内存管理、拷贝构造、赋值重载及核心成员函数逻辑。
忘忧14 浏览 一、vector 简介
vector 在 STL 中表示顺序表,使用 vector 要包含 vector 头文件。
vector 是一个模板,使用时要指定其中存储的数据类型(类模板只能显式实例化)。
vector 不支持流插入和流提取,所以不能直接用 cin、cout 输入输出。
vector 文档介绍
二、vector 的使用(常用接口)
1. vector 的定义(构造方法)
| (constructor)构造函数声明 | 接口说明 |
|---|
| vector() | 无参构造 |
| vector(size_type n, const value_type& val = value_type()) | 构造并初始化 n 个 val |
| vector(const vector& x) | 拷贝构造 |
| vector(InputIterator first, InputIterator last); | 使用迭代器进行初始化 |
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v1;
vector<int> v2(10, 1);
vector<int> v3(v2.begin(), v2.end());
vector<int> v4(v3);
return 0;
}
2. vector 的遍历
vector 的遍历有三种方法:下标 + []、迭代器、范围 for。
(1)下标 + []
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
for (size_t i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
return 0;
}
(2)迭代器
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
(3)范围 for
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
for (auto e : v) {
cout << e << " ";
}
cout << endl;
return 0;
}
3. vector 类对象的容量操作
| 容量空间 | 接口说明 |
|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变 vector 的 size,同时对新增数据初始化(未指定就调用默认构造)。resize 一般不会缩容,但会改变 size:小于 size 时删除数据,大于 size 时插入数据,空间不够时会扩容 |
| reserve | 改变 vector 的 capacity(不缩容) |
| clear | 清除 vector 的元素 |
(1)resize
改变 vector 的 size,同时对新增数据初始化(未指定就调用默认构造)。resize 一般不会缩容,但会改变 size:小于 size 时删除数据,大于 size 时插入数据,空间不够时会扩容。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(20);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.resize(15, 2);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.resize(5);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
return 0;
}
(2)capacity
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(20);
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(15);
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(5);
cout << v.size() << endl;
cout << v.capacity() << endl;
return 0;
}
从运行结果可以看出,把 capacity 改成 20 后,再使用 reserve 不会减小 vector 的 capacity。
4. vector 增删查改
| vector 增删查改 | 接口说明 |
|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找(这个是算法模块实现,不是 vector 的成员接口) |
| insert | 在 position 之前插入 val(只支持迭代器) |
| erase | 删除 position 位置的数据或删除一段迭代器区间(只支持迭代器) |
| swap | 交换两个 vector 的数据空间 |
| operator[] | 像访问数组一样访问 vector |
(1)push_back 和 insert
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
v.push_back(2);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
v.insert(v.begin(), 3);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
v.insert(v.begin() + 3, 4);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
return 0;
}
(2)erase
erase 可以删除一个位置,也可以删除一段迭代器区间。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 1);
v.erase(v.begin());
for (auto i : v) {
cout << i << " ";
}
cout << endl;
v.erase(v.begin() + 3);
for (auto i : v) {
cout << i << " ";
}
cout << endl;
return 0;
}
5. vector 的使用
vector 不仅可以存储内置类型,还可以存储自定义类型甚至存储 vector。
使用 vector 存储 vector
使用 vector 存储 vector 可以看作二维数组,也可以像访问二维数组一样使用 [][] 访问(实际上是两次函数调用)。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v(10, 0);
vector<vector<int>> vv(5, v);
for (int i = 0; i < vv.size(); i++) {
for (int j = 0; j < vv[i].size(); j++) {
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
return 0;
}
三、vector 迭代器失效问题
迭代器的主要作用是让算法能够不用关心底层数据结构,其底层就是一个指针,或者对指针进行了封装,比如vector 的迭代器其实就是原生指针 T*。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间(类似野指针),造成的后果就是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
对于 vector 可能会导致其迭代器失效的操作有:
- 会引起其底层空间改变的操作,都有可能使迭代器失效,比如:resize、reserve、insert、assign、push_back 等
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v{1, 2, 3, 4, 5};
auto it = v.begin();
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};
vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
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 下,g++ 编译器对迭代器失效的检测并不是非常严格,处理也没有 vs 极端。在 Linux 下迭代器失效后,代码不一定会崩溃,但运行结果肯定不对,如果 it 不再 begin 到 end 范围内,程序一定会崩溃。
-
与 vector 类似,string 在插入 + 扩容操作 + erase 之后,迭代器也会失效。
#include <iostream>
#include <string>
using namespace std;
int main() {
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);
}
return 0;
}
迭代器失效的解决办法:在使用前对迭代器重新赋值即可。
四、vector 模拟实现
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace zsy {
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
vector() = default;
vector(const vector<T>& v) {
reserve(v.size());
for (auto& e : v) {
push_back(e);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T()) {
reserve(n);
for (size_t i = 0; i < n; i++) {
push_back(val);
}
}
void clear() {
_finish = _start;
}
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
const vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
~vector() {
if (_start) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const {
return _start;
}
const_iterator end() const {
return _finish;
}
void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* tmp = new T[n];
for (size_t i = 0; i < old_size; i++) {
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n;
} else {
reserve(n);
while (_finish <= _start + n) {
*_finish = val;
++_finish;
}
}
}
size_t size() const {
return _finish - _start;
}
size_t capacity() const {
return _end_of_storage - _start;
}
bool empty() {
return _start == _finish;
}
void push_back(const T& x) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back() {
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end()) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const {
assert(i < size());
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template<class T>
void print_vector(const vector<T>& v) {
auto it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
}
}
相关免费在线工具
- 加密/解密文本
使用加密算法(如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