STL介绍
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合，它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. 该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。提供了一个可扩展的应用框架，高度体现了软件的可复用性。从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。
从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。
C++ STL 提供给程序员以下三类数据结构的实现：
标准容器类
顺序性容器
vector 从后面快速的插入与删除，直接访问任何元素
deque 从前面或后面快速的插入与删除，直接访问任何元素
list 双链表，从任何地方快速插入与删除
三者比较：
vector 是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list好的查询性能，有被vector好的插入、删除性能。 如果你需要随即存取又关心两端数据的插入和删除，那么deque是最佳之选。
关联容器
set 快速查找，不允许重复值
multiset 快速查找，允许重复值
map 一对多映射，基于关键字快速查找，不允许重复值
multimap 一对多映射，基于关键字快速查找，允许重复值
关联容器(Associative Container)提供了快速检索基于关键词(Key)的数据的能力。和序列容器(vector、list、deque)一样，关联容器用来存储数据，而且设计关联容器时考虑到了优化数据检索的意图 --- 通过关键词(Key)作为标识把单一的数据记录组织到特定的结构中(如tree)。STL 提供了不同的关联容器：集合(set)、多元集合(multiset)、映射(map)、多元映射(multimap)。set 和map 支持唯一关键词(unique key)，就是对每个KEY，最多只保存一个元素(数据
记录)。multiset 和multimap 则支持相同关键词(equal key)，这样可有很多个元素可以用同一个KEY 进行存储。set(multiset)和map(multimap)之间的区别在于set(multiset)中的存储数据内含了KEY 表达式；而map(multimap)则将Key 表达式和对应的数据分开存放。
容器适配器
stack 后进先出
queue 先进先出
priority_queue 最高优先级元素总是第一个出列
STL 中包含三种适配器：栈stack 、队列queue 和优先级priority_queue 。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。
STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。
栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back 、pop_back 和back 操作。
队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front 操作，因此其不能建立在vector 容器上。
posted on 2012-06-04 08:52
王海光 阅读(881)
评论(0) 编辑 收藏 引用 所属分类:
STL