C++ -vector的模拟实现

server/2025/2/2 13:09:56/

博客主页：【夜泉_ly】
本文专栏：【C++】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

自定义 vector 类的实现

我们将在 ly 命名空间下，简单实现一个模板化的 vector 类。
以下是完整的代码示例：

namespace ly {
template <class T> class vector {
public:typedef T* iterator;typedef const T* const_iterator;iterator begin() { return _start; }iterator end() { return _finish; }const_iterator cbegin() const { return _start; }const_iterator cend() const { return _finish; }vector() {}vector(int n, const T& value = T()) { resize(n, value); }vector(size_t n, const T& value = T()) { resize(n, value); }vector(long n, const T& value = T()) { resize(n, value); }template <class InputIterator>vector(InputIterator first, InputIterator last) {while (first != last)push_back(*first++);}vector(const vector<T>& v) {T* tmp = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++)tmp[i] = v._start[i];_start = tmp;_finish = tmp + v.size();_end_of_storage = tmp + v.capacity();}vector<T>& operator=(vector<T> v) {swap(v);return *this;}~vector() {delete[] _start;_start = _finish = _end_of_storage = nullptr;}size_t size() const { return _finish - _start; }size_t capacity() const { return _end_of_storage - _start; }void reserve(size_t n) {if (n > capacity()) {T* arr = new T[n];size_t _size = size();for (size_t i = 0; i < _size; i++)arr[i] = _start[i];delete[] _start;_start = arr;_finish = arr + _size;_end_of_storage = arr + n;}}void resize(size_t n, const T& value = T()) {reserve(n);for (size_t i = size(); i < n; i++)_start[i] = value;_finish = _start + n;}bool empty() const { return _start == _finish; }T& operator[](size_t pos) {assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];}void push_back(const T& x) {if (_finish == _end_of_storage)reserve(empty() ? 1 : 2 * capacity());*_finish++ = x;}void pop_back() {assert(!empty());--_finish;}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}iterator insert(iterator pos, const T& x) {assert(pos >= _start && pos <= _finish);size_t index_pos = pos - _start;if (_finish == _end_of_storage)reserve(empty() ? 1 : 2 * capacity());for (size_t i = size(); i > index_pos; i--)_start[i] = _start[i - 1];_start[index_pos] = x;++_finish;return _start + index_pos;}iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);for (size_t i = pos - _start; i < size() - 1; i++)_start[i] = _start[i + 1];--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};
} // namespace ly

接下来，我们将逐步解析这段代码，深入理解每个部分的功能和实现细节。

1. 迭代器的实现

typedef T* iterator;
typedef const T* const_iterator;iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator cbegin() const { return _start; }
const_iterator cend() const { return _finish; }

在这个实现中，迭代器被简单地定义为指向元素的原生指针。这种设计选择使得迭代器的操作与原生指针一致，简化了实现并提高了访问效率。

  • begin() 返回指向容器开始的指针。
  • end() 返回指向容器尾部的指针，指向最后一个有效元素的下一个位置。
  • cbegin() 和 cend() 分别返回指向常量版本的容器开始和尾部的指针，用于只读操作。

2. 构造函数与析构函数

默认构造函数

vector() {}

默认构造函数不执行任何操作，初始化时所有指针均为 nullptr。

带参数的构造函数

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

该构造函数创建一个包含 n 个元素的 vector，每个元素都被初始化为 value。通过调用 resize 方法实现。

迭代器范围构造函数

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last) push_back(*first++);
}

该构造函数接受一对迭代器，依次将区间内的元素添加到 vector 中。

拷贝构造函数

vector(const vector<T>& v)
{T* tmp = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++)tmp[i] = v._start[i];_start = tmp;_finish = tmp + v.size();_end_of_storage = tmp + v.capacity();
}

拷贝构造函数创建一个新的 vector，其容量和原 vector 保持一致，并复制所有元素。

赋值运算符

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

赋值运算符通过传值参数并调用 swap 方法实现，这种方式称为“拷贝并交换”技术，能够有效地处理自赋值和异常安全问题。

析构函数

~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}

析构函数释放分配的内存，并将所有指针设置为 nullptr，防止空指针。

3. 容量管理

获取大小与容量

size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
bool empty() const { return _start == _finish; }
  • size() 返回当前有效元素的数量。
  • capacity() 返回当前分配的存储容量。
  • empty() 判断容器是否为空。

保留容量

void reserve(size_t n)
{if (n > capacity()){T* arr = new T[n];size_t _size = size();for (size_t i = 0; i < _size; i++)arr[i] = _start[i];delete[] _start;_start = arr;_finish = arr + _size;_end_of_storage = arr + n;}
}

