Exponential complexity in libc++ std::tuple comparisons?

Clang Frontend
#1

While working on adding operator< to Chromium's Tuple class, I was
curious how libc++ implemented it. However, I noticed libc++'s
worst-case complexity grows exponentially with the number of tuple
elements, and I think potentially non-conforming with the C++11 spec
in a few minor ways.

I believe the patch below fixes these.

Index: tuple

#2

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...

Bye

#3

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.