非可变序列算法与迭代器.pptx

制作者 : 黄襄念 西华大学数学与计算机学院 2014.01;第六章 非可变序列算法;算法、容器、迭代器、函数对象之关系图;MSDN The STL algorithms are generic because they can operate on a variety of data structures. The data structures that they can operate on include not only the STL container classes such as vector and list, but also program-defined data structures and arrays of elements that satisfy the requirements of a particular algorithm. STL algorithms achieve this level of generality by accessing and traversing the elements of a container indirectly through iterators. The STL algorithms extend the actions supported by the operations and member functions of each STL container and allow working, for example, with different types of container objects at the same time. ;算法和容器成员函数的区别 算法：函数模板，不是容器(类模板)的成员函数 —— 直接使用，不是通过容器对象调用 算法：有些与容器的成员函数同名且功能相同 —— 用法不同 头文件 算法： algorithm 数值算法：numeric 函数对象：functional;STL 算法分类 非可变序列算法 算法不修改容器元素的值或顺序 for_each、线性查找、子序列匹配、元素个数、元素比较、最大与最小值 可变序列算法 算法要修改容器元素的值或顺序 复制、填充、交换、变换、替换、生成、删除、反转、唯一、环移、分区、搬移、随机重排。 排序相关算法 排序、折半查找、归并排序、有序集操作、堆排序 数值算法 复数运算、向量运算(值数组valarray)、通用数值计算(求和、内积、部分和、序列相邻差);非可变序列算法;迭代器语义分类;Input 能力弱 单步向前读取元素 单步：自增 iter++ 或 ++iter，错：iter+1 向前：不能反向。错：iter --，iter-1 读取：不能写入迭代器所指元素。 对：… = *iter，错：*iter = … 迭代器赋值与比较 iter1= iter2 = = != == STL 预定义迭代器 istream 迭代器;Output 能力弱 单步向前写入元素。类似 Input，区别在于： Output：只能写 *iter =…，不能读…= *iter STL预定义迭代器：ostream迭代器, inserter迭代器 Forward 能力弱 单步向前读写元素。Input 和 Output 的结合。 Bidirectional 能力较强 单步双向读写元素。在Forward基础上增加：自减-- 支持所有的容器迭代器。 Random 能力强 随机读写元素，在Bidirectional基础上增加： iter + i, iter – i, iter[i], iter.at(i) 支持容器迭代器：vector, deque, string, array ;MSDN The template class is an iterator adaptor that describes a reverse iterator object that behaves like a random-access or bidirectional iterator, only in reverse. It enables the backward traversal of a range. template class RandomIterator class reverse_iterator { … } // 所有标准容器都支持 rbegin(), rend() (const_)reverse_iterator rbegin() (const