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

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

STL应用

vector总结

注意遍历时begin()/end()和rbegin()/rend()迭代器始终为++操作。
注意resize()和reserve()的区别，size()和capacity()的区别。
front()/back()返回的是引用，可直接作为左值来用。
insert()是在指定位置之前插入，可批量插入n个元素或是一个迭代器的区间，如下：
```
insert(position, val);
insert(position, n, val);
insert(position, first, last);
```
erase()删除指定位置的元素，或是删除一个区间的元素，当删除区间时，不包括区间结束位置的元素，如下：
```
erase(position);
erase(first, last);
```

list总结

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

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

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()都会导致重新排序。

bitset总结

位域大小必须是已知的，如果想实现变长位域，可使用vector<bool>。
支持全部的位运算符，包括单目和双目位运算，如果是双目，两个操作数必须同相同长度的位域。
访问元素用下标[]或test()。
all()/any()/none()/count()方法。
set()/reset()/flip()方法。
to_string()/to_ulong()/to_ullong()方法。

sort/stable_sort/partial_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()); // 删除重复位置到结束的全部元素

lower_bound/upper_bound总结

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

代码示例：

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

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

    auto it1 = lower_bound(a.begin(), a.end(), 5); 
    cout << "*it1:" << *it1 << ", distance:" << distance(a.begin(), it1) << endl; // 5, 4, 这里找到的是第一个5

    auto it2 = upper_bound(a.begin(), a.end(), 5);
    cout << "*it2:" << *it2 << ", distance:" << distance(a.begin(), it2) << endl; // 6, 6

    return 0;
}

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;
}

页面树结构

算法基础