C++ STL 漫谈

欢迎大家来到IT世界,在知识的湖畔探索吧!

标准模板库（Standard Template Library，STL）是惠普实验室开发的一个函数库和类库。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。

STL是一个模板类库和模板函数库。STL并不仅仅是一个库，它更是一种优秀的思想以及一套约定。

STL包含三大组件：容器、算法和迭代器。容器用于容纳和组织元素；算法针对容器执行操作；迭代器则用于访问容器中的元素。这些都不是什么新东西，许多传统的程序库也都包含类似的组件，并且许多程序库也都是采用模板实现而成。STL的优秀思想体现在：容器与在容器上执行的算法之间无需彼此了解，这种戏法是通过迭代器实现的。

模板类库包含了一些常用数据结构（在STL中叫容器），这些模板类库中通常包含了一个迭代器模板类，用于提供给通常算法来遍历容器内部元素。STL容器只包含了线性结构数据，存储单一元素的容器称为序列容器，存储关联元素（用pair模板类封装的key与value）称为关联容器。容器可以动态增长、可以是顺序存储或链式存储，为查找效率需要，也可以是以红黑树作为底层的数据存储结构或哈希存储。

模板函数库包含了一些适用容器的通用算法。

Stepanov并认为，虽然C++中的继承功能可以表示泛型设计，但终究有个限制。虽然可以在基础类型（superclass）定义算法和接口，但不可能要求所有对象皆是继承这些，而且庞大的继承体系将减低虚拟（virtual）函数的运行效率，这便违反C++所强调的“效率”原则。（C++标准库和STL都是没有所谓基类Object这一语法机制。）

事实上，C++的模板，本身即是一套复杂的宏语言（macro language），宏语言最大的特色为：所有工作在编译时期就已完成。显式的声明函数模板之实例，与直接通过C++的重载功能隐式声明，结果一样，并无很大区别，只是前者加重程序员的负担，使得程序变得累赘。

STL 将“在数据上执行的操作”与“要执行操作的数据分开”，分别以如下概念指代：

容器：数据结构的概念，包含、放置数据的地方（模板类，封装了与容器结合紧密的一些操作容器元素的函数）。

迭代器：在容器中指出一个位置、或成对使用以划定一个区域，用来限定操作所涉及到的数据范围。是数据结构与算法的中间层，是封装在容器模板类内的模板类，迭代器类封装的是外部类（容器类）元素指针，迭代器通常用做算法参数或类似指针用途。

算法：可以在绝大部分容器执行的操作（以适当类别的迭代器为参数）。

1 容器（数据结构）

STL容器是对数据结构的一种抽象，以类模板的方式实现而成。由于具有不同的数据结构，因此不同的容器以不同的方式来组织其元素，以便对存取或操纵进行优化。

标准模板库包含了序列容器（sequence containers）与关系容器（associative containers）。

序列容器包括vector,list,forward_list,deque和array等。

关联容器包括set,multiset,map,multimap,unordered_set,bitset和valarray等。

2 迭代器

迭代器类似于指针（实际上指针就是一种STL迭代器）。像指针一样，迭代器可以指向序列中的一个元素，也可以对其进行解引用(dereference) , 以便获得它所指向的对象的值。我们可以像操纵指针那样操纵迭代器，使其指向序列中不同的元素（其背后中指针操作符的重载）。STL迭代器既可以是预定义的指针，也可以是用户自定义的类类型，当然，这种类型需要重载适当的操作符，以便与预定义指针拥有相同的使用语法。

迭代器是泛化的指针，通过使用迭代器，开发者可以操作数据结构而无需关心其内部实现。根据迭代器的操作方式的不同，迭代器分为输入、输出、前向、双向、随机访问迭代器。

demo code（自定义链表和迭代器）：

