c++ - C++ 是否保证标准容器进行比较时操作数的顺序？

Question

TL;DR:我有一个用例，它很重要是否 WidgetEqualTo()(new_widget, widget_inside_container)或 WidgetEqualTo()(widget_inside_container, new_widget)被称为。

相同的小部件可能会被重新创建很多次，所以我有一个 WidgetPool (为了这个例子的目的，一个围绕 std::vector<const Widget*> 的全局包装器)和一个智能构造函数:

const Widget* combine(const Widget* a, const Widget* b) {
  static std::unordered_map<std::pair<int, int>, int> cache;
  std::pair<int, int> ab = std::make_pair(a->id(), b->id());
  const auto it = cache.find(ab);
  if (it == cache.end()) {
    // The Widget ctor sets this->id() to WidgetPool::size()
    // and appends this to WidgetPool.
    const Widget* result = new Widget(a, b);
    cache[ab] = result->id();
    return result;
  } else {
    return WidgetPool::get_widget(it->second);
  }
}

我还有一个容器，其中按创建顺序插入小部件。说，std::unordered_set<const Widget*, WidgetHash, WidgetEqualTo> , 其中WidgetEqualTo看起来像这样:

struct WidgetEqualTo {
  bool operator()(const Widget* a, const Widget* b) const {
    if (a == b) {
      return true;
    }
    // My Widgets obey the associative law:
    // tedious_comparison(new Widget(new Widget(p, q), r),
    //                    new Widget(p, new Widget(q, r))) == true.
    const bool are_equal = tedious_comparison(a, b);
    if (are_equal) {
      // Cache the result of the comparison.
      // Retain the older Widget.
      if (a->id() < b->id()) {  // (***)
        WidgetPool::set_widget(b->id(), a);
        delete b;
      } else {
        WidgetPool::set_widget(a->id(), b);
        delete a;
      }
    }
    return are_equal;
  }
};

如果WidgetEqualTo()总是用 (new_element, element_already_inside_unordered_set) 调用或者反过来，我可以删除一个标记为 (***) 的测试分支. FWIW，libstdc++ 似乎调用了 WidgetEqualTo()(new_element, old_element) . C++ 标准是否保证这种行为？

Answer 1

没有。

[C++11: 25.2.5/3]: Each unordered associative container is parameterized by Key, by a function object type Hash that meets the Hash requirements (17.6.3.4) and acts as a hash function for argument values of type Key, and by a binary predicate Pred that induces an equivalence relation on values of type Key. Additionally, unordered_map and unordered_multimap associate an arbitrary mapped type T with the Key.

表 17 告诉我们 EqualityComparable 要求:

== is an equivalence relation, that is, it has the following properties:

• For all a, a == a.
• If a == b, then b == a.
• If a == b and b == c, then a == c.

^{(啊!逗号拼接!)}

请注意，比较器的给定语义没有提及给出操作数的方式:

[C++11: 25.2.5/5]: Two values k1 and k2 of type Key are considered equivalent if the container’s key_equal function object returns true when passed those values. [..]

简单地说，如果提供参数的顺序很重要，那么您的程序具有未定义的行为。

这也不是 C++ 的怪癖； equivalence implies symmetry throughout mathematics .