使用折叠表达式为数组实现 less 运算符

Question

我正在使用最新的 clang++ 在 c++17 中使用折叠表达式。我尝试使用它为数组实现 less 运算符，我想将其用于固定大小的字符串。

这是我到达的地方。有没有更好的方法来做到这一点，尤其是避免在表达式中分配索引？

使用 "clang++ test_fold_expr_less.cpp -o test_fold_expr_less -std=c++1z" 编译，输出在此处。

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

我将从一些关于折叠表达式的使用的观察和假设开始。

本质上，我们想通过单个折叠表达式来编写字典顺序比较。一旦我们可以确定结果，我们就想摆脱比较。使用一元左折叠

(... OP comparison)

评估为

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

不评估comparison(I)的唯一方法是在之前执行的比较之一中抛出异常和短路。我不认为在这里使用异常是个好主意。所以我会尝试短路。这要求 OP 为 || 或 &&，并且左边的表达式必须求值为布尔值，告诉计算是否继续：

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

comparison(N) -> bool // continue?

在字典顺序比较中，我们继续评估如果lhs 和rhs 的当前元素相等。所以comparison(I)的值一定是lhs[I] == rhs[I]:

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

整个折叠表达式的结果告诉我们两个序列是否完全相等：

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

然而，通过这样做，我们丢失了有关 lhs[I] < rhs[I] 或 lhs[I] > rhs[I] 是我们停止比较的原因的信息。我们可以使用副作用从表达式中获取此信息：

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

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

此时，我们知道 equal == true 或者我们可以使用最后存储到 less 的值来确定总体结果：

return !equal && less;

(如果lhs == rhs则!(lhs < rhs)，所以我们return假。否则，lhs != rhs，我们使用存储在less中的结果。因此， less 如果数组中至少有一个元素，则不需要初始化。）

还有改进的空间：我们可以对less进行赋值，只在需要的时候，也就是[=38]的时候才用它计算lhs[I] < rhs[I]的值=].使用另一个短路：

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

我认为这很神秘。由于使用了逗号表达式，下划线部分的值始终为 false。由于false是||的中性元素，所以整个|| (..)只是起到一个副作用，并没有改变comparison(I)的值，但是这个副作用是仅在 || 的左侧产生 false.

时执行

最后一个改进可以通过认识到如果我们从不分配给 less，我们知道 lhs == rhs 我们可以 return false.

结合起来，我们得到：

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

完整示例：

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

输出——注意我不打印折叠表达式函数的结果，但我将该结果与 std::lexicographical_compare 的结果进行比较。 true 因此意味着两种算法产生相同的结果。

=== 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

使用折叠表达式为数组实现 less 运算符

Implementing operator less for arrays using fold expressions

c++

c++17

fold-expression