vector模拟实现
- 构造函数
- 拷贝构造函数
- 析构函数
- 赋值运算符重载
- 容量大小相关的函数
- size()
- capacity()
- reserve
- resize
- 修改容器内容相关函数
- push_back
- pop_back
- insert
- erase
- swap
- 访问容器内容相关函数
- operator[]
- 与迭代器相关函数
- begin()和end()
- 关于迭代器失效的问题
构造函数
vector中有三个成员变量，_start，_finish，_end_of_sorage，其中_start指向容器最开始的位置，_end_of_sorage指向容器最结尾的位置，_finish指向有效数据结尾的位置。
方案1： 对于vector的构造函数，我们可以设置一个无参的默认构造函数，将它的成员变量全部初始化为nullptr即可：
//构造自己的命名空间，防止与标准库中的vector产生冲突
namespace gtt
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
方案2： 使用一段迭代器区间进行构造，我们可以将此迭代器设置为函数模板的形式，这样他就可以接受任何类型的数据，然后在进行尾插数据即可：
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
方案3： vector还支持构造这样一种容器，该容器当中含有n个值为val的数据。对于该构造函数，我们可以先使用reserve函数将容器容量先设置为n，然后使用push_back函数尾插n个值为val的数据到容器当中即可。
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);//扩容
for (size_t i = 0; i < n; i++)
{
push_back(val);//尾插数据
}
}
拷贝构造函数
传统写法：先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。
//传统写法
vector(const vector<T>& v)
{
_start = new T[v.size()];
//memcpy(_start, v._start, sizeof(T)* v.size())//memcpy默认浅拷贝，会出现问题
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_storage = _start + v.size();
}
我们需要注意的是，对于vector< string >，vector< vector< int > >…这样的结构来说，是会进行深拷贝的，而memcpy函数进行的是浅拷贝，就会出现两个指针指向同一片空间的问题，会出现两个问题：1.对同一片空间析构两次；2.一个对象修改会影响另外一个对象。
在这儿我们的解决办法就是使用循环的方式进行赋值，这样拷贝构造出来的结果就指向了不同的空间，就避免了他们会指向同一块空间的问题：
现代写法：使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来即可。
//现代写法
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)//避免又进行深拷贝
{
push_back(e);
}
}
析构函数
进行析构时，先释放容器的存储空间，然后将各个成员变量置为nullptr即可。
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
赋值运算符重载
传统写法：首先判断是否是给自己赋值，若是给自己赋值则无需进行操作。若不是给自己赋值，则先开辟一块和容器v大小相同的空间，然后将容器v当中的数据一个个拷贝过来，最后更新_finish和_endofstorage的值即可。
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)//判断是否自己给自己赋值
{
delete[] _start;//释放掉原空间
_start = new T[v.size()];//重新开辟空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//赋值
}
_finish = _start + v.size();//有效元素结尾
_end_of_storage = _start + v.capacity();//整个容器结尾
}
return *this;
}
现代写法：右值传参使用传值传参，相当于调用拷贝构造函数，然后将左值与拷贝构造出来容器进行交换，完成赋值，出了函数作用域，拷贝构造出来容器自动销毁
vector<T>& operator=(const vector<T> v)//传值传参
{
swap(v);//交换数据
return *this;
}
容量大小相关的函数
size()
返回的就是有效数据的个数，即用_finish - _start即可。
size_t size()const
{
return _finish - _start;
}
capacity()
返回的是容量的大小，即用_end_of_storage - _start即可。
size_t capacity()const
{
return _end_of_storage - _start;
}
reserve
对空间进行扩容，如果n<capacity，就什么也不做，如果n>capacity，就进行扩容，新开辟一个空间，将原空间数据拷贝过来，在释放掉原空间，最后让_start，_finish，_end_of_sorage指向新空间即可。
我们需要注意的是，对于reserve函数，我们依然不可以使用memcpy函数，因为它也会存在深浅拷贝的问题，我们在调用delete函数时，就会对同一片空间释放两次
void reserve(size_t n)
{
if (n > capacity())//判断是否需要进行扩容
{
size_t sz = size();
T* tmp = new T[n];//开辟新空间
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz);//不能使用，存在深浅拷贝问题
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;//释放掉原空间
}
_start = tmp;//指向新空间
_finish = _start + sz;//指向新空间
_end_of_storage = _start + n;//指向新空间
}
}
resize
1.如果扩容空间大于当前的size，调用reverse函数进行扩容，如果没有给定val值，则调用默认构造函数初始化的值。
2.如果扩容空间小于当前的size,则将size缩小到n;
我们需要注意的是，只有当n>capacity时才会改变容量的大小，其他情况下capacity并不会发生改变。
void resize(size_t n, const T& val = T())
{
if (n > capacity)//判断是否需要扩容
{
reserve(n);
}
if (n > size())
{
//初始化值
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
修改容器内容相关函数
push_back
尾插数据，如果满了，就需要进行扩容，没满直接在_finish位置插入数据即可。
//尾插数据
void push_back(const T& x)
{
if (_finish == _end_of_storage)//判断是否需要进行扩容
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;//插入数据
_finish++;//改变位置
}
pop_back
尾删数据，删完就不删了，实际就是挪动_finish指向的位置；
void pop_back()
{
assert(_finish > _start);
_finish--;
}
insert
在任意位置插入数据，将插入位置后面的数据统一向后挪动，需要判断位置的合法性，插入以后需要进行扩容。但是我们需要注意的是，扩容以后使用的就是一片新空间了，旧空间已经被释放掉了，就会出现pos位置找不到的问题，所以我们需要对pos位置做出相应的标记。
void insert(iterator pos, const T& x)
{
assert(pos <= _finish && pos >= _start);//判断pos合法性
if (_finish == _end_of_storage)//检查是否需要扩容
{
size_t len = pos - _start;//标记pos位置
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//pos指向新空间
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;//插入数据
_finish++;
}
erase
删除任意位置数据，就需要将删除位置后面的数据统一向前覆盖，stl 规定erase返回删除位置下一个位置迭代器
iterator erase(iterator pos)
{
assert(pos <= _finish && pos >= _start);//判断pos合法性
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;//覆盖数据
begin++;
}
_finish--;//改变尾的位置
return pos;
}
swap
用于交换两个容器里的数据，我们可以直接调用库里面的swap函数交换即可。
void swap(vector<T>& v)
{
::swap(_satrt, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}
访问容器内容相关函数
operator[]
支持以下标方式访问数据，直接返回相应位置的数据即可；
T& operator[](size_t pos)
{
assert(pos < size());//判断pos的合法性
return _start[pos];//返回pos位置数据
}
与迭代器相关函数
begin()和end()
begin()就是返回首地址，end()就是返回有效数据的下一个的地址
//可读可改
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//可读不可改
const iterator begin() const
{
return _start;
}
const iterator end() const
{
return _finish;
}
我们就可以使用迭代器与范围for遍历我们的vector：
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
关于迭代器失效的问题
关于insert函数，会存在两个问题：
- 我们在插入数据的过程在，如果空间足够，我们就直接插入即可，如果空间不够，就需要调用reserve函数进行扩容，而在扩容过程中就会开辟新空间，将旧空间给释放掉，此时pos是指向旧空间的，释放掉旧空间以后pos就成了野指针，程序直接就崩了，结局办法就是insert函数实现过程中将pos位置标记，即使扩容以后以后，pos依然指向的还是原来的值。
- 这儿还会存在一个问题，假设我们需要在所有偶数前面插入一个该偶数的2倍，就像下面这段程序一样，我们就会发现，程序也崩了，因为我们在pos位置插入数据以后，pos本身位置并没有发生改变，但是原本他指向的值已经向后挪动了，插入完成以后对pos进行++，依然指向的是原本的值，就会无限在该位置前面插入值，
我们的解决方式就是在插入以后接受插入位置的下一个位置迭代器，在直接将pos位置向后移动两位，然后在进行判断，问题就解决了。
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.insert(it, *it * 2);//结收插入位置下一个位置迭代器
it++;
it++;
//it先向后移动两位
}
//判断奇偶
else
{
it++;
}
}
对于erase函数，我们再删除完成以后，后面所有的值都会向前挪动一位，比如我们需要删除所有偶数，就会出现不同的情况：
针对上述情况：我们就需要接收erase删除位置下一个位置的迭代器，然后进行判断。
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);//接收删除位置下一个位置的迭代器
}
else
{
it++;
}
}
