Fix exponential complexity in operator< for std::tuple

[mclow.lists]

This looks good to me.
Do you have commit access?
If not, I can commit it for you.

[matthew]

No, I do not have commit access. I'd appreciate if you could commit it for me, thanks!

[dexonsmith]

(Some necromancy here...)

[mclow.lists]

This was committed as revision 226641.

include/tuple

 
 template <size_t _Ip>
 struct __tuple_less
 {
     template <class _Tp, class _Up>
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
     bool operator()(const _Tp& __x, const _Up& __y)
     {
-        return __tuple_less<_Ip-1>()(__x, __y) ||
-             (!__tuple_less<_Ip-1>()(__y, __x) && _VSTD::get<_Ip-1>(__x) < _VSTD::get<_Ip-1>(__y));
+        const size_t __idx = tuple_size<_Tp>::value - _Ip;
+        if (_VSTD::get<__idx>(__x) < _VSTD::get<__idx>(__y))
+            return true;
+        if (_VSTD::get<__idx>(__y) < _VSTD::get<__idx>(__x))
+            return false;
+        return __tuple_less<_Ip-1>()(__x, __y);
     }
 };
 
 template <>
 struct __tuple_less<0>
 {
     template <class _Tp, class _Up>
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11