424,988 Members | 1,367 Online
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
4 Replies

 P: n/a Thomas Kowalski wrote: Hi, I have an sorted vector

 P: n/a Thomas Kowalski wrote: I have an sorted vector

 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.