【c++】vector模拟实现与深度剖析

server/2024/10/20 9:53:44/

Alt

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

Alt

vector涉及到许多细节问题，比如双层深拷贝，迭代器失效等，本篇文章我们通过模拟实现来深度理解这块的内容

目录

  • `1.基本框架`
  • `2.构造和销毁`
  • `3.元素访问`
  • `4.获取迭代器与容量操作`
    • `reserve开空间`
  • `5.对内容的修改`
    • `迭代器失效`

1.基本框架

namespace own 
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;// 指向数据块的开始iterator _finish;// 指向有效数据的尾iterator _endOfstorage;  // 指向存储容量的尾};
}

我们首先定义了一个模版类，这里的vector三个成员均为迭代器，而Vector的迭代器是一个原生指针，我们这里为其定义别名iterator

在这里插入图片描述

私有成员:

iterator _start;         // 指向数据块的开始
iterator _finish;        // 指向有效数据的尾
iterator _endOfstorage;  // 指向存储容量的尾

这些成员变量用于管理vector内部的动态数组

  • _start: 这是一个指针，指向分配给vector的内存区域的开始。这是数组的第一个元素
  • _finish: 这个指针指向数组中最后一个实际存在的元素的下一个位置。这意味着它指向结束后的第一个元素，它用来表示存储在vector中的实际元素的结束
  • _endOfstorage: 这个指针指向分配给vector的内存块的末尾。这不是最后一个有效元素的位置，而是整个内存块的结束位置，在这之后可能会有额外的未初始化空间，预留以实现当vector增长时无需重新分配整个数组

2.构造和销毁

在这里插入图片描述
🔥vector()

空值初始化：

vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{}

我们也可以直接利用缺省值来完成：

vector()
{}private:iterator _start=nullptr;		iterator _finish=nullptr;		iterator _endOfStorage=nullptr;  
};

🔥vector(size_t n, const T& value = T())

这个函数的功能是用n个value元素来构造一个vector

实现如下：

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

const T& value = T() 是使用了一个默认参数和引用的函数参数声明。

  • = T() 这部分声明了默认值，如果在调用函数时没有提供这个参数，就会使用它。T() 创建了 T 类型的一个临时对象，这是通过类型的默认构造函数完成的。这意味着如果没有提供具体的 value 值时，构造函数将使用 T 类型默认构造出的一个新对象作为默认值。

例如，如果 T 是 int，那么 T() 就是 0。如果 T 是某个类类型，并且该类有一个无参数的构造函数，那么 T() 就会调用这个默认构造函数来创建一个新对象。

因此，这个参数声明使得构造函数可以具有灵活性：你既可以用特定的初始值来构造 vector，也可以不提供初始值，让 vector 用类型 T 的默认值来填充

🔥vector(InputIterator first, InputIterator last)

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

这个函数是vector 类的一个范围构造函数（range constructor），它允许你根据一对迭代器 first 和 last 来构造一个新的 vector 对象。这个构造函数遍历从 first 开始一直到 last 结束的序列，并将每个元素添加到新构造的 vector 中

下面是详细的说明：

  • template<class InputIterator> 这一行表述了模板参数 InputIterator，它是一种迭代器类型，用于表示输入序列中的位置。它可以是指针或支持 ++（前置递增）和 *（解引用）操作的任何类型的迭代器。

  • vector(InputIterator first, InputIterator last) 这是构造函数的声明，它接受两个参数，first 和 last，代表输入序列的开始和结束迭代器。序列不包括迭代器 last 指向的元素。序列由 [first, last) 间的元素组成，是一个左闭右开的区间

函数体内的代码逻辑如下：

  • while (first != last) 循环，将一直执行，直到 first 迭代器等于 last 迭代器，这表示已经到达了输入序列的末尾。
  • push_back(*first) 在循环体内部调用，这个函数应该是 vector 类中的成员函数，它会添加解引用迭代器 first 指向的当前元素到 vector 的末尾。
  • ++first 然后迭代器 first 递增以便在下一次迭代中指向序列中的下一个元素。

这个构造函数可以用来构造一个 vector，使其包含现存容器（如另一个 vector、list 或 array）中某个子序列的元素，或者任何由迭代器定义的元素序列。例如：

注意，除了这两个函数，我们模拟实现时需要手动增加一个函数：

vector(int n, const T& val = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}

理论上将，提供了vector(size_t n, const T& value = T())之后vector(int n, const T& value = T())就不需要提供了，但是对于：vector<int> v(10, 5);编译器在编译时，认为T已经被实例化为int，而10和5编译器会默认其为int类型就不会走vector(size_t n, const T& value = T())这个构造方法，最终选择的是：vector(InputIterator first, InputIterator last)因为编译器觉得区间构造两个参数类型一致，因此编译器就会将InputIterator实例化为int但是10和5根本不是一个区间，编译时就报错了故需要增加该构造方法

