C++(vector的实现)

🕗 发布于 2024-10-14 17:49 c++ stl

1. vector介绍

vector本质其实就是和我们数据结构中的顺序表类似，都是对一个数组进行增删查改等操作，但是这里vector的实现和顺序表的实现有所不同，vector的底层源码的实现是通过三个迭代器实现的，一个是指向开始的位置_start，一个是指向有效数据末尾的迭代器_finish还有一个是指向有效空间的迭代器_end_of_storage；而顺序表则是一个指针指向一块空间，和两个计数器int size计算有效空间内有效的元素个数和int capacity 记录有效空间大小的整形变量；

2. vector的实现

2.1 vector的类的基本结构

如上所述，vector的实现是通过三个成员即三个迭代器实现的；但库内的vector的使用通常有可以使用不同的类型例如vector<int>， vector<char>，vector<double>等等，所以我们就需要实现一个vector的模板，然后还要实现他们的迭代器，我们同源码的迭代器实现不同，但迭代器其实就跟指针的用法几乎一样，所以我们这里通过指针来实现迭代器；如下代码所示：

template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
//有三个迭代器
iterator _start = nullptr; //指向开头
iterator _finish = nullptr;   //指向有效元素末尾后一个位置
iterator _end_of_storage = nullptr;  //指向有效空间末尾
};

2.2 vector构造和析构函数的实现

如上三个迭代器成员可见，我们已经给了缺省参数nullptr，那么在实例化的过程中我们只需要有一个构造函数，他们就会自动走初始化列表使用缺省参数进行初始化；而这里我们有了个创建一个构造函数的新的用法，这是在C++11才加进的；如下代码所示：

vector() = default;

然后是拷贝构造，拷贝构造其实就是实例化出一个新的对象，而新的对象的值和传入拷贝的对象的值相同，那我们就可以直接通过一个范围for让把被拷贝的对象的值依次插入实例化出的新的对象里面即可，这里先提前使用下面会讲到的内容，我们只需要知道push_back就是往里插入数据；

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

再者就是传入一段迭代器进行构造实例化出新的对象；但我们这里要重新写一个模板，这样我们就可以把一些不同类型的不同结构的对象存到vector里面来；

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

最后是析构函数就不过多介绍；

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

2.3 赋值运算符重载、swap、begin()、end()、capacity()、size()

swap的实现：由于和string类的实现一样，如果说我们调用库的swap并且是大量的数据进行交换的话效率会降低效率；如下图：

至于为什么会降低效率是因为红色方框那里会调用一次拷贝构造；然后绿色方框那也说了会降低效率，所以我们自主实现一个在类内且不会调用拷贝构造的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就可以，而且我们的参数是传值不是传引用，所以不会对v的原数据造成影响，最后再返回*this即可；如下代码所示：

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

然后是begin()传回首元素的迭代器、end()传回尾部元素的迭代器、capacity()传回有效空间大小、size()传回有效元素个数以及empty()判断vector容器是否为空的实现如下；

begin()和end()其实就是直接返回_start和_finish即可，但是他们还有一个const_iterator就是指向不可被修改的所以实现了两种；如下代码所示：

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

capacity()和size()这里返回他们的大小，应该是整型才对，但是我们的底层是迭代器，那该怎么办呢？其实这里涉及到我们指针的一个知识点，那就是指针减指针返回的是两个指针之间的元素个数，那我们就用用到这里来；如下代码所示：

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

最后一个是判空empt()，这个其实只需要看他的_start指向的空间和_finish指向的空间是否是同一块空间即可如下代码所示：

bool empty()
{
return _start == _finish;
}

2.4 reserve的实现（重点）

reserve就是预先开空间，如果说开的空间比原有的空间小的话capacity 和size不会变化，但是比原有的空间大的话就会给他们开足n个空间；如下测试可知：

#include<vector>
#include<iostream>
using namespace std;

int main()
{
vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);

cout << "capcaity is:> " << v.capacity() << endl;
cout << "size is:> " << v.size() << endl;

v.reserve(3);
cout << "After reserve(3) capcaity is:> " << v.capacity() << endl;
cout << "After reserve(3) size is:> " << v.size() << endl;

