一：知识总览

image.png

二：vector

  • 定义vector的长度是10，并且初始化为-3

image.png

  • vector a[10] 定义了是个vector数组
  • image.png这两个函数上面提到的所有容器都有的，并且时间复杂度是O(1)的。
  • image.png注意并不是所有的容器都有清空，比如队列
  • image.png
  • auto可以遍历所有的容器，auto是c++里面的范围遍历。
  • vector clear函数只需要全部清零就可以。
  • vector倍增的思想的好处：申请1e6的空间的时间因为倍增的原因几乎是一样的，申请空间的次数是logn。
  • 迭代器：指针是一种迭代器，end()是返回最后一个数的后面一个数，a.end()其实就是a.size(); begin()和end()是两个迭代器函数。

image.png
当然也可以换成下面的auto，系统看到begin，可以自动换成迭代器的方式。
image.png

  • image.pngimage.png

    三：pair

  • c++中的自带结构体，实现两个变量的一个封装，外加一个比较函数，就是下面的例子。

  • image.pngimage.png

  • pair还可以存储三个不同的东西，通过嵌套的方式image.png

    四：string

  • substr(1, 字串的长度)，第二个参数不写的话，默认是到字符串的末尾。

  • c_str返回的是字符串的起始地址

  • size 和 length的作用是一模一样的

    五：queue

  • queue, stack, priority_queue是没有clear函数的 ，所以清空queue的方法就是重新构造实现清空

image.png

六：priority_queue

  • priority_queue c++中用vector和deque实现，其实用vector就能实现，本质上其实就是堆1
  • priority_queue默认是一个大根堆，实现小根堆的两种方法

方法一：直接插入负数：
image.png
方法二：通过定义的方法变成小根堆，比较常用
image.png

七：deque

  • 加强版的vector，突出点就是其他有的他都有，没有的也有

  • 缺点就是比一般的容器慢上好几倍。

    八：set和multiset，map,multimap

    set里面不能有重复元素，插入重复元素的时候，会被自动忽略，但是multiset里面可以有重复元素
    image.png

  • begin和end返回的是迭代器，这四个容器维护都是有序数列的容器

map可以通过数组的方式取使用a[“yxc”],调用一次的时间复杂度是logn

  • image.png

九：unordered_set, unordered_map,unordered_multiset,unordered_multiset

下面就是和上面的对应和不同，主要区别其实就是无序带来的
image.png

https://zhuanlan.zhihu.com/p/210458185

  • 链接是关于map和unordered_map的区别的。

    十：压位节省空间

    image.png通过bitset可以实现用1/8的空间实现

应用：
image.png

下面的函数现用现查
image.png