STL 在编程中的应用.doc

精品论文stl 在编程中的应用高庆，张能立 武汉理工大学计算机学院, 武汉(430073) e-mail: 摘要:stl 作为 c+标准的重要一部分，在很大程序上改变了 c+程序的结构与使用方式，stl 大大提高了软件开发的效率，降低了开发成本成维护成本，降低了开发时间与维护时间， 提高了软件稳定性与可移植性。随着软件行业的迅速发展, stl 在 c+程序中得到了广泛的 应用。本文讲述了 stl 的容器，迭代器，算法基本知识与基本理论， 使用方式, 并拿出几 个典型的容器，迭代器，算法进行讲述，并分析出特性及应注意的地方。为理解,使用 stl 作好了铺垫,最后举实例说明了如何在编程中使用 stl 的容器，迭代器，算法进行程序设计 关键词：标准模板库, 容器，算法，迭代器中图分类号：tp3131 stl 简介stl(标准模板库)是一个可复用组件库，也是一个包算法与数据结构的软件框架. stl 在1994 年走入 c+标准,使得原本即将推出的 c+标准延迟 4 年问世, 由于 stl 包含很多高效 稳定的数据结构与算法, 所以在程序开发人员中得到了广泛的使用1.stl 的实现版本主要有五种，分别为 hp 实现版本，p.j.plauger 实现版本,rouge wave 实现版本,stlport 实现版本,sgi stl 实现版本，它们所提供的功能一样，只是版权及代码的 风格不同stl 主要分容器，算法, 迭代器三大块。容器与迭代器是以类的形式提供，容器类包含 很多数据结构及其上的操作.算法是一些常用的操作的集合，包含排序，查找，拷贝，数学 运算等. 迭代器是 stl 的关键部分，它在容器与算法之间起桥梁作用, 类似于 c 语言中的指 针, 但比指针复杂2 容器，算法，迭代器2.1 容器stl 的容器主要有两种分类方式, 一种是按容器的规范来分,可分为标准容器与非标准 容器.另一种可按照容器内部的存储特性来分，可分为序列式容器与关联式容器. 所以 stl 容器一般分为以下四类:标准 stl 序列容器:vector, string, deque 和 list. 标准 stl 关联容器:set, multiset, map 和 multimap. 非标准序列容器: slist 和 rope.非标准的关联容器 hash_set,hash_multiset. hash_map 和 hash_multimap.22.2 算法stl 的算法也主要有两种分类方式，一种是按是否改变容器中无素内容来分，可分为质 变算法与非质变算法.另一种是按操作的对象可分为数值算法,基本算法，set 相关算法,heap 算法, 常用操作算法. 下面以第三种分类法介绍 stl 的算法:数值算法有 accumute, adjacent_difference, inner_product, partial_sum, power, iota.- 6 -基本算法有 equal, fill, fill_n, iter_swap, lexicographical_compare, max, min, mismatch,swap, copy, copy_backward.set 相关算法有 set_union, set_intersection, set_difference, set_symmetric_difference.heap 算法有 make_heap, pop_heap, push_heap, sort_heap常用操作算法有 :adjacent_find, count, count_if, find, find_if, find_end, find_first_of, for_each, generate, generate_n, includes, max_element, merge, min_element, partition, remove, remove_copy, remove_if, remove_copy_if, replace, replace_copy, replace_if, replace_copy_if, reverse, reverse_copy, rotate, rotate_copy, search, search_n, swap_ranges, transform, unique, unique_copy, lower_bound, upper_bound, binary_search, next_permutation, prev_permutation,random_shuffle, partial_sort, partial_sort_copy.等2.3 迭代器迭代器是一种行为类似指针的对象, 而指针的各种行为中最常见也最重要的便是内容 提领和成员访问.因些迭代器重要编程工作就是对 operator*和 operator-进行重载工作迭代器的主要内容就是迭代器型别, 迭代器的型别有五种:value type, difference type, reference, iterator category.第一种型别 value type 表示迭代器所指类型的类型.第二种型别 difference type 表示两个迭代器之间的距离的类型. 第三种型别 reference type 表示是否可改 变所指对象的内容.第四种类型表示所指之物的地址的类型.第五种类型表示迭代器的类型， 这个反映了迭代器的特性.13 stl 的应用3.1 stl 的常用方式stl 中全是模板的实现方式，所以使用时要特化, 指明类型. 对于一般层次的程序员来 说, 平时使用较多的是容器。容器也成为程序员的主要帮手。下面介绍一下一些容器，迭代 器，算法的特性.3.1.1 vectorvector 容器就像 c 语言中的数组, 其元素存放在连续的空间里，但它的空间是可以动态 伸缩的,即随着元素的增加而增加.这一点上又不同于普通的数组.vector 的的常用成员函数有 begin, end, size, capacity, empty, front, back, push_back , pop_back, erase, resize, clear, 这些含盖了 vector 的基本操作.vector 支持随机存取，所以 vector 支持的是 random access iterator.就像数组在程序设计中的广泛性一样，程序员在使用 stl 时，vector 容器也是程序员常 用的一种容器3.1.2 mapmap 是一种关联式容器.它是键值对的集合.map 类型通常可理解为关联数组：可使用 键作为下标来获取一个值, 正如内置数组类型一样.而关联的本质在于元素的值与某个特定 的键相关联, 而并非通过元素在数组中的位置来获取.3.map 的的特性是， 所有元素都会根据元素的键值自动被排序.map 的所有元素都是 pair, 同时拥有实值(value)和键值(key).pair 的第一元素被视为键值, 第二元素被视为实值.map 不 允许两个元素拥有相同的键值3.map 的常见操作有 key_comp, value_comp, begin, end, rbegin, rend, empty, size, max_size,swap, insert, erase, clear, find, count, lower_bound, upper_bound, equal_range.因为 map 的每个元素都是一个键值对，所以可来存放更多的信息，且效率高，所以也是程序员常用的容器之一.3.1.3 iterator, const_iterator, reverse_iterator 以及 const_reverse_iteratorstl 中的所有标准容器都提供了 4 种迭代器类型.对容器类 container而言，iterator 类型的功效相当于 t*, 而 const_iterator 则相当于 const t*.对一个 iterator 或者 const_iterator 进行递增则可以移动到容器中的下一个元素，通过这种方式可以从容器的头部一直遍历到尾部.reverse_iterator 与 const_reverse_iterator 同样分别对应于 t*和 const t*, 所不同的是， 对 这两个迭代器进行递增的效果是由容器的尾部反向遍历容器头部2图 1 反映了 4 种 iterator 之间的转换关系.箭头表示转化关系.从中可以发现不能从const_iterator 转化为 iterator, 也不能从 const_reverse_iterator 转化为 reverse_iterator.以为选迭 代器的类型时优先选择 iterator,以免类型无法相互匹配。图 1 4 种迭代器的转换关系3.1.4 find 算法find 算法是 stl 中较为常见的一种算法，它是循环查找一个区间first, last内的所有元 素, 找出第一个与待查元素相等的元素.如果找到，就返回一个 inputiterator 指向该元素, 否 则返回迭代器 last.其函数原型为:template inputiterator find(inputiterator first, inputiterator last, const t& value);3.1.5 for_each 算法for_each 的函数原型为 template function for_each(inputiterator first, inputiterator last, function f);此函数 f 会施行于first, last区间内的每一个元素身上。f 不可以改变元素内容， 因为 first和 last 都是 inputiterators，不保证接受赋值行为,3.1.6 copy 算法copy 的函数原型为template inline outputiterator copy(inputiterator first, inputiterator last, outputiterator result)copy 是一个常常被调用的函数。由于 copy 进行的是复制操作，而复制操作不外乎运用assignment operator 或 copy constructor, 但是某些元素型别拥有的是 trivial assignment operator,因些能够使用内存直接复制行为(比如 c 中的 memmove 或 memcpy)， 便能够节省大量时间3.2 stl 的应用行业stl 作为一种通用的程序组件库,几乎任何行业都能应用它来提高开发效率, stl 已广 泛应用在通信行业，网络游戏, windows 与 linux 应用程序设计中, 大大提高了开发的时间， 而且这些稳定的组件库的应用，相比自已亲手写的函数来说，在稳定性与可移植性方面要 好 很多.比如在通信及网络游戏行业中，map 可用来存放套接字和地址元素对，这样也便于查找, 在实际中的效果好.而 copy 算法常用在消息包的组合与解析之中,用起来非常方便，不和自已 重新开发。又比如在搜索行业，哈希表与红黑树就用得较好，这些容器本身实现就非常复杂，查找 效率很高。如果是自已开发这些东西的话，仅仅手工实现这数据结构就要花很多时间， 更不谈手工实现的代码的稳定性了，而且如果不稳定的话，组后期的维护也带来了麻烦。 由此可看出 stl 的重要性了较常用的容器 vector, list, stack, pair 会广泛用来各个行业之中，而常用算法find, for_each,count, reverse, sort, search 也是常用在日常程序设计之中4 一个实例本节以一个实例展示 stl 在网络编程中的应用，会用到 vector, map 容器，find， for_each算法.从中也可看出基本 stl 的使用方式.4.1 程序的应用结构程序分为服务器端, 客户端, 控制端三个部分，服务器与客户关可以互通基本消息，而 控制端则控制服务器向客户端的消息发送.对于客户端，控制台与服务器端的连接及 ip 地址， 可用 map 来保存, 对于连接的查找可用 find 来查找。结构图如图 2.clientcontrolserver图 2 程序结构图4.2 程序的基本流程, 基本代码服务器的存入链接与 ip 的变量定义为:map sockip;控制台发送一个含有客户端 ip 的消息到服务器后(此 ip 的变量为 srcip, 可使用 map 的基本操作查找此 ip 的客户端与服务器的套接字，从而可以向客户端发送消息.查找的代码为:iterator first = sockip.begin(); iterator last = sockip.end(); for(;first!=last&first-second!=srcip;first +)客户端的姓名与 ip 的变量定义为: map nameip;可通过 find 算法查找是否 nameip 中是否有些用户, 从而判断该客户是否在线,查找的代码为iterator first = nameip.begin();iterator last = nameip.end();iterator clientiterator = find(first, last, make_pair(srcname, strip);还可使用 for_each 在输出在线客户的姓名，地址信息. template struct displaymapvoid operator()(const t& x)cout x.first “” x.second endl;iterator first = nameip.begin();iterator last = nameip.end();for_each(first, last, displaymap);5 总结本文开始介绍了 stl 的三大主要部分容器，算法，迭代器基本知识和特性,接着分析了 stl 的常用容器，算法，迭代器的使用方式及范围，最后通过一个实例介始了在实际编程中 使用 stl 的方法.这样就能更加深刻地认识 stl 的基本理论及使用方法.stl 作为一个 c+ 中重要的一部分，学习 stl 也成为程序员的一门重要的课程参考文献1候捷. stl 源码剖析,华中科技大学出版社,2002.6 2潘爱民，陈铭，邹开红译.effectivie stl 中文版, 2006.4 3李师贤，蒋爱军，梅晓勇，林瑛译.c+ primer 中文版, 从民邮电出版社, 2008.7use stl in program desinggao qing，zhang nenglicompute