自学内容网 自学内容网
自学内容网 > 正文

【C++】- STL之vector模拟实现

🕗 发布于 2024-10-20 05:10 c++  开发语言  c语言  动态规划  数据结构  

1.vector的介绍

  1. vector是表示可变大小数组的序列容器。
  2. vector采用的连续存储空间来存储元素。意味着也可以采用下标对vector的元素进行访问，和数组一样高效。但是它的大小是可以动态改变的，而且它的大小会被容器自动处理。
  3. vector使用动态分配数组来存储它的元素，当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
  4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比时间需要的存储更大，不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
  6. 与其他动态序列容器相比（deque、list and forward_list），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

2.vector的基本结构

vector是一个顺序存储的容器，也可以说是一个数组，那么对于它的结构，我们可以用三个迭代器来组成，如下图：

在vector当中，其实迭代器就是一个指针。所以我们的vector类的基本成员变量可以这样设计。

template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};

3.vector模拟实现

3.1 构造函数

构造函数最主要的有两个：无参构造函数和拷贝构造函数。

3.1.1无参构造函数

无参构造函数只需要将全部迭代器赋值空。 

//无参构造函数：直接全部给nullptr
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}

3.1.2 带参数的构造函数（包括size_t和int类型）

对于带参数的构造函数，当参数类型为size_t时，会先为vector分配指定数量的空间，并为每个元素进行初始化。

vector(size_t n, const T& val = T())
{
_start = new T[n];
_finish = _start;
_end_of_storage = _start + n;
for (size_t i = 0; i < n; i++)
{
*_finish++ = val;
}
}

3.1.2区间构造函数

区间构造函数接收两个迭代器first和last，由于不同类型的容器迭代器类型可能不同，因此设计成函数模板，将区间内的内容尾插到vector，但是调用push_back接口通过_finish == _endofstorage判断是否满，需要初始化

template<class InoutIterator>
vector(InoutIterator first, InoutIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}

3.1.3 拷贝构造函数

拷贝构造的模拟实现可以通过一个个尾插的方式实现：

vector<int> v2(v1);

即将v1的数据从头到尾遍历一遍，遍历的时候顺便将v1的数据尾插到v2。

 

//拷贝构造函数
//vector<int> v1;
//vector<int> v2(v1);
vecotr(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
const_iterator it = v.begin();//定义一个迭代器指向v1的头
while (it != v.end())
{
push_back(*it); //将v1的数据一个个尾插到v2中，这里尾插在后面实现
it++;
}
}

注意：不要使用memcpy函数拷贝数据，如果数据是内置类型或浅拷贝的自定义类型，使用memcoy是没什么问题的，但如果数据是需要深拷贝的自定义类型（string），就会出现问题，拷贝的数据和源数据指向同一块空间，因此，我们使用for循环依次赋值，调用string的赋值运算符重载完成深拷贝，push_back在实现的时候会调用深拷贝类型的赋值运算符重载。

 3.2 析构函数

将空间释放掉，_start,_finish,_endofstorage置为空指针

//析构函数
~vector()
{
    delete[] _start;
    _start = _finish = _endofstrorage = nullptr;
}

3.3赋值运算符重载

3.3.1传统写法

vector<T>& operator=(const vector<T>& v)
{
//防止自己给自己赋值
if (this != &v)
{
//1.开辟空间
T* tmp = new T[v.capacity()];
//2.将数据拷贝到新空间当中
for (int i = 0; i < v.size(); i++)
{
tmp[i] = v._start[i];
}
//3.释放原有空间
delete[] _start;
//4.指向新空间
_start = tmp;
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
return *this;
}

3.3.2现代写法

//赋值运算符重载现代写法
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//只需要交换this和v的桑指针即可
void swap(vector<T>& v)
{
//调用标准库中的swap函数
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);

}

注意：传值传参时，自定义类型会调用拷贝构造函数形成形参，形参是实参的一份临时拷贝，因此我们可以让这个形参跟我们的this交换。

这样我们的this就成功被复制为我们想要的值了，this指向的旧空间在交换后被形参v所指向，出了这个作用域之后，形参v会调用其析构函数释放掉this指向的旧空间

因此，只需要传值传参swap交换就可以完成开辟新空间+拷贝数据+释放原有空间+指向新空间

3.4扩容函数 reserve

当n大于对象当前的capacity时，将capacity扩大到n或大于n

当n小于对象当前的capacity是，就不需要

实现步骤：

1.新开辟一块空间，若容器为空，将_start,_finish指向新开辟空间的首元素地址，_endofstorage指向新开辟空间的最后一个元素下一个位置

2.若容器不为空，将数据拷贝到新空间，释放掉旧空间，更新_start,_finish,_endofstorage的位置

注意：将数据拷贝到新空间，仍然不能用memcpy函数，因为对于需要深拷贝的自定义类型，使用memcpy函数以后，新开辟空间里的元素原空间里的元素所指向的内存空间是一样的，当旧空间被释放时，会调用自定义类型的析构函数，从而使得新开辟空间里的元素指向的内存空间也被释放 

void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//新开辟一块空间
//容器不为空
if (_start)
{
size_t sizec = size();// 计算原来容器size个数
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;//释放旧空间
_start = tmp; //更新_start
_finish = _start + sizec;// 更新_finish
_endofstorage = _start + n; // 更新_endofstorage
}
//容器为空，更新_start,_finish,_endofstorage的位置
else
{
_start = _finish = tmp;
_endofstorage = _start + n;
}
}
}

 3.5改变数组长度函数 resize

当n<size时，直接将_finish = _start+n（将有效数据长度缩小）

当size<n<=capacity时，我们将有效数据的长度增加到n，增加出来的有效数据内容是val

当n>capacity时，先调用上面的reserve函数进行增容，再将有效数据的长度增加到你，增加出来的有效数据内容是val

void resize(size_t n, const T& val = T())
{
//n<size()
if (n < size())
{
_finish = _start + n;
}
//n>size()
else
{
//增容
if (n > capacity())
reserve(n);
//填充数据val
size_t count = n - size();
while (count--)
{
*_finish = val;
++_finish;
}
}
}

 3.6 判空函数 empty

判断size() == 0

bool empty() const
{
    return size() == 0;
}

3.7 尾插函数 push_back

尾插入数据，首先要检查是否已满，已满则进行增容，增容后尾插

void push_back(const T& x)
{
//扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);

}

*_finish = x;
++_finish;
}

3.8 尾删函数 pop_back

对于尾删，首先要判断容器是否为空，若为空，则断言报错，不为空，_finish--

void pop_back()
{
assert(!empty());
--_finish;
}

3.9 插入函数 insert

容量不够，先增容，增容之前先记录下pos - _start的值，否则增容之后，pos还指向原来已经被释放的空间；

将pos位置往后的数据往后挪动一位，在pos位置插入值val；

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

 3.10 删除函数 erase

容器若为空，则做断言处理，若不为空，将pos位置往后的数据向前挪动一位,删除数字之后返回pos位置的迭代器，否则会失去该位置的迭代器，导致失效。

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

iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}

--_finish;
}


原文地址：https://blog.csdn.net/Aa_159147/article/details/142875627

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

相关文章

自学内容网
Copyright © 2015-2024