Quote:
It appears that the lower_bound function, although it scales linearly is not very fast due to the slowness of the ++ operator on the iterator. Maybe the ++ operator is very fast when you have a list of say integers, but it seems to be really slow when you have a list of data structures
By the way I wanted to point out that this does not make much sense either. Spending 70% of your time doesn't mean that increment itself is slow, it's just means that you are doing it so often. If you can think of a way to do sorted insertion without examining the list, then, yes, that would be very fast. :D