By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,988 Members | 1,367 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,988 IT Pros & Developers. It's quick & easy.

Insert to a vector quickly and get the insertation position

P: n/a
Hi,
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));
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

Sep 22 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a

Thomas Kowalski wrote:
Hi,
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));
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

Sep 22 '06 #2

P: n/a
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
Sep 22 '06 #3

P: n/a
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

Sep 22 '06 #4

P: n/a
Hi Victor,
it = lower_bound(v.begin(), v.end(), greater(val));

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

Sep 22 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.