🔥vector(const vector& v)

拷贝构造函数实现，只需要分配好空间对元素依次尾插即可

vector(const vector<T>& v)
{reserve(v.capacity());for (auto& e : v){push_back(e);}
}

上述有关reserve和push_back函数的模拟实现，我们后文会讲到

🔥~vector()

对于析构函数，我们需要释放空间并置指针指向空：

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

3.元素访问

🔥operator[ ]

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

🔥获取首尾元素

T& front()
{return *_start;
}const T& front()const
{return *_start;
}T& back()
{return *(_finish - 1);
}const T& back()const
{return *(_finish - 1);
}

4.获取迭代器与容量操作

🔥iterator begin()，iterator end()

iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

🔥size()，capacity()

获取容量大小与有效元素个数，只需要进行指针相减即可

size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _endofstorage - _start;
}

reserve开空间

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t old_size = size();memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}
}

这里我们开空间完成的是一个深拷贝的过程，用 memcpy 将旧数组中的元素复制到新数组，memcpy 在这里用于基于字节的拷贝，memcpy是一个浅拷贝，那么，如果我们vector实例化为string类，这里string类进行浅拷贝会涉及到二次释放等问题

在这里插入图片描述
虽然我的_start指向了新空间完成深拷贝，但是string类完成的是浅拷贝，仍指向原来的空间，这里为了解决上述问题，我们不能使用memcpy来进行拷贝，我们需要进行赋值操作来进行二次深拷贝

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}
}

通过一个循环，使用拷贝赋值操作符逐个拷贝旧数组中的元素到新数组

在这里插入图片描述
🔥resize（）

void resize(size_t n, const T& val = T())
{if (n > size()){reserve(n);// 插入while (_finish < _start + n){*_finish = val;++_finish;}}else{// 删除_finish = _start + n;}
}
  • 若resize传入的n大于capacity，进行扩容并用val来填满新位置
  • 若n大于有效元素个数并小于capacity，不进行扩容，用val填满空位置
  • 若n小于有效元素个数，进行删除操作

5.对内容的修改

🔥insert()

void insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = val;++_finish;
}

首先是否判断需要扩容，接着进行挪动数据，由于这里是指针，挪动数据我们就不用考虑越界问题，指针不会指向零

迭代器失效

注意，上述代码我们忽略了pos的位置

if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}

这里就会有迭代器失效的问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃，即如果继续使用已经失效的迭代器，程序可能会崩溃

在这里插入图片描述
扩容后，我原先pos指向的位置被释放，这里pos变的不可用

所以这里我们需要更新pos位置

if (_finish == _endofstorage)
{size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 如果扩容了要更新pospos = _start + len;
}

首先，记录pos到起始位置的大小，更新后新的start加上距离即可

在C++标准模板库(STL)中，迭代器失效(Iterator invalidation)是指当底层容器（例如vector，list或map等）发生改变时，其迭代器可能不再指向正确的元素，或者变得完全不可用。迭代器失效通常会发生在执行插入、删除或重新分配操作后

对于不同类型的容器，迭代器失效的条件会有所不同。对于vector：

  1. 增加容器中的元素（例如通过push_back、insert等）可能会导致存储空间重新分配，从而使所有指向容器元素的迭代器、指针和引用失效。如果容器在插入新元素前还有足够的capacity（未使用的预留空间），一般来说，除了指向插入点之后元素的迭代器之外，其他的迭代器、指针和引用会保持有效。

  2. 删除容器中的元素（例如通过erase、pop_back等）会使所有指向被删除元素以及之后元素的迭代器、指针和引用失效。

  3. 调整容器的大小（例如通过resize）至大于当前size可能会导致重新分配，这也将导致所有迭代器、指针和引用失效。

当涉及vector类的成员函数时，需要确保任何可能导致迭代器失效的操作之后都不使用旧的迭代器。例如，在调用insert的例子中，如果进行了扩容操作，之前的pos迭代器就将失效，因为reserve可能会导致动态数组的重新分配。所以代码中重新计算了pos的值来防止迭代器失效

要安全地使用迭代器，最好的实践是避免在迭代过程中修改容器的大小和结构，或者如果确实需要修改，则应在每次修改后重新获取迭代器

🔥erase()

在这里插入图片描述
注意！erase返回的值是迭代器

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;
}

erase函数的返回值是一个迭代器，它指向被删除元素的原位置。由于元素已经被移动了，这个位置现在包含了前一个被删除元素位置之后的元素。

🔥push_back和pop_back
我们这两个函数直接复用上面的函数即可：

