终于他喵的写到STL了淦, 前置的乱七八糟的东西太多了, 没错我说的就是你, 友元!
我打算先从STL的用法开始, 学习到STL的底层, STL系列也会写的更为详细, 因为他真的, 很重要

前言

STL(Standard Template Library) 源自于C艹第一个标准化版本C艹98(不是CC98哦), 它提供了强大的容器库(Containers library) 和算法库(Algorithm library) 以供使用者直接调用, 其背后体现了泛型编程(Generic programming) 的思想; 即使你像我一样对上面的一堆名词不甚了解, 也可以很好的利用它所提供的常见的数据结构和算法解决很多问题.

参考资料

 

为什么要STL

在我数据结构杂谈（一）这篇文章中, 我曾经提到, ADT的出现, 是为了处理更加普遍的情况, 而算法正是基于ADT实现的. 在这里, 我想用更加学术的语言重制这句话.

解释数据结构与算法, 就要从数据这个概念本身开始, 在那一片文章中, 我曾经将胡图图一家人看作是一个数据结构, 把胡图图, 张小丽等人看作是数据, 如果我们再深挖下去, 思考一个人是否还有其他从属于他自己的属性. 答案显然是肯定的. 胡图图是张小丽的儿子, 这个关系就可以视作一个元素, 同样, 胡图图的生理数据, 比如他的三根头发, 也是一个元素. 因此我们可以说:

  • 数据几乎总是 元素 的 集合 | Data is almost always collections of elements.

  • 每种集合有一定的 表现形式 | Each collection of elements has some representation.

而针对特定表现形式的数据结构, 也就是集合的表现形式的特定操作, 就是算法:

  • 有很多处理方法(算法) | There are many kinds of progressing(algorithms)

然而在我们的宇宙中, 即便是一个问题空间中, 数据结构的数量总是一个非常巨大的数字N, 假如数据结构两两之间需要进行数据交换, 我们就要设计C(N,2)种算法, 这个数字不是我们能轻易接受的.

为了解决以上问题, C艹引入了泛型编程的概念, 可以通俗的理解为模板, 来解决程序段复用性的问题, 而STL正是其中一个最具典型性的代表–C标准委员会提供了一组库, 以供使用者复用这个库里面的代码.

STL库最初的设计准则, 即是:

  • 综合性 Comprehensive
  • 可扩展性 Extensible
  • 高效性 Efficient
  • 自然性 Natural

正是由于对上述准则的坚持, C艹STL库才能至今仍在跟进维护 , 不像某个友元的概念

 

容器、算法与迭代器

在STL里面, 我们用容器container来描述一个数据结构, 或者说是元素集合的储存, 容器为下列操作提供支持：

  • 增删元素
  • 通过相关的迭代器读取或更新某个元素
  • 容器的迭代器脱离于容器的内部结构而存在，但是能完成对容器的特定操作并支持算法的实现

算法algorithm对应的就是普遍意义上的算法, 是对容器的操作, 但是算法并不能直接操作容器, 而是通过定义清晰的迭代器

迭代器iterator为容器与算法的交流提供一个共同单位, 确保有一个提供清晰的方法得到元素

 

容器

STL为我们提供了丰富的容器库Container library，其中主要包含了三大类，十数种容器模板：

  • 序列容器Sequence container
    序列容器是抽象于数据按某一个顺序排列的数据结构的容器：

    • 向量vector：虽然单词原意是向量，但是人们更愿意称之为可变数组 ，这是因为相比于数组，vector可以通过成员函数动态的改变自己的长度
    • 双向队列deque：一个可以在两端进行增删操作的队列，假如对其两端的操作权限作出限制，可以特化为队列或栈，因此deque相比队列或是栈，更加的灵活，但是一定程度上，也更加臃肿
    • 数组array：固定长度的数组
    • 双向链表list：相当于迭代器没有随机访问能力的deque
    • 单向链表forward_list：单向的链表

  • 关联容器Associative container
    关联容器是抽象于数据没有一个固定排列，而是通过相互之间的关系组织在一起的数据结构的容器，在C艹（以及大多数其他高级语言中）中是用红黑树（一种高效的BST）实现的：

    • 集合set：储存的是无重复、无顺序的数据集合，与数学上集合的概念相仿，但不能储存无穷多的元素（显然）
    • 映射map：在有些高级语言中，map也被叫做dictionary，map的储存单位是一一对应的键值对，其中键是无序、无重的
    • 可重集合multiset
    • 可重映射multimap：上述容器的可重版本，允许元素的重复

  • 无序关联容器Unordered associative container
    无序关联容器是上述关联容器的无序版，其底层使用hash表而不是红黑树实现：

    • unordered_set
    • unordered_map
    • unordered_multiset
    • unordered_multimap

  • 适配器Adaptor
    适配器不是严格意义上的容器，而是对既有容器（包括STL容器和使用者自定义的容器）接口的封装：

    • 栈stack
    • 队列queue
    • 优先队列priority_queue

