------- Additional Comments From SWElef at post dot sk 2005-01-14 13:33 ------- It took me quite a long time to realise that the best performance tests are those where we count the elementary operations. The best way to expose the O(n log n) complexity in non-fixed case is to supply the container with a comparator object that counts the invocations of operator() in some global variable. For an experimental proof that the fixed version is really linear one also needs to count the node manipulations by, say, replacing _Base_ptr with a "smart pointer" that acts as a plain pointer and counts every action (ctor, dtor, copy, dereference).
Regards, Vladimir Marko -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422
