std::vector的模拟实现
目录
构造函数
无参构造
用n个val来初始化的拷贝构造
拷贝构造
用迭代器初始化
析构函数
reserve
resize
pushback
pop_back
迭代器及解引用
迭代器的实现
解引用[ ]
insert
erase
赋值拷贝
补充
vector底层也是顺序表，但是vector可以储存不同的类型包括自定义类型和内置类型，所以在实现vector的时候要用模板实现。vector的成员变量与string是不同的，vector的成员变量是3个迭代器，分别是指向顺序表起始位置的指针，指向最后一个数据下一个位置的指针以及指向尾部开辟的空间。
namespace cfl
{
template<class T>
class vector
{
typedef T* iterator;
public:
private:
iterator _start; //指向顺序表的开头
iterator _finish; //指向顺序表最后一个有效数据的下一个位置
iterator _end_of_storage; //指向最后一个开辟的空间的下一个位置
};
}构造函数
vector的构造函数有5个，我们先实现4个，有一个涉及到容器分配器在写容器篇博客时会实现。
无参构造
//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}用n个val来初始化的拷贝构造
//用n个val来初始化的拷贝构造
vector(size_t n, const T& val)
{
_start = new T[n];
for (int i = 0; i < n; i++)
_start[i] = val;
_finish = _start + n;
_end_of_storage = _start + n;
}拷贝构造
注意在进行拷贝构造的时候，不建议使用memcpy，因为在使用memcpy的时候内置类型不会出问题，但是对于自定义类型可能会出现浅拷贝，自定义类型中有指针就只是简单的拷贝其地址，导致两个vector指向同一块位置，就会调用两次析构函数。
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
//拷贝构造
vector(const vector& v)
{
_start = new T[v.capacity()];
//memcpy(_start, v._start, v.size()*sizeof(T));
用memcpy，如果T是自定义类型可能会导致浅拷贝
比如T是string，则指挥拷贝string的地址，导致两个vector指向一个位置
//用for循环和赋值运算符重载来实现
for (int i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}用迭代器初始化
此处使用迭代器初始化为了方便直接调用push_back(在后面实现)。
//用迭代器初始化
template<class InputIterator>
//此处用一个函数迭代器，使得vector可以用各种类型初始化，能用int数组也能用string等
vector(InputIterator first, InputIterator last)
{
//直接调用push_back让其去开辟空间
while (first != last)
{
push_back(*first);
++first;
}
}析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}reserve
用reserve进行空间的开辟，与拷贝构造同理，这里也不建议使用memcpy进行拷贝。
void reserve(size_t n)
{
if (n > capacity())
{
iterator tmp = new T[n];
int sz = size();
for (int i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}resize
resize传参时如果小于size()，就会对空间进行缩小，如果大于就会额外对额外的空间进行初始化。
void resize(size_t n,const T& val=T()) //如果没有传val就用编译器默认的初始化
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _end_of_storage)
{
*(_finish) = val;
++_finish;
}
}
}pushback
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*(_finish) = val;
++_finish;
}pop_back
尾删。
void pop_back()
{
_finish--;
}迭代器及解引用
迭代器的实现
对于迭代器的实现就是实现begin和end。
迭代器的实现也分为两种：非const版本和const版本。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
typedef const T* const_iterator;
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}解引用[ ]
//解引用运算符重载
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}insert
insert插入。insert传的pos是在_start和_finish之间的，所以在扩容后对导致_start指向新的空间了，但是pos位置还指向原位置，所以扩容后要对pos位置进行更新。
void insert(iterator pos, const T& val)
{
assert(pos < _finish);
if (_finish == _end_of_storage)
{
int num = pos - _start; //如果想开辟空间，会导致_start指向新的位置但是pos还指向原处
reserve(2 * capacity());
pos = _start + num; //对pos位置进行更新
}
iterator end = _finish;
while (end > pos)
{
*(end) = *(end - 1);
--end;
}
*pos = val;
++_finish;
}insert后不能再使用pos这个迭代器了，因为他可能失效。 可以用一个返回值来返回新的pos位置。
erase
指定位置删除。
void erase(iterator pos)
{
iterator cur = pos;
while (cur + 1 < _finish)
{
*(cur) = *(cur + 1);
++cur;
}
--_finish;
}赋值拷贝
void swap(T& tmp)
{
swap(this->_start, tmp._start);
swap(this->_finish, tmp._finish);
swap(this->_end_of_storage, tmp._end_of_storage);
}
//赋值拷贝
T& operator=(T tmp)
{
swap(tmp);
}此处赋值拷贝还是使用交换临时变量的方法，即能够将tmp拷贝构造的空间给this还能让tmp去销毁this的原本数据。
补充
一些vector不常用的成员函数。
1）rbegin，rend从后往前开始；
2）clear()清除vector中的数据，不清除空间；
3）vector<vector<T>>实现用vector模拟二维数组。