忧郁的大能猫

好奇的探索者，理性的思考者，踏实的行动者。

Table of Contents:

STL 是一些常用数据结构和算法的模板的集合

STL容器

容器，就是能够“容纳”“存放”元素的一些数据结构。

容器的通用特性

你必须要知道所有容器都具有的一个基本特性：它保存元素采用的是“值”（value）语义，也就是说，容器里存储的是元素的拷贝、副本，而不是引用。

容器（container）中可以存放基本类型的变量，也可以存放对象。对象或基本类型的变量被插入容器中时，实际插入的是对象或变量的一个复制品
但是不能放引用，因为：
The component type of containers like vectors must be assignable. References are not assignable (you can only initialize them once when they are declared, and you cannot make them reference something else later).
Other non-assignable types are also not allowed as components of containers, e.g. vector<const int> is not allowed.

从这个基本特性可以得出一个推论，容器操作元素的很大一块成本就是值的拷贝。
解决办法：
1. 一个解决办法是，尽量为元素实现移动构造和移动赋值函数，在加入容器的时候使用
std::move() 来“转移”，减少元素复制的成本：

Point p; // 一个拷贝成本很高的对象
v.push_back(p); // 存储对象，拷贝构造，成本很高
v.push_back(std::move(p)); // 定义转移构造后就可以转移存储，降低成本

2. 使用emplace 操作函数，它可以“就地”构造元素，免去了构造后再拷贝、转移的成本，不但高效，而且用起来也很方便

3. 当然，你可能还会想到在容器里存放元素的指针，来间接保存元素，但我不建议采用这种方案。
虽然指针的开销很低，但因为它是“间接”持有，就不能利用容器自动销毁元素的特性了，你必须要自己手动管理元素的生命周期，麻烦而且非常容易出错，有内存泄漏的隐患。如果真的有这种需求，可以考虑使用智能指针 unique_ptr/shared_ptr，让它们帮你自动管理元素。
一般情况下，shared_ptr 是一个更好的选择，它的共享语义与容器的值语义基本一致。使用 unique_ptr 就要当心，它不能被拷贝，只能被转移，用起来就比较“微妙”。

容器分类
常见的一种分类是依据元素的访问方式，分成顺序容器、有序容器和无序容器三大类别。
除了以上容器外，STL 还在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：
栈 stack、队列 queue、优先级队列 priority_queue。
容器适配器 stack、queue 和 priority_queue 没有迭代器。

顺序容器

它们之所以被称为顺序容器，是因为将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。

连续存储的数组：
* array
array 是静态数组，大小在初始化的时候就固定
* vector
* deque
它可以在两端高效地插入删除元素
指针结构的链表：
* list
list 是双向链表，可以向前或者向后遍历，但查找效率比较低
* forward_list
forward_list，顾名思义，是单向链表，只能向前遍历，查找效率就更低了。

链表结构比起数组结构还有一个缺点，就是存储成本略高，因为必须要为每个元素附加一个或者两个的指针，指向链表的前后节点。
当 vector 的容量到达上限的时候（capacity），它会再分配一块两倍大小的新内存，然后把旧元素拷贝或者移动过去。这个操作的成本是非常大的，所以，你在使用 vector 的时候最好能够“预估”容量，使用 reserve 提前分配足够的空间，减少动态扩容的拷贝代价。
vector 的做法太“激进”，而 deque、list 的的扩容策略就“保守”多了，只会按照固定的“步长”（例如 N 个字节、一个节点）去增加容量。但在短时间内插入大量数据的时候就会频繁分配内存，效果反而不如 vector 一次分配来得好。

有序关联容器

顺序容器的特点是，元素的次序是由它插入的次序而决定的，访问元素也就按照最初插入的顺序。而有序容器则不同，它的元素在插入容器后就被按照某种规则自动排序，所以是“有序”的。
C++ 的有序容器使用的是树结构，通常是红黑树——有着最好查找性能的二叉树。
* set/multiset
* map/multimap
在定义容器的时候必须要指定 key 的比较函数,解决这个问题有两种办法: 一个是重载<，另一个是自定义模板参数。

无序关联容器

内部是散列表
unordered_set/unordered_multiset、unordered_map/unordered_multimap。

无序容器对 key的要求：
一是可以计算 hash值，二是能够执行相等比较操作。
第一个是因为散列表的要求，只有计算 hash 值才能放入散列表，
第二个则是因为 hash 值可能会冲突，所以当 hash 值相同时，就要比较真正的 key 值。

