📢博客主页：https://blog.csdn.net/2301_779549673

📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！

📢本文由 JohnKi 原创，首发于 CSDN🙉

📢未来很长，值得我们全力奔赴更美好的生活✨

文章目录

📢前言🏳️‍🌈一、vector 模拟实现的基础🏳️‍🌈二、构造函数与析构函数🏳️‍🌈三、元素访问与操作函数🏳️‍🌈四、数据修改函数🏳️‍🌈五、赋值运算符重载🏳️‍🌈整体代码👥总结

📢前言

在 C++ 的编程世界中，vector 是一种极为常用的数据结构。理解其内部工作原理并进行模拟实现，能让我们更深入地掌握 C++ 编程的精髓。本文将带您走进 vector 模拟实现的世界，揭示其背后的神秘面纱，助您提升编程技能。

🏳️‍🌈一、vector 模拟实现的基础

迭代器的理解

在 vector 的模拟实现中，迭代器起着关键作用。vector 的迭代器本质上是一个原生指针，这使得对元素的访问和操作相对简单。通过指针的移动和解引用，能够方便地实现对 vector 中元素的遍历、读取和修改。但需要注意的是，对于不同的容器，迭代器的实现方式可能会有所不同。比如在链表等非连续存储的容器中，迭代器的实现就会更加复杂，需要考虑节点的连接和遍历逻辑。

私有成员变量的定义及作用

在 vector 的模拟实现中，定义了三个私有成员变量：<code>start、finish 和 end_of_storage。start 指针指向 vector 的第一个元素，finish 指针指向最后一个有效元素的下一个位置，end_of_storage 指针指向整个存储空间的末尾。

这三个指针共同协作，管理着 vector 的存储空间和元素范围。通过对它们的操作和维护，实现了 vector 的动态增长、元素插入、删除、容量调整等功能。例如，在扩容操作中，需要根据 end_of_storage 和 finish 的关系来判断是否需要重新分配更大的空间，并更新这三个指针的值以保证 vector 的正常运作。

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

vector的定义

🏳️‍🌈二、构造函数与析构函数

无参构造函数

无参构造函数将三个私有成员变量 <code>start、finish 和 end_of_storage 初始化为 nullptr，实现如下：

vector() { -- -->

_start = nullptr;

_finish = nullptr;

_end_of_storage = nullptr;

}

带参数的构造函数（包括 size_t 和 int 类型）

对于带参数的构造函数，当参数类型为 size_t 时，会先为 vector 分配指定数量的空间，并为每个元素进行初始化。代码如下：

vector(size_t n, const T& val = T()) {

_start = new T[n];

_finish = _start;

_end_of_storage = _start + n;

for (size_t i = 0; i < n; ++i) {

*_finish++ = val;

}

}

区间构造函数

区间构造函数接收两个迭代器 first 和 last，通过循环将区间内的元素插入到 vector 中。代码如下：

template <class InputIterator>

vector(InputIterator first, InputIterator last) {

while (first!= last) {

push_back(*first);

++first;

}

}

拷贝构造函数

拷贝构造函数用于创建一个新的 vector 对象，其内容与原对象相同。传统写法如下：

vector(const vector<T>& v) {

_start = new T[v.size()];

for (size_t i = 0; i < v.size(); ++i) {

_start[i] = v._start[i];

}

_finish = _start + v.size();

_end_of_storage = _start + v.capacity();

}

析构函数

析构函数用于释放 vector 所占用的资源，当 _start 不为空时，释放动态分配的内存，并将三个指针置为 nullptr。代码如下：

