STL简介
STL是惠普实验室开发的一系列标准化组件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。在1994年被纳入C++标准,使之成为了C++库的重要组成部分。STL现在是C++的一部分,被内置于C++编译器中,所以学习STL不需要额外安装什么。
STL的内容从广义上讲分为三个主要部分:容器(container)、迭代器(iterator)和算法
(algorithm)。STL的一个基本理念就是将数据和操作分离,数据由容器类别加以管理,操作则由可定制的算法定义,迭代器在两者之间充当粘合剂。STL的结构可以用一张图来诠释,如图1所示。
图1 STL结构图
由图1可知, STL中的所有组件都由模板构成,其元素可以是任意类型,程序员通过选用恰当的群集类别,调用其成员函数和算法数据就万事大吉了。
在C++的标准中,STL被组织在13个头文件中:<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>、<utility>,使用不同的内容,需要包含不同的头文件。接下来我们就容器、迭代器、算法这三个组件做简要介绍。
1、容器
容器类在面向对象的语言中特别重要,几乎所有的面向对象语言中都伴随着一个容器集,在C++中,这个容器集就是标准模板库(STL)。
在C++中,容器被定义为:在数据存储上,有一种对象类型,它可以装入其它对象或指向其他对象的指针,这种对象类型就叫作容器。简单说,容器就是保存其它对象的对象。
当然,这是一种朴素的理解。这种“对象”还包含一系列处理“其它对象”的方法,因为这些方法在程序设计上经常被用到,所以容器也体现了一个好处,就是“容器类是一种对特定代码重用问题的良好的解决方案”。
容器的另一个特点是,容器可以自行扩展,在解决问题时我们常常不知道需要存储多少个对象,也就是说我们不知道应该创建多大的内存空间来保存我们的对象,显然,数组在这一方面也力不从心。容器的优势就在这里,它不需要预先知道要存储多少个对象,只要创建一个容器,所有的处理将由容器自身完成。它可以自行申请或释放内存,并且用最优的算法来执行命令。
STL主要包含的容器有以下几种:
● vector<T>,是一种向量;
● list<T>,是一个双向链表容器,完成标准C++数据结构中链表的所有功能;
● queue<T>,是一种队列容器,完成了标准C++数据结构中队列的所有功能;
● stack<T>,是一种栈容器,完成了标准C++数据结构中栈的所有功能;
● deque<T>,是双端队列容器,完成了标准C++数据结构中栈的所有功能;
● priority<T>,是一种按值排序的队列容器;
● set<T>,是一种集合容器;
● multiset<T>,是一种允许出现重复元素的集合容器;
● map<key, value>,是一种关联数组容器;
● multimap<key, value>,是一种允许出现重复key值的关联数组容器。
上面的容器可分为两大类:序列式容器和关联式容器。序列式容器主要有vector、list和deque;关联式容器包括set、map、multiset和multimap等容器类模板。
2、迭代器
迭代器是STL中最基本的一部分内容,它将容器与算法联系起来,起着粘合剂的作用,几乎STL提供的所有算法都是通过迭代器存取元素来实现的。它有些类似于指针,当参数化类型是C++内部类型时,迭代器就是指针。
STL定义了5种类型的迭代器:输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器,每种容器都支持某一种类型的迭代器。
● 输入迭代器(Input iterators):用于为程序中需要的数据源提供输入接口,数据源一般指容器、数据流等。输入迭代器只能从一个序列中读取数值,输入迭代器可以被修改、被引用。
● 输出迭代器(Output iterators):用于输出程序中已经得到的数据结果(容器、数据流)。输出迭代器只能向一个序列中写入数据,输出迭代器可以被修改、被引用。
● 前向迭代器(Forward iterators):前向迭代器只能向前移动,它不仅具有输入和输出迭代器都具有的功能,还可以多次解析一个迭代器指定的位置,因此可以对一个值进行多次读写。
● 双向迭代器(Bidirectional iterators):既可以用来读又可以用来写,它与前向迭代器相类似。双向迭代器可以同时进行前向和后向元素操作。所有的STL容器都提供了双向迭代器功能,既有利于数据的写入和读出,还有利于提供更加灵活的数据操作。
● 随机访问迭代器(Random access iterators):它可以通过跳跃的方式访问容器中的任意数据类型,随机访问迭代器具有双向迭代器的所有功能,是功能最强大的迭代器。
迭代器的诞生使算法和容器分离成为可能,STL库通过迭代器给用户提供访问接口,可以隐藏内部实现细节,满足了封装性的设计要求。使访问容器元素变的简单、易用,使代码更加紧凑、简洁。
3、算法
STL提供了大约70个实现算法的模板函数,比如算法for_each()将为指定序列中的每一个元素调用指定函数,stable_sort()对所指定的容器元素进行稳定性排序。这样一来,只要熟悉了STL后,许多代码可以被简化,只需要通过调用一两个算法模板,就可以完成所需要的功能并大大提升效率。
对于初学者来说,学习STL确实有一定的难度,需要一定的时间,但只要适应了STL处理问题的方式,那么在以后的开发中,往往会事半功倍。