第二章游戏中数据结构与算法第五节stl线性容器

0STL中的线性容器vector的使用学习重点：vector中的函数vector中的异常处理学习目标：熟练的掌握vector中的函数的使用方法了解vector的异常处理机制。1vector模拟出一个动态数组。因此，它本身是将元素添加到动态数组中加以管理的一个抽象概念。C++Standard并未要求必须以动态数组来实现vector，只是规定了相应条件和操作复杂度。5STL中的线性容器5.1：vector容器2使用vector之前，必须包含头文件<vector>#include<vector>类型vector是一个定义于namespacestd内的template：namespacestd{ template<typenameT，typenameAllocator=allocator<T>> classvector;}vector的元素可以是任意类型T，但必须具备赋值和拷贝两个性质。第二个template参数，用来定义内存模型。5STL中的线性容器5.1：vector容器3vector将其元素复制到内部的动态数组中。元素之间总是存在某种顺序，所以vector是一种有序群集。vector支持随机存取，因此只要知道位置，可以在常数时间内存取任何一个元素。vector的迭代器是随机存取迭代器，所以对任何一个STL算法都可以奏效。在末端附加或删除元素时，vector的性能相当好。前端或中部插入或删除元素，性能就比较差。因为动作点之后的每一个元素都必须移到另一个位置，而每一次移动都得调用赋值操作符。5STL中的线性容器5.1：vector容器4vector之中用于操作大小的函数有size()、empty()、max_size()。另一个与大小有关的函数是capacity()，返回vector实际能够容纳的元素数量。如果超过这个数量，vector就有必要重新分配内存。vector的容量之所以很重要，有以下两个原因：1）一旦内存重新分配，和vector元素相关的所有引用、指针、迭代器都会失效。2）内存重新分配很耗时间。5STL中的线性容器5.1：vector容器5可以使用reserve()保留适当容量，避免一再重新分配内存。std::vector<int>v;//创建空的vectorv.reserve(80); //产生80个存储单元缩减容量的方法，用两个vector交换内容，这样两个vector的容量也会互换。另一种避免重新分配内存的方法是，初始化期间就向构造函数传递附加参数，建构出足够的空间。如果参数是个数值，它将成为vector的起始大小。std::vector<T>v(5);//创建vector同时确定vector的容量5STL中的线性容器5.1：vector容器6构造函数、拷贝和析构函数函数功能vector<Elem>c产生一个空vector，其中没有任何元素vector<Elem>c1(c2)产生另一个同类型vector的副本（所有元素都被拷贝）vector<Elem>c(n)利用元素的默认构造函数生成一个大小为n的vectorvector<Elem>c(n,elem)产生一个大小为n的vector，每个元素值都是elemvector<Elem>c(beg,end)产生一个vector，以区间[beg;end)做为元素初值c.~vector<Elem>()销毁所有元素，并释放内存5STL中的线性容器5.1：vector容器7 vector<int>vContainers1;//定义空vector for(intindex=0;index<10;index++) { vContainers1.push_back(index); }为空vector赋值:用vContainers1产生vContainers2 vector<int>vContainers2(vContainers1);利用元素的默认构造函数生成一个大小为10的vector vector<int> vContainers3(10);5STL中的线性容器5.1：vector容器8 vector<int>vContainers4(10,-1);产生大小为10，每个元素值为-1的容器产生一个vector，以区间[beg;end)做为元素初值 intiarray[5]={1,2,3,4,5}; vector<int>vContainers5(iarray,&iarray[5]);5STL中的线性容器5.1：vector容器9非变动性操作函数功能c.size()返回当前的元素数量c.empty()判断大小是否为零。等同于size()==0c.max_size()返回可容纳的元素最大数量capacity()返回重新分配空间前所能容纳的元素最大数量reserve()如果容量不足，扩大容量c1==c2判断c1是否等于c2c1!=c2判断c1是否不等于c2，等同于!(c1==c2)c1<c2判断c1是否小于c2c1<=c2判断c1是否小于等于c2，等同于!(c2<c1)c1>=c2判断c1是否大于等于c2，等同于!(c1<c2)5STL中的线性容器5.1：vector容器10vector的容量操作:vector<int>vContainers1;for(intindex=0;index<10;index++){ vContainers1.push_back(index);}返回当前的元素数量:cout<<"vContainers1中含有"<<vContainers1.size() <<"元素"<<endl;判断vector大小是否为空:cout<<(vContainers1.empty()?"vContainers1容器为空\n": "vContainers1容器不为空\n");5STL中的线性容器5.1：vector容器11cout<<"vContainers1容器的最大容量为："<< vContainers1.max_size()<<endl;cout<<"vContainers1容器在重新分配空间前所能容纳的元素最大