~vector() {

if (_start) {

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

🏳️‍🌈三、元素访问与操作函数

获取迭代器的函数

begin 函数返回一个指向 vector 起始位置的迭代器，代码实现为 iterator begin() { return _start; } 。

end 函数返回一个指向 vector 结束位置（即最后一个元素的下一个位置）的迭代器，实现方式为iterator end() { return _finish; } 。

cbegin 函数返回一个常量迭代器，指向 vector 的起始位置，代码为 const_iterator cbegin() const { return _start; } 。

cend 函数返回一个常量迭代器，指向 vector 的结束位置，即 onst_iterator cend() const { return _finish; } 。

元素访问函数

operator[] 函数用于访问 vector 中的元素。

//它实现了两种版本，一种是 const 版本，用于只读访问，代码为

const T& operator[](size_t pos) const

{

assert(pos < size());

return _start[pos];

}//另一种是非 const 版本，允许通过索引修改元素的值，实现为

T& operator[](size_t pos)

{

assert(pos < size());

return _start[pos];

}

获取容量和大小的函数

size 函数用于获取 vector 中元素的个数，通过计算 _finish - _start 得出，

capacity 函数用于获取 vector 的容量大小，即通过计算 _end_of_storage - _start 得到，

empty 函数用于判断 vector 是否为空，通过比较 _start 和 _finish 是否相等来确定，

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _end_of_storage - _start;

}

bool empty()

{

return (_finish == _start);

}

在 size_t size() const 中，const 的作用主要有以下几点：

表明该函数不会修改类的成员变量：这意味着在函数内部，不能对类的非静态成员变量进行修改操作，保证了函数的只读性质。这对于保证类的封装性和数据的一致性非常重要。允许常量对象调用该函数：如果一个对象被定义为常量，即 const 类型，那么它只能调用 const 成员函数。如果 size 函数没有 const 修饰，那么常量对象就无法调用这个函数来获取元素数量。

例如，假设有一个常量的 vector 对象 const vector v; ，如果 size 函数不是 const 的，就会导致编译错误，而有了 const 修饰，就可以正常通过 v.size() 来获取元素数量。

增强代码的可读性和可维护性：当看到一个函数被标记为 const 时，开发者可以立即知道这个函数不会修改对象的状态，有助于更好地理解代码的行为。

🏳️‍🌈四、数据修改函数

扩容函数（reserve）

reserve函数用于预分配vector的存储空间。

需要注意的是，reserve分配的内存未进行初始化，且访问未初始化的内存可能导致程序崩溃。

总之，在使用这些数据修改函数时，要特别注意迭代器失效的问题，及时更新迭代器以保证程序的正确性。

void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

//memcpy(tmp, _start, size() * sizeof(T));

// T不一定是内置类型，可能会造成乱码，得深拷贝

for (size_t i = 0; i < old_size; i++)

{

tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

尾插函数（push_back）

push_back函数用于在vector的末尾添加元素。

当vector的剩余空间不足时，可能会进行内存的重新分配和数据的拷贝。

在一些情况下，这可能导致之前获取的迭代器失效。

void push_back(const T& x)

{

if (_finish == _end_of_storage)

{

reserve(capacity() == 0 ? 4 : capacity() * 2);

}

*_finish = x;

++_finish;

}

改变数组长度函数（resize）

resize函数用于改变vector的有效长度。

如果resize后的长度小于当前长度，会删除多余的元素。

如果大于当前长度，会插入新的元素并进行初始化。

使用resize时，同样要关注迭代器的有效性。

void resize(size_t n, T val = T())

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

++_finish;

}

}

}

插入函数（insert）

insert函数用于在vector的指定位置插入元素。它有多种用法：

可以在指定位置插入单个元素，返回指向插入元素的迭代器。能在指定位置插入指定数量的相同元素。还可以插入一个区间内的元素。

在使用insert时需要注意迭代器失效的问题。当插入元素导致vector重新分配内存时，之前获取的迭代器可能会失效。解决方法是在插入操作后重新获取迭代器。

iterator insert(iterator pos, const T& x)

{

assert(pos >= _start);

assert(pos <= _finish);

if (_finish == _end_of_storage)

{

size_t len = pos - begin();// 防止扩容后导致相对位置发生变化

reserve(capacity() == 0 ? 4 : capacity() * 2);

pos = begin() + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

*pos = x;

++_finish;

return pos;

}

删除函数（erase、pop_back）

erase函数可以通过迭代器删除指定元素或指定位置的元素。

使用时要注意迭代器的正确操作，避免出现野指针导致程序错误。

pop_back函数用于删除vector的最后一个元素。

当进行删除操作时，如果导致vector内存重新分配，相关迭代器也可能失效。

void erase(iterator pos)

{

assert(pos >= _start);

assert(pos <= _finish);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

it++;

}

--_finish;

}

void pop_back()

{

assert(!empty());

--_finish;

}

🏳️‍🌈五、赋值运算符重载

在 vector 的模拟实现中，赋值运算符重载 operator= 起着重要的作用。其实现方式通常是通过复制源 vector 的元素来更新目标 vector 的内容。

常见的实现方式是创建一个临时的 vector 对象，将源 vector 的元素复制到这个临时对象中，然后通过交换操作来更新目标 vector 的状态。这样可以避免直接操作目标 vector 可能导致的内存管理问题。

赋值运算符重载的作用主要有以下几点：

方便对象之间的赋值操作，使得 vector 对象可以像基本数据类型一样进行赋值，提高了代码的简洁性和可读性。支持不同 vector 对象之间的数据传递和更新，使得代码逻辑更加清晰和易于理解。确保在赋值过程中正确处理内存管理，避免内存泄漏和数据错误。

vector<T>& operator=(const vector<T>& v)

{

if (this != &v)

{

clear();

reverse(v.size());

for (auto& e : v)

{

push_back(e);

}

}

return *this;

}

🏳️‍🌈整体代码

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<string>

#include<assert.h>

#include<list>

using namespace std;

// 模板的原理是将我们要做的事交给编译器去

// vector<vector<int>> vv(10, v); // 有点像二维数组

// vector<int> v(5, 1);

namespace bit