reserve 方法确保 vector 至少有 n 个元素的存储空间。如果当前容量不足，则分配新的内存，复制现有元素，并释放旧内存。

调整大小

void resize(size_t n, const T& value = T())
{reserve(n);if (n > size())for (size_t i = size(); i < n; i++)_start[i] = value;_finish = _start + n;
}

resize 方法调整 vector 的大小：

  • 如果新的大小大于当前大小，则增加元素，并使用 value 初始化新增部分。
  • 如果新的大小小于当前大小，则减少有效元素的数量（通过调整 _finish 指针）。

4. 元素访问

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

operator[] 提供了对元素的快速随机访问，包含断言以确保访问的索引有效。

5. 修改容器

添加元素：push_back

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

push_back 方法向容器末尾添加一个元素：

  • 首先检查是否有足够的存储空间。如果没有，则调用 reserve 增加容量，通常采用倍增策略以减少重新分配的次数。
  • 然后将新元素放置在 _finish 指针指向的位置，并将 _finish 向后移动。

删除元素：pop_back

void pop_back()
{assert(!empty());resize(size() - 1);
}

pop_back 方法移除容器末尾的一个元素，通过调用 resize 减少大小。这里包括断言以确保容器非空。

交换容器：swap

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

swap 方法交换当前容器与另一个容器的所有内部指针，实现高效的内容交换。

插入元素：insert

iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);size_t index_pos = pos - _start;if (_finish == _end_of_storage)reserve(capacity() == 0 ? 1 : 2 * capacity());for (size_t i = size(); i > index_pos; i--)_start[i] = _start[i - 1];_start[index_pos] = x;return _start + index_pos;
}

insert 方法在指定位置插入一个元素：

  • 首先检查插入位置的有效性。
  • 如果存储空间不足，则调用 reserve 增加容量。
  • 然后，从插入位置开始，将后续元素向后移动一个位置，留出插入的位置。
  • 最后，将新元素放置在插入位置，并返回指向新元素的迭代器。

删除元素：erase

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);for (size_t i = pos - _start; i < size() - 1; i++)_start[i] = _start[i + 1];_finish--;return pos;
}

erase 方法移除指定位置的元素：

  • 首先检查删除位置的有效性。
  • 然后，从删除位置开始，将后续元素向前移动一个位置，覆盖被删除的元素。
  • 最后，减少 _finish 指针，表示有效元素数量减少。

6. 内部数据成员

private:iterator _start = nullptr;           // 指向数据块的开始iterator _finish = nullptr;          // 指向有效数据的尾iterator _end_of_storage = nullptr;  // 指向存储容量的尾

vector 类使用三个指针来管理其内部存储：

  • _start：指向数据块的起始位置。
  • _finish：指向有效数据的末尾，即最后一个元素的下一个位置。
  • _end_of_storage：指向分配存储空间的末尾，标志着存储的容量界限。

这种设计允许高效地管理存储容量与大小，同时支持快速的随机访问和插入删除操作。

7. 实现细节与优化

内存管理

在本实现中，内存的分配和释放通过 new[] 和 delete[] 操作来完成。需要注意的是，这种方式在对象的构造和析构过程中并未充分处理。例如，最好使用构造函数和析构函数来正确构造和销毁对象，尤其是对于复杂类型的元素。

异常安全

当前的实现中，异常安全性还需要进一步提升。例如，如果在 push_back 中的元素复制构造函数抛出异常，可能导致内存泄漏或对象处于不一致的状态。使用 RAII（资源获取即初始化）的技术，如智能指针，可以提升异常安全性。

迭代器的增强

虽然原生指针作为迭代器简单高效，但在复杂应用中，可能需要更强大的迭代器类型，以支持更多的操作和接口。

性能优化

使用 std::copy 或 std::move 等标准库算法可以进一步优化元素的复制和移动过程。此外，利用现代 C++ 的特性，如移动构造函数和完美转发，可以提高性能和灵活性。

8. 使用示例

以下是如何使用自定义的 ly::vector 类的一个简单示例：

