看完《Effective STL》之后的确有很大的收获,发现 STL 里面的坑还真是不少,这里选了几条我认为比较重要的条款来说一说。
条款9:慎重选择删除元素的方法
STL中的 remove 和 erase 有时候的确会让人比较困惑,下面分三种情况详细讨论各类容器如何使用 remove 和 erase:
1. 要删除容器中有特定值的所有对象:
(1)若容器是 vector、string 或 deque,则使用 erase-remove 习惯用法:Container<int> c;
c.erase(remove(c.begin(), c.end(), value), c.end());
注意:remove 将值为非 value 的元素依次前移,覆盖值为 value 的元素,返回指向第一个应该废弃的元素的迭代器,不改变容器的大小。
(2)若容器是list,则使用其成员函数 list::remove(当然也可以使用如上方法),即:c.remove(value); // 无返回值,这是 list 最高效的删除方法
(3)若容器是一个标准关联容器,则使用它的 erase 成员函数,即:c.erase(value); // 无返回值
2. 要删除容器中满足特定判别式(条件)的所有对象:
(1)若容器是 vector、string 或 deque,则使用 erase-remove_if 习惯用法:bool isBadValue(int) { ... }
c.erase(remove_if(c.begin(), c.end(), isBadValue), c.end());
(2)若容器是 list,则使用其成员函数 list::remove_if,即:c.remove_if(isBadValue); // 无返回值
(3)如果容器是一个标准关联容器:
方法一:使用 remove_copy_if 和 swap:AssocContainer<int> c;
...
AssocContainer<int> goodValues;
remove_copy_if(c.begin(), c.end(),
inserter(goodValues,
goodValues.end()),
isGoodValue); // bool isGoodValue(int i) { return !isBadValue(i); }
c.swap(goodValues); // 需要复制所有不被删除的元素,有额外的开销
方法二:循环遍历,注意防止迭代器失效:for (auto iterator i = c.begin(); i != c.end(); /* 什么也不做 */) {
if (badValue(*i)) c.erase(i++); // 迭代器递增->返回旧值给erase->删除元素后旧迭代器失效
else ++i;
}
3. 要在循环内部做某些(除了循环删除对象之外的,如写日志文件)操作:
(1)标准序列容器(注意用erase的返回值更新迭代器的值)ofstream logFile;
for (auto i = c.begin(); i != c.end(); ) {
if (badValue(*i)) {
logFile << "Erasing " << *i << '\n';
i = c.erase(i); // erase使i之后的所有迭代器失效,返回下一个有效的迭代器(即使重新分配内存)
}
else ++i;
}
(2)标准关联容器:只要在 2 -(3)方法二中添加写日志文件的语句即可
条款19:理解相等(equality)和等价(equivalence)的区别
相等和等价的区别也是容易让人困惑的地方,下面针对不同的容器和算法简单解释一下:
1. find 算法对“相同”的定义是相等,是以 operator== 为基础的
2. set::insert 对“相同”的定义是等价,默认是以 operator< 为基础的
template< |
注意:set 的 key_comp() 成员函数返回比较函数 Compare,它是这样判断等价的:!c.key_comp()(x, y) && !c.comp()(y, x)
3. set 的 find 成员函数对“相同”的定义是等价,即以 key_comp() 为基础
4. std::equal_to(x, y) 是以 operator== 为基础的
条款31:了解各种与排序有关的选择
STL中提供了各种与排序相关的算法,下面描述几个比较常用的算法:
1. 部分排序 partial_sort:
Widget w; |
2. nth_element 用于排序一个区间,使得位置 n 上的元素正好是排序后的第 n 个元素
nth_element(w.begin(), |
3. nth_element 用来找一个区间的中间值(或其他,如具有 75% 质量的元素)
vector<Widget>::iterator goalPositon = w.begin() + w.size() / 2; |
4. partition 把满足某条件的元素移到前部,返回指向第一个不满足条件的元素的迭代器
bool hasAcceptableQuality(const Widget& w) |
注意:
- partition 算法是非稳定的,它有一个叫做 stable_partition 的稳定版本;
- sort、partial_sort、nth_element 都是非稳定的排序算法,stable_sort 是稳定的;它们都需要随机访问迭代器,所以只能被应用于 vector、string、deque 和数组;
- list 仍然可以使用 partition 和 stable_partition 算法;还可以用 list::sort 成员函数进行排序;也可以将 list 的内容拷贝到一个 vector 中实施上面的其他操作。
条款34:了解哪些算法要求使用排序的区间作为参数
1. 查找算法:binary_search、lower_bound、upper_bound 和 equal_range
注意:传入随机访问迭代器时是对数时间,传入其他类型的迭代器时需要线性时间。
2. 集合操作:set_union、set_intersection 和 set_difference 等(线性时间)
3. 合并操作:merge 和 inplace_merge(线性时间)
4. 包含测试:includes 判断一个区间中的所有对象是否都在另一个区间内(线性时间)
5. unique 和 unique_copy 删除每一组连续相等的元素,仅保留其中的一个(线性时间)
注意:这两个函数与 remove 的机制类似,需要使用 erase 进行清理;使用“相等”即 operator== 判断两个对象是否“相同”;其他要求排序区间的算法均使用等价性判断两个对象是否“相同”,排序的指标必须和算法期望的指标一致。