1. vector的使用
1.1 vector的成员函数
1.1.1 vector的定义与构造
| (constructor)构造函数声明 | 接口说明 |
|---|---|
| vector()（重点） | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
使用举例：
void test_vector()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<double> v2;v2.push_back(1.1);v2.push_back(2.2);v2.push_back(3.3);v2.push_back(4.4);vector<string> v3;v3.push_back("张三");v3.push_back("李四");v3.push_back("王五");v3.push_back("赵六");vector<int> v4(10, 5);//初始化为10个4vector<string>(v3.begin(), v3.end());//使用迭代器进行构造
}
1.1.2 vetor的析构与赋值
1.1.3 vector的遍历
void test_vector2()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//1.下标 + []for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//2.迭代器vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}cout << endl;//3.范围forfor (auto i : v1){cout << i << " ";}
}
1.2 vector的迭代器
1.3 vector的空间增长问题
1.3.1 max_size
void test_vector3()
{vector<int> v1;cout << v1.max_size() << endl;
}
vector中的max_size()和string中的不一样，因为vector能够存储各种类型的数据，所以所能存储的数据的最大个数就是由当类型为char时的max_size除以存储数据的每个元素所占的空间大小。
1.3.2 vector的增容
#include <iostream>
#include <vector>
int main()
{size_t sz;std::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}
}
输出结果：(VS2019环境下：PJ版本的STL，扩容是1.5倍)
在Linux即SGI版本的STL下，扩容是2倍。
单次增容增多少的问题剖析：
单次增容越多，插入N个值，增容次数越少，效率就越高，浪费空间就越多。
单次增少了，会导致频繁增容，效率低下。
1.3.3 shrink_to_fit
注意：shrink_to_fit会同时改变capacity和size，同时也会有一定的代价，会重新开辟一块新的空间，存放缩容后的所有数据。
1.4 vector的增删查改
1.4.1 insert和erase
注意：vector和string不同的点在于vector使用的都是迭代器。
1.4.2 vector的查找（find）
注意：在vector中并没有单独的查找接口，只能使用STL算法中的find函数。
注意：返回值为一个迭代器，如果找到就返回相对应的迭代器，如果没有找打就返回我们所给的last迭代器。
使用举例：
#include<algorithm>
int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);auto ret = find(v.begin(), v.end(), 3);//3为要查找的那个数if (ret != v.end()){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}return 0;
}
1.4.3 vector的排序
注意：在vector中并没有单独的查找接口，只能使用STL算法中的sort函数。
使用举例：
#include<functionl>
#include<algorithm>
void test_vector2()
{vector<int> v1;v1.push_back(1);v1.push_back(5);v1.push_back(3);v1.push_back(2);v1.push_back(4);//排升序sort(v1.begin(), v1.end());for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//排降序，要使用一个仿函数greater<int>()sort(v1.begin(), v1.end(), greater<int>());for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}
}
1.5 vector在OJ中的使用
1.杨辉三角
题目：
代码：
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);for(size_t i = 0; i < vv.size(); i++){vv[i].resize(i + 1, 0);vv[i][0] = 1;vv[i][i] = 1;for(size_t j = 0; j < i; j++){if(vv[i][j] == 0){vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}return vv;}
};
2.电话号码的字母组合
class Solution {string _numToStr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};void _letterCombine(string digits, size_t di, string combineStr, vector<string>& retV){if(di == digits.size()){retV.push_back(combineStr);return;}//取到数字字符转换成数字，再取到映射的字符串int num = digits[di] - '0';string str = _numToStr[num];for(auto ch : str){_letterCombine(digits, di + 1, combineStr + ch, retV);}}
public:vector<string> letterCombinations(string digits) {vector<string> retV;if(digits.empty()){return retV;}size_t i = 0;string str;_letterCombine(digits, i, str, retV);return retV;}
};
2. vector的模拟实现
2.1 代码实现
#include<iostream>
#include<assert.h>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;
template<class T>
class myvector
{
public:typedef T* iterator;typedef const T* const_iterator;//构造函数的模拟实现myvector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}template<class InputIterator>myvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);first++;}}void swap(myvector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}myvector(const myvector<T>& v): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){myvector<T> tmp(v.begin(), v.end());this->swap(tmp);}myvector<T>& operator=(myvector<T> v){this->swap(v);return *this;}myvector(int n, const T& val = T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}//迭代器的模拟实现iterator begin(){return _start;}const_iterator begin()const{return _start;}iterator end(){return _finish;}const_iterator end()const{return _finish;}//size()和capacity()的实现size_t size()const {return _finish - _start;}size_t capacity()const{return _endofstorage - _start;}//reserve和resize的模拟实现void reserve(size_t n){size_t sz = size();if (n > capacity()){T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}//C++中内置类型也有构造函数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和pop_back的模拟实现void push_back(const T& x)//当然，此处也可以复用insert(end()){if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}void pop_back()//此处也可以复用erase(end() - 1){if (_finish > _start){--_finish;}}iterator insert(iterator pos, const T& x){//检查参数assert(pos >= _start && pos <= _finish);//扩容以后pos就失效了，需要更新一下if (_finish == _endofstorage){size_t n = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);pos = _start + n;}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;return pos;}//迭代器失效有两种：//1.由于扩容形成野指针//2.迭代器意义发生改变iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}--_finish;return pos;}//注意：在Windows环境下无法再通过pos迭代器来对myvector容器进行访问即pos迭代器失效了，但是在Linux环境下并没有失效//1.erase的失效都是意义变了，或者不再有效数据的访问范围之内//2.一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效//整体总结：对于insert和erase造成迭代器失效问题，Linux平台g++检查并不严格，基本依靠操作系统自身野指针检查机制//Windows下VS系列检查更为严格，使用一些强制检查机制，意义变了也可能会检查出来T& operator[](size_t pos){assert(pos < size());return _start[pos];}void clear(){_finish = _start;}//资源管理~myvector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}
private:iterator _start;iterator _finish;iterator _endofstorage;
};
2.2 insert和erase的迭代器失效问题
vector迭代器失效有两种
1、扩容、缩容导致的野指针失效。
2、迭代器指向的意义变了。
对这两种失效的检查方式有两种：
系统越界机制检查。-----不一定能够检查到（Linux中的g++常用这种方式进行检查）
编译实现机制的检查。-----相对靠谱（windows的VS中常用这种方式）
insert
-
野指针失效问题
解决方案：
记录下pos的相对位置，然后在扩容后进行更新即可。
-
迭代器失效问题
代码展示：
//在每一个迭代器位置为偶数的位置处插入20 void test_myvector3() {myvector<int> v;v.reserve(10);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);myvector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.insert(it, 20);//用it来接收新插入的那个位置的迭代器++it;//然后对it进行++操作，指向2的位置}++it;//使其指向3的位置}for (auto e : v){cout << e << " ";}cout << endl; }
对于STL标准库来说，windows中的VS和Linux的g++对于迭代器失效又存在不同的检查方案：
Windows下的VS（2019）环境下：
第一种失效：
第二种失效：
在VS2019的环境下，无论是否发生扩容现象，都会出现迭代器失效的情况，此时迭代器失效都会被检测到访问权限冲突的问题。
Linux下的g++环境下：
第一种失效（发生了扩容）：
输出结果：
第二种失效（未发生扩容）：
运行结果：
而在Linux环境下，Linux对迭代器的失效检测并不严格，越界并没有检测出来。
erase
iterator erase(iterator pos)
{assert(pos >= _start && pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}--_finish;return pos;
}
一般vector在删除数据，都不考虑缩容的方案。
缩容方案：size() < capacity() / 2时，可以考虑开一个size()大小的空间，拷贝数据，释放旧空间。
缩容方案的本质就是时间换空间。一般设计都不会考虑缩容方案。
Windows下的VS(2019)环境下：
VS进行了强制检查，认为pos意义发生了改变，即已经失效了，所以程序发生了崩溃。
一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效。
Linux下的环境下：
输出结果：
Linux环境下的检查并不严格，并没有认为pos失效，但实际上应该是失效了，因为意义已经发生了改变。
总结：erase(pos)以后，pos的意义变了，但是不同平台下面对于访问pos的反应是不一样的。我们用的时候统一认为pos在使用之后就已经失效了。
整体总结：对于insert和erase造成迭代器失效问题：
Linux平台检查不是很严格，基本依靠操作系统自身野指针越界检查机制。
Windows下VS系列检查更严格，使用一些强制检查机制，意义变了也可能会检查出来。
问：如果要删除vector容器中的偶数的数据，该如何进行？
答：
myvector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){it = v.erase(it);}++it;
}
考虑三种情况：
- ``1 2 3 4 5`此时程序能够正常执行
1 2 3 4此时程序出现了段错误（原因：_finish到了原来4所在的位置，然后it++，此时和_finish就错过去了）10 2 3 4 5此时程序执行后的结果为：2 3 5（原因：2把10给覆盖了，相当于把2跳过了）
修正代码：
myvector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){it = v.erase(it);}else{++it;}
}
2.3 构造函数时出现的错误
已有构造函数如下所示：
myvector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}template<class InputIterator>
myvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);first++;}
}
void swap(myvector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
myvector(const myvector<T>& v): _start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{myvector<T> tmp(v.begin(), v.end());this->swap(tmp);
}
myvector<T>& operator=(myvector<T> v)
{this->swap(v);return *this;
}myvector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
当我们执行下面的代码时就出现了错误：
void test_myvector7()
{myvector<int> v(10, 2);for (auto e : v){cout << e << " ";}cout << endl;
}
但是当我们代码变成下面的代码时就会正确：
void test_myvector7()
{myvector<char> v(10, 'x');for (auto e : v){cout << e << " ";}cout << endl;
}
问：为什么？
答：此处涉及参数匹配问题：
template<class InputIterator>
myvector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);first++;}
}myvector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
第一种出错的情况就是因为和第一种构造函数进行了匹配，所以出现了错误。
而第二种正确的原因时因为和第二种构造函数进行了匹配，所以能够正常运行。
我们该如何解决？
myvector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
2.4 当T为自定义类型时的深浅拷贝问题
旧版本代码：
void reserve(size_t n)
{size_t sz = size();if (n > capacity()){T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));//值拷贝即浅拷贝delete[] _start;}_start = tmp;}_finish = _start + sz;_endofstorage = _start + capacity();
}
myvector<vector>的扩容
总结：myvector<T>中，当T是涉及深浅拷贝的类型时，如：string/vector<T>等等，我们扩容使用memcpy拷贝数据是存在浅拷贝问题。
下面是改进方法：
void reserve(size_t n)
{size_t sz = size();if (n > capacity()){T* tmp = new T[n];if (_start){for(size_t i = 0; i < size(); i++){tmp[i] = _start[i];//调用相应T的构造函数}delete[] _start;}_start = tmp;}_finish = _start + sz;_endofstorage = _start + capacity();
}
