STL之vector篇（下）（手撕底层代码，从零实现vector的常用指令，深度剖析并优化其核心代码）
文章目录
- 1.基本结构与初始化
- 1.1 空构造函数的实现与测试
- 1.2 带大小和默认值的构造函数
- 1.3 使用迭代器范围初始化的构造函数(建议先看完后面的reserve和push_back)
- 1.4 拷贝构造函数
- 1.5 赋值操作符的实现（深拷贝）
- 1.6 析构函数
- 1.7 `begin` 与 `end` 迭代器
- 2. 容量管理
- 2.1 `reserve`函数：实现动态扩容
- 2.2 `resize`函数：改变大小
- 3. 元素插入与删除
- 3.1 `push_back`函数：尾插元素
- 3.2 `pop_back`函数：尾删元素
- 3.3 `insert`函数：在指定位置插入元素
- 3.4 `erase`函数：删除指定位置的元素
- 4.全部代码实现
- 4.1 头文件
- 4.2 源文件
前言：
在编程的浩瀚星空中，数据结构如同指引方向的星辰，它们不仅是构建算法与程序大厦的基石，更是解决复杂问题、优化性能的关键所在。其中，vector作为C++标准模板库（STL）中的一颗璀璨明珠，凭借其灵活、高效的特点，在软件开发中占据了举足轻重的地位。
vector，即向量容器，是一种能够存储任意类型对象的动态数组。它封装了动态数组的所有特性，包括自动的内存管理、灵活的元素访问方式以及高效的随机访问性能，同时还提供了丰富的成员函数来支持元素的插入、删除、遍历等操作。与静态数组相比，vector的最大优势在于其大小可以动态变化，无需程序员手动管理内存，极大地简化了编程复杂度，提高了代码的安全性和可维护性。
本文旨在深入探讨vector的内部机制、使用技巧及最佳实践，帮助读者全面了解并掌握这一强大的数据结构。我们将从vector的基本概念和特性出发，逐步深入到其内存管理策略、迭代器使用、元素操作、性能优化等多个方面。同时，结合实际应用场景，展示vector在解决各种编程问题时的独特魅力和高效性。
无论你是C++编程的初学者，还是希望提升编程技能的老手，本文都将为你提供宝贵的参考和实用的指导。让我们一起踏上这场关于vector的探索之旅，解锁C++编程的新世界，感受数据结构的魅力与力量。
1.基本结构与初始化
1.1 空构造函数的实现与测试
- 实现一个空的
vector，不分配任何内存。 - 测试是否创建了容量为0的
vector。
实现代码：
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例：
void testvector1() {
xny::vector<int> v;
assert(v.size() == 0); // 验证大小
assert(v.capacity() == 0); // 验证容量
assert(v.empty()); // 验证是否为空
cout << "testvector1 passed" << endl;
}
int main()
{
testvector1();
return 0;
}
输出：
testvector1 passed
1.2 带大小和默认值的构造函数
- 初始化一个给定大小的
vector，并使用默认值填充。 - 测试构造后大小、容量是否符合要求。
实现代码：
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){ // 缺省参数用T类型的匿名对象
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val; // 填充默认值
}
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例：
void testvector2(){
xny::vector<int> v(4, 1);
assert(v.size() == 4); // 验证大小
assert(v.capacity() == 4); // 验证容量
assert(!v.empty()); // 验证是否为空
for (size_t i = 0; i < 4; ++i) {
assert(v[i] == 1); // 验证默认值
}
cout << "testvector2 passed" << endl;
}
int main()
{
testvector3();
return 0;
}
输出：
testvector2 passed
1.3 使用迭代器范围初始化的构造函数(建议先看完后面的reserve和push_back)
【思考】：
- 假设我用上述代码去实现以下样例会发生什么呢？
void testvector3() {
int arr[] = { 1, 2, 3, 4, 5 };
xny::vector<int> v(arr, arr + 5); // 使用迭代器范围初始化构造函数
}
【结果】：
- 这时我们意识到可能需要重新定义一个构造函数，并且这个构造函数可以使用迭代器范围初始化。
添加代码如下：
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
iterator begin(){ return _start; }
iterator end(){ return _finish; }
vector() {}
vector(size_t n, const T& val = T()){ // 缺省参数用T类型的匿名对象
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val; // 填充默认值
}
}
// 使用迭代器范围初始化的构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last){
while (first != last) // 迭代器区间左闭右开
{
push_back(*first);
++first;
}
}
void reserve(size_t n){
if (n > capacity()){
size_t sz = size();
T* tmp = new T[n];
if (_start){
for (size_t i = 0; i < sz; i++){
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void push_back(const T& x){
if (_finish == _endofstorage){
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例：
void testvector3() {
int arr[] = { 1, 2, 3, 4, 5 };
xny::vector<int> v1(arr, arr + 5); // 使用迭代器范围构造函数
for (auto e : v1){
cout << e << " ";
}
cout << endl;
string str("hello world");
xny::vector<char> v2(str.begin(), str.end());
for (auto e : v2) {
cout << e << " ";
}
// 这里我们用两种不同类型的迭代器进行测试
}
输出：
【思考】：
-
怎么回事呢？编译器又报错了，并且这次报的错比较模糊，于是我们可以直接搜索
error C2100，看看编译示例：
【解释】：
- 结合以上所有的编译报错我们终于发现错误的原因可能是非法寻址了，于是再次进行改进添加代码如下：
vector(int n, const T& val = T()) {
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
输出：
1 2 3 4 5
h e l l o w o r l d
1.4 拷贝构造函数
- 实现
vector的拷贝构造函数。 - 测试拷贝后的
vector是否完全复制原来的内容和容量。
实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
vector(const vector<T>& v){
size_t sz = v.size();
_start = new T[capacity()];
for (size_t i = 0; i < sz; i++) {
_start[i] = v._start[i];
}
_finish = _start + sz;
_endofstorage = _start + v.capacity();
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
测试样例:
void testvector4() {
xny::vector<int> v1(5, 10);
xny::vector<int> v2(v1);
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "testvector4 passed" << std::endl;
}
int main()
{
testvector4();
return 0;
}
输出：
testvector4 passed
1.5 赋值操作符的实现（深拷贝）
- 实现赋值操作符重载。
- 测试两个
vector赋值后，是否正确拷贝了内容和容量。
实现代码:
namespace xny {
template<class T>
class vector {
public:
typedef T* iterator;
vector() {}
vector(size_t n, const T& val = T()){
_start = new T[n];
_finish = _start + n;
_endofstorage = _finish;
for (size_t i = 0; i < n; i++) {
_start[i] = val;
}
}
// 自定义一个swap函数方便拷贝
void swap(const vector<T> v){
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// 赋值运算符重载
vector<T>& operator=(const vector<T>& v){
swap(v);
return *this;
}
T& operator[](size_t pos) { return _start[pos]; }
size_t size() const {return _finish - _start;}
size_t capacity() const {return _endofstorage - _start;}
bool empty() const {return _start == _finish;}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
【说明】：
- **传值参数：**通过传递
vector<T>的值作为参数，创建一个临时对象v。调用拷贝构造函数时自动执行拷贝，然后在赋值操作中与现有对象交换内容。传值是安全的，避免了手动内存管理问题。 - **swap函数：**通过交换数据成员，避免手动内存释放，简化代码逻辑。交换后的临时对象
v离开作用域时自动销毁，保证资源释放。
测试样例:
void testvector5() {
xny::vector<int> v1(5, 10);
xny::vector<int> v2 = v1; // 赋值操作
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "testvector5 passed" << std::endl;
}
int main()
{
testvector5();
return 0;
}
输出：
testvector5 passed
1.6 析构函数
实现代码:
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
【注意】
- 为了避免内存泄露的问题，上述代码全部都需要添加析构函数。
1.7 begin 与 end 迭代器
【解释】：
begin函数返回指向vector起始位置的迭代器（即指向第一个元素）。end函数返回指向vector末尾的迭代器（即指向最后一个元素的下一个位置）。- 两者结合可以用于遍历
vector中的元素。
添加代码:
iterator begin(){
return _start;
}
iterator end(){
return _finish;
}
2. 容量管理
2.1 reserve函数：实现动态扩容
- 实现
reserve函数，测试在容量不足时是否能正确扩展。
添加代码：
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
for (size_ t i = 0; i < sz; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
【注意】：
-
T是自定义类型时，依次调用数组每个对象的析构函数，再释放整个空间
-
原来for循坏中使用的是
memcpy(tmp, _start, sizeof(T) * sz);但是vector是深拷贝，但是vector空间上存的对象是string数组，使用memcpy导致string对象的浅拷贝 -
解决方案：T是string这样深拷贝的类，调用的是string赋值重载，实现的是string对象的深拷贝
测试用例：
void testvector6() {
xny::vector<int> v(5, 10);
v.reserve(10); // 预留容量
assert(v.capacity() == 10); // 验证容量扩展
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证数据保持不变
}
std::cout << "testvector6 passed" << std::endl;
}
int main()
{
testvector6();
return 0;
}
输出：
testvector6 passed
2.2 resize函数：改变大小
- 实现
resize函数，测试增加或减少vector大小，如果增加，用特定字符暂时覆盖。
添加代码：
void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n;
}
else {
// 扩容n
reserve(n);
// 传值
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
测试用例：
void testvector7() {
xny::vector<int> v(5, 10);
v.resize(8, 20); // 扩展大小并填充新值
assert(v.size() == 8); // 验证扩展后大小
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证原值不变
}
for (size_t i = 5; i < 8; ++i) {
assert(v[i] == 20); // 验证新值
}
std::cout << "testvector7 passed" << std::endl;
}
int main()
{
testvector7();
return 0;
}
输出：
testvector7 passed
3. 元素插入与删除
3.1 push_back函数：尾插元素
【实现步骤】：
-
- 检查容量是否足够，若不足则扩容（通常容量加倍）。
-
- 将新元素插入到当前末尾。
-
- 更新
_finish指针，指向新的末尾。
- 更新
添加代码：
void push_back(const T& val){
if (_finish == _endofstorage) {
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // 采用2倍扩容
reserve(newcapacity);
}
*_finish = val;
++_finish;
}
优化版本：
void push_back(const T& x){
insert(end(), x);
}
测试用例：
void testvector8() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
assert(v.size() == 3); // 验证插入后的大小
assert(v.capacity() >= 3); // 验证容量是否自动扩展
assert(v[0] == 1 && v[1] == 2 && v[2] == 3); // 验证插入的元素是否正确
std::cout << "testvector9 passed" << std::endl;
}
int main()
{
testvector8();
return 0;
}
输出：
testvector8 passed
3.2 pop_back函数：尾删元素
【实现步骤】：
-
- 将
_finish指针向前移动一位，即删除最后一个元素。
- 将
-
- 不释放空间。
添加代码：
void pop_back(const T& val) {
assert(_finish != _start); // 确保vector非空
--_finish; // 逻辑删除最后一个元素
}
优化版本：
void pop_back(){
erase(--end());
}
测试用例：
void testvector9() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.pop_back();
assert(v.size() == 2); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2); // 验证剩余元素是否正确
std::cout << "testvector9 passed" << std::endl;
}
int main()
{
testvector9();
return 0;
}
输出：
testvector9 passed
3.3 insert函数：在指定位置插入元素
【实现步骤】：
-
- 检查容量是否足够，不足时扩容。
-
- 将插入位置及其后的元素整体向后移动。
-
- 将新元素插入指定位置。
-
- 更新
_finish指针。
- 更新
添加代码：
iterator insert(iterator pos, const T& val) {
// 断言判断pos的有效性
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage) {
// 用临时变量存指定位置到起点的长度
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // 采用2倍扩容
reverse(newcapacity);
// 解决pos迭代器失效问题
pos = len + _start;
}
// 将插入位置及其后的元素整体向后移动。
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
测试用例：
void testvector10() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.insert(v.begin() + 2, 3); // 在第2个位置插入3
assert(v.size() == 4); // 验证插入后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 3 && v[3] == 4); // 验证插入的元素是否正确
std::cout << "testvector8 passed" << std::endl;
}
int main()
{
testvector10();
return 0;
}
输出：
testvector10 passed
【问题】：
- 扩容之后，
pos迭代器可能会发生改变，所以不能用原来的pos。
3.4 erase函数：删除指定位置的元素
【实现步骤】：
-
- 将
erase位置之后的元素向前移动一位。
- 将
-
- 更新
_finish指针。
- 更新
添加代码：
iterator erase(iterator pos) {
// 断言判断pos的有效性
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
测试用例：
void testvector11() {
xny::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.erase(v.begin() + 2); // 删除第2个元素
assert(v.size() == 3); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 4); // 验证删除后的元素顺序
std::cout << "testvector11 passed" << std::endl;
}
int main()
{
testvector11();
return 0;
}
输出：
testvector11 passed
4.全部代码实现
【注意】：
- 以下代码会提供常量和普通变量的两种函数或者迭代器。
4.1 头文件
#pragma once
#include<assert.h>
using namespace std;
namespace xny
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
// 解决vector<int> v(10, 1)
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last) // 迭代器区间左闭右开
{
push_back(*first);
++first;
}
}
vector()
{}
vector(const vector<T>& v)
{
size_t sz = v.size();
_start = new T[v.capacity()];
// memcpy(_start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i < sz; i++)
{
_start[i] = v._start[i];
}
_finish = _start + sz;
_endofstorage = _start + v.capacity();
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T()) // T类型的匿名对象
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
// 解决pos迭代器失效问题
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 && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void print(const vector<int>& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (size_t i = 0; i < v1.size(); i++)
{
v1[i]++;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
print(v1);
}
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(5);
v1.push_back(5);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
v1.insert(v1.begin(), 100);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
/*vector<int>::iterator p = v1.begin() + 3;
v1.insert(p, 300);*/
xny::vector<int>::iterator p = v1.begin() + 3;
//v1.insert(p+3, 300);
// insert以后迭代器可能会失效(扩容)
// 记住，insert以后就不要使用这个形参迭代器了，因为他可能失效了
v1.insert(p, 300);
// 高危行为
// *p += 10;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
// v1.erase(v1.begin());
auto it = v1.begin() + 4;
v1.erase(it);
// erase之后，迭代器失效了，不能访问
// vs进行强制检查，访问会直接报错
cout << *it << endl;
++it;
cout << *it << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
vector<int> v;
v.resize(10, 0);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v3 = v1;
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
};
void test_vector6()
{
vector<string> v;
v.push_back("11111");
v.push_back("22222");
v.push_back("33333");
v.push_back("44444");
v.push_back("55555");
// 自定义类型最好加引用
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
vector<string> v1(v);
for (auto& e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
vector<int> v(10u, 1);
vector<string> v1(10, "111");
// vector<int> v2(10, 1);
}
}
4.2 源文件
#include"vector.h"
#include <bits/stdc++.h>
using namespace std;
int main()
{
xny::test_vector7();
// ...其他测试
return 0;
}