[Bug libstdc++/49717] New: Debug version checking algorithmic preconditions may have different complexity

["bangerth at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49717

           Summary: Debug version checking algorithmic preconditions may
                    have different complexity
           Product: gcc
           Version: 4.5.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: bangerth@gmail.com


This is essentially just a request to state something more explicitly on
the website:

We've started using the libstdc++ debug mode for running our testsuite (and
found a dozen or so bugs with it -- yay) but I've come to realize that
a bunch of tests now time out: they've become orders of magnitude slower.
The reason I found for this is that many of the algorithms in libstdc++
(rightfully) check preconditions. For example, std::lower_bound checks
whether indeed the given element partitions the sequence. The problem here
is that these checks violate the complexity guarantees of the algorithms:
std::lower_bound is supposed to be O(log(N)) but with the check for
partitioning, it is now O(N). In our case, we call this function for
each element of a sequence, and so we get O(N**2) instead of O(N log(N))
and the result is the increase in compute time.

There is little one can do about this -- the debug mode is meant to check
these things and it can't be done in O(log(N)). But it would be good to
state this prominently somewhere in the corresponding web sites.

Thanks
 W.