Insert to a vector quickly and get the insertation position

Discussion in 'C++' started by Thomas Kowalski, Sep 22, 2006.

  1. 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
    Thomas Kowalski, Sep 22, 2006
    #1
    1. Advertising

  2. Thomas Kowalski

    peter koch Guest

    Thomas Kowalski wrote:
    > 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
    peter koch, Sep 22, 2006
    #2
    1. Advertising

  3. Thomas Kowalski wrote:
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 22, 2006
    #3
  4. > 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
    Thomas Kowalski, Sep 22, 2006
    #4
  5. 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
    Thomas Kowalski, Sep 22, 2006
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    23,738
  2. Replies:
    10
    Views:
    1,498
    Ivan Vecerina
    May 28, 2005
  3. Replies:
    8
    Views:
    1,896
    Csaba
    Feb 18, 2006
  4. Javier
    Replies:
    2
    Views:
    548
    James Kanze
    Sep 4, 2007
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    349
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page