Way to determine proper predicate for templated types

Question

Suppose I have a function which looks like this:

template <class In, class In2>
void func(In first, In last, In2 first2);

I would like this function to call another function which accepts a predicate. My initial instinct was to do something like this:

template <class In, class In2>
void func(In first, In last, In2 first2) {
    typedef typename std::iterator_traits<In>::value_type T;
    other_func(first, last, first2, std::less<T>());
}

But there is a problem, what if In and In2 are iterators to different types? For example, char* vs int*. Depending on which is In and which is In2 the predicate may be truncating values during its comparison. For example, if In is char* then std::less<char> will be called even if In2 is an int*.

When ::operator< is given two parameters, the compiler is able to deduce the correct type and the standard type promotion rules apply. However, when selecting a predicate to pass to a function, there is no oportunity to have this happen. Is there some clever way to figure out which version of std::less<> I want to pass based on In and In2?

EDIT:

The following example illustrates the problem:

unsigned int x = 0x80000000;
unsigned char y = 1;
std::cout << std::less<unsigned char>()(x, y) << std::endl;
std::cout << std::less<unsigned int>()(x, y) << std::endl;

will output:

1
0

EDIT:

After thinking about it, what I would really like is to be able to do something like this:

typedef typeof(T1() < T2()) T;
other_func(first, last, first2, std::less<T>());

I suppose I could use gcc's __typeof__ extension..., but I don't love that idea either. Any way to get that net effect in a standard conformant way?

Answer 1

If your requirements on the algorithm are such that In's value_type need not be the same as In2's value type, then I would leave the template parameters as you have them; otherwise they should be the same.

Whether they are the same or different it is up to the client of your routine to meet the prerequisites of the algorithm, which you are allowed to specify. For example, here you could require that the value_type of In be the same as the value_type of In2. If that holds true, then, the function should compile and be correct as the client expects.

In such a case, then, you can pass a std::less<T> instance of the value_type of either template type, and you should be fine.

However, if the client violates that precondition (as in the example you provide above where char is not the same as int), then it will be up to the client, not you, to correct the compile-time error.

Make sure your algorithm is well-documented, to say the least :)

Answer 2

Taking SGI's old implementation of std::equal as an example, STL algorithms handle this kind of situation by having two versions of the same algorithm: one that uses the intrinsic < operator which the compiler deduces at compile time, and one that takes a user-defined binary predicate so the user can use any types they'd prefer:

template <class _InputIter1, class _InputIter2>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2) {
  __STL_REQUIRES(_InputIter1, _InputIterator);
  __STL_REQUIRES(_InputIter2, _InputIterator);
  __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
                 _EqualityComparable);
  __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
                 _EqualityComparable);
  for ( ; __first1 != __last1; ++__first1, ++__first2)
    if (*__first1 != *__first2)
      return false;
  return true;
}

template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _BinaryPredicate __binary_pred) {
  __STL_REQUIRES(_InputIter1, _InputIterator);
  __STL_REQUIRES(_InputIter2, _InputIterator);
  for ( ; __first1 != __last1; ++__first1, ++__first2)
    if (!__binary_pred(*__first1, *__first2))
      return false;
  return true;
}

(Note: Old SGI STL code taken from here.)

Answer 3

I seemed to remember that there was a traits for this in boost, but I can't find it after a quick search. If you are no more successful than me, you can construct it yourself,

template <typename T1, typename T2>
struct least_common_promotion;

template <>
struct least_common_promotion<short, int>
{
    typedef int type;
};

but you'll have to specify quite a few explicit specializations. The type traits library of boost can perhaps help you reduce their number.

Edit: I feel stupid, such kind of things are needed for operation (where the result type depend on the operands types), but not for predicates (where the result type is bool). You can simply write:

template <class T1, T2>
struct unhomogenous_less : public std::binary_function<T1, T2, bool>
{
   bool operator()(T1 const& l, T2 const& r) const
   { return l < r; }
};

...

typedef typename std::iterator_traits<In>::value_type value_type_1;
typedef typename std::iterator_traits<In2>::value_type value_type_2;
other_func(first, last, first2, unhomogenous_less<value_type_1, value_type_2>());