没备案的网站收录,分析网站设计对网站搜索引擎友好性的影响,新闻热点事件,做企业官网要多少资金和时间目录 一、vector的介绍二、vector的使用1、vector的构造函数2、vector的插入和三种遍历方式3、开空间4、insert5、find6、erase补充 三、vector的底层实现1、成员变量2、构造函数3、push_back4、访问方式5、pop_back6、insert - pos位置插入x7、resize8、拷贝构造9、赋值10、er… 目录 一、vector的介绍二、vector的使用1、vector的构造函数2、vector的插入和三种遍历方式3、开空间4、insert5、find6、erase补充 三、vector的底层实现1、成员变量2、构造函数3、push_back4、访问方式5、pop_back6、insert - pos位置插入x7、resize8、拷贝构造9、赋值10、erase 四、迭代器失效1、insert在pos位置插入时发生扩容pos这个迭代器就失效了2、erase进行删除的时候会发生迭代器失效 五、vector和string的优势四、算法题1、电话号码的字母组合 -- 全排列问题2、只出现一次的数字3、杨辉三角4、删除排序数组中的重复项5、数组中出现次数超过一半的数字 上次课回顾 windows和Linux下默认的string类型的大小 1windows 按理来说大小应该是12但是运行的结果却又28 多了个_Buf数组这个数组大小是16可以存15个字符 所以s1和s2的大小不是12而是18 对于_Buf这个字符数组如果string的_str的大小小于等于15就存在_Buf里面如果大于15则_Buf这个字符数组就废弃重新开辟空间。目的防止频繁开辟小空间 2Linux Linux默认64位默认release版本 上述代码放到Linux里面大小就是八字节也就是string里面就放了一个指针 浅拷贝问题 1析构两次 - 引用计数 当最后一个对象删除时才会释放这段空间 2一个修改会影响另一个 - 写时拷贝(也有缺陷) 一、vector的介绍
就是顺序表 string类是一个保存字符的动态数组由于其中有一个接口c_str,转化成c语言的字符串要以\0结尾所以string类最后会有一个\0. string支持 string支持比较大小通过ascii码 vector是一个保存T类型的动态数组vector也是保存字符的动态数组但是不会以\0结尾不保存\0. vector不支持 vector不支持比较大小也可以通过ascii码比较但意义不大 二、vector的使用
1、vector的构造函数 1全缺省构造无参的
vectorint v1;2n个value的构造
vectorint v2(5, 1);3迭代区间的构造 vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(5);vectorint v3(v1.begin(), v1.end());2、vector的插入和三种遍历方式
1、下标
#includeiostream
#includevector
using namespace std;int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (int i 0; i v1.size(); i){cout v1[i];}cout endl;return 0;
}2、迭代器
#includeiostream
#includevector
using namespace std;int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vectorint::iterator t v1.begin();while (t ! v1.end()){cout *t;t;}cout endl;return 0;
}3、范围for
#includeiostream
#includevector
using namespace std;int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout e;}cout endl;return 0;
}3、开空间
1、开空间reserve
void test2()
{vectorint v1;int sz v1.capacity();for (int i 0; i 100; i){v1.push_back(i);if (sz ! v1.capacity()){cout capacity: v1.capacity() endl;sz v1.capacity();}}
}int main()
{test2();return 0;
}1.5倍扩容Linux一般是二倍扩容 减少频繁扩容的方式使用reserve而不使用resize因为resize不仅扩容还会初始化那么再插入的时候还需要扩容
2、开空间加初始化resize vector的resize不缩容缩容用Shrink_to_fit void test2()
{vectorint v1;v1.reserve(100);int sz v1.capacity();for (int i 0; i 100; i){v1.push_back(i);if (sz ! v1.capacity()){cout capacity: v1.capacity() endl;sz v1.capacity();}}v1.resize(10);cout capacity: v1.capacity() endl;cout size: v1.size() endl;
}4、insert 1在某一位置插入val
void test3()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(5);for (auto e : v1){cout e ;}cout endl;v1.insert(v1.begin(), 10);for (auto e: v1){cout e ;}cout endl;
}2、在某一位置插入n个val
void test3()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(5);for (auto e : v1){cout e ;}cout endl;v1.insert(v1.begin(), 2,10);for (auto e: v1){cout e ;}cout endl;
}3在某一位置插入一个迭代区间 v1.insert(v1.begin(), v2.begin(), v2.end());cout v1:;for (auto e : v1){cout e ;}cout endl;5、find
vector没有find用的是算法里面的find string为何要自己写find 1string查找的更为复杂不仅要查一个字符还有可能查一个字串 2string返回下标更合适 void test4()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;v1.insert(find(v1.begin(), v1.end(), 2), 20);for (auto e : v1){cout e ;}cout endl;}6、erase
补充
vector不支持流插入和流提取 因为vector打印时每个之间用什么隔开自己决定 string如果没有特殊需求一般打印的时候都是连着
三、vector的底层实现
相比于之前string的直接定义_a、_size、_capacity这里的vector是间接定义的
1、成员变量
vector不使用下标只使用迭代器进行访问、插入等
private:iterator start;iterator finish;iterator end_of_storage;2、构造函数
3、push_back
namespace zyh
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}size_t size(){return finish - start;}size_t capacity(){return end_of_storage - start;}void reverse(size_t n){if (n capacity()){size_t oldsize size();T* tmp new T[n];if (start){memcpy(tmp, start, old * sizeof(T));}delete[] start;start tmp;finish start oldsize;end_of_storage start n;}}void push_back(const T x){if (finish end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reverse(newcapacity);}*finish x;finish;}iterator begin(){return start;}iterator end(){return finish;}const_iterator begin() const{return start;}const_iterator end() const{return finish;}private:iterator start;iterator finish;iterator end_of_storage;4、访问方式
迭代器
iterator begin(){return start;}iterator end(){return finish;}const_iterator begin() const{return start;}const_iterator end() const{return finish;}vectorint::iterator it1 v1.begin();while (it1 ! v1.end()){std::cout *it1 ;it1;}std::cout std::endl;范围for v1.push_back(5);for (auto v : v1){std::cout v ;}std::cout std::endl;[] T operator[](size_t pos){assert(pos size());return start[pos];//return *(start pos);}v1.push_back(6);for (int i 0; i v1.size(); i){std::cout v1[i] ;}std::cout std::endl;5、pop_back void pop_back(){assert(size() 0);--finish;}6、insert - pos位置插入x void insert(iterator pos,const T x){assert(pos start pos finish);if (finish end_of_storage){reverse(capacity() 0 ? 4 : capacity() * 2);}memmove(pos 1, pos, sizeof(T) * (finish - pos));finish;*pos x;}问题扩容时pos迭代器失效 void insert(iterator pos,const T x){assert(pos start pos finish);int len pos - start;if (finish end_of_storage){reverse(capacity() 0 ? 4 : capacity() * 2);pos start len;}memmove(pos 1, pos, sizeof(T) * (finish - pos));finish;*pos x;}7、resize
capacity和size都要变 T()是个匿名对象因为要给一个缺省值又因为T是不确定的因此使用匿名对象 在模板里面无论是内置类型还是自定义类型都是可以初始化的 void resize(size_t n, T val T()){if (n size())finish start n;else if (n size() n capacity()){while (finish ! start n){*finish val;finish;}}else{reverse(n);while (finish ! start n){*finish val;finish;}}}8、拷贝构造 //拷贝构造vector(const vectorT v){reverse(v.capacity());for (const auto i : v){push_back(i);}}1、因为v是const的所以在使用范围for进行遍历的时候注意也要是const auto 9、赋值
下面这样写是不对的全局的swap两个变量都不能有const的 vectorT operator(vectorT v){//swap(v);std::swap(start, v.start);std::swap(finish, v.finish);std::swap(end_of_storage, v.end_of_storage);return *this;}10、erase void erase(iterator pos){assert(pos finish);assert(pos start);iterator it pos 1;while (it finish){*(it - 1) *it;it;}finish--;}四、迭代器失效 insert和erase形参pos都可能会失效 原则是insert和erase过的迭代器不要使用 1、insert在pos位置插入时发生扩容pos这个迭代器就失效了
2、erase进行删除的时候会发生迭代器失效 erase有一个返回值返回的是刚刚删除元素的下一个位置 删除所以元素中的偶数
五、vector和string的优势
1、尾插和尾删 2、随机访问
四、算法题
1、电话号码的字母组合 – 全排列问题
class Solution {
public:string num2str[10] {,,abc,def,ghi,jkl,mno,pqrs,tuv, wxyz};void combinstr(string digits, int dinum, string str, vectorstring v){if(dinum digits.size()){v.push_back(str);return;}int num digits[dinum] - 0;string numstr num2str[num];for(int i 0; i numstr.size(); i){combinstr(digits, dinum 1, str numstr[i], v);}}vectorstring letterCombinations(string digits) {vectorstring v;if(digits.size() 0)return v;combinstr(digits, 0, , v);return v;}
};2、只出现一次的数字 对于此题的解法就是异或^ 0和任意数a异或还是a0^a a 任意数a和其自身异或为0a^a 0; class Solution {
public:int singleNumber(vectorint nums) {int res 0;for(int i 0; i nums.size(); i){res res ^ nums[i];}return res;}
};3、杨辉三角 逻辑与两个结果都为真时才为真 || 逻辑或两个结果有一个为真则为真 class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows);for(int i 0; i numRows; i){vv[i].resize(i1);for(int j 0; j i1; j){if(j 0 || j i || i 0){vv[i][j] 1;}else{vv[i][j] vv[i-1][j-1] vv[i-1][j];}}}return vv;}
};改进 if(j 0 || j i || i 0) { vv[i][j] 1; } 对于这行代码可以使用vector里面的front和back class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows);for(int i 0; i numRows; i){vv[i].resize(i1);vv[i].front() vv[i].back() 1;for(int j 1; j i; j){vv[i][j] vv[i-1][j-1] vv[i-1][j];}}return vv;}
};也可以把所有的位置都初始化为0vv[i].resize(i1, 0); 在对v[i][j]进行赋值的时候可以直接判断只给0的位置因为1的位置已经赋值了 4、删除排序数组中的重复项 class Solution {
public:int removeDuplicates(vectorint nums) {if(nums.size() 0)return 0;if(nums.size() 1)return 1;size_t i 1;size_t j 0;int len 1;while(i nums.size()){if(nums[i] nums[j]){i;}else{nums[len] nums[i];len;j i;i;}}return len;}
};对于排序的序列去重使用双指针 5、数组中出现次数超过一半的数字 使用两个指针遍历数组当两个指针指向的内容不同时就删除最后留下的就是多个一样的数或一个数 #include cstddef
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param numbers int整型vector * return int整型*/int MoreThanHalfNum_Solution(vectorint numbers) {// write code heresize_t len numbers.size();if(len 1)return numbers[0];auto i numbers.begin();auto j numbers.end()-1;while(i ! j){if(*i ! *j){numbers.erase(j);numbers.erase(i);j numbers.end() - 1;i numbers.begin();}else{i;}}return numbers[0];}
};
