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

From: Joel de Guzman (joel_at_[hidden])
Date: 2008-08-22 00:51:11

Zeljko Vrba wrote:
> 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.

Well, you have to choose between what's ideal and what's practical
at some point. Fusion follows the footsteps of MPL. In MPL map too,
it's the same. The order of the elements matter. I'd bet it's
the same with variant too. Otherwise, the implementation would be
very inefficient at compile time. Or maybe not. Hmmm...

> 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?

You are right. It's best to add the relations operators following
== and !=. Would you provide a patch?

> [*] 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?

Yes it's possible. I'll leave the details as an intellectual exercise :-)

> Does it already exist?

No.

Regards,
-- 
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net