From 53afae49eec4fad26478176ddbfaefd2a9d46a93 Mon Sep 17 00:00:00 2001
From: "Duncan P. N. Exon Smith" <dexonsmith@apple.com>
Date: Wed, 21 Jan 2015 02:51:17 +0000
Subject: [PATCH] tuple: Make operator<() linear instead of exponential

Patch by Matthew Dempsky!

llvm-svn: 226641
---
 libcxx/include/tuple | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

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