void push_back(const T& val)
{insert(end(), val);
}void pop_back()
{erase(end() - 1);
}

本节内容到此结束！！感谢大家阅读，文章完整代码如下：

namespace own 
{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(){}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);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}bool empty(){return _start == _finish;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}T& front(){return *_start;}const T& front()const{return *_start;}T& back(){return *(_finish - 1);}const T& back()const{return *(_finish - 1);}void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);// 插入while (_finish < _start + n){*_finish = val;++_finish;}}else{// 删除_finish = _start + n;}}void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = val;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}void push_back(const T& val){insert(end(), val);}void pop_back(){/*assert(!empty());--_finish;*/erase(end() - 1);}private:iterator _start=nullptr;		iterator _finish=nullptr;		iterator _endOfstorage=nullptr;  };template<class T>void print_vector(const vector<T>& v){for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//typename vector<T>::const_iterator it = v.begin();/*auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;*/}
}

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

相关文章

JavaEE——Spring Boot + jwt

JavaEE——Spring Boot + jwt

目录 什么是Spring Boot jwt&#xff1f; 如何实现Spring Boot jwt&#xff1a; 1. 添加依赖 2、创建JWT工具类 3. 定义认证逻辑 4. 添加过滤器 5、 http请求测试 什么是Spring Boot jwt&#xff1f; Spring Boot和JWT&#xff08;JSON Web Token&#xff09;是一对常…
阅读更多...
【Ajax-异步刷新技术】什么是Ajax之续章 !

【Ajax-异步刷新技术】什么是Ajax之续章 !

文章目录 Ajax第五章1、layui的后台布局2、layui的数据表格1、在jsp页面中编写table2、在页面中引入文件3、编写代码4、参照文档修改表格属性 **3、最终效果** 第六章1、继续第五章内容1、layui组件2、添加数据3、查看数据4、修改数据5、删除数据 2、批量删除核心 3、数据表格重…
阅读更多...
Qt ： 禁用控件默认的鼠标滚轮事件

Qt ： 禁用控件默认的鼠标滚轮事件

最近在写一个模拟器&#xff0c;在item中添加了很多的控件&#xff0c;这些控件默认是支持鼠标滚动事件的。在数据量特别大的时候&#xff0c;及容易不小心就把数据给修改了而不自知。所有&#xff0c;我们这里需要禁用掉这些控件的鼠标滚轮事件。 实现的思想很简单&#xff0c…
阅读更多...
2014NOIP普及组真题 1. 珠心算测验

2014NOIP普及组真题 1. 珠心算测验

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1965 核心思想&#xff1a; 1、题目所求为“有多少个数其他两个数之和”&#xff0c;故不管5是由14组成&#xff0c;还是23组成&#xff0c;都只算一次。 2、利用 set 有 自动去重 的功…
阅读更多...
【U+】U+智享版运维平台账号密码重置

【U+】U+智享版运维平台账号密码重置

【问题描述】 友加畅捷系列中的U智享版软件&#xff0c; 系统运维平台账号admin密码忘记了&#xff0c;无法登录。 【解决方法】 在软件的安装目录下&#xff0c;找到sysconfig_accounts文件&#xff0c;并删除。 【路径&#xff1a;X:\U系列软件\U智享版\WebSite\config\】 …
阅读更多...
electron中preload.js文件的用法

electron中preload.js文件的用法

在Electron中&#xff0c;preload.js文件扮演着非常重要的角色&#xff0c;它允许你在渲染进程中的全局作用域里安全地、有选择地集成Node.js和Electron的API。这是一种在保持渲染进程与主进程隔离的同时&#xff0c;又能使渲染进程具有访问特定Electron API的能力的方法。这种…
阅读更多...
QT C++（信号与槽函数，自定义信号和槽函数）

QT C++（信号与槽函数，自定义信号和槽函数）

文章目录 1. QT信号与槽函数2. QT自定义信号和槽函数 1. QT信号与槽函数 QT信号关键要素&#xff1a; 信号源&#xff1a;那个控件发送的信号信号类型&#xff1a;用户进行不同的操作&#xff0c;就可能触发不同的信号。 eg&#xff1a;点击按钮&#xff0c;移动鼠标等信号处…
阅读更多...
基于 SpringCloud 的在线交易平台商城的设计与实现

基于 SpringCloud 的在线交易平台商城的设计与实现

摘 要 随着互联网的快速发展&#xff0c;人们对商品经济的消费和思考不再停留在传统 的经济模式上&#xff0c;网上购物商城是企业与企业进行、企业与消费者进行电子商 务交易的一个很好平台。网上购物商城极大地降低了企业商家的交易成本&#xff0c; 缩短企业供应链周期&…
阅读更多...
最新文章

Copyright @ 2022~2023