#include <iostream>
#include "ly_vector.h" // 假设上述代码保存在 ly_vector.h 文件中int main()
{ly::vector<int> vec;vec.push_back(1);vec.push_back(2);vec.push_back(3);std::cout << "Vector elements: ";for(auto it = vec.begin(); it != vec.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;vec.pop_back();std::cout << "After pop_back, size: " << vec.size() << std::endl;vec.insert(vec.begin() + 1, 10);std::cout << "After insert, elements: ";for(auto it = vec.begin(); it != vec.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;vec.erase(vec.begin());std::cout << "After erase, elements: ";for(auto it = vec.begin(); it != vec.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;return 0;
}

输出结果：

Vector elements: 1 2 3 
After pop_back, size: 2
After insert, elements: 1 10 2 
After erase, elements: 10 2

总结

本文通过解析一段自定义的 C++ vector 实现代码，深入探讨了动态数组的内部机制。尽管这个实现还存在一些可以改进的地方，如异常安全性和内存管理的优化，但它为理解标准库容器的工作原理提供了一个良好的起点。通过尝试实现自己的容器，不仅能够加深对 C++ 的理解，还能培养解决复杂编程问题的能力。

在实际开发中，建议尽量使用标准库提供的容器，因为它们经过了高度优化和充分测试。然而，了解其内部实现无疑会使你成为一个更优秀的 C++ 程序员。
在这里插入图片描述

希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！


http://www.ppmy.cn/server/164342.html

相关文章

智能汽车网络安全威胁报告

智能汽车网络安全威胁报告

近年来随着智能汽车技术的快速发展&#xff0c;针对智能汽车的攻击也逐渐从传统的针对单一车辆控制器的攻击转变为针对整车智能化服务的攻击&#xff0c;包括但不限于对远程控制应用程序的操控、云服务的渗透、智能座舱系统的破解以及对第三方应用和智能服务的攻击。随着WP.29 …
阅读更多...
spark运行流程

spark运行流程

spark运行流程 任务提交后&#xff0c;先启动 Driver 程序随后 Driver 向集群管理器注册应用程序集群管理器根据此任务的配置文件分配 Executor 并启动Driver 开始执行 main 函数&#xff0c;Spark 查询为懒执行&#xff0c;当执行到 Action 算子时开始反向推 算&#xff0c;根…
阅读更多...
编辑器Vim基本模式和指令 --【Linux基础开发工具】

编辑器Vim基本模式和指令 --【Linux基础开发工具】

文章目录 一、编辑器Vim 键盘布局二、Linux编辑器-vim使用三、vim的基本概念正常/普通/命令模式(Normal mode)插入模式(Insert mode)末行模式(last line mode) 四、vim的基本操作五、vim正常模式命令集插入模式从插入模式切换为命令模式移动光标删除文字复制替换撤销上一次操作…
阅读更多...
如何使用 DeepSeek 和 Dexscreener 构建免费的 AI 加密交易机器人？

如何使用 DeepSeek 和 Dexscreener 构建免费的 AI 加密交易机器人？

我使用DeepSeek AI和Dexscreener API构建的一个简单的 AI 加密交易机器人实现了这一目标。在本文中&#xff0c;我将逐步指导您如何构建像我一样的机器人。 DeepSeek 最近发布了R1&#xff0c;这是一种先进的 AI 模型。您可以将其视为 ChatGPT 的免费开源版本&#xff0c;但增加…
阅读更多...
MYSQL5.7 全文检索中文无返回数据

MYSQL5.7 全文检索中文无返回数据

在MySQL 5.7.6之前&#xff0c;全文索引只支持英文全文索引&#xff0c;不支持中文全文索引&#xff0c;需要利用分词器把中文段落预处理拆分成单词&#xff0c;然后存入数据库。 从MySQL 5.7.6开始&#xff0c;MySQL内置了ngram全文解析器&#xff0c;用来支持中文、日文、韩文…
阅读更多...
directx12 3d+vs2022游戏开发第三章 笔记五 变换

directx12 3d+vs2022游戏开发第三章 笔记五 变换

一、变换实质 总结来说就是通过矩阵和向量计算控制点变换&#xff0c;变换的效果可以实现局内物体的平移&#xff0c;旋转&#xff0c;缩放等一系列操作。 具体实现为先使用线性变换&#xff0c;即向量矩阵控制物体对于自身坐标系的旋转&#xff0c;缩放。 再使用仿射变换&a…
阅读更多...
k8s--部署k8s集群--控制平面节点

k8s--部署k8s集群--控制平面节点

环境 Vmware虚拟机&#xff0c;使用Ubuntu 24.04.1 LTS无桌面操作系统。 新建虚拟机参考 注意&#xff1a;在配置网络的时候要正确&#xff0c;不然后面下载系统组件会失败。 选择Docker Engine作为容器运行时。安装docker 官网容器运行时说明 关闭防火墙 sudo ufw disabl…
阅读更多...
一文读懂Python之random模块（31）

一文读懂Python之random模块（31）

random模块是Python的内置标准库&#xff0c;用于生成各类随机数&#xff0c;可以用作生成网站初始登录密码和随机验证码。 一、random模块简介 random模块可以生成随机数&#xff0c;包括随机整数、浮点数、随机元素等。 二、random模块相关概念 随机数&#xff1a; 是指在…
阅读更多...
最新文章

Copyright @ 2022~2023