如果只想要单纯的集合、字典，没有排序需求，就应该用无序容器，没有比较排序的成本，它的速度就会非常快。 

使用这些容器的小技巧，就是多利用类型别名，而不要“写死”容器定义。因为容器的大部分接口是相同的，所以只要变动别名定义，就能够随意改换不同的容器，对于开发、测试都非常方便。

STL 中的许多算法（即函数模板），如排序、查找等算法，在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用运算符进行，比较大小通常用<运算符进行，因此，被放入容器的对象所属的类最好重载等于和小于运算符，以使得两个对象用进行比较是有定义的。

STL迭代器iterator

算法操作容器，但实际上它看到的并不是容器，而是指向起始位置和结束位置的迭代器，算法只能通过迭代器去“间接”访问容器以及元素，算法的能力是由迭代器决定的。

这种间接的方式有什么好处呢？
这就是泛型编程的理念，与面向对象正好相反，分离了数据和操作。算法可以不关心容器的内部结构，以一致的方式去操作元素，适用范围更广，用起来也更灵活。

可以把迭代器简单地理解为另一种形式的智能指针，只是它强调的是对数据的访问，而不是生命周期管理。

要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以
1.读写它指向的元素,
2.通过递减或递增来改变指向。
从这一点上看，迭代器和指针类似。
iterator const_iterator  reverse_iterator const_reverse_iterator  move_iterator

迭代器的功能分类

1. 正向迭代器(不支持大于小于比较)
2. 双向迭代器(不支持大于小于比较)
3. 随机访问迭代器(可以比较，可以随机访问)

迭代器的辅助函数

• advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
• distance(p, q)：计算两个迭代器之间的距离，如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
• iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

底层实现

#include <iostream>

template <typename T>
class ArrayIterator {
public:
    ArrayIterator(T* ptr) : current(ptr) {}

    T& operator*() {
        return *current;
    }

    ArrayIterator& operator++() {
        ++current;
        return *this;
    }

    bool operator!=(const ArrayIterator& other) const {
        return current != other.current;
    }

private:
    T* current;
};

template <typename T>
class Array {
public:
    Array(T* data, size_t size) : data(data), size(size) {}

    ArrayIterator<T> begin() {
        return ArrayIterator<T>(data);
    }

    ArrayIterator<T> end() {
        return ArrayIterator<T>(data + size);
    }

private:
    T* data;
    size_t size;
};

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    Array<int> myArray(arr, 5);

    for (int value : myArray) {
        std::cout << value << " ";
    }

    return 0;
}

STL算法

虽然算法是 STL（标准库前身）的三大要件之一（容器、算法、迭代器），也是 C++ 标准库里一个非常重要的部分，但它却没有像容器那样被大众广泛接受。

在 C++ 里，算法的地位非常高，甚至有一个专门的“算法库”。早期，它是泛型编程的示范和应用，而在 C++ 引入 lambda 表达式后，它又成了函数式编程的具体实践，所以，学习掌握算法能够很好地训练你的编程思维，帮你开辟出面向对象之外的新天地

C++ 里的算法，指的是工作在容器上的一些泛型函数，会对容器内的元素实施的各种操作。
不过要是“说白了”，算法其实并不神秘，因为所有的算法本质上都是 for 或者 while，通过循环遍历来逐个处理容器里的元素。

STL 提供能在各种容器中通用的算法，如插入、删除、查找、排序等。算法就是函数模板。
算法通过迭代器来操纵容器中的元素

STL 中的大部分常用算法都在头文件 algorithm 中定义。此外，头文件 numeric 中也有一些算法。
有的算法会改变其所作用的容器。例如：
* copy：将一个容器的内容复制到另一个容器。
* remove：在容器中删除一个元素。
* random_shuffle：随机打乱容器中的元素。
* fill：用某个值填充容器。
有的算法不会改变其所作用的容器。例如：
* find：在容器中查找元素。
* count_if：统计容器中符合某种条件的元素的个数。

//统计等于 1 的元素个数
vector<int> v = {1,3,1,7,5}; 
auto n1 = std::count( 
    begin(v), end(v), 1 
);

int n2 = 0;
for(auto x : v) { 
    if (x == 1) {
        n2++;
    }
}

//配合lambda效果更好
auto n = std::count_if( 
    begin(v), end(v),
    [](auto x) { 
        return x > 2;
    }
);

这是追求更高层次上的抽象和封装，也是函数式编程的基本理念。

手写循环的替代品 for_each

