Реализация оператора less для массивов с использованием выражений свертки
Я играю с выражением фолда в C ++ 17 с последним Clang ++. Я попытался реализовать оператор 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;
}
Решение
Я начну с некоторых наблюдений и гипотез, касающихся использования выражений складки здесь.
По сути, мы хотим написать лексикографическое сравнение с помощью одного выражения сгиба. Мы хотим выручить сравнения, когда сможем определить результат. Используя одинарный левый сгиб
(... 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, Следовательно, 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
Другие решения