Гарантирует ли 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]: Каждый неупорядоченный ассоциативный контейнер параметризован Key по типу объекта функции Hash что соответствует Hash требования (17.6.3.4) и действует как хеш-функция для значений аргументов типа Key и двоичным предикатом Pred что вызывает отношение эквивалентности для значений типа Key, Дополнительно, unordered_map а также unordered_multimap ассоциировать произвольный сопоставленный тип T с Key,

Таблица 17 говорит нам EqualityComparable требования:

== является отношением эквивалентности, то есть имеет следующие свойства:

• Для всех a, a == a,
• Если a == b , затем b == a ,
• Если a == b а также b == c, затем a == c,

^{(Гах! запятая!)}

И обратите внимание, что в данной семантике компаратора не упоминается, каким образом обойти операнды:

[C++11: 25.2.5/5]: Два значения k1 а также k2 типа Key считаются эквивалентными, если контейнер key_equal функция объекта возвращает true когда прошли эти значения. [..]

Проще говоря, ваша программа имеет неопределенное поведение, если имеет значение, в каком порядке передаются аргументы.

Это тоже не странность C++; эквивалентность подразумевает симметрию всей математики.