вопрос про operator<() для std::tuple
От: niXman Ниоткуда https://github.com/niXman
Дата: 29.04.15 20:53
Оценка:
в libstdc++ оно реализовано так:
// This class performs the comparison operations on tuples
template<typename _Tp, typename _Up, size_t __i, size_t __size>
struct __tuple_compare {
    static constexpr bool __eq(const _Tp& __t, const _Up& __u) {
        return bool(std::get<__i>(__t) == std::get<__i>(__u))
        && __tuple_compare<_Tp, _Up, __i + 1, __size>::__eq(__t, __u);
    }
    
    static constexpr bool __less(const _Tp& __t, const _Up& __u) {
        return bool(std::get<__i>(__t) < std::get<__i>(__u))
            || (!bool(std::get<__i>(__u) < std::get<__i>(__t)) // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< вопрос в этой строке
            && __tuple_compare<_Tp, _Up, __i + 1, __size>::__less(__t, __u));
    }
};

template<typename _Tp, typename _Up, size_t __size>
struct __tuple_compare<_Tp, _Up, __size, __size> {
    static constexpr bool __eq(const _Tp&, const _Up&) { return true; }
    static constexpr bool __less(const _Tp&, const _Up&) { return false; }
};

template<typename... _TElements, typename... _UElements>
constexpr bool
operator<(const tuple<_TElements...>& __t, const tuple<_UElements...>& __u) {
    static_assert(sizeof...(_TElements) == sizeof...(_UElements), "tuple objects can only be compared if they have equal sizes.");
    using __compare = __tuple_compare<tuple<_TElements...>, tuple<_UElements...>, 0, sizeof...(_TElements)>;
    return __compare::__less(__t, __u);
}

интересующая строка отмечена.
вопрос в том, зачем менять аргументы местами и проверять что они не меньше?
т.е. тут мы берем по одному элементу из обеих тьюплов по индексу '__i', проверяем на меньше, а потом меняем тьюплы местами, берем те же самые элементы, и проверяем на НЕ меньше.

в чем смысл?


спасибо.
пачка бумаги А4 стОит 2000 р, в ней 500 листов. получается, лист обычной бумаги стОит дороже имперского рубля =)
Re: вопрос про operator<() для std::tuple
От: Nikе Россия  
Дата: 29.04.15 20:57
Оценка: 9 (1) +2
Здравствуйте, niXman, Вы писали:

Если первый аргумент меньше — выходим сразу, иначе, если аргументы равны — проверяем следующую пару, иначе фалс. В чём проблема?
Нужно разобрать угил.
Отредактировано 29.04.2015 20:58 Nikе . Предыдущая версия .
Re[2]: вопрос про operator<() для std::tuple
От: niXman Ниоткуда https://github.com/niXman
Дата: 29.04.15 21:08
Оценка:
Здравствуйте, Nikе, Вы писали:

N>Если первый аргумент меньше — выходим сразу, иначе, если аргументы равны — проверяем следующую пару, иначе фалс. В чём проблема?
наверное я чего-то не так объяснил...
вопрос вот в чем:
static constexpr bool __less(const _Tp& __t, const _Up& __u) {
        return bool(std::get<__i>(__t) < std::get<__i>(__u))
            || (!bool(std::get<__i>(__u) < std::get<__i>(__t)) // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< вопрос в этой строке
            && __tuple_compare<_Tp, _Up, __i + 1, __size>::__less(__t, __u));
}

а именно(чуть дооформлю):
auto l = std::get<__i>(__t);
auto r = std::get<__i>(__u);

bool ok = (l < r) || (!(r < l));

(вроде ничего не напутал)

вопрос в том, зачем тут еще и проверка (!(r < l))?
пачка бумаги А4 стОит 2000 р, в ней 500 листов. получается, лист обычной бумаги стОит дороже имперского рубля =)
Re[2]: вопрос про operator<() для std::tuple
От: niXman Ниоткуда https://github.com/niXman
Дата: 29.04.15 21:10
Оценка:
Здравствуйте, Nikе, Вы писали:

N>Если первый аргумент меньше — выходим сразу, иначе, если аргументы равны — проверяем следующую пару, иначе фалс. В чём проблема?
ах да, все верно! %)
спасибо!

вопрос закрыт.
пачка бумаги А4 стОит 2000 р, в ней 500 листов. получается, лист обычной бумаги стОит дороже имперского рубля =)
Отредактировано 29.04.2015 21:17 niXman . Предыдущая версия .
Re[3]: вопрос про operator<() для std::tuple
От: Nikе Россия  
Дата: 29.04.15 21:11
Оценка:
Здравствуйте, niXman, Вы писали:

N>>Если первый аргумент меньше — выходим сразу, иначе, если аргументы равны — проверяем следующую пару, иначе фалс. В чём проблема?
X>наверное я чего-то не так объяснил...
X>вопрос вот в чем:
X>
X>static constexpr bool __less(const _Tp& __t, const _Up& __u) {
X>        return bool(std::get<__i>(__t) < std::get<__i>(__u))
X>            || (!bool(std::get<__i>(__u) < std::get<__i>(__t)) // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< вопрос в этой строке
X>            && __tuple_compare<_Tp, _Up, __i + 1, __size>::__less(__t, __u));
X>}
X>

X>а именно(чуть дооформлю):
X>
X>auto l = std::get<__i>(__t);
X>auto r = std::get<__i>(__u);

X>bool ok = (l < r) || (!(r < l));
X>

X>(вроде ничего не напутал)

X>вопрос в том, зачем тут еще и проверка (!(r < l))?

Не, там не так. Там:
if ( l < r ) // если текущий левый меньше правого - всё ок, тупл меньше
 return true;
if ( r < l ) // если текущий правый меньше левого - всё пропало, тупл точно не меньше
 return false;
return __tuple_compare<_Tp, _Up, __i + 1, __size>::__less(__t, __u) // если текущие аргументы примерно равны - проверяем следующую пару.
Нужно разобрать угил.
Re[3]: вопрос про operator<() для std::tuple
От: _DAle_ Беларусь  
Дата: 29.04.15 21:13
Оценка: 9 (1) +2
Здравствуйте, niXman, Вы писали:

X>вопрос в том, зачем тут еще и проверка (!(r < l))?

Это проверка на l == r. Обычное сравнение пары:
ok = a.first < b.first || a.first == b.first && a.second < b.second;

Здесь же вместо оператора ==, естественно используется все тот же operator<
Re: вопрос про operator<() для std::tuple
От: Кодт Россия  
Дата: 01.05.15 10:28
Оценка: 9 (1) +1
Здравствуйте, niXman, Вы писали:

X>в чем смысл?

В самодостаточности предиката "меньше" для лексикографического сравнения.
Оно так для всех структур определяется — будь то строки, векторы, пары.
(a,b...) < (c,d...) =
  a <  c ||
  a == c && (b...) < (d...)       -- рекурсивная формула

(a == c) = !(a < c) && !(c < a)   -- аксиома

(a,b...) < (c,d...) =
   (a < c) ||
  !(a < c) && !(c < a) && (b...) < (d...)
  ~~~~~~~~
     это избыточно
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.