版本比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
介绍算法与算法复杂度,引入一些基础算法,这些算法不需要很详细的推导过程,虽然与后续的内容有关联,但大都可作为独立主题进行分类与学习。
本节的另一个重点是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()都会导致重新排序。
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()); // 删除重复位置到结束的全部元素 |
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大的元素,将其放置在n位置,并将小于等于n位置的元素放左边,大于n位置的元素放右边,函数原型:
代码块 |
---|
//排序规则采用默认的升序排序
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;
} |
目录 |
---|