Strict Weak Ordering and std::set / std::map

Question

#include <iostream>
#include <set>
#include <tuple>

struct Key {
  int field1;
  int field2;

  Key(int field1, int field2) : field1(field1), field2(field2) {}

  bool operator<(const Key& other) const {
    // Is this acceptable?! Seems to work
    if (field2 == 0 || other.field2 == 0) {
      return field1 < other.field1;
    } else {
      return std::tie(field1, field2) < std::tie(other.field1, other.field2);
    }
  }
};

int main() {
    std::set<Key> values{Key(4,3), Key(5,9), Key(5,7), Key(5,8), Key(6,1)};
    std::cout << values.find(Key(5,0))->field2 << std::endl; // Prints '7'
    auto range = values.equal_range(Key(5,0));
    for (auto i = range.first; i != range.second; i++) {
        std::cout << i->field2; // Prints '789'
    }
    return 0;
}

Field2 is not always available in my data, so sometimes I use a wildcard value of 0, which can match any value for which field1 matches. Is this valid in C++ if I never insert elements that have a wildcard value, and only ever look them up in the set? I'm okay with the find function returning any of the values in this case which happens rarely in my code, though hopefully it would be the same value when called repeatedly.

According to the specification, it seems like strict weak ordering is not required for binary_search, which should be the only algorithm used on the data structure when performing a lookup, right? Or is there some undefined behavior I should worry about here?

25.4 Sorting and related operations

... For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values...

25.4.3 Binary search

Answer 1

You're mistaken. std::set::find does a lookup in a binary search tree (in a typical implementation). That might seem like binary search algorithm, but the algorithms in 25.4.3 are not typically used for the lookup. A tree supports only non-random-access iterators and binary search with linear iterators is much slower than a lookup using the knowledge that the data is in a BST.

The comparator of std::set must comply to the Compare concept, which does require strict weak ordering.

Is this valid in C++ if I never insert elements that have a wildcard value, and only ever look them up in the set?

Technically no, since you're breaking the requirements. At the very least you will have indeterminate results, when looking up {x, 0} from a set that contains {x, a} and {x, b}. Either could be found. If that doesn't matter, then I doubt a typical implementation would pose trouble. What you're doing is not guaranteed to work by the standard though, which is enough for most people to shy away from it.