Analyzing STL lower_bound: why does it iterate the whole list twice?

I criticized an STL algorithm in a previous entry, calling it “unintuitive but correct.”. That’s pretty arrogant of me, considering the STL has been published for fifteen or so years. You’d think that if an STL algorithm were incorrect, someone would have noticed by now. Or taken differently, STL doesn’t need an obscure blogger’s approval. […]

Also tagged