在C++中，vector是标准模板库（STL）中的一种动态数组容器，它可以存储任意类型的元素，并且能够自动调整大小。vector提供了许多方便的成员函数，使得对数组的操作更加简单和高效。
vector的使用
vector的构造函数
vector迭代器
vector的成员函数
vector的模拟实现
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
vector()
/*:_start(nullptr)
,_finish(nullptr)
,_end_of_stroage(nullptr)*/
{}
vector(initializer_list<T> il) {
/*typename initializer_list<T>::iterator it = il.begin();
while (it!=il.end()) {
push_back(*it);
++it;
}*/
for (auto& e : il) {
push_back(e);
}
}
vector(int n,const T& val=T())
/*:_start(nullptr)
, _finish(nullptr)
, _end_of_stroage(nullptr)*/
{
reserve(n);
for (int i = 0; i < n; i++) {
push_back(val);
}
}
//vector(const vector<T>& v) {
// //reserve(v.capacity());
// /*for (auto e : v) {
// push_back(e);
// }*/
// _start = new T[v.capacity()];
// //memcpy(_start, v._start, sizeof(T) * v.size());
// for (size_t i = 0; i < v.size(); i++) {
// _start[i] = v._start[i];
// }
// _finish = _start + v.size();
// _end_of_stroage = _start + v.capacity();
//}
//vector(const vector& v) {
vector(const vector<T>& v) {
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
void swap(vector<T>& v) {
//void swap(vector& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_stroage, v._end_of_stroage);
}
//vector<vector<T>> 深层次的拷贝
// v1=v2
vector<T>& operator=(vector<T> v) {
//vector& operator=(vector v) {
swap(v);
return *this;
}
// [first,last)
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
/*:_start(nullptr)
, _finish(nullptr)
, _end_of_stroage(nullptr)*/
{
while (first != last) {
push_back(*first);
++first;
}
}
}
~vector() {
delete[] _start;
_start = _finish = _end_of_stroage = nullptr;
}
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const{
return _start;
}
const_iterator end() const{
return _finish;
}
void resize(size_t n,T val=T()) {
if (n < capacity()) {
//删除数据
_finish = _start + n;
}
else {
if (n > capacity()) {
reserve(n);
}
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < sz; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
//_finish = tmp + size();//size()是原来空间的_finish-_start
//_start = tmp;
_start = tmp;
_finish = _start + sz;
_end_of_stroage = tmp + n;
}
}
void push_back(const T& x) {
if (_finish == _end_of_stroage) {
reserve(capacity() ==0 ? 4:capacity()* 2);
}
*_finish = x;
++_finish;
}
void pop_back() {
assert(!empty());
--_finish;
}
//iterator insert(iterator pos, const T& val) {
void insert(iterator pos, const T& val) {
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_stroage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
//扩容后更新pos,解决迭代器pos失效的问题
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
//return pos;
}
//void erase(iterator pos) {
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator start = pos + 1;
while (start != _finish) {
*(start - 1) = *start;
++start;
}
--_finish;
return pos;
}
size_t capacity() const {
return _end_of_stroage - _start;
}
size_t size() const{
return _finish - _start;
}
bool empty() {
return _start == _finish;
}
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const{
assert(pos < size());
return _start[pos];
}
private:
iterator _start=nullptr;//指向第一个元素的迭代器
iterator _finish= nullptr;//指向最后一个元素的下一个位置的迭代器
iterator _end_of_stroage= nullptr;//指向分配的内存空间的末尾位置的迭代器
};
}
vector的构造函数
vector()
/*:_start(nullptr)
,_finish(nullptr)
,_end_of_stroage(nullptr)*/
{}
vector(initializer_list<T> il) {
//C++11：没有实例化的类模板只要取内嵌类型就会报错，因为编译器分不清是类模板里面的静态变量(可以取)还是类型(实例化才能取)
// 说明类型时，前面要加typename
/*typename initializer_list<T>::iterator it = il.begin();
while (it!=il.end()) {
push_back(*it);
++it;
}*/
for (auto& e : il) {
push_back(e);
}
}
vector(int n,const T& val=T())
/*:_start(nullptr)
, _finish(nullptr)
, _end_of_stroage(nullptr)*/
{
reserve(n);
for (int i = 0; i < n; i++) {
push_back(val);//尾插n个值为val的数据到容器当中
}
}
vector的拷贝构造
传统写法：
vector(const vector<T>& v) {
//reserve(v.capacity());
/*for (auto e : v) {
push_back(e);
}*/
_start = new T[v.capacity()];
//memcpy(_start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i < v.size(); i++) {
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_stroage = _start + v.capacity();
}
现代写法：
//vector(const vector& v) {
vector(const vector<T>& v) {
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
void swap(vector<T>& v) {
//void swap(vector& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_stroage, v._end_of_stroage);
}
迭代器
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const{
return _start;
}
const_iterator end() const{
return _finish;
}
赋值运算符重载
//vector<vector<T>> 深层次的拷贝
// v1=v2
vector<T>& operator=(vector<T> v) {
//vector& operator=(vector v) {
swap(v);
return *this;
}
// [first,last)
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
/*:_start(nullptr)
, _finish(nullptr)
, _end_of_stroage(nullptr)*/
{
while (first != last) {
push_back(*first);
++first;
}
}
}
vector的析构函数
~vector() {
delete[] _start;
_start = _finish = _end_of_stroage = nullptr;
}
扩容
void resize(size_t n,T val=T()) {
if (n < capacity()) {
//删除数据
_finish = _start + n;
}
else {
if (n > capacity()) {
reserve(n);
}
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < sz; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
//_finish = tmp + size();//size()是原来空间的_finish-_start
//_start = tmp;
_start = tmp;
_finish = _start + sz;
_end_of_stroage = tmp + n;
}
}
尾插和尾删
void push_back(const T& x) {
if (_finish == _end_of_stroage) {
reserve(capacity() ==0 ? 4:capacity()* 2);
}
*_finish = x;
++_finish;
}
void pop_back() {
assert(!empty());
--_finish;
}
插入和删除
void insert(iterator pos, const T& val) {
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_stroage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
//扩容后更新pos,解决迭代器pos失效的问题
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
//return pos;
}
//void erase(iterator pos) {
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator start = pos + 1;
while (start != _finish) {
*(start - 1) = *start;
++start;
}
--_finish;
return pos;
}
获取容量大小
size_t capacity() const {
return _end_of_stroage - _start;
}
获取元素个数
size_t size() const{
return _finish - _start;
}
判断是否为空
bool empty() {
return _start == _finish;
}
访问下标元素
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const{
assert(pos < size());
return _start[pos];
}
重载运算符[ ]时需要重载一个适用于const容器的，因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作，不能对数据进行修改
迭代器失效
由于vector的元素是分配在连续的内存中，当进行insert和erase操作，都会使得插入点和删除点之后的元素挪位置，插入点和删除掉之后的迭代器全部失效。
解决方法就是更新迭代器，对于删除，erase（）返回的是删除元素的下一个位置，可以通过利用erase（）方法可以返回下一个有效的 iterator来避免迭代器失效。insert同理，insert返回的是插入元素的迭代器的位置。
