Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

3
  • 2
    This is not exactly true. The STL is unlike most other libraries in that it provides explicit big-O requirements for most of its operations. There is a guaranteed difference between 2 * O(log n) and 1 * O(log n), regardless of what implementation the functions use to achieve that O(log n) behavior. Whether or not that difference is significant on your platform is a different question. But the difference will always be there. Commented Nov 11, 2013 at 17:42
  • @srm defining big-O requirements still doesn't tell you how long an operation will take in absolute terms. The guaranteed difference you speak of doesn't exist. Commented Nov 11, 2013 at 18:41
  • @MarkRansom: That said, if insert doesn't use the provided hint from a lower_bound call to avoid a second O(log n) search, that's a pretty terrible quality defect. There's no reason for find, lower_bound or insert to use fundamentally different algorithms, so reducing two O(log n) lookups to one should provide a meaningful benefit by avoiding the second lookup entirely. Commented Nov 21, 2022 at 16:24