C++ 标准模板库(STL).pdf

目 录 1 STL 简介2 2 顺序性容器2 2.1 C++ VECTOR （向量容器）2 2.2 C++ LIST （双向链表）4 2.3 C++ DEQUE(双向队列) 6 2.4 三者比较8 3 关联容器8 3.1 特点8 3.2 C++ SETS MULTISETS 9 3.3 C++ MAPS MULTIMAPS 11 4 容器适配器 12 4.1 特点 12 4.2 C++ STACKS （堆栈） 13 4.3 C++ QUEUES(队列) 13 4.4 C++ PRIORITY QUEUES(优先队列) 13 5 迭代器 14 5.1 解释 14 5.2 功能特点 14 6 C++标准库总结 15 6.1 容器 15 6.2 算法 15 6.3 函数对象 17 6.4 迭代器 19 6.5 分配器 19 6.6 数值 19 1 1 STL 简介 /reference/stl/更加详细的资料 C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集 合，它提供给程序员一些标准的数据结构的实现如 queues( 队列), lists(链表), 和 stacks(栈)等. C++ STL 提供给程序员以下三类数据结构的实现： 标准容器类 顺序性容器 vector 从后面快速的插入与删除，直接访问任何元素 deque 从前面或后面快速的插入与删除，直接访问任何元素 list 双链表，从任何地方快速插入与删除 关联容器 set 快速查找，不允许重复值 multiset 快速查找，允许重复值 map 一对多映射，基于关键字快速查找，不允许重复值 multimap 一对多映射，基于关键字快速查找，允许重复值 容器适配器 stack 后进先出 queue 先进先出 priority_queue 最高优先级元素总是第一个出列 程序员使用复杂数据结构的最困难的部分已经由STL完成. 如果程序员想使用包 含int数据的stack, 他只要写出如下的代码: stackint myStack; 接下来, 他只要简单的调用 push() 和 pop() 函数来操作栈. 借助 C++ 模板的 威力, 他可以指定任何的数据类型，不仅仅是int类型. STL stack实现了栈的功 能，而不管容纳的是什么数据类型. 2 顺序性容器 2.1 C++ Vector （向量容器） 是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩 展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数 组。 在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据 2 存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即 capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配 一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作： 首先，vector 会申请一块更大的内存块； 然后，将原来的数据拷贝到新的内存块中； 其次，销毁掉原内存块中的对象（调用对象的析构函数）； 最后，将原来的内存空间释放掉。 如果vector 保存的数据量很大时，这样的操作一