v.reserve(20);
cout << "After reserve(20) capcaity is:> " << v.capacity() << endl;
cout << "After reserve(20) size is:> " << v.size() << endl;
return 0;

}

👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇

运行结果为：

那我们的实现也要和源码的功能一样，如果n比capacity小则不出现变化，如果比capacity大的话就需要进行扩容，而这里也涉及了深浅拷贝问题，我们需要自己new一段n一样大的空间然后把数据往里放，我先直接上代码，里面有些需要注意的地方在下面进行讲解：

void reserve(size_t n)
{
if (n > capacity())
{

size_t old_size = size();
T* temp = new T[n];
//memcpy(temp, _start, size() * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
temp[i] = _start[i];
}
delete[]_start;
_start = temp;

//_finish = temp + size();//这个是错误的示范，因为delete掉_start了，
//那temp = _strt +size()（_finish-_start) 就为_finish，但是finish为NULL
//因为已经被释放了
_finish = temp + old_size;

_end_of_storage = temp + n;
}
}

重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！

（内心所言：换个颜色的字体会不会让眼睛看的舒服点哈哈哈哈）

首先需要注意的第一点是：上面代码加了一个old_size进行记录size()并不是多余，如果说上面不加的话会出现错误，因为前面已经释放了_start，而size() = _finish - _start，而_finish还指向原来已经被释放的空间，_finish = temp + _finish - _start；而_start = temp，_finish被释放了为NULL，所以最后的结果会为NULL，所以我们需要预先把size()保存下来；

然后先说一下赋值运算符重载vv = v的实现实质上是把vv原有的空间释放掉，然后开一片和v一样大的空间，上面做到了开一样的空间，而只需要把v的值复制到vv就可以，但为什么我把memcpy注释掉了呢？因为memcpy只是进行单纯的值和值赋值操作，如果说我用一个vector容器储存string类呢？只进行值的拷贝就会导致浅拷贝而出现错误；下面举出了例子：
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;


void reserve(size_t n)
{
if (n > capacity())
{

size_t old_size = size();
T* temp = new T[n];
memcpy(temp, _start, size() * sizeof(T));
delete[]_start;
_start = temp;
_finish = temp + old_size;

_end_of_storage = temp + n;
}
}

private:
//有三个迭代器
iterator _start = nullptr; //指向开头
iterator _finish = nullptr;   //指向有效元素末尾后一个位置
iterator _end_of_storage = nullptr;  //指向有效空间末尾
};

void test2()
{
vector<string> v;
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
Print_Container(v);
    v.push_back("11111111111111111111");
Print_Container(v);
}

int main()
{
test2();
return 0;
}
这里就是把memcpy解开了，那让我们来看看结果如何

👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇

运行结果为：

出现很多随机值，正如我们所说，单纯的memcpy只会把值进行浅拷贝如下图所示：

但为什么我们只进行单纯的赋值操作就可以实现深拷贝了呢？那是因为我们传了string类型即vector<string>，而改段赋值其实就是调用了string里的赋值运算符，库内的已经重载过了，所以会进行深拷贝操作；

2.5 push_back和pop_back()操作实现

其实也没有什么可讲的，因为和string类实现的非常相似，我们只需要注意当容器满的时候就需要进行扩容，然后把值放到*_finish里，然后finish还要往后走；而尾删pop_back更简单，因为她不需要考虑空间是否充足，只需要看空间是否为空即可；如下代码所示：

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

2.6 resize的实现

resize顾名思义就是改变size的，实现他的话有两种需要注意的情况，第一种如果说改变的大小n如果size < n < capacity的话则需要改变_finish的位置，但是capacity不会变；第二种如果说n>capacity的话则需要扩容，如果有给值则初始化新开的空间的值，如果没有则给匿名对象实例化出的值进行初始化如下代码所示：

void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
//这里包括两种情况，一种是 size < n < capacity;
//还有一种是capacity < n 那就需要拿n来进行扩容操作，而这步操作在reserve(n)
//会实现
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
}

