《Effective STL》中值得注意的几个条款

发表于

看完《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<
    class Key,
    class Compare = std::less<Key>, // 默认是 operator<
    class Allocator = std::allocator<Key>
> class set;

注意：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;
...
bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
     // 返回lhs的质量是否好于rhs的质量
}
...
partial_sort(w.begin(),
             w.being() + 20, // 前两个参数指出一个区间
             w.end(),
             qualityCompare); // 将质量最好的 20 个元素顺序放在 w 的前 20 个位置上

2. nth_element 用于排序一个区间，使得位置 n 上的元素正好是排序后的第 n 个元素

nth_element(w.begin(),
            w.being() + 19, // 指出这个位置n，即第20个元素
            w.end(),
            qualityCompare);

3. nth_element 用来找一个区间的中间值（或其他，如具有 75% 质量的元素）

vector<Widget>::iterator goalPositon = w.begin() + w.size() / 2;
nth_element(w.begin(), goalPositon, end, qualityCompare);

4. partition 把满足某条件的元素移到前部，返回指向第一个不满足条件的元素的迭代器

bool hasAcceptableQuality(const Widget& w)
{
     // 判断w的质量是否满足条件
}

vector<Widget>::iterator goodEnd =
partition(w.begin(),
          w.end(),
          hasAcceptableQuality);

注意：

  • 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== 判断两个对象是否“相同”；其他要求排序区间的算法均使用等价性判断两个对象是否“相同”，排序的指标必须和算法期望的指标一致。

0%