STL中有哪些副作用或稍不注意会产生性能开销的地方？

发表于 2年以前 | 总阅读数：369 次

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。