使用折叠表达式为数组实现较少的运算符

Question

我正在使用最新的clang ++在c ++ 17中使用fold表达式.我尝试使用这个为数组实现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

我将从这里开始讨论使用fold-expressions的一些观察和假设.

基本上,我们希望通过单个fold-expression编写词典比较.一旦我们确定结果,我们希望摆脱比较.使用一元左折

(... OP comparison)

评估为

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

不评估的唯一方法comparison(I)是在之前执行的比较和短路之一中抛出异常.我不认为使用例外是一个好主意.所以我会尝试短路.这需要是或者,并且左边的表达式必须求值为bool,告诉计算是否继续: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])

然后整个fold-expression的结果告诉我们两个序列是否完全相等:

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.因此,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