扩展阅读：
C艹STL库官方文档 ｜ 容器

 

算法

C++同样为我们提供了丰富的算法库Algorithm library，如同前面所说，算法是脱离于容器存在的，但是实现确是通过迭代器操作容器，因此在对算法做介绍之前，我们需要简单讲一下如何获取某个容器的迭代器。

auto i = v.begin();
auto j = v.end();

这两个函数分别可以获取指向容器v开头或结尾的迭代器（是的，你可以将迭代器粗浅的理解为指针，一个有自己重载后的++运算符的特殊指针）

在上面的例子中，使用了一个全新的变量类型声明关键字auto，这代表了使用者并不关心i、j的具体变量类型，而是交由编译器自行推导（类似于模板函数参数表的推导）

 

不修改序列的操作

find()

auto res = find(start, stop, target);

其中res、start、stop的数据类型均为迭代器，target的数据类型为v的元素的数据类型；

函数的作用是在v（通常是array或vector）中左闭右开区间[start,stop)上寻找值等于target的元素，并返回其迭代器，找不到则返回stop

count()

int cnt = count(start, stop, target);

count_if()

int cnt = count_if(start, stop, p);

其中p是一个谓词 ，可以是函数、函数指针、函数对象（即对()进行重载）或lambda函数。

这个函数会返回区间上满足谓词p的元素的数量

for_each()

for_each(start, stop, func);

类似于其他高级语言中的map()函数，即对区间上所有的元素调用函数func

 

修改序列的操作

reverse()

reverse(start, stop);

fill()

fill(start, stop, value);

 

排序操作

sort

sort(strat, end);       //重载<运算符后
sort(start, end, cmp);  //用cmp()函数或对象作为比较依据

stable_sort

stable_sort(strat, end);        //重载<运算符后
stable_sort(start, end, cmp);   //用cmp()函数或对象作为比较依据

与sort()不同的是, stable_sort()是稳定的排序

partial_sort

partial_sort(start, middle, end);       //重载<运算符后
partial_sort(start, middle, end, cmp);  //用cmp()函数或对象作为比较依据

重新排序, (默认)把最小的一部分元素按升序置于区间[start,middle)中

 

二分查找操作(对于有序序列)

binary_search

bool res = binary_search(start, stop, target, cmp);

lower_bound

auto lower = lower_bound(start, stop, target, cmp);

(默认)返回区间内大于target的第一个元素的迭代器

upper_bound

auto upper = upper_bound(start, stop, target, cmp);

(默认)返回区间内不小于target的第一个元素的迭代器

 

其他操作

集合操作(对于有序序列)

includes(start1, stop1, strat2, stop2, cmp);    //返回序列1是否包含了序列2
set_difference(start1, stop1, strat2, stop2, res, cmp); //求序列1和序列2的差集, 结果储存在迭代器res里
set_intersection(start1, stop1, strat2, stop2, res, cmp);   //求序列1和序列2的交集, 结果储存在迭代器res里
set_symmetric_difference(start1, stop1, strat2, stop2, res, cmp);   //求序列1和序列2的并集与交集的差集, 结果储存在迭代器res里
set_union(start1, stop1, strat2, stop2, res, cmp);   //求序列1和序列2的并集, 结果储存在迭代器res里

大小比较操作

auto maxn = max(a, b, cmp);
auto maxn = max({a, b, c, d});
auto maxn = max_element(start, stop, cmp);  //返回第一个最大值的迭代器

堆操作

make_heap(start, stop, cmp);
pop_heap(v.begin(), v.end(), cmp);  auto top = v.back();
v.push_back(value); push_heap(v.begin(), v.end());

比较操作

bool res = equal(start1, stop1, start2);    //判断两个对象是否相等
bool res = lexicographical_compare(start1, stop1, start2, stop2);    //按照字典序判断对象1是否大于对象2

 

cmp函数参数

上文中所有带cmp参数的函数, 都可以省略之, 编译器会自动用<或重载后的<来替代之.

在函数实现时:

  • x > y等价于!(x < y)或!cmp(x,y)
  • x != y等价于!(x < y) && !(y < x)或!cmp(x,y) && !cmp(y,x)

因此, 当你想按照降序排列某个序列时, 请使用

bool cmp(int x, int y){
    return !(x<y);
}
int main(){
    int _array[] = {1,4,6,2,4,5};
    vector<int> array(_array, _array+6);
    for(auto i=array.begin();i<array.end();++i){
        cout<<*i<<' ';
    }
    cout<<endl;
    sort(array.begin(), array.end(), cmp);
    for(auto i=array.begin();i<array.end();++i){
        cout<<*i<<' ';
    }
    cout<<endl;
}
/*
输出结果:
1 4 6 2 4 5 
6 5 4 4 2 1 
*/

扩展阅读：

C艹STL库官方文档 ｜ 算法