它能够促使我们更多地以“函数式编程”来思考，使用 lambda 来封装逻辑，得到更干净、更安全的代码。

vector<int> v = {3,5,1,7,10};   // vector容器
for(const auto& x : v) {        // range for循环
    cout << x << ",";
}
auto print = [](const auto& x)  // 定义一个lambda表达式
{
    cout << x << ",";
};
for_each(cbegin(v), cend(v), print);// for_each算法

排序

很多时候，用sort排序做的成本比较高，比如 TopN、中位数、最大最小值等，我们只关心一部分数据，如果你用 sort()，就相当于“杀鸡用牛刀”，是一种浪费。
1. 要求排序后仍然保持元素的相对顺序，应该用 stable_sort，它是稳定的；
2. 选出前几名（TopN），应该用 partial_sort；
3. 选出前几名，但不要求再排出名次（BestN），应该用 nth_element；
4. 中位数（Median）、百分位数（Percentile），还是用 nth_element；
5. 按照某种规则把元素划分成两组，用 partition；
6. 第一名和最后一名，用 minmax_element

如果是 list 容器，应该调用成员函数 sort()，它对链表结构做了特别的优化。
有序容器set/map 本身就已经排好序了，直接对迭代器做运算就可以得到结果。
而对无序容器，则不要调用排序算法，原因你应该不难想到（散列表结构的特殊性质，导致迭代器不满足要求、元素无法交换位置）。

查找算法

• binary_search    它只返回一个 bool 值，告知元素是否存在，用在在有序序列中
• lower_bound      在有序序列中返回第一个“大于或等于”值的迭代器，判断是否找到：一个是迭代器是否有效，另一个是迭代器的值是不是要找的值。
• upper_bound，  返回的是第一个“大于”值的迭代器。begin < x <= lower_bound < upper_bound < end
• find   find_if  查找算法，找到第一个出现的位置
• search

对于有序容器 set/map，就不需要调用这三个算法了，它们有等价的成员函数 find/lower_bound/upper_bound，效果是一样的。

因为标准算法的名字实在是太普通、太常见了，所以建议你一定要显式写出“std::”名字空间限定，这样看起来更加醒目，也避免了无意的名字冲突。

STL中“大”、“小”和“相等”的概念

在 STL 中，默认情况下，比较大小是通过<运算符进行的，和>运算符无关
y比x大意味着x<y为真，而不是y>x为真。y>x的结果如何并不重要，甚至y>x是没定义的都没有关系。
综上所述，使用 STL 中的关联容器和许多算法时，往往需要对<运算符进行适当的重载，使得这些容器和算法可以用<运算符对所操作的元素进行比较。

STL vector（可变长的动态数组）

STL list（双向链表）

STL 中的算法 sort 可以用来对 vector 和 deque 排序，它需要随机访问迭代器的支持。因为 list 不支持随机访问迭代器，所以不能用算法 sort 对 list 容器排序。因此，list 容器引入了 sort 成员函数以完成排序。

STL deque（双向队列详解）

deque 也是顺序容器的一种，同时也是一个可变长数组。所有适用于 vector 的操作都适用于 deque。
优点:头尾增删元素都具有较好的性能

函数对象详解

如果一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象其实就是重载了()的对象，是一个更加面向对象的函数指针，它可以用很多面相对象的很多特性。

class CAverage
{
public:
    double operator()(int a1, int a2, int a3)
    { //重载()运算符
        return (double)(a1 + a2 + a3) / 3;
    }
};
int main()
{
    CAverage average; //能够求三个整数平均数的函数对象
    cout << average(3, 2, 3); //等价于 cout << average.operator(3, 2, 3);
    return 0;
}

STL关联容器

关联容器内部的元素都是排好序的，有以下四种。
* set：排好序的集合，不允许有相同元素。
* multiset：排好序的集合，允许有相同元素。
* map：每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的。不允许有多个元素的关键字相同。
* multimap：和 map 类似，差别在于元素的关键字可以相同。
不能修改 set 或 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 set 或 multiset 容器中某个元素的值，
正确的做法是先删除该元素，再插入新元素。
同理，也不能修改 map 和 multimap 容器中元素的关键字。
使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时，该元素会和已有的元素进行比较，最终被插入一个合适的位置。
关联容器一般是用平衡二叉树实现的。

pair类模板

在学习关联容器之前，首先要了解 STL 中的 pair 类模板，因为关联容器的一些成员函数的返回值是 pair 对象
STL 中还有一个函数模板 make_pair，其功能是生成一个 pair 模板类对象

