一. 构造和析构
💦构造函数
胡不多说，测试：
vector<int> v1;//无参构造 vector<int> v2(10, 1);//构造10个val，初始化为1 vector<int> v3(v2);//拷贝构造 vector<int> v3(++v2.begin(), --v2.end()); //迭代器区间初始化
那vector可以代替string吗？不可以！因为有'\0'，在操作上+=、find、<<、>>，因为vector是针对T 泛型，一般针对其他类型（int、double）,所以vector无法替代string
💦析构函数
还是老规矩，不用管，系统自己会调用
二. 遍历
⚡operator[]
//下标+[] 可读可写 for (size_t i = 0; i < v1.size(); ++i) { v1[i]++; cout << v1[i] << endl; }
⚡迭代器 & 范围for
✨ iterator 内嵌类型
iterator的使用 接口说明
begin + end（重点） 获取第一个数据位置的， 获取最后一个数据的下一个位置的
rbegin + rend 获取最后一个数据位置，获取第一个数据前一个位置
// 遍历 - 可读可写 vector<int>::iterator it = v.begin(); while (it != v.end()) { (*it) --; cout << *it << " "; it++; } cout << endl;
支持迭代器就支持范围for🍬(底层就是迭代器)
//范围for for (auto e : v1) { cout << e << " "; } cout << endl;
三.增删查改
🌈reserve & resize
resize初始化可以自己指定值
测试vector的默认扩容机制
#include<iostream> #include<vector> using namespace std; int main() { size_t sz; vector<int> foo; sz = foo.capacity(); 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'; } } }
vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
g++以标准的2倍增长 ——
🌈push_back & pop_back
尾插尾删，不多赘述了
vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4);
🌈find
vector类中并没有find，这是因为算法库中就提供了一个模板函数，在迭代器区间中查找(左闭右开)，若查找到了，就返回迭代器；没找到就返回s.end()
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int>::iterator pos = find(v1.begin(), v1.end(), 3); if (pos != v1.end()) { cout << "找到了！" << *pos << endl; }
🌈insert & erase
可头插头删
insert & erase 可以搭配 find 使用。string类的insert和erase通常支持下标，因为它find也刚好返回下标
// 头插 v.insert(v.begin(), 0); vector<int>::iterator pos = find(v1.begin(), v1.end(), 3); if (pos != v1.end()) { v1.insert(pos, 30); } pos = find(v1.begin(), v1.end(), 3); if (pos != v1.end()) { v1.erase(pos); }
注意vector没有重载流提取和流插入<<、>>,遍历有迭代器和[],所以就不需要了
四. 排序
函数模板排序，对迭代器区间进行排序，默认是升序
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(10); v1.push_back(4); sort(v1.begin(), v1.end()); for (auto e : v1) { cout << e << " "; } cout << endl;
那我们想实现降序这么办呢？ 仿函数（后面栈细细分说），现在先会用
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(10); v1.push_back(4); sort(v1.begin(), v1.end()); for (auto e : v1) { cout << e << " "; } cout << endl; less<int> ls;//升序 greater<int> gt;//降序 sort(v1.begin(), v1.end(), greater<int>());//匿名对象~ 传参 for (auto e : v1) { cout << e << " "; } cout << endl;
不仅仅可以排vector，string也能排（按照ascll码排序）
五. 小细节
举例：
vcctor<string> strV; string str1("张三"); strV.push_back(str1); strV.push_back(string("李四")); strV.push_back("王五");//这个为什么能实现呢？？ 答：会构造一个临时对象，然后被引用
因为构造函数是一个单参数，支持隐式类型转换
string(const char* str)//构造函数 {}
如果要使用范围for的时候，要谨慎小心 再小心
for(const auto& str:: strV) { cout<<str<<endl; }
此处会被替换成迭代器，迭代器会依次取数据去赋值，如果不加引用就是就会调用拷贝构造，此时还是深拷贝，如果多次赋值就会浪费很多空间，所以要加&引用，拷贝别名，更加高效
经典题型讲解
0️⃣易错课后题
下面这个代码输出的是( C )
#include <iostream> #include <vector> using namespace std; int main(void) { vector<int>array; array.push_back(100); array.push_back(300); array.push_back(300); array.push_back(300); array.push_back(300); array.push_back(500); vector<int>::iterator itor; for(itor=array.begin();itor!=array.end();itor++) { if(*itor==300) { itor=array.erase(itor); } } for(itor=array.begin();itor!=array.end();itor++) { cout<<*itor<<""; } return 0; }
A.100 300 300 300 300 500
B.100 3OO 300 300 500
C.100 300 300 500
D.100 300 500
E.100 500
F.程序错误
解析：
vector::erase()：从指定容器删除指定位置的元素或某段范围内的元素 vector::erase()方法有两种重载形式 如下：
iterator erase( iterator _Where); iterator erase( iterator _First,iterator _Last);
如果是删除指定位置的元素时： 返回值是一个迭代器，指向删除元素下一个元素;
如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素;
在本题中，当 itor==300成立时，删除第一个值为300的元素，同时itor指向下一个元素（即是第二个值为300的元素）；在for(;;itor++)执行itor，itor指向第三个值为300的元素，进入下一个循环。
所以整个过程中，只删除了2个值为300的元素
💛T是一个数据类型，关于std::vector::at 和 std::vector::operator[] 描述正确的是( C )
A.at总是做边界检查， operator[] 不做边界检查.
B.at 不做边界检查， operator[] 做边界检查.
C.at和operator[] 都是会做边界检查的
D.以上都不对
at() 函数和 [] 运算符的重载，两者都可以得到相应下标的值，并且两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 是报出 assert 错误
1️⃣只出现一次的数字（单身狗）
题目链接：136. 只出现一次的数字
著名的单身狗问题，异或解法最经典：相同为0, 不同为1
class Solution { public: int singleNumber(vector<int>& nums) { int ret =0; for(auto& i : nums) { ret^=i; } return ret; } };
2️⃣只出现一次的数字ii（进阶）
题目链接：137. 只出现一次的数字 II
巧妙的思路：如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字
class Solution { public: int singleNumber(vector<int>& nums) { int ret =0; size_t sum =0;//统计个数 for(size_t i = 0; i< 32 ;++i) { sum = 0; for(auto& ch : nums) { sum += (ch>>i)&1; } sum %=3; ret += (sum<<i); } return ret; } };
3️⃣只出现一次的数字iii（两只单身狗）
题目链接：260. 只出现一次的数字 III
著名的两只单身狗的故事
class Solution { public: vector<int> singleNumber(vector<int>& nums) { //全员异或 int ret =0; for(auto e: nums) { ret ^= e; } //找到两个单身狗数字不同的一位(二进制) size_t pos = 0; while(pos < 32) { if((ret >> pos)&1 == 1 ) break; pos++; } //分组异或 vector<int> retArr(2); for(size_t i=0;i<nums.size();++i) { if((nums[i] >> pos)&1 == 1) { retArr[0] ^= nums[i]; } else { retArr[1] ^= nums[i]; } } return retArr; } };
4️⃣删除有序数组中的重复项
题目链接：26. 删除有序数组中的重复项
解题思路：双指针移动，fast指针遍历，fast！=slow时候，fast赋值给++slow，不断遍历，最后返回长度。
ps：返回是要求长度，slow+1，不加就漏了最开始的那个数据
class Solution { public: int removeDuplicates(vector<int>& nums) { //慢指针、快指针 int slow = 0, fast =0; while(fast < nums.size()) { if(nums[slow] == nums[fast]) { ++fast; } else { nums[++slow] = nums[fast++]; } } return slow + 1; } };
5️⃣杨辉三角OJ
题目链接：118. 杨辉三角
用c语言做相当的麻烦，要动态开辟二维数组，所以我们学了vector之后就简单多了
vv[i][j]本质上是两次的[]函数调用~
💗核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]
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].front() = vv[i].back() = 1; } //遍历 for(size_t i =0; i< vv.size() ; ++i) { for(size_t j = 0; j <vv[i].size(); ++j) { if(vv[i][j] == 0) { vv[i][j] = vv[i-1][j] + vv[i-1][j-1]; } } } return vv; } };
6️⃣电话号码组合（中等）
题目链接：17. 电话号码的字母组合
本题是一道多路递归的深度遍历，简单的映射&回溯 ，递归深度取决于数字串长度，数字串映射多长就是，几路递归！！
class Solution { //单参数构造 char* numTok[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public: void Combine(string digits, int di, vector<string>& retV, string combineStr) { if(di == digits.size()) { retV.push_back(combineStr); return ; } //先取数字字符映射的字符串 int num = digits[di] - '0'; string str = numTok[num]; for(auto ch: str) { Combine(digits, di+1, retV, combineStr + ch); } } vector<string> letterCombinations(string digits) { vector<string> v; if(digits.empty()) return v; string str; Combine(digits, 0, v , str); return v; } };
ps:
建立映射的时候，不需要用vector，因为是固定长度，并且可以想string("abc")那样初始化，因为支持隐式类型转化
思路不清晰的可以自己画画递归展开图：
📢写在最后
慢慢要开始笔试强化了，每天坚持写完并且博客输出易错知识点
