Re: [Boost-users] how to make fusion::pair less-than-comparable?

From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2008-08-21 11:56:23

On Thu, Aug 21, 2008 at 10:35:22PM +0800, Joel de Guzman wrote:
> 
> The reason is I don't know (yet) how to do 1 :-) If there are some
> suggestions, I see no reason why it can't be added to the library.
> So... how do you compare a half-static-half-runtime pair? Compare
> just the value part? How about pairs with different static parts
> but comparable runtime parts, how do they compare? Simply disallow?
> Comments, suggestions welcome.
> 

Hmm, an inverted email: first rationale, then conclusion.  I asked whether

typedef map<pair<pin, unsigned>, pair<net, unsigned> > Map1;
typedef map<pair<net, unsigned>, pair<pin, unsigned> > Map2;

were different because either way makes sense, depending on whether you view
the template list as an unordered set or as an ordered list.  My "intuition",
coming from the run-time case of std::map would lead me to believe that types
Map1 and Map2 were the same.  Namely, std::map  is an unordered set of (K,V)
pairs.  So, { (a, 1), (b, 2), (c, 3) } and { (c, 3), (a, 1), (b, 2) } have
different layout, but for the purpose of asking "which number the letter 'a'
is mapped to", they are the same mapping.  This coincides with the
mathematical definition of function equality: f1 == f2 if domain(f1) ==
domain(f2), codomain(f1) == codomain(f2), and pointwise equality, f1(x) ==
f2(x) for each x from the domain.  Mathematicians also sometimes say map
instead of function:

http://mathworld.wolfram.com/Map.html

In the light of the above, fusion::map might be kinda misnomer, depending on
what you put into the definition of a map.  fusion::map is a mapping from types
to types, and both Map1 and Map2 assign pin->unsigned and net->unsigned, hence
they should be considered as being the same in the mathematical meaning of
"map", but they are not the same in fusion.  I like this *now* because that's
exactly what I need *now* :-)  If I wanted it the other way around, I'd
probably dislike it[*] :-)

So, Map1 and Map2 are not the same type, because of the C++'s strong type
system combined with an implementation detail as a vector of pairs.  The above
consideration lead me to believe that the comparison of pair<K1, T1> and
pair<K2, T2> is defined only if the compiler thinks that K1 and K2 are the
same[**] type; in that case the result would be the same as the comparison of
T1 and T2.  Such definition would be consistent with the already present strong
typing that differentiates between Map1 and Map2 which are conceptually the
same (mathematical) mapping.

[**] Same, as really being identical.  Possible conversions from a pointer to
void* or to a pointer to a public base class would not be considered for the
purposes of comparisons.

Now that I've written all of this, your question comes a bit surprising:
operators == and != are already present.. how do they behave now for different
K1 and K2?  Why not extend them in the same way to other relational operators?

==

[*] Just as an intellectual curiosity, I don't need this now: how would
unordered_map be implemented in fusion (structure that would make Map1 and Map2
same types)?  Is it possible to do it at all within the C++'s type system?
Does it already exist?