小白的面试题之路——STL库

一、基本排序方法介绍

首先，我们需要了解基本的排序以及时间复杂度：比如冒泡排序（On^2)，选择排序（On^2）,插入排序（On^2）,希尔排序（nlogn），归并排序（nlogn），快速排序（nlogn），堆排序（nlogn），桶排序（n+k）。以冒泡排序举例，随便排一个100000的数组就超时了，因此我们要尽量避免使用冒泡排序，优先考虑快速排序。

二、Sort的基本用法

sort函数是STL自带的系统函数，它的格式是：sort（要排序元素的起始位置，要排序元素的结束位置，比较函数），通常可以省略比较函数，默认是从小到大排序的（升序排序）。

三、Map

Map是STL提供的关联容器，它是一对一hash。第一个为关键字（key），每个关键字只能在Map中出现一次，第二个是关键字的值（value）。

map<类型， 类型>m; //如何定义map

//举个例子

int main(){
    map<string, int>Scorelist;
    Scorelist["小明"] = 95;
    Scorelist["小红"] = 100;
    std::cout<<"小明的成绩："<<Scorelist["小明"]<<endl;
return 0 ;
}

输出：

小明的成绩：95

四、Stack（栈）

4.1栈的介绍：栈就像一个箱子，可以放入和取出元素，先放入的元素会放在箱子的底部，后放入的元素离箱子的顶部近，所以先放进的元素后出，后放入的元素先出，即先进后出、后进先出。

4.2栈的定义

stack<类型（可以不写）>st1;
stack st2;

 4.3栈的成员函数：

1. .empty（）——判断栈是否为空，为空返回true。
2. .pop（）——移除栈顶元素。
3. .push（）——在栈顶增加元素。
4. .size（）——输出栈中元素的个数。
5. .top（）——返回栈顶元素。

五、STL介绍

5.1前面我们介绍了一些排序方法和数据结构，下面我们介绍一下STL(Standard Template Library)标准模板库，是一个基于泛型编程思想（模板）的程序库，内嵌于C++编译器中。它提供了几乎所有常见的数据结构类型及其算法，是对基础数据结构的补充与强化。它有两个特征： 

1. 数据结构与算法的分离。基于泛型编程思想，STL中算法并不依赖于数据结构进行实现。换句话说，STL中的一个算法可以操作几种不同的容器数据。例如，sort()可作用于动态数组、栈和队列，甚至是链表。实际上，这主要是通过迭代器实现的。
2. STL并非面向对象(OOP)。STL中的数据结构与算法皆不具有明显的继承关系，各部分之间相互独立。“采用非面向对象的方法在逻辑上降低了各部分之间的耦合关系，以提升各自的独立性、弹性、交互操作性”。这符合泛型编程设计原理。不过，STL也采纳了一些封装的思想，令使用者不必知晓其底层实现也能应用自如。

5.2 STL组件：要设计一个复杂的项目，不是简单一个.cpp就能完成的，因此STL在整体上遵循将一个框架拆分成各个组件从而分别进行设计，再将这些组件按照一定规则组合起来，STL由6个组件组成：容器、算法、迭代器、仿函数、容器适配器、空间适配器。

• 容器：各种数据结构，如vector、list、deque、set、map。以模板类的方式提供。
• 算法：对容器中的数据执行操作的模板函数，如sort()、find()。在 std 命名空间中定义。
• 迭代器：一种访问容器的方法，可理解为指针。算法对容器的操作要借助迭代器才能实现。
• 仿函数：一种类，可以像使用函数一样使用它，可理解为更高级的运算符重载。
• 容器适配器：一种接口类，封装了一些基本容器，如stack、queue等。
• 空间适配器：自动配置与管理内存空间。使用STL时无需手动管理内存。

六、STL三大组件之一——容器 

6.1容器介绍：要操作任何数据，我们需要先将数据储存起来，容器相当于一个收纳柜，但每个不同的容器有对应的规则将数据串联起来，就形成了数据结构，而且容器里还存放了成员函数。根据组织方式的不同，容器分为序列容器、排序容器、哈希容器，其中后两个容器成为关联容器。

1. 序列容器：主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。元素在容器中的位置同元素的值无关，即容器不是排序的。类似数组，序列容器随机存储性能较好。
2. 排序容器：包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素是排序好的（按键排序）。类似函数映射，排序容器查找性能较好。
3. 哈希容器：C++11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。哈希容器中的元素是未排序的，元素的位置由哈希函数决定。哈希容器查找性能比排序容器更好，而遍历效果较差。

6.2序列式容器

