C++-vector模拟实现

🕗 发布于 2024-10-03 19:07 c++ 开发语言

###vector底层相当于是数组，查看源码可以发现，这个类的私有成员变量是三个迭代器；在实现时迭代器就可以当作是vector里面的元素的指针类型；

###vector是一个类模板，实现时也应当按照这样的写法用一个模板去实现，类模板vector中数据类型是T；

private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;

_start指向vector的开始地址，_finish指向vector的有效元素的结束地址，_end_of_storage指向vector最大存储数据的地址；

一、迭代器

typedef T* iterator;
typedef const T* const_iterator;

//迭代器
iterator begin()
{
return _start;
}
const_iterator begin()const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end()const
{
return _finish;
}

二、容量

size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
bool empty()const
{
return size() == 0;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//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;
_end_of_storage = tmp + n;
}
}
void resize(size_t n, const T& val = T())//匿名对象作为缺省值
{
if (n < capacity())
{
_finish = _start + n;
}
else
{
reserve(n);
for (iterator i = _finish ; i < _start + n; i++)
{
Insert(i,val);
}
}
}

1、reserve

基本思路：开辟一个临时的数组存放T类型的数据，让这个数组的大小为指定的n，将vector对象中的数据全部放到这个临时数组中，再清空vector中的数据，最后让vector对象存放数据的地址就是这个临时数组的地址；

两个关键点：

old_size：若是不先记录下size的话，后面给_finish重新赋值时使用到size()，size（）函数中_size不再是原来的_size,而是tmp，此时用_size去减_finish会出错;
深、浅拷贝问题：若是使用memcpy就是浅拷贝，对于vector中是内置类型的数据可以，但是若是vector对象中涉及到自定义类型，例如string为数据的情况，浅拷贝拷贝的是地址，那么tmp中的数据的地址就是vector对象中的数据地址，之后再delete掉_start，就相当于把要存放数据的tmp中的数据给释放了，这样会让数据丢失；所以一个一个赋值，对于内置类型无影响，对于自定义类型，例如string的类型，就是赋值重载，string实现时是深拷贝，这样就解决了。

2、resize

基本思路：若是比原来的size小，那么就让_finish等于_start+n，这样就访问不到n之后的数据了；若是比原来的size大，没有给值就用匿名对象T()，对于内置类型给初始值（0、空指针、0.0一类），对于自定义类型，调用默认构造函数，实现部分：先扩容，再插入数据。

三、元素获取

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& val)
{
if (_end_of_storage == _finish)
{
reserve(size() == 0 ? 4 : 2 * capacity());
}
*_finish = val;
_finish++;
}
void pop_back()
{
assert(size() > 0);
_finish--;
}
iterator Insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_end_of_storage == _finish)
{
size_t len = pos - _start;
reserve(size() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *(end);
end--;
}
*pos = val;
_finish++;
return pos;
}

iterator Erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator tmp = pos + 1;
while (tmp < _finish)
{
*(tmp - 1) = *tmp;
tmp++;
}
--_finish;
return pos;
}

1、insert和erase调用时迭代器失效的问题

insert：实现时若是涉及到空间不够要扩容，扩容时要先记录下pos和_start之间的距离，扩容之后_start不是之前的了，那么pos也要跟着更新;此时在调用insert时若是插入之后还要访问pos就要更新pos（因为pos已经改变了，若是不更新就使用原来的pos会找不到原来的数据）

就算没有扩容，空间够，insert之后使用到pos还是要先更新，因为此时的pos指向的是新插入进来的数据，而不是我们想要访问的原来的数据。

erase：erase的迭代器失效举一个例子：

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
container_print(v);
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl;
vector<int>::iterator p = v.begin();
while(p < v.end())
{
if (*p % 2 == 0)
{
v.Erase(p);
}
p++;
}
container_print(v);

运行结果似乎很正确，那再看：

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

container_print(v);
cout << "size:" << v.size() << endl;
cout << "capacity:" << v.capacity() << endl;
vector<int>::iterator p = v.begin();
while(p < v.end())
{
if (*p % 2 == 0)
{
v.Erase(p);
}
p++;
}
container_print(v);

此时会发现有偶数没有删除完全，这是因为迭代器失效了

原因：erase的实现中删除了pos指向的数据之后返回pos，此时的pos指向的是原来要删除的数据的下一个数据，在这个删除偶数的例子中，{1，2，3，4，5}pos指向2.删除之后pos指向3，再加加就是指向4，刚好到了下一个偶数，删除之后，pos指向5，再加加，循环结束，这里只是一个巧合；数据是{1，2，3，4，4，5}删除完2，pos指向第一个4，删除之后，pos指向第二个4，再加加那么pos指向是5了，就跳过了这个4，此时就是迭代器失效了；

为了解决，erase要使用到pos就要更新迭代器；

while(p < v.end())
{
if (*p % 2 == 0)
{
p=v.Erase(p);
}
else
{
p++;
}
}

