• 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想

• 三种O(n^2)的排序：冒泡、选择、插入
• 三种不基于比较的排序：桶、基数、计数（桶+前缀和）

归并排序

• 每次把待排序区间一分为二，将两个子区间排序，然后将两个已经排好序的序列合并

• 选择一个基准，将小于基准的放在基准左边，大于基准的放在基准右边，然后对基准左右都继续执行如上操作直到全部有序。

• 标准库STL，就是C++自身携带的，国际通用的，没有BUG的，老少皆宜的，令一众算法竞赛选手喜闻乐见的C++的附加产品。
• 主要分两大类：算法类（又称为操作类）和容器类。

算法类

• 最大值最小值（别看简单，C语言自身却没有这个）
• template
• _Tp min(_Tp a, _Tp b)
• _Tp max(_Tp a, _Tp b)
• 快速排序 sort(a, a + 10);
• 数据交换 swap(a, b);
• 求下一个排列 next_permutation(a,a+n)

容器类

• 字符串string
• 不限制长度的数组，vector
• 队列queue，堆栈stack，双端队列deque
• 优先队列（堆）priority_queue
• 简单红黑树（一种较高效率的平衡二叉树）set
• 通过键值来建立的平衡二叉树map
• 允许多个相同值的上述两种结构multiset和multimap
• 位集bitset

VECTOR

• VECTOR是一个不限制数组长度的数组！（最简单的理解方式）

VECTOR实现了什么

• 首先是最基础的数据访问功能
operator[], top(), back()
• 其次是简单的数据操作:
删除erase(int index, int size)
插入insert(int index, int size)
添加到数据后面push_back(int value)
弹出最后一个数据pop_back()
• 还有一些自身属性操作：数据大小和重新整理内存单元size(), resize(int size)
• 最后是整体的操作：清空clear(), 是否为空empty()

迭代器Iterator

• 定位：既能像指针一样访问数据，又能保证整体工程的稳定性
• 实际作用：用于访问一个容器内的数据的指针。
• 具体实现了什么？
• 返回第一个元素的迭代器begin()
• 返回容器末尾的迭代器end()（同样遵循左开右闭原则）

Stack 和Queue——栈和队列

• stack常用函数：
• push() ——向栈顶压入元素
• pop()——弹出栈顶元素
• top()——访问栈顶元素
• queue常用函数：
• front()——访问队首元素
• back()——访问队尾元素
• push_back()——向队尾插入元素
• pop_front()——弹出队首元素

map

• map内部使用平衡二叉树实现
• 但是我们应用的时候可以把它理解成“自定义下标的数组”，或者是一个数对的集合。
• 而且它实际上是有序的