TransparentSet.cpp

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <string>
#include <tuple>

using namespace std;

struct A { int i; };   bool operator<(const A&x, const A&y) { return x.i < y.i; }
struct B { float f; }; bool operator<(const B&x, const B&y) { return x.f < y.f; }
struct C { char c; };  bool operator<(const C&x, const C&y) { return x.c < y.c; }

typedef tuple<A, B, C> TABC;
typedef tuple<A, B> TAB;

struct TupCompare {
  typedef void is_transparent;
  bool operator() (const TABC &x, const TABC &y) const
  { return x < y; }

  bool operator() (const TABC &x, const TAB  &y) const {
  if (get<0>(x) < get<0>(y)) return true;
  if (get<0>(y) < get<0>(x)) return false;
  if (get<1>(x) < get<1>(y)) return true;
  if (get<1>(y) < get<1>(x)) return false;
  return false;
  }

  bool operator() (const TAB  &x, const TABC &y) const {
  if (get<0>(x) < get<0>(y)) return true;
  if (get<0>(y) < get<0>(x)) return false;
  if (get<1>(x) < get<1>(y)) return true;
  if (get<1>(y) < get<1>(x)) return false;
  return false;
  }

};

int main () {
	set<TABC, TupCompare> s2;
	s2.emplace(A{1}, B{2.f}, C{'3'});
	s2.emplace(A{1}, B{2.f}, C{'4'});
	s2.emplace(A{1}, B{2.f}, C{'5'});
	s2.emplace(A{4}, B{5.f}, C{'6'});
	
	for (const auto el: s2)
		cout << get<0>(el).i << ' ' << get<1>(el).f << ' ' << get<2>(el).c << endl;
		
	auto eq = s2.equal_range(TAB(A{1}, B{2.f}));
	cout << distance(eq.first, eq.second) << endl;
}

This is a neat idea, but unfortunately it doesn't work out in practice for one notable flaw. The issue comes from the fact that TupCompare basically says that Tup<A, B> can be equal to Tup<A, B, C>. If you do find with a Tup<A, B> instance you will get an actual value found as opposed to the desired missing entry (since there's no entry associated with a Tup<A, B> instance).

One workaround is to use std::equal_range which can take in a custom comparison function, but obviously that's not as efficient as actually knowing the internal map data structure since it is a red-black tree usually. The implementations would be similar asymptotically I believe, but do differ.

But as for being able to do heterogenous lookup on the map with equal_range via a subset of the key, it does not seem it can be done without that other side effect.

I disagree - it does work in practice. But - as you say - this also affects the results of calls like find.

The surprising thing to me was in line 51, where equal_range returned a range that had more than one element in it, even though this is a set, which contains unique entries.

Is it useful? That's a different question.

In the heat of writing a comment, I did overstep in saying it doesn't work in practice. If it works for a scenario depends on the scenario.

The important point though is that there is a very critical change in behavior to operations like find and it's a type of error that is unexpected (usually it's not a concern if you passed in the right type of lookup key) and can never be flagged by a compiler. With no warning on the code sample or examples of issues, it feels like it's presented as a free lunch.