目录
一、介绍vector
1.vector是什么
2.vector的特点
1.随机访问
2.缓存命中
3.vector的结构
二、vector的函数
1.构造函数（创建）编辑
2.Iterator（迭代器）
3.Capacity（容量）
三、迭代器失效
四、实现vector
一、介绍vector
1.vector是什么
vector是C++中STL（Standard Template Library）提供的一个容器类，它是一个动态数组，能够存储同一类型的元素。
vector是STL容器中一种常用的容器，和数组类似，由于其大小 (size)可变，常用于数组大小不可知的情况下来替代数组。vector是为了实现动态数组而产生的容器。
这里是官网vector - C++ 参考 (cplusplus.com)可以进行详细的了解
2.vector的特点
1.随机访问
vector是一种顺序容器，在内存中连续排列，因此可以通过下标快速访问，时间复杂度为O(1)。然而，连续排列也意味着大小固定，数据超过vector的预定值时vector将自动扩容。
2.缓存命中
对于我们需要寻找的元素，可以通过下标快速确定位置
3.vector的结构
如图所示，vector内部有三个指针，分别指向数据块的开始、有效数据的结尾、存储容量的结尾
_start : 指向数据块的开始
_finish : 指向有效数据的结尾
_endofstorage : 指向存储容量的结尾
_finish - _start ：数据有效元素的个数
_endofstorage - _start ：开辟空间的大小——数组的大小
_endofstorage - _finish ：除有效数据外，剩余空间的大小
二、vector的函数
本文对于使用只是带大家了解底层函数参数，具体使用不过多介绍。相信大家可以自己搞明白！
1.构造函数（创建）
解释一下关键字 explicit
不要把 explicit 误认为是返回值类型，它在 c++ 中是关键字，用于防止不应该允许的隐式类型转换
如这段代码，explicit关键字阻止了 int 到 MyClass 的隐式转换
allocator_type是分配器类型，用于控制容器中元素的存储和回收。不做过多介绍
2.Iterator（迭代器）
begin：返回开始的位置
end：返回结尾的位置
r：反向迭代器
c：const 迭代器 （不能改变指针指向的内容，但可以改变指针本身）
3.Capacity（容量）
这些是基本的函数，需要了解之后才能去进行 增删查改 的操作，对于增删查改，不进行介绍，建议大家去官方网站自己学习 vector - C++ Reference (cplusplus.com)
https://legacy.cplusplus.com/reference/vector/vector/?kw=vector
三、迭代器失效
因为会发生扩容，即申请新的空间，所以原指针会失效。
使用while循环直接赋值，则可以避免浅拷贝问题！
四、实现vector
注意：实现时复用了已经实现的函数！
#include<iostream>
#include<stdio.h>
#include<assert.h>
using namespace std;
#include<string.h>
namespace bit
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
{}
~vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}
vector(int n, const T& value = T())
{
resize(n, value);
}
vector(const vector<T>& v)
{
/*_start = new T[v.capacity()];
memcpy(_start, v._start, v.size() * sizeof(T));
_finish = _start + v.size();
_endofstorage = _start + v.capacity();*/
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
iterator begin() const
{
return _start;
}
iterator end() const
{
return _finish;
}
const_iterator cbegin() const
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish && pos >= _start);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容pos会失效
pos = _start + len;
}
iterator it = _finish - 1;
while (it >= pos)
{
*(it + 1) = *it;
--it;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos < _finish);
assert(pos >= _start);
iterator it = pos + 1;
while (it<_finish)
{
*(it - 1) = *it;
++it;
}
_finish--;
return pos + 1;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, n * sizeof(T));
for (size_t i = 0; i < old; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = value;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
private:
iterator _start= nullptr;// 指向数据块的开始
iterator _finish= nullptr;// 指向有效数据的尾
iterator _endofstorage= nullptr;// 指向存储容量的尾
};
}