1. array<T, N>（数组容器）：可存储N个元素的高级数组，容器一旦建立，长度则固定不变。
2. vector<T>（向量容器）：一个长度可变的序列容器，也是我在工作中最常使用的数据结构，它在尾部增加和删除的效率最高，为O（1），在其他位置插入或删除的效率一般为O（N）。
3. deque<T>(双端队列容器)：其使用方法和vector非常相似，只不过头部和尾部效率都是O(1).
4. list<T>（链表容器）:一个长度可变的序列容器，底层为双向链表。在这个序列的任何地方都可以高效地增加或删除元素O(1)，但随机访问的效率一般O(n). 
5. forward_list<T> (正向链表容器)：和 list 容器非常类似，但底层为单链表，只能正向进行访问。它比链表容器快、更节省内存。

6.3排序式容器

1. pair<T, T> (键值对类模板)：一个类模板，用以创建键值对。
2. map<T, T> (映射容器)：其中存储pair对象，存储时会自动根据键的大小进行排序 (内部排序，对使用者是不可见的，除非用迭代器遍历)。容器中的键都是唯一不重复的，且不能被修改。 
3.  multimap<T, T> (多重映射容器)：与map容器非常相似，区别在于multimap容器可以同时存储多个键相同的键值对。
4. set<T> (集合容器) ：类似于map，set容器也存储pair对象，但要求键值对的 键 与 值 必须相等，故只需一个参数T。
5. multiset<T> (多重集合容器)：与set容器非常相似，区别在于multiset容器可以同时存储多个键相同的键值对。

6.4哈希容器 ： 哈希容器与排序式容器类似，但其底层依靠哈希表实现；它不会对键值对进行排序，元素的位置由哈希函数决定，常见的哈希容器有unordered_map<T, T>(哈希映射)。

七、STL三大组件之二——迭代器

7.1迭代器概述： 虽然我们学习了许多不同的容器，但是本质上它们都是用来存储大量数据的，都是一串存储大量数据的存储单元，因此对数据的操作如排序、插入、查找等操作从逻辑上都是类似的，既然类似那我们就可以用到泛型技术，将它们设计成适用所有容器的通用算法，而算法的具体化交给迭代器完成，这将大大降低我们的使用难度。我们可以将迭代器看作一个适用于所有容器的强大指针。

 STL标准库为每一种标准容器定义了一种迭代器类型，常见的有：前向迭代器、双向迭代器、随机访问迭代器、输入迭代器、输出迭代器。要注意的是，这五种迭代器都用同一语法定义：

容器类型::iterator it

而 it 具体是哪种迭代器，是由容器类型决定的；不同容器的对应的迭代器类型如下：

• vector、array、deque——随机访问迭代器
•  list、set/multiset、map / multimap——双向迭代器
• forward_list、unordered_map / unordered_multimap、unordered_set / unordered_multiset——前向迭代器
• stack和queue不支持迭代器

详细文档迭代器是什么，C++ STL迭代器（iterator）用法详解 

7.2五种迭代器：

• 前向迭代器（ ForwardIterator）：支持 ++、* 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
• 双向迭代器（BidirectionalIterator）：在前向迭代器的基础上，添加了 -- 操作。
• 随机访问迭代器（RandomAccessIterator）：具有双向迭代器的全部功能，与指针极其相似。RandomAccessIterator 还支持 <、>、<=、>= 比较运算符。表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差。
• 输入迭代器：将输入流作为操作对象，了解即可
• 输出迭代器：将输出流作为操作对象，了解即可

7.3迭代器的使用方法：一般来说，算法常用 first、last 迭代器作为参数。另外，你常见到的 a.begin()、a.end()、a.begin() + 1，它们都是迭代器。 

用迭代器遍历容器：

//用iterator遍历容器
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
vector<int>::iterator it;

for (it = v.begin(); it != v.end(); ++it)
    std::cout<<*it<<endl;

这里的 v.begin() 以及 v.end() 是 vector<int> 类型的迭代器，故可以相比较；反向迭代器的语法特殊，详见：STL反向迭代器适配器详解

八、STL三大组件之三——算法

STL中的算法提供了一些对容器的常用的操作方法，这些算法被内嵌到C++编译器中，1其体积小、速度快，且空间和时间开销都基本优化到了极限。若你熟悉STL算法，你会发现LeetCode上乱七糟八的题，只需要几行代码就可以搞定！正如开头先介绍的排序算法就是常见的算法之一，STL中的算法提供了一些对容器的操作方法，下面我再来介绍一个我们经常会用到的算法。

查找算法

九、总结

容器即存放数据的地方，分为两类，序列式容器和关联式容器；算法有排序，复制等，以及各个容器特定的算法；迭代器是STL的精髓，迭代器提供了一种方法，使得它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构，它将容器和算法分开，让二者独立设计。

致谢

最后感谢您的阅读