数量为："<<vContainers1.capacity()<<endl;返回可容纳的元素最大数量:返回重新分配空间前所能容纳的元素最大数量:扩大vContainers3容量vector<int>vContainers3(3);cout<<"扩充之前："<<vContainers3.capacity()<<endl;vContainers3.reserve(6);cout<<“扩充之后："<< vContainers3.capacity()<<endl;5STL中的线性容器5.1：vector容器12vector关系操作：vector<int>vContainers1;for(intindex=0;index<10;index++){ vContainers1.push_back(index);

}vector<int>vContainers2(5);for(intindex=0;index<vContainers2.size();index++){ vContainers2[index]=index; }判断vContainers1是否等于vContainers2cout<<((vContainers1==vContainers2)?"vContainers1== vContainers2":"vContainers1!=vContainers2")<<endl;5STL中的线性容器5.1：vector容器13判断vContainers1是否不等于vContainers2cout<<((vContainers1!=vContainers2)?"vContainers1!= vContainers2":"vContainers1==vContainers2")<<endl;判断vContainers1是否小于vContainers2cout<<((vContainers1<vContainers2)?"vContainers1< vContainers2":"vContainers1>vContainers2")<<endl;判断vContainers1是否大于等于vContainers2cout<<((vContainers1>=vContainers2)?"vContainers1>= vContainers2":"vContainers1<=vContainers2")<<endl;5STL中的线性容器5.1：vector容器14赋值操作函数函数功能c1=c2将c2的全部元素赋值给c1c.assign(n,elem)复制n个elem，赋值给cc.assign(beg,end)将区间[beg;end)内的元素赋值给cc1.swap(c2)将c1和c2元素互换swap(c1,c2)同上。此为全局函数所有赋值操作都可能会调用元素类型的默认构造函数、拷贝构造函数、赋值操作符和（或）析构函数，视元素数量的变化而定。5STL中的线性容器5.1：vector容器15vector赋值操作：vector<int>vContainers1,vContainers2;for(intindex=0;index<10;index++){ vContainers1.push_back(index); }将vContainers1的全部元素赋值给vContainers2：vContainers2=vContainers1;将3个0，赋值给vContainers2vContainers2.assign(3,0);5STL中的线性容器5.1：vector容器16將vContainers1和vContainers2元素互換vContainers1.swap(vContainers2);全局函数swap()將vContainers1和vContainers2元素互換std::swap(vContainers1,vContainers2);将区间[beg;end)内的元素赋值给vContainers2intiarray[5]={1,2,3,4,5};vContainers2.assign(iarray,&iarray[5]);5STL中的线性容器5.1：vector容器17元素存取直接用来存取vector元素的各项操作函数：函数功能c.at(idx)返回索引idx所标示的元素。如果idx越界，抛出out_of_range异常c[idx]返回索引idx所标示的元素，不进行范围检查c.front()返回第一个元素，不检查第一个元素是否存在c.back()返回最后一个元素，不检查最后一个元素是否存在5STL中的线性容器5.1：vector容器18只有at()会进行范围检查。如果索引越界，at()会抛出一个out_of_range异常。其他函数都不作检查。如果发生越界错误，会引发未定义行为。对着一个空vector调用operator[]，front()，back()，都会引发未定义行为。调用operator[]时，必须确定索引有效；调用front()或back()时必须确定容器不为空：std::vector<Elem>coll; //vector为空if(coll.size()>5){coll[5]=elem;} //正确if(!coll.empty()){cout<<coll.front();} //正确coll.at(5)=elem; //抛出out_of_range异常5STL中的线性容器5.1：vector容器19vector<int>vContainers1;for(intindex=0;index<10;index++){ vContainers1.push_back(index);}直接用来存取vectors元素的各项操作通过at()获取vector中的元素cout<<"vContainers1.at(3):"<<vContainers1.at(3)<<endl;通过[]获取vector中的元素cout<<"vContainers1[3]："<<vContainers1[3]<<endl;5STL中的线性容器5.1：vector容器20返回vContainers1容器中第一个元素cout<<"vContainers1容器中第一个元素为：" <<vContainers1.front()<<endl;返回vContainers1容器中最后一个元素cout<<"vContainers1容器中最后一个元素为：" <<vContainers1.back()<<endl;5STL中的线性容器5.1：vector容器21vector的迭代器相关函数函数功能c.begin()返回一个随机存取迭代器，指向第一个元素c.end()返回一个随机存取迭代器，指向最后元素的下一个位置c.rbegin()返回一个逆向迭代器，指向逆向迭代器的第一个元素c.rend()返回一个逆向迭代器，指向逆向迭代器的最后元素的下一个位置5STL中的线性容器5.1：vector容器22vector迭代器是随机存取迭代器。对vector来说，通常就是普通指针。普通指针就是随机存取迭代器，而vector内部结构通常也就是一个数组，所以指针行为可以适用。vector迭代器持续有效，除非发生两种情况：

