目录
- 简介:
- 私有成员:
- 迭代器:
- 无参构造函数:
- push_back:
- reserve:
- resize:
- push_back:
- operator[]重载:
- begin && end:
- size && capacity:
- insert:
- erase:
- 带参构造:
- 迭代器区间构造:
- 拷贝构造 && 赋值运算符重载:
- 析构函数:
- 深浅拷贝的验证:
简介:
本文将利用C/C++模拟vector常用接口实现,可以更好的帮助理解vector底层。
主体的实现思路是先搭起来一个能跑的架子,再一点点的补充完善。
私有成员:
与我们曾经实现过得顺序表有些不一样,顺序表是一个malloc出来的指针指向数组,另外还有capacity与size
但在这里我们参照vector的原码进行模拟,使用三个迭代器进行控制这个动态数组。
private:
iterator start = nullptr;
iterator finish = nullptr;
iterator end_of_storage = nullptr;
故因此我们先要了解一下这个迭代器的设计,我们在模拟string时,由于string底层也是数组,由于虚拟地址的存在,我们认为数组在内存是连续的,故可以直接使用原生指针进行模拟迭代器,vector也是数组,我们当然也可以使用原生指针进行模拟迭代器
关于各个指针的含义
迭代器:
由于我们的vector需要支持不同类型,需要使用模版进行设计,故我们设置迭代器时如下图定义即可。
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
}
至于为什么设计两个类型迭代器是为了const对象
也可以调用,更具体可以看一下string模拟实现中的迭代器。
无参构造函数:
无参的没什么好说的,直接全初始化为nullptr。
vector()
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{}
push_back:
reserve:
因为push_back等很多操作涉及扩容的问题,故我们可以先实现一个reserve的接口,方便接下来使用:
void reserve(size_t n)
{
size_t capacity = end_of_storage - start;
if (capacity < n)
{
size_t size = finish - start;
T* tmp = new T[n];
//memcpy(tmp, start, size * sizeof(T));
for (int i = 0; i < size; i++)
{
*(tmp + i) = *(start + i);
}
delete[] start;
start = tmp;
finish = tmp + size;
end_of_storage = tmp + n;
}
}
关于为什么使用逐个赋值而不是直接memcpy是为了防止浅拷贝,在接下来会有演示
既然都实现了reserve那么resize也就顺便实现一下。
resize:
void resize(size_t n, const T& val = T())
{
size_t capacity = end_of_storage - start;
if (n > capacity)
{
reserve(n);
size_t len = end_of_storage - finish;
while (len--)
{
*finish = val;
finish++;
}
}
else
{
finish = start + n;
}
}
push_back:
void push_back(const T& val)
{
if (finish == end_of_storage)
{
size_t capacity = end_of_storage - start;
reserve(capacity == 0 ? 4 : capacity * 2);
}
*finish = val;
finish++;
}
这里针对嵌套类型也不用担心浅拷贝。
如果嵌套string类
*finish是一个string对象,赋值时会调用string内部的深拷贝。
operator[]重载:
T& operator[](size_t pos)
{
return start[pos];
}
const T& operator[](size_t pos) const
{
return start[pos];
}
由于const对象也会调用,故我们也要实现const版本的重载。
begin && end:
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
const_iterator end() const
{
return finish;
}
const_iterator begin() const
{
return start;
}
size && capacity:
size_t size()
{
return finish - start;
}
size_t capacity()
{
return end_of_storage - start;
}
size_t size() const
{
return finish - start;
}
size_t capacity() const
{
return end_of_storage - start;
}
insert:
void insert(iterator pos, const T& val)
{
if (finish == end_of_storage)
{
int distance = pos - start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = start + distance;
}
int i = 0;
int count = finish - pos;
while(count--)
{
*(finish - i) = *(finish - i - 1);
i++;
}
finish++;
*pos = val;
}
erase:
void erase(iterator pos)
{
assert(size());
int count = finish - pos - 1;
int i = 0;
while (count--)
{
*(pos + i) = *(pos + i + 1);
i++;
}
finish--;
}
带参构造:
vector(int n, const T& val = T())
{
reserve(n);
while (n--)
{
push_back(val);
}
}
迭代器区间构造:
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
拷贝构造 && 赋值运算符重载:
关于拷贝构造与赋值运算符重载一般有两种实现方案,一般方法与现代方法
下图是现代方法,龙我们已经写好的接口进行拷贝,不用自己开空间,自己赋值等操作。
vector(const vector<T>& v)
{
for (auto& val : v)
{
push_back(val);
}
}
而赋值的做法更绝,因为传参不带引用会调用拷贝构造。我们直接利用拷贝构造的成果,进行swap,而等赋值拷贝结束会自动调用析构,帮助我们将旧的vector对象进行解决。
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> val)
{
swap(val);
return *this;
}
析构函数:
~vector()
{
delete[] start;
start = finish = end_of_storage = nullptr;
}
深浅拷贝的验证:
当我们在vector内放置自定义类型,如果你的程序浅拷贝,那么大概率会报错
而深浅拷贝都会发生在扩容,我们的扩容依赖的都是reserve这个接口,故这个接口一定不能发生浅拷贝的问题。
就像我们在reserve哪里说的,不能使用memcpy,这样会发生浅拷贝
解决方法也很简单,利用自定义类型的深拷贝即可