STL 中有哪些副作用或稍不注意会产生性能开销的地方?
The following article is from 编程往事 Author 果冻虾仁
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。- EOF -
关注『CPP开发者』
看精选C++技术文章 . 加C++开发者专属圈子
点赞和在看就是最大的支持❤️