c++ - 使用折叠表达式为数组实现 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要么是||或 && , 左边的表达式必须求值为 bool 值，告诉计算是否继续:

(  ( (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) ，那么我们返回 false。否则，我们返回 lhs != rhs 并且我们使用存储在 less 中的结果。因此，如果我们有 at，则不需要初始化 less数组中至少有一个元素。)

还有改进的余地:我们可以执行分配给less , 以及 lhs[I] < rhs[I] 的值计算只有当我们需要的时候，也就是只有当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我们可以返回 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