Test if elements are sorted with C++17 fold-expression

Question

I am looking for a way to check that arguments are sorted using a c++ fold expression. The naive approach:

template <typename... Args>
bool are_strictly_increasing(Args const&... args) {
    return (args < ...);
}

Does not work as it expands to ((arg0 < arg1) < arg2) < ... which ends up comparing bool to whatever the typename Args is (that can be treacherous when using e.g. int as it compiles unless you crank up warning levels).

The trick to single out the first argument in the list works for checking all elements are equal:

template <typename Arg, typename... Args>
bool are_all_equal(Arg const& arg0, Args const&... args) {
    return ((arg0 == args) && ... );
}

but it won't work here for operator< since it would only test whether all arguments are greater than the first one.

Answer 1

It seems to me that is better if your first argument is isolated anyway

template <typename A0, typename... Args>
constexpr bool are_strictly_increasing(A0 const & a0, Args const&... args)

Supposing there is a common type for the arguments

using CT = std::common_type_t<A0, Args...>;

and given two variable of common type, one initialized with the first argument a0

CT c0, c1 = a0;

your fold expression can be

return ((c0 = c1, c0 < (c1 = static_cast<CT>(args))) && ...);

Without isolating the first argument, there is the problem of the inizialization of c1. You can try with std::numeric_limits<CT>::min(), but the code fail if the first value of args... is equal to this value (that isn't improbable when you check unsigned values).

The following is a full compiling example

#include <iostream>

template <typename A0, typename... Args>
constexpr bool are_strictly_increasing(A0 const & a0, Args const&... args)
{
  using CT = std::common_type_t<A0, Args...>;

  CT c0, c1 = a0;

  return ((c0 = c1, c0 < (c1 = static_cast<CT>(args))) && ...);
}

int main()
{
  std::cout << are_strictly_increasing(0, 1, 2, 3, 4) << std::endl;
  std::cout << are_strictly_increasing(0, short{1}, 2l, 3u, 4ull) << std::endl;
  std::cout << are_strictly_increasing(0, 1, 2, 3, 4, 4) << std::endl;
  std::cout << are_strictly_increasing(0, 1, 21, 3, 4, 4) << std::endl;
}

Answer 2

Inspired by @max66's answer I went for that refinement which avoids copies.
It uses a single auxiliary variable thanks to the use of the ternary operator with a nested comma operator in ((*arg < args ? (arg = &args, true) : false)

template <typename Arg, typename... Args>
bool are_strictly_increasing(Arg const& arg0, Args const&... args) {

  if constexpr (sizeof...(args) == 0) {
    (void) arg0; // avoid unreferenced formal parameter compiler warning
    return true;
  } else {
    Arg const* arg = &arg0;
    return ((*arg < args ? (arg = &args, true) : false) && ...);
  }
}

Answer 3

Fold expressions are cool, but in this case is better to drop them and use old solutions with recursion:

template <typename Arg1, typename Arg2>
bool are_strictly_increasing(Arg1 const& a, Arg2 const& b)
{
    return a < b;
}

template <typename Arg1, typename Arg2, typename... Args>
bool are_strictly_increasing(Arg1 const& a, Arg2 const& b, Args const&... args)
{
    return (a < b) && are_strictly_increasing(b, args...);
}

https://godbolt.org/z/3E58P5n46

Answer 4

Although it might be easier to solve this task without fold expression, still it is solvable with it if to use extra helper function:

Try it online!

#include <tuple>
#include <type_traits>
#include <iostream>
#include <iomanip>

template <typename ... Args, std::size_t Index0, std::size_t ... Indices>
bool helper(std::tuple<Args...> const & args,
       std::index_sequence<Index0, Indices...> const &) {
    return ((std::get<Indices - 1>(args) <
             std::get<Indices>(args)) && ...);
}

template <typename ... Args>
bool are_strictly_increasing(Args const & ... args) {
    return helper(std::tie(args...), std::index_sequence_for<Args...>{});
}

int main() {
    std::cout << std::boolalpha
        << are_strictly_increasing(false, true, 2, 3) << std::endl
        << are_strictly_increasing(3, 2, 1) << std::endl;
}

Output:

true
false