C++ STL详解.ppt

ACM/ICPC程序设计 C++ 标准模板库C++ Standard Template Libarary 计算机学院 万波 主要内容 STL概述：组件、容器、迭代器（iterator）、算法 STL容器： 常用容器：vector、deque、 list、 map/multimap 、set 特殊容器：stack、queue，priority_queue 其他容器：hashtable STL算法：搜寻、排序、拷贝、数值运算 STL概述 STL是C++标准程序库的核心，深刻影响了标准程序库的整体结构 STL是泛型（generic）程序库，利用先进、高效的算法来管理数据 STL由一些可适应不同需求的集合类（collection class），以及在这些数据集合上操作的算法（algorithm）构成 STL内的所有组件都由模板（template）构成，其元素可以是任意类型 STL是所有C++编译器和所有操作系统平台都支持的一种库 STL概述 STL概述 STL概述 模板（template） 函数模板 STL概述 模板（template） 类模板 STL概述 STL组件 容器（Container） － 管理某类对象的集合 迭代器（Iterator） － 在对象集合上进行遍历 算法（Algorithm） － 处理集合内的元素 容器适配器（container adaptor） 函数对象(functor) STL概述 STL容器类别 序列式容器－排列次序取决于插入时机和位置 关联式容器－排列顺序取决于特定准则 STL概述 STL容器的共通能力 所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。 所有元素都形成一个次序（order），可以按相同的次序一次或多次遍历每个元素 各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未定义的行为 STL概述 STL容器元素的条件 必须能够通过拷贝构造函数进行复制 必须可以通过赋值运算符完成赋值操作 必须可以通过析构函数完称销毁动作 序列式容器元素的默认构造函数必须可用 某些动作必须定义operator ==，例如搜寻操作 关联式容器必须定义出排序准则，默认情况是重载operator STL概述 STL容器的共通操作 初始化（initialization） 产生一个空容器 以另一个容器元素为初值完成初始化 以数组元素为初值完成初始化 STL概述 STL容器的共通操作 与大小相关的操作（size operator） size()－返回当前容器的元素数量 empty()－判断容器是否为空 max_size()－返回容器能容纳的最大元素数量 比较（comparison） ==,!=,,=,,= 比较操作两端的容器必须属于同一类型 如果两个容器内的所有元素按序相等，那么这两个容器相等 采用字典式顺序判断某个容器是否小于另一个容器 STL概述 STL容器的共通操作 赋值（assignment）和交换（swap） swap用于提高赋值操作效率 与迭代器（iterator）相关的操作 begin()－返回一个迭代器，指向第一个元素 end()－返回一个迭代器，指向最后一个元素之后 rbegin()－返回一个逆向迭代器，指向逆向遍历的第一个元素 rend()－返回一个逆向迭代器，指向逆向遍历的最后一个元素之后 STL概述 容器的共通操作 元素操作 insert(pos,e)－将元素e的拷贝安插于迭代器pos所指的位置 erase(beg,end)－移除[beg，end]区间内的所有元素 clear()－移除所有元素 STL概述 迭代器（iterator）（示例:iterator） 可遍历STL容器内全部或部分元素的对象 指出容器中的一个特定位置 迭代器的基本操作 STL概述 迭代器（iterator） 所有容器都提供获得迭代器的函数 STL概述 迭代器（iterator） 所有容器都提供两种迭代器 container::iterator以“读/写”模式遍历元素 container::const_iterator以“只读”模式遍历元素 迭代器示例：iterator STL概述 迭代器（iterator） 迭代器分类 双向迭代器 可以双向行进,以递增运算前进或以递减运算后退、可以用==和!=比较。 list、set和map提供双向迭代器 随机存取迭代器 除了具备双向迭代器的所有属性，还具备随机访问能力。 可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用和之类的关系运算符比较两个迭代器。 vector、deque和string提供随机存取迭代器 S