vector使用与实现
1.vector的使用
1.1.vector的介绍
vector表示可变大小数组的序列容器
vector采用连续的空间存储数据，可以用下标对vector进行随机访问
1.2 vector的构造
| 构造函数声明 | 接口说明 |
| vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
vector<int> v1; //无参构造
vector<int> v2(v1); //拷贝构造
vector<int> v3(10,0); //构造并初始化//迭代器区间构造
vector<int> v = { 1,2,3,4,5 };
vector<int> vv(v.begin(),v.end());1.3 迭代器的使用
| iterator的使用 | 接口说明 |
| begin+end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rbegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
vector<int> v{1,2,3,4,5,6};
vector<int>::iterator it = v.begin();
while(it!=v.end())
{cout<<*it<<" ";it++;
}
cout<<endl;
1.4 vector空间接口
| 容量接口 | 空间说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| resize | 改变vector的size，开辟空间并初始化 |
| empty | 判断是否为空 |
| reserve | 改变vector的容量，开辟空间 |
1.5 vector增删查改接口
| vector增删查改 | 接口说明 |
| push_back | 尾插 |
| pop_back | 尾删 |
| erase | 删除pos位置的数据 |
| find | 查找指定的元素(注意:算法模块实现，不是成员接口函数) |
| insert | 在pos位置前插入元素 |
| swap | 交换两个vector的数据空间 |
| operator[ ] | 像数组一样访问下标 |
由于push_back，pop_back等接口与前面string类似，不再过多介绍
1.5.1find
find函数原型
函数使用
// 使用find查找3所在位置的iterator
vector<int> v ={1,3,4,5,6};
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
迭代器失效
1.会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、 push_back等。迭代器并不会在这些操作使用时立即失效而是进行下次访问操作时失效
迭 代 器 失 效 解 决 办 法 ： 在 使 用 前 ， 对 迭 代 器 重 新 赋 值 即 可
2.vector的实现
template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:// 给缺省值，避免每个构造函数都要写初始化列表iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;
}构造函数和析构函数
vector() //我们在定义的时候给了缺省值，这里不需要再写了
{
}
~vector()
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}由于后面接口函数会使用size,capacity这些，我们先来实现一下
T& operator[](size_t i)
{assert(i < size());return _start[i];
}
const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _endofstorage - _start;
}迭代器的实现
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}reserve
在插入的时候会遇到空间不够的时候，因此我们需要来进行增容
我们通常使用的方法是：开辟一块新的空间，将vector里面的内容拷贝到新空间里面，再释放掉vector里的内容，最后再将新空间里的赋值给vector
在拷贝的时候我们会遇到深浅拷贝问题
void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz); //按字节拷贝，浅拷贝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i]; //调用的是operator= 深拷贝}delete[] _start;}_start = tmp;_finish = tmp + sz;_endofstorage = tmp + n;}
}push_back , pop_back
void push_back(const T& x)
{if (_finish == _endofstorage) //判断是否需要增容{size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);}*_finish = x;_finish++;
}
void pop_back()
{assert(_start < _finish);--_finish;
}insert, erase
insert:在pos位置插入 erase:删除pos位置
void insert(iterator pos, const T& x)
{assert(pos <= _finish);if (_finish == _endofstorage){size_t n = pos - _start; //记录pos所指向的值size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);//如果增容原来的pos就失效了，需要重新计算pos的位置pos = n + _start;}iterator end = _finish - 1;while (pos <= end){*(end + 1) = *end;end--;}*pos = x;_finish++;
}iterator erase(iterator pos) //要求有返回值，返回pos位置的下一个
{assert(pos < _finish);iterator it = pos;while (it < _finish){*(it) = *(it + 1);it++;}_finish--;return pos;
}resize
resize的主要作用是改变容器中元素的数量(size为有效元素个数，capacity为容量）
三种情况：
n > size ，n<capacity
resize的参数值大于当前容器中size的大小，小于capacity，会在容器末尾插入新的元素，不进行扩容（插入的元素可指定，也可以默认使用默认构造）
n > capacity
resize的参数值大于当前容器的capacity大小，进行扩容，并插入新的元素
n < size
resize的参数值小于当前容器的size大小，那么会删除多余的元素
void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n; //n<_size resize直接删除后面}else{reserve(n);while (_finish < _start + n){*_finish = val; //n>_size resize首先增容，然后将后面位置补特定的值_finish++;}}
}拷贝构造和赋值
vector(const vector<T>& v)
{reserve(v.capacity());for (const auto& e : v){push_back(e);}
}vector<T>& operator=(vector<T>& v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);return *this;
}补充：memset 按字节处理，只能将数组初始化为0,int有四个字节，每个字节改为1，而实际上的值则不为1