STL基本概念

容器：用于存放数据的类模板，比如vector, list, stack, queue等。
迭代器：用于存取容器中存放的元素，可以理解成指针，用于遍历和操作容器。使用迭代器可以实现以相同的风格访问和操作大部分的容器。
算法：用来操作容器中元素的函数模板，比如sort, unique等。

容器

用于存放元素，实例化时指定元素类型。如果存储的是一个对象，那么最好重载==和<运算，因为大部分算法都会用这两个运算符来进行相等判断和排序。

容器分为两大类：

顺序容器：可变长动态数组vector、双端队列deque、双向链表list。顺序容器的元素具有前后关系，可指定位置插入和删除。

关联容器：set、multiset、map、multimap。关联容器的元素是排序过的，不能指向插入位置。插入的元素会自动排序。默认情况下，关联容器中的元素按从小到大排序，使用运算符"<"进行比较。关联容器在查找时有很好的性能。

容器适配器：栈stack、队列queue、优先队列priority_queue。在上两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能。

任何两个容器对象，只要类型相同，就可以用<、<=、>、>=、==、!=进行字典式的比较，它们的运行规则如下：

a == b: a和b中的元素个数相同，且对应元素相等，使用==运算符。

a < b: 类似于单词的字典序比较，使用<运算符。

a != b: 等价于!(a == b)。

a > b: 等价于 b < a。

a <= b：等价于 !(b < a)。

a >= b: 等价于!(a < b)。

所有的容器都有以下两个成员函数：

int size()：返回容器对象中元素的个数。

bool empty()：判断容器对象是否为空。

顺序容器和关联容器还有以下成员函数：

begin(): 返回指向容器第一个元素的迭代器。

end(): 返回指向容器最后一个元素后面的位置的迭代器。

rbegin(): 返回指向容器最后一个元素的反向迭代器。

rend(): 返回指向容器第一个元素前面的位置的迭代器。

erase(): 删除一个或几个元素。

clear(): 删除所有元素。

顺序容器还有以下常用成员函数：

front(): 返回容器中第一个元素的引用。

back(): 返回容器中最后一个元素的引用。

push_back(): 在容器末尾增加新的元素。

pop_back(): 删除容器末尾的元素。

insert(): 插入一个或多个元素。

迭代器

用于访问容器中的元素，有以下四种：

1. 正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

2. 常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

3. 反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

注意，容器适配器stack、queue和priority_queue没有迭代器，它们有自己的方法用于访问元素。

不同的容器的迭代器功能有强弱之分，这决定了容器是否支持某种STL算法，比如，排序算法sort需要通过迭代器支持随机访问功能，如果某种容器不支持随机访问，如list，那就不支持使用sort进行排序。

常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问5种：

正向迭代器：支持++p和p++、*p，两个迭代器可以赋值，可以用==和!=比较；

双向迭代器：支持正向迭代器的全部功能，还支持--p和p--；

随机访问迭代器：在双向迭代器的基础上，支持 p+i、p-i、p+=i、p-=i、p[i]，还支持 <、>、<=、>=比较。

不同容器的迭代器功能：

容器	迭代器功能
vector	随机访问
deque	随机访问
list	双向
set/multiset	双向
map/multimap	双向
stack	不支持
queue	不支持
priority_queue	不支持

迭代器的辅助函数：

advance(p, n): 使迭代器向前或向后移动n个元素。

distance(p, q): 计算两个迭代器之间的距离，即p经过多少次++后和q相等，如果p本身就在q后面，则这个函数会陷入死循环。

iter_swap(p, q): 用于交换两个迭代器q、q指向的值，相当于通过指针交换元素内容。

算法

能在各种容器上通用的函数模板，通过迭代器来操作元素。

大部分算法需要通过迭代器提供一个操作区间，比如begin()~end()。

有的算法返回一个迭代器，比如find算法。

排序、查找等算法需要对元素进行比较，比较判断大小及是否相等。在STL中，比较大小通过"<"运算符来实现，和">"无关。而比较相等时，并不一定是使用"=="运行符，而是要根据情况来确定。如果是在未排序的区间上应用find进行查找，那么使用"=="运算符来判断相等。如果是在已经排序好的区间上进行查找、合并等操作（比如折半查找算法binary_search，关联容器自身的find成员函数)，那么判断x=y的条件是x<y和y<x同时为假。如果一个类将"<"运算符重载为永远返回false，那么对于STL算法来说，这个类的所有对象都是相等的。

vector

可变长数组，支持以下迭代器：

begin()/end()
rbegin()/rend()
cbegin()/cend()
crbegin()/crend()

支持以下容量相关的操作：

size()
empty()
resize()
reserve()
capacity()

