第二章游戏中的数据结构与算法第四节stl基本概念

STL基本概念STL概论容器迭代器了解容器和迭代器的概念14STL基本概念4.1：STL概论STL（StandardTemplateLibrary，标准模板库)是惠普实验室开发的,在被引入C++之前该技术就已经存在了很长的一段时间。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。STL各部分之间的关系：容器迭代器算法将容器中的数据通过迭代器送到算法中进行运算，得到我想要的结果24STL基本概念4.2：STL中的容器在实际的开发过程中，数据结构本身的重要性不会逊于操作数据结构的算法的重要性。当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。34STL基本概念4.2：STL中的容器容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器，可以通过下表总结一下它们和相应头文件的对应关系。容器描述头文件vector

向量连续存储的元素vectorlist列表由节点组成的双向链表listdeque双队列连续存储的指向不同元素的指针所组成的数组dequestack栈后进先出的值的排列stackmap映射

由{键，值}对组成的集合mapset集合由节点构成的红黑树set4容器：用来管理一组元素。为了适应不同需要，STL提供了不同的容器4STL基本概念4.2：STL中的容器5容器可分为两类：1）序列式容器，是可序群集，其中每个元素均有固定位置，元素的位置取决于插入时机和地点，和元素值无关。如果在容器尾添加6个元素，它们的排列次序将和添加次序一致。STL提供3个定义好的序列式容器：vector，deque，list。2）关系型容器，是一种已序群集，元素位置取决于特定的排序准则。如果将6个元素添加到这样的群集中，它们的位置取决于元素值，和插入次序无关。STL提供了4个关系型容器：set，multiset，map，multimap。4STL基本概念4.2：STL中的容器6关系型容器自动对其元素排序，这并不意味着它们就是用来排序的。也可以对序列式容器的元素加以手动排序。自动排序带来的主要优点是，当搜寻元素时，可获得更好效率。明确地说可以放心使用二分搜寻法。自动排序只不过是关系型容器的一个（有用的）副作用而已。STL中的容器都有一些共同的能力，也就是有相同的函数接口，这些函数主要是用于进行数据比较、迭代和存储的。4STL基本概念4.2：STL中的容器7STL容器都必须满足以下3个条件：1）容器进行元素的插入操作时，内部实现的是拷贝操作，置于容器内。因此STL容器内的每一个元素都必须能够被拷贝。也就是说要存放到容器内的对象具有公有属性的拷贝构造函数。如果容器内放置的是指针类型的数据则无此要求。2）总体而言，所有元素形成一个次序。也就是说多次遍历每个元素时的次序总是相同的。3）一般而言，各项操作并非绝对安全。调用者必须确保传给操作函数的参数符合需求，违反这些需求（例如使用非法索引）会导致未定义的行为，通常STL在这个情况下不会抛出异常。4STL基本概念4.2：STL中的容器8容器类的通用的函数：函数功能ContTypec产生一个未含任何元素的空容器ContTypec1(c2)产生一个同型容器ContTypec(beg,end)复制[beg;end]区间内的元素，作为容器初值c.~ContType()删除所有元素，释放内存c.size()返回容器中的元素数量c.empty()判断容器是否为空c1!=c2 判断是否c1不等于c2，相当于!(c1==c2)c1<c2 判断是否c1小于c2c1>c2 判断是否c1大于c2，相当于c2<c14STL基本概念4.2：STL中的容器9c1<=c2 判断是否c1小于等于c2，相当于!(c2<c1)c1>=c2 判断是否c1大于等于c2，相当于!(c1<c2)c1=c2 将c2的所有元素赋值给c1c1.swap(c2) 交换c1和c2的数据swap(c1,c2) 同上，是个全局函数c.begin() 返回一个迭代器，指向第一个元素c.end() 返回一个迭代器，指向最后元素的下一个位置4STL基本概念4.2：STL中的容器10c.rbegin() 返回一个逆向迭代器，指向逆向遍历时的第一个元素c.rend() 返回一个逆向迭代器，指向逆向遍历时的最后元素的下一个位置c.insert(pos,elem) 将elem的一份副本安插于pos处。返回值和pos的意义并不相同c.erase(beg,end) 移除[beg;end]区间内的所有元素。某些容器会返回未被移除的第一个接续元素c.clear() 移除所有元素，令容器为空c.get_allocator()返回容器的内存模型（memorymodel）4STL基本概念4.2：STL中的容器11迭代器是一个“可遍历STL容器內全部或部分元素”的对象。一个迭代器用來指出容器中的一个特定位置。1）Operator*传回当前位置上的元素值。如果该元素拥有成员，可以通过迭代器直接以operator->取用它们。2）Operator++将迭代器前进至下一个元素。大多数迭代器还可使用operator--退回到前一个元素。4STL基本概念4.3：迭代器几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。123）Operators==和Operator!=判断两个迭代器是否指向同一个位置。4）Operator=为迭代器赋值（将其所指元素的位置赋值给其他迭代器）。迭代器是个所谓的智能指针，具有遍历复杂数据结构的能力。其下层运作机制取决于其所遍历的数据结构。每一种容器类型都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套方式定义于内部。因此各种迭代器的接口相同，类型却不同。4STL基本概念4.3：迭代器13泛型程序设计的概念：所有操作行为都使用相同接口，虽然它们的类型不同。因此，可以使用templates将泛型操作公式化，使之得以顺利运作那些“能够满足接口需求”的任何类型。所有容器类都提供了一些成员函数，以获得迭代器并用其遍历容器中所有元素。1）begin()返回一个迭代器，指向容器起始点，也就是第一个元素（如果有的话）的位置。4STL基本概念4.3：迭代器142）end()返回一个迭代器，指向容器结束点。结束点在最后一个元素之后，这样的迭代器又称作“逾尾”迭代器。begin()和end()形成了一个半开区间，从第一个元素开始，到最后一个元素的下一位置结束。4STL基本概念4.3：迭代器15begin()和end()形成了一个半开区间，有两个优点：1）为“遍历元素时，循环的结束时机”提供了一个简单的判断依据。只要尚未到达end()，循环就可以继续进行。2）不必对空区间采取特殊处理手法。空区间的begin()就等于end()。任何一种容器都定义有两种迭代器类型：container::iterator1）这种迭代器以“读/写”模式走访元素。container::const_iterator2）container表示任意的容器，这种迭代器以“只读”模式走访元素。4STL基本概念4.3：迭代器164STL基本概念4.4：算法STL中算法存在的意义：函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求平方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。174STL基本概念4.4：算法算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类，用以声明函数对象。18本节介绍C++标准模板库（STL）的基本概念与分类。容器类（简称容器）用来管理一组元素。为了适应不同需要，STL提供了不同的容器。迭代器用來指出容器中的一个特定位置。判断试题迭代器就是一个指向元素的指针。（