#include <list> #include <iostream> #include <string> using namespace std; template <typename T> // 1 数据组成 struct singleList { singleList<T>* next; T data; singleList() // 创建表头 { this->next = NULL; } singleList(T data) // 创建节点 { this->data = data; this->next = NULL; } singleList(T data, singleList<T>* next) // 创建节点+连接节点的功能 { this->data = data; this->next = next; } }; template <typename T> class List{ public: List() // 构造函数的万金油写法 { // 构造函数作用:构造对象 // 初始化基本数据成员，描述最初状态 sizeList = 0; listHeadNode = listTailNode = NULL; // 对应STL库list的迭代器begin()和end()返回的指针 } void push_back(T data) // 基本行为：插入操作 { singleList<T>* newNode = new singleList<T>(data); if (listHeadNode == NULL) listHeadNode = newNode; else listTailNode->next = newNode; listTailNode = newNode; // 两种情况的尾节点都指向新节点 //listTailNode->next=NULL; } void push_front(T data) { singleList<T>* newNode = new singleList<T>(data); if (listHeadNode == NULL) listTailNode = newNode; else newNode->next = listHeadNode; listHeadNode = newNode; // 两种情况的头节点都指向新节点 } //测试行为：遍历结构（打印输出） void printList() { singleList<T>* pMove = listHeadNode; while (pMove) { cout << pMove->data << " "; pMove = pMove->next; } cout << endl; } singleList<T>* begin() { return listHeadNode; } singleList<T>* end() { return listTailNode->next; // 表示链表最后那个位置，NULL的位置 } //万金油行为 int size() const { return sizeList; } bool empty() const { return sizeList == 0; } public: class iterator // 迭代器是一个类中类，用类的对象来模仿指针，需包含一个对象指针和重载操作符 { public: // 实现begin对iterator对象的初始化 void operator=(singleList<T>* pMove) { // 实质初始化对象中的属性，而不是对象的例子 this->pMove = pMove; } singleList<T>* getData() { return pMove; } bool operator!=(singleList<T>* pMove) { return this->pMove != pMove; } // ++实质是链表的一个移动指针走到一下一个节点 iterator& operator++() // 前置++重载 { this->pMove = this->pMove->next; // 链式存储指针的移动 return (*this); } T operator*() { return this->pMove->data; } protected: singleList<T>* pMove; }; protected: // 抽象数据成员 // 遵循的原则：抽象出来的属性能够便于描述行为(成员函数) singleList<T>* listHeadNode; singleList<T>* listTailNode; //万金油属性 int sizeList; }; int main() { cout<<"STL中list的使用："<<endl; list<string> mylist; mylist.push_back("I"); mylist.push_back("Love"); mylist.push_back("you"); list<string>::iterator listIter; for (listIter = mylist.begin(); listIter != mylist.end(); ++listIter) { cout << *listIter << " "; } cout << endl; cout<<"自定义list的使用："<<endl; List<string> myList; myList.push_back("I"); myList.push_back("Love"); myList.push_back("you"); //myList.printList(); List<string>::iterator myIter; //myIter=myList.begin(); //cout<<myIter.getData()->data<<endl; for (myIter = myList.begin(); myIter != myList.end(); ++myIter) { cout << *myIter << " "; } cout << endl; cin.get(); return 0; } /* 输出 STL中list的使用： I Love you 自定义list的使用： I Love you */

欢迎大家来到IT世界,在知识的湖畔探索吧!

3 算法

STL提供了一些常见的算法，如排序和搜索等。这些算法与数据结构的实现进行了分离。因此，也可对自定义的数据结构使用这些算法，只需让这些自定义的数据结构拥有算法所预期的迭代器。

STL算法是对函数的一种抽象，采用函数模板实现。大多数STL算法用于处理一个或多个序列的值，其中每一个序列由一对有序的迭代器定义。其中第一个迭代器指向序列的第一个元素，第二个迭代器则指向序列最后一个元素之后的那个位置（而不是最后一个元素）。如果两个迭代器指向同一个位置，那么它们就定义了一个空白序列。

迭代器提供了一种使容器与算法协同工作的机制。一个容器可以生成一对迭代器来指定一个元素序列（可以是全部元素，也可以只是一个子区间），而算法则对该序列进行操作。采用这种方式，容器和算法可以紧密地协作，同时还可以保持彼此不知情。

4 函数对象和适配器

除了容器、算法和迭代器之外，STL还定义了大量的辅助性功能。算法和容器可以采用函数指针和函数对象根据需要进行定制，而这些函数对象又可以通过形形色色的函数对象适配器(function object adapter)进行配接和联合。容器也可以利用容器适配器(container adapter)进行配接，从而将容器的接口修改为栈、队列或优先队列。

4.1 函数对象

狭义的函数对象即重载了操作符()的类的实例，而广义来讲所有可用 x(…) 形式调用的 x 都可称为函数对象、或曰可调用对象。

4.2 适配器

适配器（Adaptor）为一个模板类，用于提供接口映射。

5 约定(convention)

STL对约定(convention)有着很强的依赖。容器和函数对象必须通过一套标准的嵌套类型名字对其自身进行描述。容器和函数对象适配器均要求成员函数具有特定的名字并包含特定的类型信息。算法要求传递给它的迭代器支持特定的操作并能够识别是什么样的操作。当使用或扩展STL时，如果弃约定于不顾，那么同时也就放弃了美梦成真的希望。遵守约定，将拥有简单而轻松的生活。

STL约定并未指明具体的实现细节，但对实现指定了效率方面的约束。此外，由于STL是一个模板库，许多优化和性能调整可以在编译期进行。前面提到的命名和信息约定会对编译期优化起到重要的作用。一般而言，STL的效率可以与专家手写代码的效率相雄美，而明显比普通程序员和程序员小组的手写代码胜出一筹。另外，使用STL可以使代码变得更清晰，更易于维护。

6 萃取器（traits）

有时仅仅知道对象的类型是不够的，通常来说，某些与对象类型有关的信息对于处理对象来说不可或缺。

traits类是一个关于某个类型的信息的集合。然而，与嵌套的容器信息不同的是，traits类独立于它所描述的类型。

有关traits类的一个常见的应用，是在泛型算法和不遵从算法期望的约定的类型之间，放入一个遵从约定的中间层。根据类型的traits编写算法。在一般情况下通常假设存在某种约定。

－End－