注意：size()和resize()是配套的，用于调整数组的实际大小，调小时截断，调大时补零。reserve()和capacity()是配套的，用于调整数组的预分配空间大小，这个大小不影响数组的内容和size()的返回值。如果对性能要求不高，那么完全不需要调用reserve()来预分配空间，而是只使用vector默认的增长策略。

resize()除了可以重新分配大小外，还可以直接赋初值，如下：

vector<int> v;
v.resize(10);
v.resize(10, -1);
vector<vector<int>> v;
v.resize(10, vector<int>(10, -1));

支持以下元素访问操作：

下标操作符[]
front()
back()

注意front()和back()都是返回引用，也就是可以直接通过这两个函数的返回值来修改元素。

支持以下修改操作：

push_back()
pop_back()
insert()
erase()
clear()

以下是vector的一些示例操作：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v1{1, 2, 3, 4, 5};

    cout << "size:" << v1.size() << endl;           // 5
    cout << "capacity:" << v1.capacity() << endl;   // 5

    v1.reserve(15);
    cout << "size:" << v1.size() << endl;           // 5
    cout << "capacity:" << v1.capacity() << endl;   // 15


    v1.resize(10);
    cout << "size:" << v1.size() << endl;           // 10, 后面的5个元素值为全零
    cout << "capacity:" << v1.capacity() << endl;   // 15

    v1.resize(5); // 截断后面5个元素

    // 正向遍历
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 反向遍历，注意it仍为++
    for(auto it = v1.rbegin(); it != v1.rend(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 访问元素
    v1.front();
    v1.front() = 0;
    v1.back();
    v1.back() = 6;

    // 修改元素
    v1.push_back(6);
    v1.pop_back();
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // insert
    v1.insert(v1.begin(), -1);      // 在指定位置之前插入
    v1.insert(v1.end(), 7);
    v1.insert(v1.begin(), 5, -2);   // 批量插入
    {
        vector<int> tmp{8, 9, 10};
        v1.insert(v1.end(), tmp.begin(), tmp.end());  // 在指定位置插入一个区间的值
    }
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // erase
    v1.erase(v1.begin());                   // 删除当前位置的元素
    v1.erase(v1.begin(), v1.begin() + 4);   // 删除一个区间的元素
    for(auto it = v1.begin(); it != v1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    return 0;
}

list

与vector同为顺序容器，但是不支持随机访问，其访问过程只能是从前往后遍历或是从后往前遍历。

支持的迭代器如下：

begin()/end()
rbegin()/rend()
cbegin()/cend()
crbegin()/crend()

以上迭代器只支持双向操作，也就是it++和it--，不支持随机访问，比如it+n。

容量相关的操作如下：

size()
empty()

元素访问：

front()
back()

修改元素：

push_front()
pop_front()
push_back()
pop_back()
insert()
resize()

上面的resize()和vector的resize()类似，用于重新分配大小，不够补上空的元素，多了截断多余的元素。

示例代码：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> a{1, 2, 3, 4, 5};

    for(auto it = a.begin(); it != a.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 前后插入/删除元素
    a.pop_front();
    a.pop_back();
    a.push_front(0);
    a.push_back(6);

    for(auto it = a.begin(); it != a.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 删除单个元素
    for(auto it = a.begin(); it != a.end(); it++) {
        if(*it == 3) {
            a.erase(it);
            break; // 这里必须break，因为it被删除后已经被回收了，不再指向下一个元素
        }
    }

    // 循环体中删除元素
    auto it = a.begin();
    while(it != a.end()) {
        if(*it == 2) {
            it = a.erase(it); // 返回删除元素的下一个元素
        } else {
            it++;
        }
    }

    for(auto it = a.begin(); it != a.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    return 0;
}

queue/deque

queue和deque都是队列，用于先进先出操作，不同的是queue只能在一头插入，在另一头弹出，而deque两头都可以插入和弹出，通过比较它们支持的方法即可分辨出区别：

queue支持的方法：

push();
pop();
front();
back();
size();
empty();
clear();

deque支持的方法：

push_front();
push_back();
pop_front();
pop_back();
front();
back();
size();
empty();
clear();

stack

先进后出，支持以下方法：

push();
pop();
top();
size();
emtpy();

注意stack不支持清空操作！！！如果要清空一个队列，可以将其与一个空的栈进行swap。

set

集合类型，用于去重和排序，默认使用==进行相等判断，使用<进行排序，也就是说如果想实现自定义类型的set操作，则必须要重载该类型的==和<运算符。

set默认按从小到大排序，如果想改成从大到小，则以下是供参考的写法：

set<int> s1;               // s1按从小到大排序，等效于set<int, less<int>> s1;
set<int, greater<int>> s2; // s2按从大到小排序

auto comp = [](int a, int b) { return a < b; }; // 自定义比较方法
set<int, decltype(comp)> s3(comp);

class Comp {    // 自定义比较方法，仿函数形式
    bool operator()(int a, int b) { return a < b; } 
};
set<int, Comp> s4;

set支持全部的四种类型的迭代器，但是只能进行双向迭代，也就是it++和it--。

容量操作：

size()
empty()

修改元素：

insert()
erase()
clear()

集合操作：

find()
count()
lower_bound()
upper_bound()
equal_range()

示例代码：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(4);
    s.insert(3);
    s.insert(2);
    s.insert(1);
    
    // 遍历
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // 查找与删除元素
    auto it = s.find(1);
    if(it != s.end()) {
        s.erase(it);
    }
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // lower_bound，找第一个大于或等于的元素的位置
    auto it1 = s.lower_bound(3);
    cout << "it1:" << *it1 << endl; // 3

    // upper_bound，找第一个大于某个元素的位置
    auto it2 = s.upper_bound(4);
    cout << "it2:" << *it2 << endl; // 5

    // 查找指定元素的范围，由于set是去重的，所以返回的区间长度只能是1或0
    auto p = s.equal_range(4);
    cout << "first:" << *p.first << ", second:" << *p.second << endl;
    cout << "distance:" << distance(p.first, p.second) << endl;

    return 0;
}

unordered_set

无序集合，使用哈希表实现，相比于set，由于是无序的，所以不支持lower_bound/upper_bound操作，也无需在构造时指定比较函数。

unordered_set只支持正向遍历，所以不存在反正迭代器。unordered_set的迭代器只支持++操作。

unordered_set支持的所有方法如下：

迭代器：

begin()/end()
cbegin()/cend()

容量相关：

size()
empty()

查找：

find()
count()

修改：

insert()
erase()
clear()

multiset

可以存储重复值的set，内部也是排序好的，操作方法与set完全一样，因为可以存储重复值，所以以下接口与set有区别：

find() 只返回第一个元素的位置
lower_bound()/upper_bound() 结果将不一样，因为存储的元素可能相等
equal_range()返回的区间长度可能大于1，这可以用于一次找到全部相等的元素

map

排序的关联容器，形式为map<key, value>，通过key进行排序，每个key映射一个value。key的排序规则可自定义，由第三个模板参数决定，默认为less<T>，也就是按key从小到大排序。

map支持正向和反向遍历，支持上下边界和范围查找，以下是其支持的方法：

迭代器：

begin()/end()
cbegin()/cend()
rbegin()/rend()
crbegin()/crend()

元素访问：

下标运算符[]
at()

容量：

size()
empty

修改：

下标运算符[]
erase()
clear()

查询：

find()
count()
lower_bound()
upper_bound()
equal_range()

unordered_map

map的无序版本，不支持反向遍历，不支持上下边界和范围查询。

multimap

map的可重复版本，支持正向/反向遍历，支持上下边界和范围查询。

priority_queue

优先队列，也称为堆，包括最大堆与最小堆。priority_queue默认为最大堆。

priority_queue有三个模板参数，如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<T>
> class priority_queue;

第一个参数是存储类型，第二个参数是底层容器的类型，默认为vector，也可以自定义为deque（注意不能为queue，因为queue不支持push_back，也不能为list，因为list不支持通过迭代器获取元素间隔），第三个类型为排序规则，默认为less<T>，效果为最大堆，如果想实现最小堆，则只需要将第三个参数改成greater<T>即可。由于修改了最后一个模板参数，所以前两个模块参数也必须给出。

priority_queue支持的操作如下：

top();
size();
empty()
push();
pop();

注意不支持clear()。

示例代码：

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    while(!q.empty()) {
        std::cout << q.top() << ' ';
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    const auto data = {1,8,5,6,3,4,0,9,7,2};
 
    for(int n : data) q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int>> q2(data.begin(), data.end());
 
    print_queue(q2);
 
    // 通过lambada表示式指定排序规则
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : data) q3.push(n);
 
    print_queue(q3);
}

bitset

已知大小的位域数据结构，构建时需指定位数，比如bitset<16>表示包含16个二进制位的类型。

位域的初始化有以下几种方式：

bitset<16> a;
bitset<16> b(0xa5a5);
bitset<16) c("01010010");

位域支持全部的位操作，比如与、或、取反、左移、右移、异或等，注意，双目运算符的两个位域必须是相同长度的，不同长度的位域类型不能进行运算。

除此以外，位域还支持以下操作：

成员访问：

下标运算符[]
test()
all()
any()
none()
count()

关于以上函数，test()用是返回某个位是否为1，传入位的下标，all()返回是否全1，any()返回是否至少有1个1，none()返回是否全0。count()返回1的数量。

修改数据：

set()
reset()
flip()

set()用于设置全1，也可以设置某个具体的位的值，比如set(1)或set(1, false)。reset()用于清空位，flip()用于翻转位，这两具接口都可以不传参数，表示针对全部的位操作，也可以传入一个下标，表示针对具体的位操作。

转换输出：

to_string()
to_ulong()
to_ullong()

可直接用<<或>>进行输入或输出。

最后，bitset使用的前提是位数是确定的，如果想实现变长位域，可使用vector<bool>代替。

sort/stable_sort/partial_sort

排序算法，sort使用快速排序，不稳定，stable_sort使用归并排序，稳定，partial_sort用于部分排序。它们的原型如下：

sort(begin, end);
sort(begin, end, comp);
stable_sort(begin, end);
stable_sort(begin, end, comp);
partial_sort(begin, middle, end); // 排序整个数组，并填充区间[begin, middle)为已排序好的值，剩余部分不处理
partial_sort(begin, middle, end, comp);

默认按从小到大排序，对应的comp默认为less<T>，如果想改成从大到小排序，则使用greater<T>即可，也可以自定义排序规则，如下：

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    int a[] = {3, 2, 5, 1, 5, 0, 9};
    
    sort(begin(a), end(a));
    for(int i = 0; i < sizeof(a)/sizeof(a[0]); i++) {
        cout << a[i] << endl;
    }

    // sort(begin(a), end(a), greater<int>());
    sort(begin(a), end(a), [](int &a, int &b) { return a > b; }); // 从大到小排序
    for(int i = 0; i < sizeof(a)/sizeof(a[0]); i++) {
        cout << a[i] << endl;
    }

    return 0;
}