{

template<class T>

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

// C++11 前置生成默认构造

vector() = default;

// 拷贝构造

//vector(const vector<T>& v)

vector(const vector& v)

{

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

// 重载

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;

}

// v3 =v1

vector<T>& operator=(const vector<T>& v)

{

if (this != &v)

{

clear();

reverse(v.size());

for (auto& e : v)

{

push_back(e);

}

}

return *this;

}

// 模板

// 任意类型迭代器初始化，要求类型是匹配的

template <class InputIterator>

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

// 如果第二个const没有，就会导致，对于 const 对象，将无法调用这个 begin 函数。因为 const 对象只能调用 const 成员函数。

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];

//memcpy(tmp, _start, size() * sizeof(T));

// T不一定是内置类型，可能会造成乱码，得深拷贝

for (size_t i = 0; i < old_size; i++)

{

tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _end_of_storage - _start;

}

bool empty()

{

return (_finish == _start);

}

// 尾插

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 - begin();// 防止扩容后导致相对位置发生变化

reserve(capacity() == 0 ? 4 : capacity() * 2);

pos = begin() + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

*pos = x;

++_finish;

return pos;

}

// 删除指定位置

void erase(iterator pos)

{

assert(pos >= _start);

assert(pos <= _finish);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

it++;

}

--_finish;

}

void resize(size_t n, T val = T())

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

++_finish;

}

}

}

T operator[](size_t i)

{

assert(i < size());

return _start[i];

}

//void swap(vector<T>& v)

void swap(vector& v)// 类里面加不加<T>都行

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_end_of_storage, v._end_of_storage);

}

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

// 添加模板

template<class T>

void print_vector(const vector<T>& v)

{

// 必须加typename

// 在没有实例化的内模板（没有int等）中取东西，编译器不能区分这个const_iterator是类型还是静态成员变量（仅是初步检查）

typename vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << "";

++it;

}

cout << endl;

for (auto e : v)

{

cout << e << "";

}

cout << endl;

}

template<class Container>

void print_container(const Container& v)

{

/*auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;*/

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

}

void test_vector1()

{

vector<int> v;

v.push_back(1);

v.push_back(2);

v.push_back(3);

v.push_back(4);

v.push_back(4);

v.push_back(5);

v.insert(v.begin() + 2, 9);

for (size_t i = 0; i < v.size(); i++)

{

cout << v[i] << " ";

}

cout << endl;

vector<int>::iterator it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

for(auto e : v)

{

cout << e << " ";

}

cout << endl;

cout << endl;

print_vector(v);

cout << endl;

vector<double> vd;

vd.push_back(1.1);

vd.push_back(2.2);

vd.push_back(3.3);

vd.push_back(4.4);

vd.push_back(5.5);

vd.insert(vd.begin() + 2, 9);

print_vector(vd);

}

void test_vector2()

{

vector<int> v;

v.push_back(1);

v.push_back(2);

v.push_back(3);

v.push_back(4);

v.push_back(4);

v.push_back(5);

print_container(v);

// 删除所有的偶数

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

v.erase(it);

else

++it;

}

print_container(v);

}

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(4);

v1.push_back(5);

v1.resize(10, 9);

v1.resize(20);

print_container(v1);

vector<int> v2(v1);

print_container(v2);

vector<int> v3(v1.begin(), v1.begin() + 3);

print_container(v3);

vector<string> v4(10, "11111");

print_container(v4);

v4.push_back("22222");

v4.push_back("22222");

v4.push_back("22222");

v4.push_back("22222");

v4.push_back("22222");

print_container(v4);

}

}

👥总结

vector模拟实现的要点包括：

迭代器的巧妙运用，通过原生指针实现简单高效的元素访问和操作。合理定义和管理私有成员变量start、finish和end_of_storage，实现对存储空间和元素范围的精确控制。构造函数涵盖了多种情况，满足不同的初始化需求。丰富的元素访问和操作函数，如insert、erase、push_back等，实现了对元素的灵活处理。准确获取容量、大小等信息，以及通过reserve、resize等函数进行空间管理。赋值运算符重载确保了对象赋值的便捷和安全。

优化方向

内存管理优化：可以考虑更精细的内存分配策略，减少不必要的内存浪费和频繁的重新分配。性能提升：例如在插入和删除操作中，采用更高效的数据移动方式。异常处理完善：增强对各种异常情况的处理，提高程序的健壮性。

拓展可能性

支持更多的模板参数：如增加内存分配器的选择，适应不同的场景需求。与其他数据结构的结合：例如与链表或树结构结合，形成更复杂但功能更强大的数据结构。多线程安全：使vector在多线程环境下能够安全地进行操作。自定义比较器：支持用户自定义元素的比较规则，丰富排序和查找等操作。

本篇博文对 vector的模拟实现 做了一个较为详细的介绍，不知道对你有没有帮助呢

觉得博主写得还不错的三连支持下吧！会继续努力的~