Insert to a vector quickly and get the insertation position

T

Thomas Kowalski

Hi,
I have an sorted vector<double> v 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));
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?

Thanks in advance,
Thomas Kowalski
 
P

peter koch

Thomas said:
Hi,
I have an sorted vector<double> v 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));
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?

Well first of all, you use your iterator after the insert: you can't as
the iterator might be invalidated. Secondly, the search-time will be
O(log n), but the time to insert is O(1). You probably use the wrong
container (I propose std::set), but that depends on your needs.

/Peter
 
V

Victor Bazarov

Thomas said:
I have an sorted vector<double> v 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
 
T

Thomas Kowalski

Well first of all, you use your iterator after the insert: you can't as
the iterator might be invalidated.
Right, thanks for mentioning it.
Secondly, the search-time will be O(log n), but the time to insert is O(1).
Don't you mean that the insertation time will be O(n) ?
You probably use the wrong container (I propose std::set),
but that depends on your needs.
Thanks again, but since I need to optimize other methodes primarily, I
guess the vector is the best tradeoff in overall speed.

Regards,
Thomas Kowalski
 
T

Thomas Kowalski

Hi Victor,
What's the "greater" for?

Ok, I just check the docu again and I guess I don't need it.
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,

There is just one insertation. Probably I am "over-optimizing" this
methode since it actually don't really need to be fast, but this is
mainly for educatiuonal purpose.
(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();

Thanks for the tip.


Thanks,
Thomas Kowalski
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top