C++入门篇8---vector

vecctor是动态顺序表

一、了解vector的相关接口及其功能

1.构造函数相关接口

函数声明	功能介绍
vector()	无参构造
vector(size_type n,const value_type& val=value_type())	构造并初始化n个val
vector(const value& x)	拷贝构造
vector(InputIterator first, InputIterator last)	使用迭代器进行构造

上面不认识的类型如size_type、value_type等都是被typedef过的，可以根据英文意思直接理解，或者找相关的文档进行查询

void test1()
{vector<int> v;for (auto x : v){cout << x << " ";}cout << endl;vector<int> v1(5, 2);for (auto x : v1){cout << x << " ";}cout << endl;vector<int> v2(v1);//vector<int> v2(v1.begin(),v1.end());和上一行代码等价for (auto x : v2){cout << x << " ";}cout << endl;string s = "hello world";vector<char> v3(s.begin(), s.end());//不同类型的迭代器也能初始化for (auto x : v3){cout << x << " ";}cout << endl;
}

2.vector iterator的使用

iterator的使用	接口说明
begin()+end()	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin()+rend()	获取第一个数据位置的reverse_iterator/const_reverse_iterator，获取最后一个数据的下一个位置的reverse_iterator/const_reverse_iterator

void test2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it = v.begin();//注意如果写类型名，那么一定要写正确，如加不加reverse、const一定要写对//如果不想写这么长的类型，可以写auto自动类型推导while (it != v.end()){cout << *it << " ";it++;}cout << endl;vector<int>::reverse_iterator it1 = v.rbegin();while (it1 != v.rend()){cout << *it1 << " ";it1++;}cout << endl;
}

 3.vector空间增长问题

函数名称	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变vector的capacity

void test3()
{vector<int> v;cout << v.size() << endl;cout << v.capacity() << endl;cout << v.empty() << endl;cout << "----------" << endl;vector<int> v1(5, 2);cout << v1.size() << endl;cout << v1.capacity() << endl;cout << v1.empty() << endl;cout << "----------" << endl;//vector<int> v2(v1);vector<int> v2(v1.begin(),v1.end());cout << v2.size() << endl;cout << v2.capacity() << endl;cout << v2.empty() << endl;cout << "----------" << endl;string s = "hello world";vector<char>v3(s.begin(), s.end());cout << v3.size() << endl;cout << v3.capacity() << endl;cout << v3.empty() << endl;
}

 结论：构造函数创建对象时，有多少个数据开多少空间

void test4()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int n = sizeof(arr) / sizeof(int);vector<int> v(arr, arr + n);//vector迭代器本质就是指针，所以这里传指针没问题cout << v.size() << ":" << v.capacity() << endl;v.reserve(100);v.resize(20);cout << v.size() << ":" << v.capacity() << endl;v.reserve(50);v.resize(5);cout << v.size() << ":" << v.capacity() << endl;
}

 结论：resize控制size()的大小，空间不够会扩容，reserve申请预留的空间如果小于已经开出的空间capacity()，则空间大小不变，如果大于，则会扩容（至于扩多大的容，主要看编辑器，但是至少保证空间够用）

4.vector的增删查改

函数名称	接口说明
push_back()	尾插
pop_back()	尾删
find	查找（vector没有find成员函数，这个find是算法库中的），如果找到find
insert	在pos之前插入val，返回新插入元素位置的迭代器
erase	删除pos位置的数据，返回被删除元素的下一个元素位置的迭代器
swap	交换两个vector的数据空间
operator[]	像数组一样用下标访问数据

void test6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v.pop_back();for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v.insert(v.begin() + 1, 10);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;v.erase(v.begin() + 2);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;auto itx = find(v.begin(), v.end(), 10);//返回迭代器if (itx != v.end())//没找到返回end()cout << *itx;
}

 5.迭代器失效（重点）

由于vector的迭代器底层是指针，所以vector迭代器失效本质就是野指针问题

对于vector可能会导致其迭代器失效的操作有

1.在插入元素的过程中，导致扩容，而导致原本的空间被释放，那么在扩容之前获取的迭代器就会失效（这是一个例子，其实只要引发扩容，都可能导致迭代器失效）

2.删除操作，一般来说删除元素不会出现问题，但是如果删除的元素是最后一个元素，那么最后一个元素（即被删除元素位置）的迭代器就会失效

（如果没看懂的，可以看看后面对插入删除功能的模拟实现）

以下代码的功能是删除vector中所有的偶数，请问while循环的代码是正确的

void test7()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}while (it != v.end()){if (*it % 2 == 0)v.erase(it);else++it;}while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}
}

很显然第一个while循环错误，因为删除是将后面的元素整体往前移动，所以删除完成之后，it就已经指向了后一个元素，不需要++，

而第二个while循环逻辑上没有问题，但是不同的编辑器会有不同的结果，在vs上，编辑器会严格检查在可能导致迭代器失效的操作之后使用之前的迭代器，直接报错，而在g++上就不会报错

第三个while循环才是标准的写法，而这也是对迭代器失效问题的解决---为erase函数设置了返回值，返回删除元素后面一个元素的迭代器，这样就确保不会发生迭代器失效的问题了

二、模拟实现vector的基本功能

namespace zxws
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// 构造和析构vector(){}vector(int n, const T& value = T()){reserve(n);while (n--) {push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& x : v){push_back(x);}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}// capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if (n > size()){reserve(n);for (size_t i = size(); i < n; i++){_start[i] = value;}}_finish = n + _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 push_back(const T& x){if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back(){assert(size() > 0);_finish--;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t l = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + l;}iterator it = _finish;while (it > pos){*it = *(it - 1);--it;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos;while (it < _finish - 1){*it = *(it + 1);it++;}_finish--;return pos;}private:iterator _start = nullptr;// 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};void test(){//vector<int> v;vector<int> v(10);vector<int> v(10,2);//v.push_back(1);//v.push_back(2);//v.push_back(3);//v.push_back(4);//for (auto x : v)//{//    cout << x << " ";//}//cout << endl;//vector<int>v1(v);//for (auto x : v1)//{//    cout << x << " ";//}//cout << endl;string s = "hello world";vector<char> s1(s.begin(), s.end());for (auto x : s1){cout << x << " ";}cout << endl;vector<char> s2;s2 = s1;for (auto x : s2){cout << x << " ";}cout << endl;}void test1(){vector<string>v;v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");v.push_back("11111111");for (auto x : v){cout << x << " ";}cout << endl;}void test2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it = v.begin();while(it!=v.end()){if (*it % 2 == 0)it = v.erase(it);elseit++;}for (auto x : v){cout << x << " ";}cout << endl;v.pop_back();for (auto x : v){cout << x << " ";}cout << endl;}void test3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.insert(v.begin()+2, 0);v.insert(v.end(),0);for (auto x : v){cout << x << " ";}cout << endl;}
}