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.

There is no simple way to use a fold expression to achieve this since comparison operators [don't make much sense](https://stackoverflow.com/questions/37361286/folding-expressions-in-c17-usecase-for-comparison-operators) in fold-expressions. — 康桓瑋, Mar 26 '22 at 16:02
You can make two lists (offset by 1) and compare the pairs. All should be true. — QuentinUK, Mar 26 '22 at 16:04

max66 · Accepted Answer · 2022-03-26T17:25:05.200

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;
}

That solves my use case (using ints). The usage of std::common_type_t is nice. For the sake of code clarity I put a premium on having a single self-contained approach as opposed to helper function/various templates. — gg99, Mar 26 '22 at 19:05
Suggestion: can we do away with the copy? Not that it matters In the case of ints and a constexpr method but assuming we had a custom CT type which was not trivial / constexpr to copy, we could use pointers to a0 and a1 instead which we would dereference for the comparison. — gg99, Mar 26 '22 at 19:11
@gg99 - yes... for complex types with a heavy copy constructor it's a problem. When the arguments are all of the same type (exactly the same type), following your example and using pointers, you can simply write: `A0 const *pc0; A0 const *pc1 = &a0; return ((pc0 = pc1, *pc0 < *(pc1 = &args)) && ...);`. But only if all arguments are of the same type, or this is the recipe for a disaster. — max66, Mar 26 '22 at 19:37

score 1 · Answer 2 · answered Mar 26 '22 at 19:18

1

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) && ...);
  }
}

answered Mar 26 '22 at 19:18

gg99

445
6
12

1

Nice... but the first case (`sizeof...(args) == 0`) isn't required: a fold expression with `&&` as operator return `true` when the list is empty. – max66 Mar 26 '22 at 19:24
The problem I see in your solution is that works when the `args...` of the same type... but when you have different types the `args = &args` assign a poiter of a type in a variable pointer of another type. Not sure but should be UB (undefined behaviour) or even worse. – max66 Mar 26 '22 at 19:31
Wouldn't assigning a pointer of a different type result in a compilation error (absent a reinterpret_cast) unless there is a natural semantic fit (e.g. conversion child to base)? Do you have an example of a genuine UB scenario? – gg99 Mar 26 '22 at 19:40
Yes, your right... I'm an old C programmer and I tend to forget that there is this limitation in C++... but remain the problem: your solution is a good solution but works only when the type ore equals or pointer compatibles (so doesn't works comparing `int`s with `long`s, for example). – max66 Mar 26 '22 at 19:48

score 0 · Answer 3 · answered Mar 26 '22 at 16:27

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

score 0 · Answer 4 · answered Mar 26 '22 at 17:35

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

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

4 Answers4