Thomas Kowalski wrote:
I have an sorted vector<doublev and want to insert a new double val.
What I need is the position the val have been inserted at in the
vector. My basic idea is something like this (pseudo-code) :
it = lower_bound(v.begin(), v.end(), greater(val));
What's the "greater" for?
v.insert(it,val);
size_t pos = it - v.begin();
Does anyone know whether lower_bound finds the first occurrence of an
object in a vector in O(log(n)) in case the values in the vector are
unique?
Are there any better ideas how to do it easy and most important fast?
Insertions in a vector are notoriously slow. Consider (a) reserving the
room by calling 'reserve' if you know how many elements your vector will
contain when you complete all insertions, (b) not writing separate
statements - the compiler may or may not be able to optimize them, so
use a single expression like
size_t pos = v.insert(lower_bound(v.begin(), v.end(), val), val)
- v.begin();
(c) if you need to hold onto the iterator - use ther return value of
'insert', and not from 'lower_bound'.
It may be faster to insert all of the values and then re-sort.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