这里第二个参数是T val = T()，T()其实就是匿名对象（这也看出匿名对象的作用，就是给不知道给什么类型缺省值的参数用的）；

2.7 insert和erase的实现

insert不单纯只是说插入数据，这里面还涉及到一个迭代器失效的知识点，就是当如果调用v.insert(p,10) 想在p的位置插入10的，但出现了空间不足需要扩容的情况后，p迭代器需要被更新，因为扩容后是新开的一块空间，但p还指向原来的空间，所以会出现野迭代器的情况；而解决方案是，我们先记录相对位置，即len = _start到pos位置的距离，最后再让pos走到相对位置处即pos = _start +len最后再返回pos即可；

上面标色的是特殊的迭代器失效的情况；下面是实现insert的思路：

1. 首先判断空间是否充足，因为你要插入数据；

2. 插入数据前需要把数据往后挪，然后再在pos位置插入数据；

3. 最后记得让_finish++, 因为插入数据后容量发生变化；如下代码所示：

iterator insert(iterator pos, const T& v)
{
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 = v;
++_finish;
return pos;
}

erase的实现：

erase也会出现迭代器失效的问题，如果说编译器出现缩容的情况下也会出现和上面insert的一样，而且还有一种情况就是如果说erase了某个迭代器，那么我们就不能对这个迭代器进行访问，因为编译器会强行检察报错，他们不允许再使用一个调用了erase且未更新的迭代器；如下代码所示：

void testErase()
{
std:: vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5); 

auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
 v.erase(it);
}
else
{
++it;
}
}
}

👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇

调试结果为：

直接崩掉了，但我们加上it = v.erase更新他的话就可以过；如下代码所示：

void testErase()
{
std:: vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5); 

auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
 it = v.erase(it);
}
else
{
++it;
}
}
}

👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇 👇

运行结果为：

所以由此可见erase的返回值应该是个迭代器，那么我们就可以来实现自己的erase；

实现思路：

1、首先要判断pos的位置不能不在有效数据内

2、删除操作和顺序表一样，直接让后面的数覆盖需要删除的数即可；

3、最后需要--finish 因为删掉了数据，然后还要返回pos；如下代码所示：

iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);

auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}

2.8 方括号重载即下标访问

直接返回对应下标的值即可直接上代码：

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

2.9 实现Print_vector操作

打印值其实很简单，但是里面有一点需要注意的是：在没有实例化的类模板里，编译器不能区分const_iterator是类型还是静态成员变量所以需要在前面加个typename，还有另外的解决方案如下代码所示：

template<class T>
void Print_vector(const vector<T>& v)
{
// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
// 是类型还是静态成员变量，需要在前面加个typename
vector<T>::const_iterator it = v.begin();

//或者换一种
//auto it = v.begin();
//第一种遍历vector容器
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//第二种遍历vector容器
//for (auto e : v)
//{
//cout << e << " ";
//}
//cout << endl;
}

2.10 实现打印所有容器（加餐）

template <class Container>
void Print_Container(const Container& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}

3. 完整的vector实现代码如下

vector.h

#pragma once
#include<iostream>
#include<assert.h>
#include <vector>
namespace Tao
{
using namespace std;

template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//构造函数
//这个是前置构造函数
vector() = default;
vector(const vector<T>& v)
{
for (auto e : v)
{
push_back(e);
}
}

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

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


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

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

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

size_t capacity()const
{
return _end_of_storage - _start;
}
size_t size()const
{
return _finish - _start;
}
bool empty()
{
return _start == _finish;
}



//reserve开空间
void reserve(size_t n)
{
if (n > capacity())
{

size_t old_size = size();
T* temp = new T[n];
//memcpy(temp, _start, size() * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
temp[i] = _start[i];
}
delete[]_start;
_start = temp;

//_finish = temp + size();//这个是错误的示范，因为delete掉_start了，
//那temp = _strt +size()（_finish-_start) 就为_finish，但是finish为NULL
//因为已经被释放了
_finish = temp + old_size;

_end_of_storage = temp + n;
}
}

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

void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
//这里包括两种情况，一种是 size < n < capacity;
//还有一种是capacity < n 那就需要拿n来进行扩容操作，而这步操作在reserve(n)
//会实现
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
}


