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

[Milian Wolff]

On Wednesday 10 December 2014 13:24:52 Matthew Dempsky wrote:
> 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
> ===================================================================
> --- tuple (revision 223962)
> +++ tuple (working copy)
> @@ -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);
>      }
>  };

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
-- 
Milian Wolff
mail at milianw.de
http://milianw.de