unique

用于去除重复的相邻元素，比如对于一个已排序的数组进行unique，可保证操作之后的数组是唯一的，它的形式如下：

unique(begin, end);
unique(begin, end, comp);

第二种形式是传入一个自定义的判断相等的函数，用于替代默认的==运算。

unique的重点是返回值，它返回去重后的第一个重复元素的位置，这个位置之前的元素是已经去重的，对排序后的数组进行去重并删除重复元素的代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a{1, 2, 3, 1, 4, 6, 5, 3, 2};
    sort(a.begin(), a.end());
    for(auto &i : a) cout << i << endl;

    auto end = unique(a.begin(), a.end()); // 去除相邻重复元素
    a.erase(end, a.end()); // 删除重复位置到结束的全部元素
    for(auto &i : a) cout << i << endl;
    return 0;
}

lower_bound/upper_bound

lower_bound(begin, end, val)：查找区间内第一个大于或等于val的元素位置。
upper_bound(begin, end, val)：查找区间内第一个大于val的元素位置。

这两个函数都是返回迭代器类型，算偏移的话要用std::distance()。如果不存在，则返回end。

nth_element

部分排序算法，规则如下：

将数组中第n大的数放到nth所在的位置。
nth位置之前的数都不大于nth之后的数。

以下是函数原型：

