STL中稍不注意会产生性能开销的地方
STL容器的clear的时间复杂度不是O(1)
可能很多人都不在意，在使用STL容器的时候，潜意识里面将clear()成员函数视为常量时间复杂度O(1)的。但是其实不然。我感觉可能是很多人都知道对于vector而言，clear()之后，修改了size()的结果，不影响capacity()的结果，因而得出clear()只是修改了某个标记，是常量时间复杂度的错误结论。
其实C++标准明确指出不管是序列容器（比如vector）还是关联容器（比如unordered_map)其clear()成员函数都是线性时间复杂度O(n)的。因为只要执行了clear()就需要对其存储的元素调用析构函数，这个析构操作显然是逐个析构的。因而时间复杂度是O(n)。
当然在实践中，也有个例。比如当vector存储基本数据类型或POD类型（比如基本数据类型构成的struct）的时候，由于其元素类型没有析构函数（也不需要析构函数），加之vector内部连续存储的特性，编译器的实现是可以在常量时间完成clear()的。
Linear in size(destructions). This may be optimized to constant complexity for trivially-destructible types(such as scalar or PODs), where elements need not be destroyed
🔗 http://www.cplusplus.com/reference/vector/vector/clear
当然仅限于vector存储基本数据类型和POD类型的时候，编译器可能有此优化。如果vector存储的是其他类型的对象，或者是其他容器（比如list、map、unordered_map）都是没办法做这个优化的！
所以在工程实践中，我们要思考是否每次都需要及时的clear掉一个容器。比如在后台服务中，有些容器类型的变量在命中某些条件下要进行clear()，后续逻辑中判断容器是空的，就不在用之进行某些逻辑（比如遍历它，进行某种操作）。其实也可以用一个bool标记来存储后续是否需要遍历该容器，待到本次请求的响应返回给client之后，再来清理这个容器也不迟。
当然这种操作在容器的元素个数不多的时候是完全没有必要的，会丧失一些可读性。不过这种思考还是需要有的。如果元素过多的时候，或许可能是性能优化的一个小点。
auto替代手写类型
比如在基于范围的循环中尽量使用auto&，否则容易踩坑。这个观点在Scott Meryer的《Effictive Modern C++》一书的条款5中已经讲得很清楚了。
下面简要概述一下，对于unordered_map而言，其中的元素类型是：
std::pair<const std::string, int>
如果你这样遍历：
std::unordered_map<std::string, int> m; for (const std::pair<std::string, int>& p: m) { ... }
你因为你有一个const就对了么？实则不然。这里会触发pair<const std::string, int>类型的原始对象构造一个pair<std::string, int>的临时对象。有额外的拷贝构造开销。并且这里的引用还是引用的临时对象！
但如果你使用auto&则不会出问题。编译器自动的类型识别会帮你处理好！
std::unordered_map<std::string, int> m; for (auto& p: m) { ... }
减少隐性的重复操作
从map中查找某个key对应的value。我们一般怎么写呢？
是这样：
// dict_data是一个unordered_map<string, double> // vec是一个vector<string> double sum = 0; for (auto& key : vec) { if (dict_data.count(key)) {// 或dict_data.count(key) > 0 sum += dict_data[key]; // 或 sum += dict_data.at(key); } }
或者这样：
for (auto& key : vec) { if (dict_data.find(key) != dict_data.end()) { sum += dict_data[key]; // 或 sum += dict_data.at(key); } }
其实map或unordered_map的[]或者at()函数内部也会进行查找。不管这次查找的开销大或不大吧。既然我们已经查找过一次key是否存在了，那么就把结果存储下来就好了。为什么要二次查询呢？
for (auto& key : vec) { auto it = dict_data.find(key); if (it != dict_data.end()) { sum += it->second; } }
当然你可能觉得这样丑点，所以不这样写……但我的原则一向是不要进行重复操作。
对于vector也有at()所以也有人这样写：
if (index < v.size()) { auto& e = v.at(index); // do sth for e ... }
这个at()内部同样会检查是否越界，并在越界的时候抛异常。所以对于vector，你直接[] 就好了。vector的[] 几乎没有开销，和那些关联容器不同。
if (index < v.size()) { auto& e = v[index]; // do sth for e ... }
或者直接不检查，而是加try catch
try { ... auto& e = v.at[index]; // do sth for e ... } catch (...) { }
当然代码更丑一点。。而且我不鼓励在生产环境中使用会抛异常的函数。因为C++不同于java。java如果有未捕获或throw的异常，编译都过不了。而C++则不管。所以如果你的代码不小心抛出了异常，而没被catch，那么就可能让程序core dump！
sort给定义对象排序，可能存在对象拷贝的开销
STL中的sort()应该是一个高频使用的函数了。比如对于一个vector进行排序。当vector存储的时候自定义类型的时候，我们也都知道给sort()传入一个比较算子，或者在外部重载一下operator<增加一个自定义类型的比较功能。
但是大家可能会忽略，当你的自定义类型没有移动构造函数的时候，调用的是拷贝构造函数！当然如果你的类型，比较简单（比如只是保护2个基本数据类型）那么拷贝构造的开销也不大。但如果你的自定义类型比较复杂的时候，拷贝构造的开销显然大于移动构造函数。
所以当你的最好给你的自定义对象添加一个移动构造函数，另外为了使sort()能够成功通过编译，在定义完移动构造函数以后，还要再定义一个移动赋值函数。
当然如果你不想这么麻烦的话，那么用vector存储该类型的指针，然后传入一个该类型指针进行比较大小的lambda表达式，会是更简单的解决方案。只是这样对于老代码来说可能是侵入性的。而直接修改类定义的方法，则对老代码透明。
如果要排序，不要无脑使用sort()
如果你想着拥有N个元素的vector排序，然后取出K个元素。那么这是典型的TopK问题。不要无脑的使用sort()。STL的算法中还有一个partial_sort()，只帮助你找到最大（或最小）的K个元素，而不需要把整个vector变得有序。
STL中容易踩坑的副作用
clear()不会清空vector的内存
尽管clear()会调用vector中元素的析构函数，但是并不会释放掉元素所占用的内存。这并不难理解，因为在vector为空的时候，我们也可以用reserve()函数来预分配内存。所以vector所占的内存并不会随着元素的释放而释放。如果你想在vector生命周期结束之前及时释放掉vector的内存，请：
vector<int>().swap(v);
用一个匿名的vector对象来和已有的vector对象v来swap。虽然swap是交换，但由于涉及匿名对象，反过来swap是无法编译通过的：
v.swap(vector<int>()); // 编译失败
size()-1
如何遍历一个vector？当然在C++11以后我能手写for-range循环了。
for (auto& e: v) { // do sth for e ... }
但是有时候我们在循环内需要下标信息，而不仅仅是元素本身。所以就变成传统的下标遍历了。有两种写法，各位看官看看是否有区别？
for (int i = 0; i < v.size(); ++i) { auto& e = v[i] // do sth for e and i ... }
另外一种：
for (int i = 0; i <= v.size() - 1; ++i) { auto& e = v[i] // do sth for e and i ... }
看起来好像一样？实则不然。因为size() 返回是无符号整型，当vector是空的时候，size()返回0，无符号的0 减去1，得到的是一个极大的正数。因而在vector是空的时候，第二种写法会陷入死循环！
int和size()比较
看过上一节内容，你是不是以为容器肯定大于0的时候，或者不去对size()做减一的时候，就没有什么副作用的地方了呢？那也未必。可以通过一道leetcode 173这道题来介绍一下。
🔗 https://leetcode-cn.com/problems/binary-search-tree-iterator/
实现一个二叉搜索树的迭代器，其中有个函数hashNext()返回还有没有下一个元素。next()表示向右移动虚拟的迭代器，并返回其值，所以我定义了一个成员变量i，初始化为-1。
int next() { return tree[++i]->val; } bool hasNext() { return i < tree.size() - 1; } ... int i = -1; vector<TreeNode*> tree;
题目保证容器肯定大于0，所以tree.size() - 1的结果最小也就是0（size()为1的时候）。在第一次调用next()的时候， i 是 -1，tree().size() - 1即使是0，也是满足小于关系的。所以hasNext()应该返回true，结果意外的是hasNext()返回的是false!
这个是因为tree.size()是无符号类型，有符号类型i在和它比较的时候被自动转型成了无符号的整型，所以取值为-1的i，变成了一个极大的整数，所以hasNext()返回了false！
这是一个常见的坑。
i < v.size()
这种表达式，在i会自动转型成无符号整型，然后你本以为的i（负数）小于v.size() (大于等于0），却判断成了大于！从而触发一下程序逻辑上的bug。
各位，可要小心啊。
多线程一写多读STL容器也不是线程安全的
好吧，关于STL容器的线程安全问题有点老生常谈了。
我在之前文章C++ STL容器如何解决线程安全的问题？ 中有写过：
并发多个线程去写STL容器（“写”指的是插入新元素） 不是线程安全的，可能会触发core dump。但大家可能常常忽略一种不常见的情况：一个线程写，其他线程都是读的时候 其实也不是线程安全的。
比如vector，尽管只有一个线程来写入，但是如果他触发了扩容了。那么其他线程尽管是只读这个vector的，其中的迭代器也会失效。对于unordered_map也是类似，单线程不停插入元素的话，可能触发rehash，导致其他线程中在unordered_map中find的过程中core dump。