这样写，每次删除完之后，pos指向就是原来要删除数据的下一个数据，若是这个数是偶数那就继续删，是奇数就加加跳过，这样就能够不错过数据了。

五、构造

1、强制的默认构造写法

vector() = default;//强制的默认构造

2、拷贝构造

//拷贝构造
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto it : v)
{
push_back(it);
}
}

3、赋值重载

void clear()
{
_finish = _start;
}
void swap(const vector<T>& tmp)
{
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}
//赋值重载（传统写法）
vector<T>& operator=(const vector<T>& v)
{
if (_start)//说明被赋值的对象不是空，要先清除
{
clear();
}
reserve(v.capacity());
for (auto it : v)
{
push_back(it);
}
}

//赋值重载（现代写法）
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}

a、传统写法：

若是原vector不为空，先置为空，之后再扩容，扩到和v一样的大小，再使用拷贝构造那一套，将v的数据一个一个尾插进入要被赋值的vector

b、现代写法：

传参时用tmp接收赋值等式右边的vector，进行拷贝构造，之后再和赋值等式左边的vector进行交换；（现代写法一般要在拷贝构造写好的情况下进行）；

4、迭代器初始化

//迭代器初始化
template <class InputIterator>//可以接收不同的迭代器，但是迭代器里面的数据的类型要相同
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}

这里使用到模板是为了接收各种类型的迭代器，但是值得注意的是这些迭代器的各自的容器里面的数据类型应该和此时的待构造的vector里面的数据保持一致，再不济也可以强制类型转换；

5、n个val去初始化

//n个 val 去初始化
vector(size_t n, const T& val = T())//不给值就用匿名对象,这个对象是 vector 里面的值
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}

6、析构

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

六、容器打印函数模板中的注意事项：

template <class T>
void vector_print(const vector<T>& v)
{
//要写 typename,否则没有实例化的 vector<T> 不知道const_iterator是类型还是静态成员变量
typename vector<T>:: const_iterator it = v.begin();
//auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}

这个函数模板定义在我们自己实现的vector类外面，用来打印vector，使用到迭代器，但是在写时注意这一行：

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

要加上typename，否则编译器分不清这是类里面的静态成员变量还是类型，当然若是写成静态成员变量去使用，那就一定是静态成员变量，但是这里不能直接写，要在前面加上tyepname；第二种方法可以直接用auto自动生成类型去使用。

原文地址：https://blog.csdn.net/zc331/article/details/142692336

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

上一篇：优化后的版本
下一篇：docker 搭建minimalist-web-notepad

作业4-23
【代码】作业4-23。
阅读更多2024-10-08
Dubbo常见的几个八股题
Dubbo 是一个高性能，轻量级的 RPC 框架，它提供了分布式架构下的服务之间通信方案，使得开发者可以不需要关心网络通信的细节。通过该框架可以使得远程服务调用方式和本地服务调用方式一样简单。由
阅读更多2024-10-08
杭电2041-2050
这个题目中组合数的实现方式值得我们借鉴。
阅读更多2024-10-08
uniapp使用Vue3组合式，如何进行Vue模块自动导入
通过使用插件，我们可以在uniapp项目中实现Vue3组合式API的自动导入，从而减少重复劳动，提高开发效率。这是一个简单但非常实用的技巧，值得每个uniapp开发者尝试。版权声明：本博客内容为原创，
阅读更多2024-10-08
redux 2020 (2)创建一个项目
【代码】redux 2020 (2)创建一个项目。
阅读更多2024-10-08
惊！Win11 24H2更新后文本框光标离奇失踪？解决方法在此！
系统之家于10月8日发出最新报道，有用户反馈，升级到Win11 24H2版本后，遭遇了文本框光标离奇失踪的困扰。具体表现是在运用基于Chromium的应用（如Google Chrome、Microso
阅读更多2024-10-08
节后超市店长需要干的七件事！
国庆时期如果销售依然不好，只有两种可能，要么是部分商品卖得不好，要么店内整体销售都不行。如果是第二种，就需要店长和采购分析及时销售下降原因，酌情改善，迅速提升销售了。节后要根据假日期间的工作情况，查缺
阅读更多2024-10-08
Java GC 分类，8和9使用的哪种？
对于Java 8来说，默认的垃圾收集器配置取决于JVM启动时指定的模式（Client还是Server）。如果是Server模式，默认采用的是Parallel GC；到了Java 9及以上版本，G1被设
阅读更多2024-10-08
软件测试学习笔记丨Mitmproxy使用
Mitmproxy是一款开源、免费的代理工具，支持Mac、Windows、Linux。相比其他代理工具，可以通过Python和Mitmproxy工具本身的插件机制，实现通过脚本对Mitmproxy的完
阅读更多2024-10-08
双十一好物清单！这5款高端又实用的双十一好物千万别错过！
在快时代的生活中，一种胶卷相机不断的席卷而来，让人们体验到老一辈人的烂漫，富士instax mini是一款以此成像的相机，拥有智能的自动曝光功能，在不同照明条件下能够实现心中所想要的目标亮度，此外小巧
阅读更多2024-10-08