//排序规则采用默认的升序排序
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last);
//排序规则为自定义的 comp 排序规则
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last,
                  Compare comp);

示例代码：

int main() {
    vector<int> a{0, 2, 1, 5, 4, 2, 3, 6};

    nth_element(a.begin(), a.begin() + 2, a.end()); // 找出第三大的元素，放在a.begin()+2这个位置
    for(auto &i : a) cout << i << " "; cout << endl; // 1 0 2 2 3 4 5 6

    return 0;
}

round/floor/ceil/trunc

包含在<math.h>头文件中，用于整数四舍五入，向上、向下取整，截断，原型如下：

// 四舍五入
double round  (double x);
float roundf (float x);
long double roundl (long double x);

// 向下取整
double floor (double x);
float floor (float x);
long double floor (long double x);

// 向上取整
double ceil (double x);
float ceil (float x);
long double ceil (long double x);

// 截断
double trunc (double x);
float trunc (float x);
long double trunc (long double x);

参考以下表格：

value   round   floor   ceil    trunc
-----   -----   -----   ----    -----
2.3     2.0     2.0     3.0     2.0
3.8     4.0     3.0     4.0     3.0
5.5     6.0     5.0     6.0     5.0
-2.3    -2.0    -3.0    -2.0    -2.0
-3.8    -4.0    -4.0    -3.0    -3.0
-5.5    -6.0    -6.0    -5.0    -5.0

页面树结构

STL应用

STL基本概念

容器

迭代器

算法

vector

list

queue/deque

stack

set

unordered_set

multiset

map

unordered_map

multimap

priority_queue

bitset

sort/stable_sort/partial_sort

unique

lower_bound/upper_bound

nth_element

round/floor/ceil/trunc