Implementing operator less for arrays using fold expressions

Question

I am playing around with fold expression in c++17 with the latest clang++. I tried to implement the less operator for an array using this which I want to use for fixed size strings.

Here is where I got to. Is there a better way to do this, especially avoiding assigning the index in the expression?

Compiling this using "clang++ test_fold_expr_less.cpp -o test_fold_expr_less -std=c++1z" and the output is here.

prompt$ ./test_fold_expr_less
=== less ===
0
1
0
0
1
0
0
0
0
1
1
1

#include <iostream>
#include <utility>

std::uint64_t arr1[8] = {1, 7, 2, 4, 8, 9, 3, 6};
std::uint64_t arr2[8] = {1, 7, 2, 4, 8, 9, 3, 6};
std::uint64_t arr3[8] = {1, 7, 2, 5, 8, 9, 3, 6};
std::uint64_t arr4[8] = {1, 7, 2, 3, 8, 9, 3, 6};

struct less_t
{
    template < typename T, std::size_t N, std::size_t... I >
    bool impl(T const (& lhs)[N], T const (& rhs)[N], std::index_sequence < I... >) const
    {
      std::size_t i{0};
      if (((i = I, (lhs[I] < rhs[I]) ? true : lhs[I] != rhs[I]) || ...))
          return lhs[i] < rhs[i];
      else
          return false;
    }

    template < typename T, std::size_t N >
    bool operator () (T const (& lhs)[N], T const (& rhs)[N]) const
    {
        return impl(lhs, rhs, std::make_index_sequence < N >());
    }
};

int main()
{
    std::cout << "=== less ===" << std::endl;
    less_t const less{};
    std::cout << less(arr1, arr2) << std::endl;
    std::cout << less(arr1, arr3) << std::endl;
    std::cout << less(arr1, arr4) << std::endl;

    std::cout << less(arr2, arr1) << std::endl;
    std::cout << less(arr2, arr3) << std::endl;
    std::cout << less(arr2, arr4) << std::endl;

    std::cout << less(arr3, arr1) << std::endl;
    std::cout << less(arr3, arr2) << std::endl;
    std::cout << less(arr3, arr4) << std::endl;

    std::cout << less(arr4, arr1) << std::endl;
    std::cout << less(arr4, arr2) << std::endl;
    std::cout << less(arr4, arr3) << std::endl;
}

Answer 1

I'll start with some observations and hypotheses concerning the use of fold-expressions here.

Essentially, we want to write a lexicographical comparison via a single fold-expression. We want to bail out of the comparisons once we can determine the result. Using a unary left fold

(... OP comparison)

evaluates to

(  ( (comparison(0) OP comparison(1)) OP comparison(2) )...  )

The only ways to not evaluate the comparison(I) are throwing an exception in one of the comparisons executed earlier and short-circuiting. I don't think using exceptions is a good idea here. So I'll try short-circuiting. This requires OP to be either || or &&, and the expression to the left must evaluate to a bool that tells the computation whether or not to continue:

(  ( (comparison(0) && comparison(1)) && comparison(2) )...  )

comparison(N) -> bool // continue?

In lexicographical comparison, we continue evaluating if the current elements of the lhs and rhs are equal. So the value of comparison(I) must be lhs[I] == rhs[I]:

#define comparison(I) (lhs[I] == rhs[I])

The result of the whole fold-expression then tells us whether or not both sequences are entirely equal:

auto equal = (... && comparison(I));

However, by doing this, we lose the information about whether lhs[I] < rhs[I] or lhs[I] > rhs[I] was the reason we stopped the comparison. We can get this information out of the expression by using a side-effect:

#define comparison(I) (less = lhs[I] < rhs[I], lhs[I] == rhs[I])

bool less;
auto equal = (... && comparison(I));

At this point, we know either equal == true or we can use the value last stored to less to determine the overall result:

return !equal && less;

(If lhs == rhs then !(lhs < rhs), so we return false. Otherwise, lhs != rhs and we use the result stored in less. Therefore, less doesn't need to be initialized if we have at least one element in the array.)

There is still room for improvement: We can perform the assignment to less, and with it the value computation of lhs[I] < rhs[I] only when we need it, that is, only when lhs[I] != rhs[I]. Using another short-circuit:

#define comparison(I) (lhs[I] == rhs[I] || (less = lhs[I] < rhs[I], false))
//                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I'd consider this quite cryptic. The value of the underlined part is always false due to the use of a comma-expression. Since false is the neutral element of ||, the whole || (..) only performs a side-effect but doesn't change the value of comparison(I), but this side-effect is only performed if the left-hand side of || yields false.

One last improvement can be achieved by recognizing that if we never assign to less, we know that lhs == rhs and we can return false.

Combined, we get:

bool less = false;
auto equal = (... && (lhs[I] == rhs[I] || (less = lhs[I] < rhs[I], false)));
(void)equal; // we don't need you
return less;

---

Complete example:

#include <iostream>
#include <utility>

struct loud
{
    std::uint64_t v;
    loud(int x) : v(x) {}
    static auto& opEqual() { static int v = 0; return v; }
    static auto& opLess() { static int v = 0; return v; }
    friend bool operator==(loud l, loud r) { return opEqual()++, l.v == r.v; }
    friend bool operator<(loud l, loud r) { return opLess()++, l.v < r.v; }

    static void print_stats(std::ostream& o) {
        o << "operator< " << opLess() << " operator== " << opEqual();
    }
    static void reset_stats() {
        opEqual() = opLess() = 0;
    }
};

loud arrs[][8] = {
 {1, 7, 2, 4, 8, 9, 3, 6}
 ,{1, 7, 2, 4, 8, 9, 3, 6}
 ,{1, 7, 2, 5, 8, 9, 3, 6}
 ,{1, 7, 2, 3, 8, 9, 3, 6}
};

struct less_t
{
    template < typename T, std::size_t N, std::size_t... I >
    bool impl(T const (& lhs)[N], T const (& rhs)[N], std::index_sequence < I... >) const
    {
            bool less = false;
    auto equal = (... && (lhs[I] == rhs[I] || (less = lhs[I] < rhs[I], false)));
    (void)equal; // we don't need you
    return less;
    }

    template < typename T, std::size_t N >
    bool operator () (T const (& lhs)[N], T const (& rhs)[N]) const
    {
        return impl(lhs, rhs, std::make_index_sequence < N >());
    }
};

template<class T, int N>
void test(T const (&lhs)[N], T const (&rhs)[N])
{
    auto const stdres = std::lexicographical_compare(lhs, lhs+N, rhs, rhs+N);
    loud::reset_stats();
    auto const foldres = less_t{}(lhs, rhs);
    std::cout << (stdres == foldres) << " -- ";
    loud::print_stats(std::cout);
    std::cout << "\n";
}

int main()
{
    std::cout << std::boolalpha;
    std::cout << "=== less ===" << std::endl;
    for(auto& lhs : arrs)
           for(auto& rhs : arrs)
                test(lhs, rhs);
}

Output -- note I do not print the result of the fold-expression-function, but I compare that result to the result of std::lexicographical_compare. true therefore means both algorithms produced the same result.

=== less ===
true -- operator< 0 operator== 8
true -- operator< 0 operator== 8
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 0 operator== 8
true -- operator< 0 operator== 8
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 0 operator== 8
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 1 operator== 4
true -- operator< 0 operator== 8