Re: [Boost-users] EqualityComparable of unordered containers

From: Daniel Krügler (dsp_at_[hidden])
Date: 2008-08-19 08:14:57

David Abrahams wrote:
> on Mon Aug 18 2008, Daniel Krügler <dsp-AT-bdal.de> wrote:
> 
>>David Abrahams wrote:
>>
>>>I suggest requiring that the predicates themselves be equality
>>>comparable, and that equal predicates perform the same computation.
>>>Containers with unequal predicates would not be considered equal.
>>
>>Yes, this proposed resolution has also be given by Pablo Halpern
>>in a different mailing channnel. I totally agree that some tagging
>>technique (or concepts in C++0x) would be good idea. 
> 
> 
> I don't see what tagging has to do with my suggestion, and concepts are
> certainly not applicable because we're discussing runtime tests.

I apologize, my nomenclature was wrong. Technically
I meant the application of a SFINAE mechanism with a
corresponding compile-time predicate.

>>I had some
>>resistance concerning requiring EqualityComparable for non-empty
>>predicates (This was his very nice idea: Distinguish empty from
>>non-empty predicates and require EqualityComparable only for non-empty
>>ones), 
> 
> 
> That's not a bad idea.
> 
> 
>>because I thought it would be too intrusive. Maybe I was to
>>strict in my position. The reason for my resistance is that in several
>>scenarios an object type with overloaded operator() has *more*
>>than one operator() overload and by requiring operator== this would
>>have the effect that we don't know, for *which* overload of
>>operator() this EqualityComparable concept would apply.
> 
> 
> An operator== that applied for only one of many overloads would be an
> abomination, especially if the class were empty.

Right, if the class is empty, all operator() overloads
are stateless, but this is not necessarily the case,
if at least one of them is statefull (and therefore the
complete class type is not empty). There are still good
chances, that some (or even all) of them are still stateless
(because they are not influenced by that state).

Or to express the problem in different words: In general
there exists a one-to-many relation between a class
type and it's operator() overloads [acting as predicates],
so the class-type alone is not sufficient to define
an equality of *one* special operator() overload, which
we are interested in. Therefore the predicate equality needs
to be  restricted to a given predicate (a given operator()
overload).

Yesterday night I wrote some code (with concepts) to bind the
predicate of a predicate ;-) to a specific argument-type
sequence of the corresponding operator() overload. I'm quite
sure that this can be retrofitted with C++03 means (SFINAE
and friends). Here is a simplified sketch of this in terms
of C++03 (with many options to do it even better ;-) ):

#include <cstring>
#include <iostream>
#include <ostream>

typedef bool (*streq_t)(const char*, const char*);

bool strcmp_equal(const char* a, const char* b) {
   return std::strcmp(a, b) == 0;
}

bool strcoll_equal(const char* a, const char* b) {
   return std::strcoll(a, b) == 0;
}

// Define USE_EMPTY to make S an empty structure:
//#define USE_EMPTY

// Define ALL_EMPTY to let "is_empty" (as defined below)
// accept everything as empty. Less insane code would use
// boost::is_empty, of course:
//#define ALL_EMPTY

// A class type with more than one operator() overload.
// Depending on the USE_EMPTY #define some are stateful
// or all are stateless:
struct S {
#ifndef USE_EMPTY
   streq_t scmp;
   explicit S(streq_t sc = strcmp_equal) : scmp(sc) {}
#endif
   bool operator()(int a, int b) const {
     return a == b;
   }
   bool operator()(const char* a, const char* b) const {
#ifndef USE_EMPTY
     return scmp(a, b);
#else
     return strcol_equal(a, b);
#endif
   }
};

// Don't take this too serious - use boost::enable_if(_c):
template <bool B, class T = void>
struct enable_if { typedef T type; };

template <class T>
struct enable_if<false, T> {};

// Pseudo is_empty compile-time predicate (all or nothing):
template <typename T>
struct is_empty {
#ifdef ALL_EMPTY
   static const bool value = true;
#else
   static const bool value = false;
#endif
};

template <typename P, typename T1, typename T2 = T1,
typename Enable = void>
struct comparable_predicate;

template <typename P, typename T1, typename T2>
struct comparable_predicate<P, T1, T2, typename 
enable_if<!is_empty<P>::value>::type> {
   static bool eq(const P& a, const P& b) {
     std::cout << "Primary" << std::endl;
     return &a == &b;
   }
};

template <typename P, typename T1, typename T2>
struct comparable_predicate<P, T1, T2, typename 
enable_if<is_empty<P>::value>::type> {
   static bool eq(P, P) {
     std::cout << "IsEmpty spec." << std::endl;
     return true;
   }
};

template <>
struct comparable_predicate<S, int> {
   static bool eq(S, S) {
     std::cout << "(S, int) spec." << std::endl;
     return true;
   }
};

#ifndef USE_EMPTY
template <>
struct comparable_predicate<S, const char*> {
   static bool eq(S a, S b) {
        std::cout << "(S, const char*) spec." << std::endl;
     return a.scmp == b.scmp;
   }
};
#endif

template<typename P, typename T>
bool compare(P p1, P p2, T arg1, T arg2) {
   if (comparable_predicate<P, T>::eq(p1, p2))
     return p1(arg1, arg2) && p2(arg1, arg2);
   else
     return false;
}

int main() {
   S s1, s2;
   bool res = compare(s1, s2, 42, 42);
   std::cout << res << std::endl;
   res = compare(s1, s2, "A", "A");
   std::cout << res << std::endl;
   s2.scmp = strcoll_equal;
   res = compare(s1, s2, "A", "A");
   std::cout << res << std::endl;
   std::cin.get();
}

Concept code is quite similar, with the syntactic sugar
that you can write p1 == p2 in the constrained compare
function (I was too lazy to constrain the C++03 compare()
above) instead of comparable_predicate<P, T>::eq(p1, p2).

The advantage is that you can specialize the predicate for
each overload of operator() separately.

What do you think?

Greetings from Bremen,

- Daniel