C++标准模板库Stand Template Library(STL)简介与STL string类
分类：数据结构-算法-编程
参考《21天学通C++》第15和16章节，在对宏和模板学习之后，开启对C++实现的标准模板类STL进行简介，同时介绍简单的string类。虽然前面对于vector、deque、list等进行过学习和总结，但并没有一个宏观上的把握，现在通过上一篇和这一篇博文，将对C++模板以及基于C++模板的STL关联起来，形成一个总体的把握，对于掌握C++中模板（template）这一强有力的工具会十分有帮助。本文的主要内容有：
（1） STL容器；
（2） STL迭代器；
（3） STL算法；
（4） STL字符串类。
简单的来说，标准模板库是一组模板类和函数，向程序员提供了用于存储信息的容器、用于访问容器存储信息的迭代器和用于操作容器内容的算法。最后结合非常常用的STL string类进行介绍。
一、STL标准模板库************************************************************************************************************************************1. STL容器
容器是用于存储数据的STL类，STL提供了两种类型的容器：顺序容器和关联容器。另外，还提供了容器适配器（Container Adapter）的类，它们是顺序容器和关联容器的变种，用于满足特殊需求。
（1） 顺序容器
按照顺序存储数据，比如数组和列表。顺序容器插入速度快但查找操作相对较慢。主要包括以下几种标准模板类实现：std::vector，操作与动态数组一样，在最后插入数据；std::deque，与vector类似，可在开头插入和删除元素；std::list，操作与双向链表一样，可视为链条，对象被连接在一起，可在任意位置插入和删除对象；std::forward_list，类似std::list，是单向链表，只能沿着一个方向遍历。
（PS：如果上面介绍的数据结构不太清楚的话，可以参考我的系列博文：数据结构（二）:线性表的使用原则以及链表的应用-稀疏矩阵的三元组表示；数据结构（二）:链表、链队列；数据结构（二）:线性表包括顺序存储结构（顺序表、顺序队列和顺序栈）和链式存储结构（链表、链队列和链栈）；）
正如上面博文中介绍的，vector和deque是顺序存储结构，而list是链式存储结构，vector和deque都是连续的内存组织，而list则可使用不连续的内存块组织，所以list不需要像vector和deque那样给内部数组重新分配内存。所以在使用中，涉及到频繁插入和删除操作的，一般使用链式存储结构的list，否则一般使用vector足矣。
（2） 关联容器
关联容器按指定的顺序存储数据，就像词典一样，这将降低插入数据的速度，但是在查询方面有很大的优势。
STL提供的关联容器包括：
std::set，存储各不相同的值，在插入时进行排序；容器的复杂度为对数。
std::unordered_set，存储各不相同的值，在插入时进行排序；容器的复杂度为常数。
std::map，存储键值对，并根据唯一的键排序；容器的复杂度为对数。
std::unordered_map，存储键值对，并根据唯一的键排序；容器的复杂度为对数。
std::multiset，与set类似，但允许存储多个值相同的项，即值不需要是唯一的。
std::unordered_multiset，与unordered_set类似，但允许存储多个值相同的项。
std::multimap，与map类似，但不要求键是唯一的。
std::unordered_multimap，与unordered_map类似，但不要求键是唯一的。
（3） 选择合适的容器
显然，可能有多种STL容器能够满足应用程序的需求，但哪一个是较好的选择呢？
下面对STL容器的特点进行梳理：
std::vector（顺序容器）的优点是在末尾插入数据时快（时间固定），可以像访问数组一样进行访问，缺点是调整大小时将影响性能，搜索时间与容器包含的元素个数成正比，只能在末尾插入数据；
std::deque（顺序容器）的优点是具备vector所有优点，还可以在容器开头插入数据，插入时间固定。缺点是：vector所有缺点，与vector不同的是根据规范，deque不需要支持reserve函数，该函数让程序元能够给vector预留内存空间，以免频繁地调整大小，从而提高性能。
std::list（顺序容器）的优点是在list开头、中间或末尾插入数据，所需时间都是固定的，将元素从list中删除所需的时间是固定的，而不管元素的位置如何，插入或删除元素后，指向list中其他元素的迭代器仍然有效，缺点是不能像数组那样能够根据索引随机访问元素，搜索速度比vector慢，因为元素没有存储在连续的内存单元中，搜索时间与容器的个数成正比。
std::forward_list（顺序容器）优点是单向链表类，只能沿一个方向遍历，缺点是只能使用push_front在链表表头插入元素。
std::set（关联容器），搜索时间不是与容器中的元素个数而是与元素个数的对数成正比，因此搜索速度通常比顺序容器要快，缺点是元素的插入速度比顺序容器慢，因为插入时要进行排序。
打掉的应是脆弱的铁屑，锻成的将是锋利的钢刀。
