6

我正在使用最新的 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;
}
4

1 回答 1

6

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

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

(... OP comparison)

评估为

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

不评估 的唯一方法是在之前执行的比较之一和短路comparison(I)中抛出异常。我不认为在这里使用异常是一个好主意。所以我会尝试短路。这需要是or ，并且左边的表达式必须计算为一个布尔值，告诉计算是否继续：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 == rhsthen !(lhs < rhs)，那么我们返回 false。否则，lhs != rhs我们使用存储在 中的结果less。因此，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);
}

输出——注意我不打印 fold-expression-function 的结果，但我将该结果与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
于 2015-07-08T19:22:57.627 回答