第八站：vector及其常用操作【上】

vector介绍vector是表示可变大小数组的序列容器。vector与数组的相似点与不同点相同点都是采用连续存储空间来存储元素这就意味着可以采用下标对vector进行访问和数组一样高效不同点vector的大小是可以动态改变的而且它的大小会被容器自动处理vector 底层依靠一块动态分配的数组存储所有元素。 当插入新元素的时候且存储空间不够的时候数组会自动重新分配一个更大的新数组然后将所有元素都移到这个数组中代价较高。 因此每当一个新的元素加入到容器的时候vector并不会每次都重新分配内存。 总结相较于数组vector会占用更多的内存以此换取自动内存管理高效动态扩容的能力vector分配空间策略vector会预先分配一部分额外内存预留扩容空间所以vector的容量capacity通常大于当前实际存储元素的大小size)注意C 标准仅规定 vector 尾插均摊 O (1)未限定扩容倍数各 STL 实现策略不同Windows VS 的 PJMSVCSTL 采用 1.5 倍扩容计算方式为旧容量 旧容量 / 2内存碎片更少但是增容次数更多效率更低因为每次增容都要付出代价Linux GCC 的 libstdc 基于经典 SGI STL 实现采用 2 倍扩容逻辑简单、扩容次数少但是浪费的空间更多因此不能固化认为 vector 一定 2 倍扩容扩容因子由标准库实现决定。同时增多少是一种选择各有利弊均衡一点。注意reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。 对size没有影响resize在开空间的同时还会进行初始化为0影响size不会影响底层的容量capacity。举例//n 当前 size截断尾部多余元素销毁超出部分//n 当前 size尾部新增元素内置类型默认值初始化int 补 0//resize(n, val)扩容时新增的元素统一用 val 填充#includeiostream#includevectorintmain(){std::vectorintmyvector;// set some initial content:for(inti1;i10;i)myvector.push_back(i);myvector.resize(5);myvector.resize(8,100);myvector.resize(12);std::coutmyvector contains:;for(inti0;imyvector.size();i)std::cout myvector[i];std::cout\n;return0;}//输出myvector contains: 1 2 3 4 5 100 100 100 0 0 0 0vector的简单使用1.创建一个vector数组vector数据类型数组名;2.向数组中插入元素数组名.push_back(值;3.返回vector中元素的个数数组名.size();4.遍历数组假设数组名为v4.1.for循环遍历:operator[] sizefor(size_t i0;iv.size();i){coutv[i] ;}coutendl;//换行4.2.迭代器vectorint::iteratoritv.begin();while(it!v.end()){cout*it ;it;}coutendl;4.3.范围for被编译器替换成迭代器方式遍历来支持for(auto e:v){coute ;}coutendl;4.4.关于只读数组的遍历vectorint::const_iteratoritv.begin();while(it!v.end()){// *it 1;会报错cout*it ;it;}coutendl;4.5.关于数组的逆置输出//用到的迭代器函数reverse_iterator rbegin();const_reverse_iterator rbegin() const;vectorint::reverse_iteratorritv.rbegin();while(rit!v.rend()){cout*rit ;rit;}coutendl;5.赋值运算符的使用vector 赋值 operator 赋值会覆盖目标容器全部内容目标 size、内容完全和右侧容器保持一致capacity 会根据实现重新分配适配#includeiostream#includevectorintmain(){std::vectorintfoo(3,0);//创建包含 3 个元素每个元素值都为 0std::vectorintbar(5,0);//创建包含 5 个元素每个元素值都为 0barfoo;//bar 丢弃原来 5 个 0完全复制 foo 的内容foo 不变size 依旧是 3foostd::vectorint();//std::vectorint() 调用无参构造生成一个空临时 vectorsize0无任何元素std::coutSize of foo: int(foo.size())\n;//Size of foo: 0std::coutSize of bar: int(bar.size())\n;//Size of foo: 3return0;}注意1.int(foo.size()) 强制转换原因size() 返回值类型是无符号整数size_t直接输出没问题这里强转 int 是为了避免无符号 / 有符号类型警告。vector 的是**深拷贝**两个容器内存完全独立后续修改 foo 不会影响 bar6.关于给数组赋值时访问越界时不同访问方式可能出现的情况6.1.用[]访问时v[值下标]给定值;//会报断言错误常使用6.2.用at访问v.at(值下标给定值;//会报异常错误7.插入数据v.insert(v.begin(),值);//头插v.insert(v.end(),值);//尾插8.删除数据v.erase(v.begin());//头删v.erase(v.end());//尾删9.寻找数组中特定值的下标使用find函数vectorint::iteratorposfind(v.begin(),c.end(),值);ifpos!v.end())//pos到了v.end()表示没找到{v.erase(pos);//删除pos下标对应的值}10.排序函数sort的使用sort(v.begin(),v.end());vector 迭代器失效问题迭代器失效实际就是迭代器底层对应指针所指向的 空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃举例1插入元素崩溃//1.插入数据引起迭代器的失效因为vector容量不够时会扩容扩容后原来的空间会被释放//而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的//空间而引起代码运行时崩溃。//解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可或将迭代器操作放在插入元素后计算voidtest1(){vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//计算迭代器vectorint::iteratori1v.begin();v.push_back(6);v.push_back(7);//迭代器遍历数组while(i1!v.end()){cout*i1 ;i1;}coutendl;}举例2删除元素崩溃及修正方法//2.删除元素崩溃voidtest2(){vectorintv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);//计算迭代器vectorint::iteratori1v.begin();//删除容器中的所有偶数/*while (i1 ! v.end()) { if (*i1 % 2 0) { v.erase(i1); } i1; } //删除i1后i1就失效了i1的位置不对了再不可以vs下报错编译检查出来的gcc下可能会报错可能正常运行但可能有偶数没删掉 //这样写程序会崩溃 *///修正写法while(i1!v.end()){if(*i1%20){i1v.erase(i1);//erase会返回删除的i1的下一个位置的迭代器}else{i1;}}//遍历for(auto e:v){coute ;}coutendl;}注意 resize、reserve、insert、assign、 push_back等 都有可能是迭代器失效。memset的使用按字节处理拷贝内容memset(a,0,sizeof(int)*10);//合理每一位都是0memset(a,1,sizeof(int)*10);//不合理int类型有4个字节如果每一位都赋予00000001的话总的结果不是原来的值小知识c中变量初始化intiint();//i 0intjint(1);//j 1doubleddouble();//d0.0doubleedouble(1.1);//e 1.1vector模拟实现https://gitee.com/papaya-2/test.c.4/commit/efa1d4c71285a08dc8625104e0f969c2de6e7d46