sort_heap complexity guarantee

[François Dumont]

Then I think we need this patch which also fix other issues.

2014-10-22  François Dumont  <fdumont@gcc.gnu.org>

     * testsuite/25_algorithms/make_heap/complexity.cc: Add missing test
     variable.
     * testsuite/25_algorithms/sort_heap/complexity.cc: Likewise and use
     log2.
     * testsuite/25_algorithms/pop_heap/complexity.cc: Likewise and require
     normal mode.
     * testsuite/25_algorithms/push_heap/complexity.cc: Likewise.

Tested under Linux x86_64.

Ok to commit ?

François


On 20/10/2014 22:48, Marc Glisse wrote:
> On Mon, 20 Oct 2014, François Dumont wrote:
>
>> On 18/10/2014 09:24, Marc Glisse wrote:
>>> On Mon, 6 Oct 2014, François Dumont wrote:
>>>
>>>>    * testsuite/25_algorithms/push_heap/complexity.cc: New.
>>>
>>> This test is randomly failing in about 1% to 2% of cases.
>>>
>> Is it for a particular platform ? I just run it thousands of times on 
>> my Linux and never experimented any failure.
>
> x86_64-linux-gnu, debian testing
>
> Here is a deterministic version.
>
> By the way, when the standard says "log" and there isn't an implicit 
> O(), it usually means "log2".
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: complexity.patch
Type: text/x-patch
Size: 2827 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20141022/6ee4c7ba/attachment.bin>