C++-11标准模板库STL

1标准模板库主要内容：1.STL2.容器类3.迭代器4.算法库泛型程序设计C++语言的核心优势之一就是便于软件的重用C++中有两个方面体现重用:1.面向对象的思想:继承和多态,标准类库2.泛型程序设计(genericprogramming)的思想:模板机制,以及标准模板库STL2泛型程序设计简单地说就是使用模板的程序设计法。将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。有了STL,不必再写大多的标准数据结构和算法,并且可获得非常高的性能。3STL基本概念容器:可容纳各种数据类型的通用数据结构,是类模板迭代器:可用于依次存取容器中元素,类似于指针算法:用来操作容器中的元素的函数模板sort()来对一个vector中的数据进行排序find()来搜索一个list中的对象算法本身与他们操作的数据的类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。4510.1StandardTemplateLibrary1.STL的基本思想可以把软件部件想象成一个三维空间第一维表示数据类型(int,double,char,…)第二维表示容器(array,linked-list,…)第三维表示算法(sort,merge,search,…)根据图示，需要设计i*j*k个不同的代码版本，比如整数数组的排序算法、double数组的排序算法，doublelinked-list的搜索算法…。int,double,class,…array,linked-list…sort,merge,search,…kij6通过使用数据类型作为参数的模板函数，第一维(i轴)就可取消，而仅需要设计j*k个不同的代码。下一步是让算法可以工作在不同的容器上，这就意味着排序算法既可以用在array上，也可用在linked-list上。即只需要设计j+k个不同的代码版本。STL具体化了上述思想，期望通过减少开发时间以简化软件开发，简化调试、维护并增加代码的可移植性（跨平台，硬件和系统）。72.什么是STL标准模板库（StandardTemplateLibrary,STL)，是ANSI/ISOC++最新的标准函数库中的一个子集，是一个泛型化（generic)的数据结构和算法库。从逻辑层次来看，在STL中体现了泛型化程序设计（GP）的思想，引入了诸多新的名词，比如像容器(container)算法(algorithm)，迭代器(iterator)等。与OOP中的多态（polymorphism）一样，泛型也是一种软件的复用技术。从实现层次看，整个STL是以一种类型参数化（typeparameterized）的方式实现的，这种方式基于C++语言的模板机制。8图1STL和C++标准函数库9STL中的软件包主要包括：容器(Container)：一种存储有限集合数据元素的数据结构，例如，向量、列表、集合、映射等。迭代器(Iterator)：或称游标，是一种面向对象的泛型指针，实现对容器中的任意类型对象的遍历，从而对各对象进行处理。算法库(Algorithms)：包括了各种基本算法，如sort,copy,search,revese等，对容器中的对象进行各种操作。函数对象(FunctionObject)：定义了函数调用操作符(operator())的类。适应器(Adaptor)：封装一个部件以提供另外的接口(例如用list实现stack)。10迭代器intarray[100];该数组就是容器,而int*类型的指针变量就可以作为迭代器,sort算法可以作用于该容器上,对其进行排序:sort(array,array+70);//将前70个元素排序111.STL的组织在C++标准中，STL被组织为下面的13个不带.h后缀的头文件：algorithm、deque、functional、iterator、vector、list、map、memory、numeric、queue、set、stack和utility。1210.2容器类1.容器的基本概念容器指一种存储有限集合数据元素的数据结构。容器类是一批相关的标准类模板的总称，它包含最基本的7个标准类模板，分为两大类：顺序容器类(SequenceContainer)在其中存储的对象是有序的，用户可以在指定位置插入或存取对象。vector(向量)list(列表)deque(双端队列)13关联容器类(AssociativeContainer)在其中存储的对象是无序的，对象在容器中的装入位置由非线性方法确定。map(映像)set(集合)multiset(多重集合)multimap(多重映像)关联容器提供了基于KEY的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。当一个KEY对应一个Value时，可以使用集合(Set)和映射(Map)；若对应同一KEY有多个元素被存储时，可以使用多集合(MultiSet)和多映射(MultiMap)。141.容器类的特点1)任何一个容器类都可以容纳任何类型的对象或任何基本数据类型的数值。STL自动把基本数据类型的数据包装转换为类型的对象。对用户自定义类类型的对象，要求必须提供正确的构造函数、拷贝构造函数和析构函数。2)所有容器类都提供了一些与其特性相关的成员函数。3)每个容器类都提供了一个相应的迭代器。4)每个容器类都提供有一个参数为空的构造函数，方便用户定义容器类对象。15对象被插入容器中时,被插入的是对象的一个复制品。许多算法,比如排序,查找,要求对容器中的元素进行比较,有的容器本身就是排序的,所以,放入容器的对象所属的类,往往还应该重载==和运算符。16顺序容器1.7种容器的逻辑结构vector和deque用动态数组实现，允许顺序访问和随机访问。list用链表实现，允许顺序访问，不支持随机存取。AddRemoveheadtail17Vectorvector头文件vector动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间)。18Vector可变长的动态数组必须包含头文件#includevector支持随机访问迭代器根据下标随机访问某个元素时间为常数在尾部添加速度很快在中间插入慢所有STL算法都能对vector操作19vector的成员函数构造函数初始化20vector的成员函数其他常用函数21Vector实例22二维动态数组vectorvectorintv(3);//v有3个元素,//每个元素都是vectorint容器23二维动态数组24dequedeque头文件deque双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。25Deque容器双向队列必须包含头文件#includedeque所有适用于vector的操作都适用于dequedeque还有push_front(将元素插入到容器的头部)和pop_front(删除头部的元素)操作26Listlist头文件list双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。27List容器28List容器还支持8个成员函数:291.列表容器类list头文件为list。标准类模板list的定义：templateclassT,classA=…//T代表容器中的数据类型，A与内存分配有关，系统给出了默认值classlist{public:…voidsplice(iteratorit,list&x);//粘接voidsplice(iteratorit,list&x,iteratorfirst);voidsort();voidmerge(list&x);voidpush_front(constT&x);voidpop_front();…};30列表容器是用链表方法实现的。链表的优点：若只在链表头部或链表尾部插入或删除数据元素时，效率很高。链表的缺点：随机访问效率很低。和使用向量容器相比，使用列表容器的优点：顺序访问时不仅效率高，并且不会因频繁申请数组空间并复制原数组内容而降低效率。使用列表容器的缺点：若要频繁地进行随机访问，其效率不高。list没有重载下标运算符“[]”，从而不支持随机存取。31关联容器元素是排序的插入任何元素,都按相应的排序规则来确定其位置在查找时具有非常好的性能通常以平衡二叉树方式实现,插入和检索的时间都是O(log(N))32关联容器set和multisetset/multiset头文件setset即集合。set中不允许相同元素,multiset中允许存在相同的元素。用动态数组实现，采用排序的方法保存集合中的数据元素，查找效率很高。x331.集合容器类set头文件为set。set采用动态数组结构实现，STL采用排序的方法保存集合中的数据元素，从而提高了查找效率。集合中的数据元素无序且不重复。set没有重载下标运算符“[]”。multiset容器允许存在相同值的对象，头文件为set。34关联容器map和multimapmap/multimap头文件mapmap与set的不同在于map中存放的元素有且仅有两个成员变量,一个名为first,另一个名为second,map根据first值对元素进行从小到大排序,并可快速地根据first来检索元素。map同multimap的不同在于是否允许相同first值的元素。ABCD1234351.映像容器类map头文件为map。映像容器中的数据元素必须成对出现，也称做字典数组（或关联数组）。STL中定义了成对数据类型的模板类型的结构体pair:templateclassT,classUstructpair{typedefTfirst_type;typedefUsecond_type;Tfirst;Usecond;pair();pair(constT&x,constU&y);};36map提供对“(key,value)”数对进行有效存取与管理的机制。其中key是作为键出现的，value作为对应于该键的一个具体数据值。要求键key在容器中是唯一的，而其对应的value数据值则可以重复。重载了下标运算符“[]”，以进行基于key值的存取与插入。map采用动态数组结构实现，STL采用排序的方法保存集合中的数据元素，从而提高了查找效率。multimap容器可存在相同关键字的对象，头文件为map。multimap中没有重载下标运算符“[]”。map姓名，手机号contact;contact[张三]=13987340954;contact[Ellen]=13342340954;37容器适配器queue头文件queue队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。先进先出。38容器适配器priority_queue头文件queue优先级队列。最高优先级元素总是第一个出列39顺序容器和关联容器中都有的成员函数begin返回指向容器中第一个元素的迭代器end返回指向容器中最后一个元素后面的位置的迭代器rbegin返回指向容器中最后一个元素的迭代器rend返回指向容器中第一个元素前面的位置的迭代器erase从容器中删除一个或几个元素clear从容器中删除所有元素40顺序容器的常用成员函数front:返回容器中第一个元素的引用back:返回容器中最后一个元素的引用push_back:在容器末尾增加新元素pop_back:删除容器末尾的元素erase:删除迭代器指向的元素(可能