Re: [Boost-users] EqualityComparable of unordered containers

19 Aug 2008

      David Abrahams wrote:
...
on Mon Aug 18 2008, Daniel Krügler  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 
struct enable_if { typedef T type; };

template <class T>
struct enable_if {};

// 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 
struct comparable_predicate;

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

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

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

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

template
bool compare(P p1, P p2, T arg1, T arg2) {
   if (comparable_predicate::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::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