commit 07b133f2a7b8afcb6b23750412f1317ab5a9262f
author Duncan P. N. Exon Smith <dexonsmith@apple.com> Wed Jan 21 02:51:17 2015 +0000
committer Duncan P. N. Exon Smith <dexonsmith@apple.com> Wed Jan 21 02:51:17 2015 +0000
tree d666449dab4d2cd55e0cb82c0049ed551ba323ba
parent b3289a0c88b4ab566ed3b524900bf4d3876edb45

tuple: Make operator<() linear instead of exponential

Patch by Matthew Dempsky!

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@226641 91177308-0d34-0410-b5e6-96231b3b80d8

include/tuple

diff --git a/include/tuple b/include/tuple
index 5fc27f9..93518d8 100644
--- a/include/tuple
+++ b/include/tuple
@@ -927,8 +927,12 @@
     _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);
     }
 };