1）用户在一个较小索引位置上插入或删除元素。2）由于容量变化而引起内存重新分配。5STL中的线性容器5.1：vector容器23vector的迭代器相关操作：vector<int>vContainers;for(intindex=0;index<10;index++){ vContainers.push_back(index);

}定义迭代器vector<int>::iteratorbegin=vContainers.begin(),end=vContainers.end();for(;begin!=end;begin++) cout<<*begin<<'';定义逆向迭代器vector<int>::reverse_iteratorrbegin=vContainers.rbegin(), rend=vContainers.rend();for(;rbegin!=rend;rbegin++) cout<<*rbegin<<'';5STL中的线性容器5.1：vector容器24插入和删除操作vector的插入、删除相关操作函数函数功能c.insert(pos,elem)在pos位置上插入一个elem副本，并返回新元素位置c.insert(pos,n,elem)在pos位置上插入n个elem副本，无返回值c.insert(pos,beg,end)在pos位置上插入区间[beg;end)内的所有元素的副本，无返回值c.push_back(elem)在尾部添加一个elem副本c.pop_back()删除最后一个元素（但不返回删除的元素）5STL中的线性容器5.1：vector容器25c.erase(pos)删除pos位置上的元素，返回下一个元素的位置c.erase(beg,end)删除[beg,end)区间内的所有元素，返回下一个元素的位置c.resize(num)将元素数量改为num（如果size()变大了，多出来的新元素都需以默认构造函数构造完成）c.resize(num,elem)将元素数量改为num（如果size()变大了，多出来的新元素都是elem的副本）c.clear()删除所有元素，将容器清空5STL中的线性容器5.1：vector容器26vector的插入、删除操作vector<int>vContainers;

vContainers.push_back(1);vContainers.push_back(2);vContainers.push_back(3);在pos位置上插入一个元素，并返回新元素位置vector<int>::iteratorpos=vContainers.begin();vContainers.insert(pos,0);在pos位置上插入5个-1。无返回值pos=vContainers.end()-3;vContainers.insert(pos,5,-1);5STL中的线性容器5.1：vector容器27在pos位置上插入区间[beg;end)内的所有元素的副本。无返回值intiarray[3]={4,5,6};pos=vContainers.end()--;vContainers.insert(pos,iarray,&iarray[3]);从vContainers中删除元素vContainers.pop_back();删除pos位置上的元素，返回下一元素的位置pos=vContainers.begin()+5;pos=vContainers.erase(pos);5STL中的线性容器5.1：vector容器28删除[beg,end)区间内的所有元素，返回下一元素的位置vector<int>::iteratortemp=vContainers.begin()+5;pos=vContainers.begin()+1;pos=vContainers.erase(pos,temp);将元素数量改为7（如果size()变大了，多出来的新元素都需以默认构造函数vContainers.resize(7);将元素数量改为num