ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【C++】STL——vector模拟实现 [打印本页]

作者: 滴水恩情 时间: 2022-6-25 22:42
标题: 【C++】STL——vector模拟实现

目录
实现框架
一、基本的结构雏形
二、默认成员函数
1.构造函数
1.无参构造
2.迭代器区间构造
2.拷贝构造
1.传统写法
2.现代写法
3.赋值运算符重载函数
1.传统写法
2.现代写法
4.析构函数
5.操作符重载函数
三、迭代器相关的函数
四、容量相关的函数
1.size和capacity
2.reserve
3.resize
五、增删查改相关的函数
1.push_back
2.pop_back
3.insert
4.erase
5.swap
六、完成代码

实现框架

一、基本的结构雏形

首先我们将所需的成员变量一一罗列出来

//为了避免和库里的vector产生冲突，在自己的命名空间内实现vector
namespace vec
{
template<class T>//通过模板能够实现不同类型的数据存储
class vector
{
public:
typedef T* iterator;
/*
各类函数功能实现
*/
private:
iterator _start; //指向容器中的起始位置
iterator _finish; //指向容器中最后一个有效数据的下一个位置
iterator _end_of_storage; //指向容器中现有容量的位置
};
}

复制代码

二、默认成员函数

1.构造函数

1.无参构造

对于vector的无参构造，我们只需要将三个成员变量置为空指针即可。

//构造函数 --- 无参构造
vector()
//初始化成员列表
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}

复制代码

2.迭代器区间构造

当我们想要以某个对象的区间来进行初始化时，就需要用到模板了。它既可以是类模板，也可以是函数模板。
例如：
用一个常量字符串来构造vector

const char* p = "hello";
vector<char>v(p, p + 2);

复制代码

用一个数组来构造vector

int a[5] = { 1,2,3,4,5 };
vector<int>v1(a, a + sizeof(a) / sizeof(a[0]));

复制代码

用一个string类来构造vector

string s1("hello");
vector<char>v2(s1.begin(), s1.end());

复制代码

//构造函数 --- 迭代器区间构造
template <class InputIterator>//既是一个类模板的成员函数，又可以是一个函数模板
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);//尾插
++first;
}
}

复制代码

2.拷贝构造

对于拷贝构造函数，因为涉及到深浅拷贝的问题，我们这里提供传统写法与现代写法。
1.传统写法

/*用v1去拷贝构造v2*/
//v2(v1)
//传统写法1
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //让v2开辟一块和v1一样大小的空间
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
memcpy(_start, v._start, v.size() * sizeof(T));
}
//v2(v1)
//传统写法2
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //让v2开辟一块和v1一样大小的空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//通过循环进行赋值
}
//最后调整_finish和_end_of_storage的大小
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}

复制代码

  以上两种写法存在样的区别呢？
  写法1：依然存在浅拷贝的问题；写法2彻底完成了深拷贝的问题；
          从代码上来看，两者的区别在于写法1对于数据的拷贝采用的是memcpy函数，写法2对于数据的拷贝采用的是for循环进行赋值拷贝；两者在拷贝数据的方式上对于内置类型或不需要进行深拷贝的自定义类型，完全是满足要求的；但是当vector存储的是string时，一定存在问题。

          vectorv1存储了5个数据，每个数据都是string类，vectorv2(v1),v2也开辟了5个空间，并且在memcpy下完成拷贝，但是它们却指向了同一块空间，在调用析构函数时，就会导致同一块空间释放多次，最终内存泄露。
  对于写法2，它会去调用string类的赋值重载函数进行一个深拷贝
  2.现代写法

//v2(v)
//现代写法
vector(const vector<T>& v)//也支持vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end()); //通过迭代器区间对tmp进行拷贝
swap(tmp); //交换v2和tmp的数据
//this->swap(tmp);
}

复制代码

3.赋值运算符重载函数

和拷贝构造一样，使用memcpy时存在浅拷贝的问题
1.传统写法

//v1 = v2
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //先将v1的空间释放掉
_start = new T[v.capacity()]; //再开辟一块和v2一样大小的空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//通过循环进行赋值
}
//最后调整_finish和_end_of_storage的大小
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
return *this;
}

复制代码

2.现代写法

//v1 = v2
//现代写法
vector<T>& operator=(vector<T> v)//v2传给v，实际上拷贝构造一个和v2一样的v
{
swap(v); //然后直接交换数据即可
return *this;
}

复制代码

4.析构函数

//析构函数
~vector()
{
if (_start)//防止对空指针进行释放
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}

复制代码

5.操作符重载函数

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

复制代码

三、迭代器相关的函数

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; //返回的是容器最后一个数据的下一个位置
}

复制代码

四、容量相关的函数

1.size和capacity

size_t size() const
{
return _finish - _start;//返回的是容器中有效数据的个数
}
size_t capacity() const
{
return _end_of_storage - _start;//返回的是容器的实际有效容量
}

复制代码

2.reserve

reserve增容：
1.当 n > capacity 时，将capacity扩大到n；
2.当 n < capacity 时，不进行任何操作；

void reserve(size_t n)
{
if (n > capacity())//判断是否需要扩容
{
//扩容
size_t sz = size(); //提前算好增容前的数据个数
T* tmp = new T[n]; //开辟n个空间
if (_start)
{
//数据拷贝，也不能去使用memcpy函数
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start; //释放旧空间
}
_start = tmp; //指向新空间
_finish = _start + sz;
_end_of_storage = _start + n;
}
}

复制代码

对于reserve，我还需要注意两个问题：
1.对增容前的数据个数进行记录

如果不提前算好增容前的数据个数，而是在增容完后更新_start，对于_finish和_end_of_storage都会出现问题，因为增容完后，就需要释放旧空间。
2.增容前后的数据拷贝不能使用memcpy

如果使用memcpy进行数据的拷贝后，随着_start的释放，tmp作为新的_start后，当进行访问操作时，就存在非法访问
3.resize

当nsize时，我们还需要判断n是否大于capacity，是否增容
在resize函数中的第二个参数val，采用的是缺省（匿名对象），因为我们并不知道T是什么类型，如果是int/int*给val = 0是可以的，但是T还有可能是vector，我们给到匿名对象作为缺省值的好处在于，对于内置类型它也有自己的默认构造函数

例如:
int i = int(); // i = 0
int j = int(10);// j = 10

复制代码

当我们不给val传任何参数时，它会去调用自己的默认构造函数给val

void resize(size_t n, const T& val = T())
//T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}

复制代码

五、增删查改相关的函数

1.push_back

尾插数据时，首先需要判断容器是否已满，若满则去调用reserve

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

复制代码

2.pop_back

在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。

void pop_back(const T& x)
{
assert(_finish > _start);
--_finish;
}

复制代码

3.insert

insert是在某个位置插入数据，插入数据就存在是否扩容，如果不需要扩容，插入数据时不会存在然后的问题；如果需要扩容，但未调整pos，会存在pos失效；

iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
//扩容会导致pos失效，需要更新一下pos
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;
}
void test_vector4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
if (it != v1.end())
{
//如果insert中发生了扩容，那么会导致it指向的空间被释放
//it本质就是一个野指针，这种问题，我们叫做迭代器失效
v1.insert(it, 30);
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)