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.

Table 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.

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

Does C++ guarantee the order of operands in comparisons made by standard containers?

c++

unordered-set

c++-standard-library

c++11