您现在的位置是:首页 >技术交流 >【STL】模拟实现vector(详解)网站首页技术交流
【STL】模拟实现vector(详解)
文章目录
前言
本文将讲述怎么模拟实现vector类,有些同学可能会问了,我要实现这个有什么用?会用不就可以了吗?
你没有错,但是我们通过模拟实现vector类可以帮助我们更加深入的了解它具体是怎么一回事?它的内部结构是怎么样的?如果以后我们写程序,碰到某个地方报错,也能很快排查出问题哦~
?欢迎关注:?点赞?收藏✍️留言
?码字不易,你的?点赞?收藏❤️关注对我真的很重要,有问题可在评论区提出,感谢阅读!!!
持续更新中~
vector的模拟实现
一,搭建框架
我们首先把大概框架搭建出来,就像打铁,要先打个大概的模子再细细锤炼,它和string的不同在于,vector 是基于连续内存的动态数组,而 string 可以是基于指针或数组的动态字符序列,所以vector 的成员函数是三个指针:指向数组的指针 start_、指向最后一个元素的下一个位置的指针 finish_,以及指向整个内存空间末尾的指针 end_of_storage_。那么我们现在就来搭建一下:
#pragma once
#include <assert.h>
namespace hxq
{
template<class T>
//这里要用模板,因为数组不只有一种类型
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;//返回首元素位置的指针
}
iterator end()
{
return _finish;//返回最后一个元素下一个位置的指针
}
//const类型
const_iterator begin() const
{
return _start;//返回首元素位置的指针
}
const_iterator end() const
{
return _finish;//返回最后一个元素下一个位置的指针
}
~vector()//析构函数,释放资源
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t capacity() const
{
//返回vector空间大小
return _end_of_storage - _start;
}
//const类型
const T& operator[](size_t pos) const
{
//用于访问指定位置上的元素
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos)
{
//用于访问指定位置上的元素
assert(pos < size());
return _start[pos];
}
//返回vector的元素数量
size_t size() const
{
return _finish - _start;
}
//返回第一个元素
T& front()
{
assert(size() > 0);
return *_start;
}
//返回最后一个元素
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
private:
iterator _start;//指向数组的指针
iterator _finish;//指向最后一个元素的下一个位置的指针
iterator _end_of_storage;//指向整个内存空间末尾的指针
};
}
二,实现构造函数
vector的构造函数非常简单,因为成员变量都是指针,所以我们只要将它们置空即可。
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
三,构造的其他方式
和我们实现string一样,vector也有传统1写法和现代写法,他们实现的效果是一样的,不过是思维不一样而已,那么我们再来一起尝试写一写两种方式。
传统写法
1.拷贝构造
假设说是v1(v2)
步骤:
- 给v1开辟新空间
- 将v2的值按位拷贝给v1
- 将成员变量更新
所以我们可以这样写:
vector(const vector<T>& v)
{
_start = new T[v.size()]; // v.capacity()也可以
//这里还可以复用reserve函数,后面我们再实现它
//思考题:
//思考一下这里我们可以这样写吗?
//memcpy(_start, v._start, sizeof(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.size();
}
思考题答案是不能
在实现vector拷贝构造函数时,使用memcpy是一种浅拷贝,它仅仅是复制了vector对象的数据成员_start所指向的内存区域,而没有复制_start所指向的数组中的每个元素内容。这意味着,如果原始vector发生变化,则新的vector也会受到影响,导致两个vector共享同一个数组。这样就会出现问题,当其中一个vector执行析构函数时,可能会释放已经被释放的内存区域,导致程序崩溃。
因此,为了避免这种问题,我们需要对vector的每个元素进行逐个拷贝,以实现深度拷贝。因此,上述代码采用了for循环来依次拷贝每个元素的方式,确保了新的vector与原始vector具有独立的数组空间和元素值。
拷贝构造还可以这样写,复用之后我们实现的函数实现。
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
reserve(v.size());//设置空间
for (const auto& e : v)
{
push_back(e);//尾插
}
}
我们先能看懂大概意思就好,后面会一一实现这些函数的。
这里我们先将其初始化,再调用函数给它分配空间,调用函数插入数据(也就是拷贝数据了)。
2. 重载赋值操作符
假设是v1=v2
思路:
- 直接利用另一个 vector 对象的值。在函数内部使用
swap()
函数交换了两个 vector 对象的_start
、_finish
和_end_of_storage
成员变量,从而将右侧的 vector 对象中的数据成员拷贝到了当前对象中,完成了赋值操作- 为什么可以?因为它是传值,所以不影响原对象
vector<T>& operator=(vector<T> v)
{
swap(v._start, _start);
swap(v._finish, _finish);
swap(v._end_of_storage, _end_of_storage);
return *this;
}
3. 使用迭代器构造
当我们需要构造一个包含一定数量元素的 vector 对象时,可以使用 vector 的构造函数。其中,vector(InputIterator first, InputIterator last) 构造函数接受一对迭代器 [first, last) 作为参数,用于指定需要添加到 vector 中的元素范围。构造函数的实现方式是遍历迭代器范围,每次调用 push_back() 函数将迭代器指向的元素添加到当前 vector 对象的末尾。
需要注意的是,在构造函数中,vector 的 _start、_finish 和 _end_of_storage 成员变量都被设置为 nullptr,表示当前 vector 对象还没有分配任何内存空间。在循环遍历迭代器范围时,每次添加元素时,vector 内部的内存管理函数会自动动态地分配内存空间,并将新的元素存储在这个空间中。当元素个数超过了当前内存空间的大小时,vector 会自动扩充内存空间,以满足新增元素的需求。
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while(first != last)
{
push_back(*first);
++first;
}
}
4. 初始化为N个val的vector
还有一种初始化方式是初始化为N个val的vector,它需要两个参数,一是数量n,二是val,这里实现时要注意的是,我们要考虑的不只是一种类型,所以这里要用到模板相关知识。
具体实现就简单多了,这只需要先初始化再申请空间,将val的值利用push_back函数插入即可,可能你会问:“为什么老是用这些函数?不自己再实现一遍呢?”,我们要注意的是,这些函数后文我们都会再实现的,但是这里为什么要用函数呢?是为了
复用
,你想想,要是我们写的代码中有一堆功能相似的代码,是不是屎山代码,极其不美观?我们要尽量避免大量重复代码这种情况。
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
现代写法
1. 拷贝构造
还有一种现代写法
这是一种有着资本主义或者说老板思维,让员工干活
具体怎么回事呢?
v2(v1)
我们可以新建一个vector对象,并且以nullptr来初始化它
的三个成员变量,然后再新建一个空间,这个新的空间以v1的值、以 迭代器的方式初始化,再使用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);
}
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
2. 赋值重载
和传统写法一样,不过这里可以复用前面的swap函数
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
四,实现vector相关函数
1. reserve函数
在 C++ 的 vector 中,
reserve(size_type n)
是一个用于预留内存空间的函数。具体来说,
reserve()
函数接受一个参数n
,代表需要预留的内存空间大小。在调用reserve()
函数后,vector 内部会分配一块大小为n
的内存空间,但不会改变 vector 的元素个数(即size()
函数返回值不受影响)。这意味着,我们可以通过reserve()
函数提前为 vector 分配足够的内存空间,以避免频繁的动态扩容操作,从而提高程序的性能。需要注意的是,尽管
reserve()
函数为 vector 分配了一定大小的内存空间,但并不意味着这些内存空间都被包含在 vector 的有效元素范围内。只有当这些内存空间真正被添加到 vector 对象中时,它们才被视为 vector 对象的一部分。因此,在调用reserve()
函数后,如果需要使用新的内存空间,则应该通过push_back()
、insert()
等函数添加元素,从而将新的元素存放到 vector 对象中。需要注意的是:我们应该根据实际情况慎重考虑应该预留多少内存空间,以避免过度浪费内存资源。
实现思路:
- 首先判断传入的参数是否大于已有空间
- 需要扩容则开辟一块新的空间
- 将所有元素拷贝到新空间
- 再将成员变量更新
这里有个问题,将所有元素拷贝到新空间可以用memcpy
函数吗?
回顾一下memcpy
函数的使用:
当调用 memcpy() 函数时,它会将从源内存地址开始的 n 个字节的数据拷贝到目标内存地址中,也就是从 src 所指向的内存地址开始的 n 个字节的数据会被拷贝到 dest 所指向的内存地址中。
所以我们能使用它来拷贝数据吗?仔细思考就会发现,它不完全符合条件。
std::vector 对象的内部存储结构是动态分配的,对其使用 memcpy() 拷贝时可能会出现未定义行为。
std::vector 是 C++ 标准库提供的容器之一,它除了存储元素外还有管理容器大小、元素添加和移除等操作。使用 memcpy() 会绕过 std::vector 对象自身的管理和维护,可能会导致程序出现异常或者崩溃。
std::vector 可能包含自定义类型的元素,而这些元素可能包含指针等资源,需要进行深拷贝才能正确复制。如果使用 memcpy() 直接拷贝内存,就无法正确处理这些元素的拷贝。
具体怎么回事?
在 C++ 中,
std::vector
可以存储任意类型的元素。当这些元素是自定义类型时,往往会包含指针等资源。例如:struct point { int x; int y; }; struct line { point* p1; point* p2; };
在上面的代码中,我们定义了
point
和line
两个结构体,其中line
的成员变量p1
和p2
是指向point
类型对象的指针。如果我们将line
对象作为元素插入到std::vector
容器中,那么这个容器就包含了指向堆内存中的point
对象的指针。当我们需要对
std::vector
容器进行拷贝操作时,如果直接对容器中的指针进行拷贝,就直接复制了指针的值,而没有复制指针所指向的对象。也就是说,新的std::vector
容器中的元素指向的是旧的std::vector
容器中的元素所指向的对象,造成两个std::vector
容器共享同一块堆内存,无法正确地实现拷贝。为了解决这个问题,需要对包含指针等资源的自定义类型进行深拷贝。深拷贝是一种将指针所指向的对象也复制一份的拷贝方式,以确保新的对象与旧的对象相互独立,不会共享同一个资源。对于包含指针等资源的自定义类型,可以通过重载拷贝构造函数和赋值运算符,或者使用智能指针等方法进行深拷贝。但是,这些方法不能与
memcpy()
函数兼容,如果直接使用memcpy()
函数会导致指针指向错误的内存地址,无法正确地完成拷贝操作。而且,在 C++ 中,
std::vector
是一个动态数组容器,它使用动态分配的内存来存储元素。当我们向std::vector
容器中添加元素时,如果容器已经占满了当前的内存空间,就会自动重新分配更大的内存,并将原有的元素复制到新的内存空间中。这个过程称之为“重新分配”(re-allocation)。在重新分配内存时,
std::vector
会自动调用元素类型的构造函数来构造新的元素对象,并调用元素类型的析构函数来销毁旧的元素对象。这个过程会保证std::vector
容器中的元素始终是合法的、可访问的对象。如果对
std::vector
使用memcpy()
函数进行拷贝操作,由于memcpy()
只会简单地复制一段内存的内容,不会触发任何构造函数或析构函数的调用,从而导致拷贝出的容器中的元素对象处于不合法的状态。这样的拷贝结果是未定义的,可能会导致程序运行出错、崩溃、甚至安全问题,因此不建议使用memcpy()
来进行std::vector
的拷贝操作。
代码:
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
2,resize函数
在 C++ 中,
std::vector
容器提供了resize()
函数来改变容器的大小。该函数接受一个整型参数newSize
,表示容器调整后的大小。如果当前容器大小小于newSize
,则会在容器尾部插入一定数量的元素来扩充容器大小;如果当前容器大小大于newSize
,则会删除容器尾部的一定数量的元素来缩小容器大小。具体来说,当
newSize
小于当前容器大小时,resize()
会将末尾多余的元素删除,释放内存空间;当newSize
大于当前容器大小时,resize()
会在末尾插入必要数量的元素,并分配更多的内存空间。
代码:
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);//如果空间少了就申请空间
}
if (n > size())
{
// 初始化填值
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
3,push_back函数
在C++中,
std::vector
是一个动态数组容器,其大小可以动态地增加或减少。我们可以使用push_back()
函数向std::vector
容器的尾部添加元素。
push_back()
函数接受一个参数,表示需要添加到容器尾部的元素值,该函数会将元素添加到容器的末尾,并自动调整容器的大小。如果容器已经占满了目前已分配的内存空间,那么会自动申请更多的内存空间,并将原来的元素对象移动到新的空间中保存。
它可以使用两种方式实现:
-
自给自足
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; }
-
复用insert函数
void push_back(const T& x) { insert(end(), x); }
4,pop_back函数
在C++中,
std::vector
是一个动态数组容器,其大小可以动态地增加或减少。我们可以使用pop_back()
函数从std::vector
容器的尾部移除元素。
pop_back()
函数没有参数,它将从容器尾部移除一个元素。如果容器不为空,那么该函数会将容器的大小减少 1,并将最后一个元素对象从容器中销毁,释放内存空间。
思路:
这里我们可以不需要去删除元素,只要控制_finish的位置即可
代码:
void pop_back()
{
assert(_finish > _start);
--_finish;
}
5,insert函数
std::vector
是 C++ 标准库中的一个容器,可以快速、高效地对一组元素进行动态数组式的操作。其中,insert
函数是std::vector
容器提供的一个成员函数,用于在指定位置插入一个或多个元素。
这里我们仅实现插入一个元素的函数
思路:
insert函数是用来在
std::vector
容器的任意位置插入一个新元素的函数。在该函数中,我们需要传入两个参数,分别是迭代器pos
和元素x
。首先,我们需要通过迭代器找到要插入新元素的位置。对于
std::vector
容器而言,迭代器类型为T*
,即指向存储容器元素的指针。该函数的第一个参数pos
就是要传入指向容器中某个元素的指针,表示将新元素插入到该元素前面或后面。接下来,我们需要指定要插入的新元素的类型。由于
std::vector
容器中所有元素类型必须相同,因此我们使用模板参数T
来表示要插入元素的类型,并将其定义为const T&
常量引用。最后,使用内部实现逻辑,我们可以通过比较迭代器
pos
和_start
、_finish
、_end_of_storage
三个指向容器起始、末尾和存储空间末尾位置的指针来确认pos
的位置是否合法,从而防止越界访问或插入。然后,我们将新元素插入到指定位置,将原先位置及其后面的元素向后移动一位。这样,我们就可以在
std::vector
容器中的任意位置插入一个新元素,从而添加、修改或更新容器中的元素。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
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 = x;
++_finish;
return pos;
}
6,erase函数
std::vector
是 C++ 标准库中的一个容器,可以快速、高效地对一组元素进行动态数组式的操作。其中,erase
函数是std::vector
容器提供的另一个成员函数,用于删除指定位置或一段区间内的一个或多个元素。
这里我们仅实现删除一个元素的函数
思路:
在 STL 中,
erase
函数返回的是指向被删除元素之后的一个元素的迭代器,而不是指向被删除元素的迭代器。这种设计是考虑到erase
函数的常见用法,即在循环中删除符合条件的元素。在这种情况下,如果返回指向被删除元素的迭代器,那么在执行 erase 操作后,迭代器会失效,即无法正常访问和操作,进而导致循环出错甚至崩溃。因此,STL 设计者规定返回指向被删除元素之后的一个元素的迭代器,避免使用已经失效的迭代器。
代码:
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
源码
#pragma once
#include <assert.h>
#include <iostream>
namespace hxq
{
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()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//传统写法
//拷贝构造
// v2(v1)
// vector(const vector<T>& v)
// {
// _start = new T[v.size()]; // v.capacity()也可以
// //memcpy(_start, v._start, sizeof(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.size();
// }
// v2(v1)
// vector(const vector<T>& v)
// :_start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
// {
// reserve(v.size());
// for (const auto& e : v)
// {
// push_back(e);
// }
// }
//初始化为N个val
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
//使用迭代器构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while(first != last)
{
push_back(*first);
++first;
}
}
//现代写法
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// v2(v1)
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
// v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
size_t size() const
{
return _finish - _start;
}
//相关函数
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
// 初始化填值
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
void push_back(const T& x)
{
/* if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
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 = x;
++_finish;
return pos;
}
// stl 规定erase返回删除位置下一个位置迭代器
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
//if (size() < capacity()/2)
//{
// // 缩容 -- 以时间换空间
//}
return pos;
}
T& front()
{
assert(size() > 0);
return *_start;
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
后记
这篇我们主要讲了vector是怎么实现的,首先搭建大概的框架,然后实现构造函数,再拓展到构造的其他方式,有拷贝构造、迭代器构造、初始化为N个val的构造等等,它们还有传统和现代两种实现方式,功能都是一样的,只不过思想不一样,现代的实现更加侧重复用
和老板思维
最后我们实现了相关常见的函数,至此vector便已模拟实现。
对学习这里的同学的建议是,考虑清楚每一个函数的实现目的,再考虑实现方式,以及自己动手撸一遍肯定比只看印象深刻。
感谢大家支持!!!
respect!
下篇见!