目录
实现框架
namespace lzg
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默认成员函数
vector(); //构造函数
vector(size_t n, const T& val); //构造函数
vector(initializer_list<T> il) //构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last); //构造函数
vector(const vector<T>& v); //拷贝构造函数
vector<T>& operator=(const vector<T>& v); //赋值运算符重载函数
~vector(); //析构函数
//迭代器相关函数
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量和大小相关函数
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器内容相关函数
void push_back(const T& x);
void pop_back();
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//访问容器相关函数
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start; //起始位置
iterator _finish; //结尾位置
iterator _endofstorage;//容量
};
}一、默认成员函数
构造函数
1.无参默认构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}2.initializer list constructor(初始值设定项列表构造函数)
std::initializer_list（初始化列表）是 C++11 引入的重要特性，支持花括号 {}初始化对象，极大简化了容器和自定义类型的初始化操作
vector (initializer_list<value_type> il,
const allocator_type& alloc = allocator_type());
vector(initializer_list<T> il) //il{1,2,3,4,5};
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}3.range constructor(范围构造函数)
template <class InputIterator>
vector (InputIterator first, InputIterator last);
vector还支持使用一段迭代器区间进行对象的构造。因为该迭代器区间可以是其他容器的迭代器区间，也就是说该函数接收到的迭代器的类型是不确定的，所以我们这里需要将该构造函数设计为一个函数模板，在函数体内将该迭代器区间的数据一个个尾插到容器当中即可。
template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
//将迭代器区间在[first,last)的数据一个个尾插到容器当中
while (first != last)
{
push_back(*first);
first++;
}
}4.fill constructor
vector还支持构造这样一种容器，该容器当中含有n个值为val的数据。
vector(size_t n, const T& val)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n); //调用reserve函数将容器容量设置为n
for (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中
{
push_back(val);
}
}注：此函数要注意传的实参和形参类型是否一样，如果不一样会走上面的range constructor
拷贝构造函数
vector的构造函数涉及深拷贝问题，这里提供两种深拷贝的写法：
传统写法
// v2(v1)
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_endofstorage = _start + v.capacity(); //整个容器的尾
}现代写法
//现代写法
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同
for (auto e : v) //将容器v当中的数据一个个尾插过来
{
push_back(e);
}
}
赋值运算符重载函数
传统写法
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
return *this; //支持连续赋值
}现代写法
赋值运算符重载首先在右值传参时并没有使用引用传参，因为这样可以间接调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。
//现代写法
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{
swap(v); //交换这两个对象
return *this; //支持连续赋值
}
析构函数
//析构函数
~vector()
{
if (_start) //避免对空指针进行释放
{
delete[] _start; //释放容器存储数据的空间
_start = nullptr; //_start置空
_finish = nullptr; //_finish置空
_endofstorage = nullptr; //_endofstorage置空
}
}
迭代器相关函数
vector当中的迭代器实际上就是容器当中所存储数据类型的指针。
typedef T* iterator;
typedef const T* const_iterator;
begin和end
iterator begin()
{
return _start; //返回容器的首地址
}
iterator end()
{
return _finish; //返回容器当中有效数据的下一个数据的地址
}
const_iterator begin()const
{
return _start; //返回容器的首地址
}
const_iterator end()const
{
return _finish; //返回容器当中有效数据的下一个数据的地址
}其实这和前面string迭代器的实现差不多，接下来让我演示一下操作
并且实现了迭代器，范围for也就自然实现了
int main()
{
lzg::vector<int> v(5, 3);
lzg::vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl; //3 3 3 3 3
return 0;
}容量和大小相关函数
size和capacity
用上面三个指针来完成size() capacity()
size_t size()const
{
return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{
return _endofstorage - _start; //返回当前容器的最大容量
}
reserve
reserve规则：
1、当n大于对象当前的capacity时，将capacity扩大到n或大于n。
2、当n小于对象当前的capacity时，什么也不做。
//1、缺陷版-迭代器失效
void reserve(size_t n)
{
if (n > capacity())//只扩容
{
iterator tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
_finish = _start +size();//_start+ (_finish-_start)
_endofstorage = _start + n;
}
}
//2、正确写法 限内置类型
void reserve(size_t n)
{
if (n > capacity())//只扩容
{
size_t OldSize = size(); //避免后面旧_finish位置失效导致新_start-旧_finish
iterator tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * OldSize);
delete[] _start;
}
_start = tmp;
_finish = _start + OldSize;//保证了_finish的有效性
_endofstorage = _start + n;
}
}
resize
void resize(size_t n, T val = T())
{
if (n <= size())
{
_finish = _start + n; //小于size直接结尾
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
empty
empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。
bool empty()const
{
return _start == _finish;
}
修改容器内容相关函数
push_back
void push_back(T x)
{
/*if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;*/
insert(_finish, x);
}在实现了insert后可以复用insert函数
pop_back
尾删数据之前得先检查容器是否为空。
//尾删数据
void pop_back()
{
assert(!empty()); //容器为空则断言
_finish--; //_finish指针前移
}
insert
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish); //保证pos位置的合法
size_t len = pos - _start; //记录pos偏移量后面方便更新pos
if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
pos = _start + len; //扩容后pos指向旧地址，这里进行更新避免失效
iterator i = _finish-1;
while (i >= pos)
{
*(i + 1) = *i;
i--;
}//把pos及结尾的数据向后移动方便插入
*pos = x;
++_finish;
return pos;
}模拟函数实现时需要调用扩容函数的话，一定要谨慎检查是否有迭代器失效的问题
erase
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator i = pos + 1;
while (i < _finish)
{
*(i - 1) = *i;
++i;
}
_finish--;
return pos;
}swap
//交换两个容器的数据
void swap(vector<T>& v)
{
//交换容器当中的各个成员变量
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_endofstorage, v._endofstorage);
}
注意： 在此处调用库当中的swap需要在swap之前加上“::”（作用域限定符），告诉编译器这里优先在全局范围寻找swap函数，否则编译器会认为你调用的就是你正在实现的swap函数（就近原则）。
operator[ ]
T& operator[](size_t i)
{
assert(i < size()); //检测下标的合法性
return _start[i];
}
const T& operator[](size_t i)const
{
assert(i < size()); //检测下标的合法性
return _start[i];
}
总结：
vector的模拟实现和string类的模拟大体相似，不过在vector中更重视要避免迭代器失效的问题，比如在一些地方对容器进行拷贝时调用的memcpy函数不要对自定义类型(需要申请空间的)拷贝，用到memcpy的地方可以换成赋值