sort_heap complexity guarantee

[François Dumont]

Hi

     I took a look at PR 61217 regarding pop_heap complexity guarantee. 
Looks like we have no test to check complexity of our algos so I start 
writing some starting with the heap operations. I found no issue with 
make_heap, push_heap and pop_heap despite what the bug report is saying 
however the attached testcase for sort_heap is failing.

     Standard is saying std::sort_heap shall use less than N * log(N) 
comparisons but with my test using 1000 random values the test is showing:

8687 comparisons on 6907.76 max allowed

     Is this a known issue of sort_heap ? Do you confirm that the test 
is valid ?

     Note that counter_type needs a patch to make the test ok, 
less_compare_count must be updated when operator< is invoked.

Thanks

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: complexity.cc
Type: text/x-c++src
Size: 1663 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20141005/e77e7e93/attachment.bin>