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

本节的另一个重点是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集合后,这个元素就不可以修改了,因为一旦修改元素就破坏元素的有序性了,所以,只能先删除元素,再添加新元素。














  • 无标签