STL的那些事

  1. 判断元素存不存在的时候不能map 直接访问元素下标。默认这样做新的元素会被创建,导致 map 变慢并且会有一定的几率出错
  2. 用迭代器来访问STL。会比下标访问更快。
  3. C++版本<11的时候不能auto 。
  4. 不要尝试用 lower_bound 查找结构体。会出错。
  5. set / map 等STL自带的 lower_bound来查找元素。不然复杂度会变为$O(\log^2 n)$。
  6. $n=100000$的时候考虑$O \left (\dfrac{n^2}{\omega} \right)$的复杂度



0

STL的max,min真的慢?

看到一篇文章.里面的博主很生气的写道:STL的max真的慢…所以变成了80分TLE…

这不禁令人生疑:至于这样吗?

于是我便做了一次测试.此次测试不打开O2,认为是对STL没有利的.

测试平台:i7 8700k@4.7Ghz

1.STL测试

测试代码1:


跑了5次,取平均之后用时2.16s

数据范围改大,max改成min,又测了一下


跑了5次,取平均之后用时4.30s

2.手写测试

测试代码1:


用了喜闻乐见的问号表达式.可能有些人会怀疑是不是用 if 比问号表达式快,我可以很明确的告诉你是不存在的,也测试过了.然而跑了5次取平均之后,用时2.19s.

和上面一样,测试代码2:


用时4.37s,还是略大于STL

所以我想说,STL或许有些情况下比手写慢,但不是绝对的.要根据情况而判断哪个快哪个慢,而不是慢就成了STL的代名词.

0