每周技巧 #132：避免冗余的 map 查找

本节阅读量:

本文翻译自 Abseil 官网的 Tip of the Week #132: Avoid Redundant Map Lookups。

原文最初作为 TotW #132 发布于 2017 年 3 月 30 日。

作者：Matt Kulukundis

更新于 2019 年 11 月 25 日。

快捷链接：abseil.io/tips/132

“正是寻找 Snark 的地方！” 钟人喊道，当他小心地让船员登岸；他用缠在每个人头发里的手指，把他们支撑在潮水之上。

“正是寻找 Snark 的地方！我说过两遍：这本身就该鼓舞船员。正是寻找 Snark 的地方！我说过三遍：我告诉你三次的事就是真的。”

– Lewis Carroll，《猎鲨记》

各种形态的关联容器是 C++ 中最常见的抽象之一。有几种常见模式会让我们做不必要的工作。下面是一些避免额外成本的技巧。

累积结果

有时 map 用来收集共同的 key 并聚合信息。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 糟糕代码：key 字符串在两个 map 中都被复制
absl::flat_hash_map<std::string, int> word_counts;
absl::flat_hash_map<std::string, std::vector<std::string>> word_origins;
for (const auto& [origin, words] : origin_to_words) {
  for (const std::string& w : words) {
    if (!word_counts.contains(w)) {      // 第 1 次查找
      InsertOrDie(&word_counts, w, 0);   // 第 2 次查找；第 1 次额外字符串复制
    }
    ++word_counts[w];                    // 第 3 次查找

    if (!word_origins.contains(w)) {     // 第 4 次查找
      InsertOrDie(&word_origins, w, {}); // 第 5 次查找；第 2 次额外字符串复制
    }
    word_origins[w].push_back(origin);   // 第 6 次查找
  }
}

当人们忘记 operator[] 会在 key 尚不存在时插入一个值初始化的 V 实例时，这种模式相当常见。因此我们可以直接写：

1
2
3
4
5
6
7
8
9


// key 字符串在两个 map 中都被复制
absl::flat_hash_map<std::string, int> word_counts;
absl::flat_hash_map<std::string, std::vector<std::string>> word_origins;
for (const auto& [origin, words] : origin_to_words) {
  for (const std::string& w : words) {
    ++word_counts[w];                    // 第 1 次查找
    word_origins[w].push_back(origin);   // 第 2 次查找
  }
}

更进一步，把两个 map 合并成一个结构体，以避免重复查找和 key 的双份存储。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


struct WordInfo {
  int count = 0;
  std::vector<std::string> origins;
};

absl::flat_hash_map<std::string, WordInfo> words_to_info;
for (const auto& [origin, words] : origin_to_words) {
  for (const std::string& w : words) {
    auto& info = words_to_info[w];
    ++info.count;
    info.origins.push_back(origin);
  }
}

只要默认值正好匹配累积的基础情况，这种模式就适用。它读起来也非常清晰。

一次性初始化

另一些时候，map 会缓存重型计算或复杂对象。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// 糟糕代码
class CobblerCache {
 public:
  const CobblerInterface& GetCobbler(const std::string& key) {
    if (!cobblers_.contains(key)) {                          // 第 1 次查找
      InsertOrDie(&cobblers_, key, FluevogMaker::Create());  // 第 2 次查找
    }
    return *FindOrDie(cobblers_, key);                       // 第 3 次查找
  }

 private:
  absl::flat_hash_map<std::string, std::unique_ptr<CobblerInterface>> cobblers_;
};

这里可以利用 std::unique_ptr 默认构造为 null 的事实，检测 operator[] 何时插入了新值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class CobblerCache {
 public:
  const CobblerInterface& GetCobbler(const std::string& key) {
    auto& cobbler = cobblers_[key];
    if (cobbler == nullptr) {
      cobbler = FluevogMaker::Create();
    }
    return *cobbler;
  }

 private:
  absl::flat_hash_map<std::string, std::unique_ptr<CobblerInterface>> cobblers_;
};

注意，cobbler 是对 map 中 value 的引用，这让我们可以在 operator[] 调用之后设置该值，而不需要任何额外工作。只要 mapped_type() 的默认值也能充当某种哨兵，这种模式就适用。

安全查找

有时你只是想在 map 中查找某个东西，找不到就安全退出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// 糟糕代码
class CobblerCache {
 public:
  std::unique_ptr<Shoe> MaybeMakeShoe(const std::string& key,
                                      const ShoeSpec& spec) {
    if (!cobblers_.contains(key)) return nullptr;      // 第 1 次查找
    return FindOrDie(cobblers_, key)->MakeShoe(spec);  // 第 2 次查找
  }

 private:
  absl::flat_hash_map<std::string, std::unique_ptr<CobblerInterface>> cobblers_;
};

可以改写成下面这样。

1
2
3
4
5
6
7
8


class CobblerCache {
 public:
  std::unique_ptr<Shoe> MaybeMakeShoe(const std::string& key,
                                      const ShoeSpec& spec) {
    auto it = cobblers_.find(key);
    if (it == cobblers_.end()) return nullptr;
    return it->second->MakeShoe(spec);
  }

统计冲突

有时你想在未找到时插入，并据此做出反应。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// 糟糕代码
int duplicates = 0;
absl::flat_hash_set<std::string> seen;

for (const std::string& id : ids) {
  if (seen.contains(id)) {  // 第 1 次查找
    ++duplicates;
  } else {
    seen.insert(id);        // 第 2 次查找
  }
}

原生 API 再次提供了替代方案。

提示：回忆一下，absl::flat_hash_set::insert（和 map::insert 一样）会返回一个 pair：一个指向插入元素（或已有元素）的迭代器，以及一个表示是否发生插入的 bool。

1
2
3
4
5
6
7
8


int duplicates = 0;
absl::flat_hash_set<std::string> seen;

for (const std::string& id : ids) {
  if (!seen.insert(id).second) {
    ++duplicates;
  }
}

最佳实践

通常可以在不牺牲可读性的情况下高效使用关联容器。学习并使用那些允许你做到这一点的 API。容器类型使用得如此普遍，因此可以假设你的读者熟悉这些技巧。

每周技巧 #131：特殊成员函数和 `= default`

每周技巧 #134：`make_unique` 和私有构造函数

本节目录