[cfe-dev] Exponential complexity in libc++ std::tuple comparisons?

[Matthew Dempsky]

On Wed, Dec 10, 2014 at 2:11 PM, Milian Wolff <mail at milianw.de> wrote:
> No clue about the actual stuff, but wouldn't this change mean that the
> function cannot be constexpr in C++11? Could be fixed by using the ternary
> operator, but it becomes much less readable then...

I suppose if necessary it could be written as something like:

    template <size_t _Ip>
    struct __tuple_less {
        template <typename _Tp, typename _Up>
        bool operator()(const _Tp& __x, const _Up& __y) {
            return __less(__x, __y) || (!__less(__y, __x) &&
__tuple_less<_Ip-1>()(__x, __y);
        }

        template <typename _Tp, typename _Up, size_t _Idx =
tuple_size<_Tp>::value - _Ip>
        bool __less(const _Tp& __x, const _Up& __y) {
            return _VSTD::get<_Idx>(__x) < _VSTD::get<_Idx>(__y);
        }
    };

which isn't terrible, IMO.

On the upside, constexpr only seems to be required for operator< on
std::tuple since C++14, and C++14 also relaxes constexpr enough that I
believe my original patch should be okay unless constexpr for C++11 is
desirable.