iterator insert(iterator pos, const T& v)
{
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 = v;
++_finish;
return pos;
}

iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);

auto 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)
{
// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
// 是类型还是静态成员变量，需要在前面加个typename
vector<T>::const_iterator it = v.begin();

//或者换一种
//auto it = v.begin();
//第一种遍历vector容器
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//第二种遍历vector容器
//for (auto e : v)
//{
//cout << e << " ";
//}
//cout << endl;
}

template <class Container>
void Print_Container(const Container& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}

END!

原文地址：https://blog.csdn.net/2301_80475151/article/details/142826500

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【开源物联网平台】Fastbee系统稳定性和压测报告
下一篇：Leetcode 乘积最大子数组

linux上的smb共享文件夹
在Linux和Windows上分别用SMB实现文件夹共享
阅读更多2024-10-15
Flythings学习（二）控件相关
本系列笔记根据flythings官方文档进行学习，连接如下，相关下载在文档中的环境安装部分。
阅读更多2024-10-15
入门网络安全工程师要学习哪些内容
大家都知道网络安全行业很火，这个行业因为国家政策趋势正在大力发展，大有可为!但很多人对还是不了解，不知道需要学什么?知了堂小编总结出以下要点。是一个概称，学习的东西很多，具体学什么看自己以后的职业定位
阅读更多2024-10-15
jvm笔记
内存分一半，只操作一半内存的数据，标记活下来的放到另一半内存，原先内存数据全部删除。不同的锁标志位，会导致32bit的数据展示的不一样，对象的hashcode在其他锁状态没有是因为存到其他地方了。指针
阅读更多2024-10-15
Unity3D 同步怪物实体到客户端详解
在上面的代码中，MonsterSync脚本实现了IPunObservable接口，用于同步怪物实体的位置和旋转信息。通过上面的介绍，我们了解了在Unity3D中如何实现怪物实体的同步。在游戏开发中，怪
阅读更多2024-10-15
MySQL-约束
注意：目前上述的两张表，在数据库里面，并未建立外键关联，所以是无法保证数据的一致性和完整性的。1.概念:约束是作用于表中字段上的规则，用于限制存储在表中的数据。注意：约束是作用于表中字段上的，可以在创
阅读更多2024-10-15
一区鱼鹰优化算法+深度学习+注意力机制！OOA-TCN-LSTM-Attention多变量时间序列预测
一区鱼鹰优化算法+深度学习+注意力机制！OOA-TCN-LSTM-Attention多变量时间序列预测
阅读更多2024-10-15
SAM应用：医学图像和视频中的任何内容分割中的基准测试与部署
最近在分割基础模型方面的进展，使得在广泛的自然图像和视频上能够进行准确和高效的分割，但它们对医学数据的实用性仍然不清楚。在这项工作中，作者首先对Segment Anything Model 2（SAM
阅读更多2024-10-15
架构设计笔记-11-未来信息综合技术
包括：服务化原则、弹性原则、可观测原则、韧性原则、所有过程自动化原则、和架构持续演进原则。是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构，并以密码学方式保证的不可篡改和不可伪造的
阅读更多2024-10-15
【WebGis开发 - Cesium】三维可视化项目教程---图层管理基础
本篇主要讨论如何管理二三维图层，仅以wmts和3dtiles做图层管理示例。我会在接下来的教程里专门针对其他各类图层加载方式做详细介绍。二三维图层管理是三维可视化项目里重要的组成部分，通过树结构管理图
阅读更多2024-10-15

C++(vector的实现)

1. vector介绍

2. vector的实现

2.1 vector的类的基本结构

2.2 vector构造和析构函数的实现

2.3 赋值运算符重载、swap、begin()、end()、capacity()、size()

2.4 reserve的实现（重点）

2.5 push_back和pop_back()操作实现

2.6 resize的实现

2.7 insert和erase的实现

2.8 方括号重载即下标访问

2.9 实现Print_vector操作

2.10 实现打印所有容器（加餐）

3. 完整的vector实现代码如下

相关文章