For that individual operation performed once, it is cheaper to use lower_bound
and insert
. lower_bound
is O(log(n))
and insert
will be (worst and average case) O(n)
, giving a final complexity of O(n)
.
If you don't need the vector sorted until after you're done inserting into it, it will be much cheaper to sort only once, since all the push_back
s will be O(1)*O(n) = O(n)
and the final sort will be O(n*log(n))
, giving you a final complexity of O(n*log(n))
, whereas the multiple lower_bound
+insert
will give you a complexity of O(n)*O(n) = O(n**2)
.
If you need the elements sorted throughout the insertion process, which one is cheaper will depend heavily on your usage pattern (how often and when you need the elements sorted). It can often be the case that you only need the elements sorted at the end of the construction process, which is why sorting at the end can be a very powerful tool in your tool belt. If that is not your usage pattern, you may want to at least consider using an associative container such as multi_set
or multi_map
.