介绍算法与算法复杂度，引入一些基础算法，这些算法不需要很详细的推导过程，虽然与后续的内容有关联，但大都可作为独立主题进行分类与学习。

本节的另一个重点是STL应用，所谓工卻善其事，必先利其器，STL容器与算法就是解决算法问题的利器，必须对STL应用非常熟悉，才可以在写代码时得心应手，事半功倍。

STL应用

vector总结

1. 注意遍历时begin()/end()和rbegin()/rend()迭代器始终为++操作。
2. 注意resize()和reserve()的区别，size()和capacity()的区别。
3. front()/back()返回的是引用，可直接作为左值来用。

4. insert()是在指定位置之前插入，可批量插入n个元素或是一个迭代器的区间，如下：

   代码块
   insert(position, val); insert(position, n, val); insert(position, first, last);

5. erase()删除指定位置的元素，或是删除一个区间的元素，当删除区间时，不包括区间结束位置的元素，如下：

   代码块
   erase(position); erase(first, last);

list总结

1. 迭代器只能前向或后向遍历，也就是it++和it--。 
2. 支持前后删除和插入元素。

3. 删除元素时传入迭代器，注意删除之后该迭代器就不可用了，如果是在循环中删除，则需要下面这样的代码：

   代码块
   auto it = a.begin(); while(it != a.end()) { if(xxx) { // a.erase(it); // 错误，a.erase(it)之后it不可用 it = a.erase(it); } else { it++; } }

queue/deque总结

一个是只能一头进另一头出，一个是两端都可以进出，queue只支持push()和pop()，而deque比queue多支持以下方法：

push_front();
push_back();
pop_front();
pop_back();

除此外它们共享以下方法：

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

stack总结

注意，stack不支持清空，如果要快速清空，可将其与一个空的栈进行swap。

set/unordered_set/multiset总结

• set：有序，不存在重复值，可以查找上边界、下边界以及范围。
• unordered_set：无序，不存在重复值，只支持find()和count()查询，是纯粹的集合概念。
• multiset：有序列，可以存在重复值，可以查找上边界、下边界、相同元素范围。

注意：一旦将元素插入到以上set集合后，这个元素就不可以修改了，因为一旦修改元素就破坏元素的有序性了，所以，只能先删除元素，再添加新元素。

map/unordered_map/multimap总结

• map<key, value>：有序，key必须唯一，按key值排序，一个key对应一个value，通过下标或at()访问，可以查询上下边界及范围。
• unordered_map：无序，只支持find()和count()查询。
• multimap：有序，key可以重复，支持上下边界和范围查询。

priority_queue总结

优先队列，用于实现最大堆或最小堆，形式如下：

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

以上默认为最大堆，底层使用vector存储元素，如果想修改为最大堆，则可以使用greater<T>。

priority_queue()只能通过top()来访问堆顶部的元素，这个值为堆的最大值或最小值。除此外，push()用于存入值，pop()用于弹出值，每次push()和pop()都会导致重新排序。

sort/stable_sort总结

了解如何自定义排序规则即可，如下：

sort(a.begin(), a.end(), [](int &a, int &b) { return a > b;}); // 从大到小排序

unique总结

用于删除相邻的重复元素，操作的对象一般是排序后的数组，可自定义判断重复的函数。

unique返回去重后第一个重复元素的位置，从这个位置到数组末尾都是可删除的重复元素，一段使用unique去重的代码如下：

vector<int> a{1, 2, 3, 1, 4, 6, 5, 3, 2};
sort(a.begin(), a.end());
auto end = unique(a.begin(), a.end()); // 去除相邻重复元素，返回开始重复元素的位置
a.erase(end, a.end()); // 删除重复位置到结束的全部元素