pair<int,double> p1;
pair<string,int> p2("this",20);
pair<int,int> p3(pair<char,char>('a','b'));
pair<int,string> p4 = make_pair(200,"hello");
int firstValue = p4.first; 
int secondValue = p4.second;

multiset

multiset 是关联容器的一种，是排序好的集合（元素已经进行了排序），并且允许有相同的元素。

<运算符必须经过适当重载，才可以向 multiset <A>容器中插人元素。

#include <set>
using namespace std;
class A{};
int main(){
    multiset <A> a;
    a.insert( A() ); //编译出错，因为不能用“<”运算符比较两个A对象
}


typedef multiset<A> MSET1; //用“<”运算符比较大小
MSET1::iterator pp = m1.find(19);
if (pp != m1.end())
{
    cout << "found" << endl; //本行会被执行，输出 found
    cout << *m1.lower_bound(22)
    << "," << *m1.upper_bound(22) << endl; //输出 22,33

}
pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));

set

set 是关联容器的一种，是排序好的集合（元素已经进行了排序）。set 和 multiset 类似，它和 multiset 的差别在于 set 中不能有重复的元素。multiset 的成员函数 set 中也都有。
由于不能有重复元素，所以 set 中插入单个元素的 insert 成员函数与 multiset 中的有所不同，其原型如下：

pair<iterator, bool> insert(const T & val);

如果 set 的 insert 成员函数的返回值是 pair 模板类对象 x，如果 x.second 为 true，则说明插入成功，此时 x.first 就是指向被插入元素的迭代器；
如果 x.second 为 false，则说明要插入的元素已在容器中，此时 x.first 就是指向原有那个元素的迭代器。

multimap

multimap 是关联容器的一种，multimap 的每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的，并且允许有多个元素的关键字相同。

STL map

不允许有多个元素的关键字相同。

C++容器适配器简介

STL 中的容器适配器有 stack、queue、priority_queue 三种。它们都是在顺序容器的基础上实现的，屏蔽了顺序容器的一部分功能，突出或增加了另外一些功能。
容器适配器是没有迭代器的，因此 STL 中的各种排序、查找、变序等算法都不适用于容器适配器。

stack

stack的定义如下：

template < class T, class Cont == deque <T> >
class stack{
    ...
};

第二个参数表明，在默认情况下，stack 就是用 deque 实现的。当然，也可以指定用 vector 或 list 实现。

queue

queue 的定义如下：

template < class T, class Cont = deque<T> >
class queue{
    ...
};

priority_queue

priority_queue 是“优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。
priority_queue 可以用 vector 和 deque 实现，默认情况下用 vector 实现。
priority_queue实现是二叉堆，特别适用于“不停地在一堆元素中取走最大的元素”

#include <queue>
#include <iostream>
using namespace std;
int main()
{
    priority_queue<double> pq1;
    pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
    while(!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    } //上面输出 9.8 9.8 5.4 3.2
    cout << endl;
    priority_queue<double,vector<double>,greater<double> > pq2;
    pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
    while(!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    //上面输出 3.2 5.4 9.8 9.8
    return 0;
}

STL算法分类

在 STL 中，算法就是函数模板。STL 中的算法大多数是用来对容器进行操作的，如排序、 查找等。大部分算法都是在头文件 <algorithm> 中定义的，还有些算法用于数值处理，定义在头文件 <numeric> 中。
大多数重载的算法都有两个版本，其中一个用==判断元素是否相等，或用<比较大小；
而另一个版本多出来一个类型参数 Pred 以及函数形参 Pred op，该版本通过表达式op(x, y)的返回值是 true 还是 false 来判断 x 是否“等于”y 或者“小于”y。比如下面有两个版本的 min_element：

iterate min_element(iterate first, iterate last);
iterate min_element(iterate first, iterate last, Pred op);

min_element 返回区间中最小的元素。第一个版本用<比较大小，而第二个版本用自定义的比较器 op 来比较大小，op(x, y) 的值为 true，则说明 x 比 y 小。

C++ bitset类

bitset 模板类由若干个位（bit）组成，它提供一些成员函数，使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。

template <size_t N>
class bitset
{
    ...
};

size_t 可看作 unsigned int。将 bitset 实例化时，N 必须是一个整型常数。例如：

bitset <40> bst;

则 bst 是一个由 40 个位组成的对象，用 bitset 的成员函数可以方便地访问其中任意一位。bitset 中的位从 0 开始编号，第 0 位是最右边的位。