C++ Container question.

Discussion in 'C++' started by Pat, Apr 28, 2004.

  1. Pat

    Pat Guest

    Hi,

    I use "vector<int> v" in my program. If "v" contains the following:

    (front) 1 2 3 4 2 5 7 1 (end),

    I want to remove some element, say "2", and I want the resultant "v" to be
    as follows:

    (front) 1 3 4 5 7 1 (end)

    What function should I use? "erase" or "remove"? On the other hand, if my
    vector is very larger (say 50000 elements). What function is efficient to do
    the above action?

    Thanks for your help.

    Pat
    Pat, Apr 28, 2004
    #1
    1. Advertising

  2. "Pat" <> wrote in message news:408fd6f2$-cable.com...
    > Hi,
    >
    > I use "vector<int> v" in my program. If "v" contains the following:
    >
    > (front) 1 2 3 4 2 5 7 1 (end),
    >
    > I want to remove some element, say "2", and I want the resultant "v" to be
    > as follows:
    >
    > (front) 1 3 4 5 7 1 (end)
    >
    > What function should I use? "erase" or "remove"? On the other hand, if my
    > vector is very larger (say 50000 elements). What function is efficient to

    do
    > the above action?
    >
    > Thanks for your help.
    >
    > Pat
    >


    remove is a function which removes a given value from the container. In
    other words it must loop through the entire container looking for any
    matching values and removing all of them.

    erase on the other hand is a method of vector (and others) which removes
    elements at a specified positions. It is therefore much more efficient than
    remove. But on the other hand if you are going to have to loop though the
    entire vector to find the element(s) you want to erase, you might as well
    use remove instead.

    So in your case

    std::remove(v.begin(), v.end(), 2);

    would seem to be right.

    john
    John Harrison, Apr 28, 2004
    #2
    1. Advertising

  3. Pat

    Siemel Naran Guest

    "Pat" <> wrote in message news:408fd6f2$-cable.com...

    > I use "vector<int> v" in my program. If "v" contains the following:
    >
    > (front) 1 2 3 4 2 5 7 1 (end),
    >
    > I want to remove some element, say "2", and I want the resultant "v" to be
    > as follows:
    >
    > (front) 1 3 4 5 7 1 (end)
    >
    > What function should I use? "erase" or "remove"? On the other hand, if my
    > vector is very larger (say 50000 elements). What function is efficient to

    do
    > the above action?


    Use erase.

    vector::iterator i = find(v.begin(), v.end(), 2);
    v.erase(i);

    Anyone know if v.erase(v.end()) is undefined or has no effect?

    The running time of vector::erase is O(N) because the container has to copy
    elements.

    If you do lots of erasing, consider an alternative design: use std::list
    where erasing is O(1), std::deque where erasing is O(M) where M is the
    blocksize, erase many elements at once using remove_if which actually just
    moves the elements to be removed to the end of the array and then call the
    v.erase of two arguments, create a deleted flag in each object (which allows
    you to undo your delete easily :), etc.
    Siemel Naran, Apr 28, 2004
    #3
  4. "John Harrison" <> wrote in message
    news:c6olt0$ejgt1$-berlin.de...
    >
    > "Pat" <> wrote in message news:408fd6f2$-cable.com...
    > > Hi,
    > >
    > > I use "vector<int> v" in my program. If "v" contains the following:
    > >
    > > (front) 1 2 3 4 2 5 7 1 (end),
    > >
    > > I want to remove some element, say "2", and I want the resultant "v" to

    be
    > > as follows:
    > >
    > > (front) 1 3 4 5 7 1 (end)
    > >
    > > What function should I use? "erase" or "remove"? On the other hand, if

    my
    > > vector is very larger (say 50000 elements). What function is efficient

    to
    > do
    > > the above action?
    > >
    > > Thanks for your help.
    > >
    > > Pat
    > >

    >
    > remove is a function which removes a given value from the container. In
    > other words it must loop through the entire container looking for any
    > matching values and removing all of them.
    >
    > erase on the other hand is a method of vector (and others) which removes
    > elements at a specified positions. It is therefore much more efficient

    than
    > remove. But on the other hand if you are going to have to loop though the
    > entire vector to find the element(s) you want to erase, you might as well
    > use remove instead.
    >
    > So in your case
    >
    > std::remove(v.begin(), v.end(), 2);
    >
    > would seem to be right.
    >
    > john
    >


    Actually no. I'm forgetting the gotcha the remove does not erase anything,
    just rearranges the vector so that the elements to be removed are at the end
    of the vector where they can then be erased. In other words what you want is

    v.erase(std::remove(v.begin(), v.end(), 2), v.end());

    john
    John Harrison, Apr 28, 2004
    #4
  5. "Siemel Naran" <> wrote in message
    news:eek:9Rjc.59048$...
    > "Pat" <> wrote in message news:408fd6f2$-cable.com...
    >
    > > I use "vector<int> v" in my program. If "v" contains the following:
    > >
    > > (front) 1 2 3 4 2 5 7 1 (end),
    > >
    > > I want to remove some element, say "2", and I want the resultant "v" to

    be
    > > as follows:
    > >
    > > (front) 1 3 4 5 7 1 (end)
    > >
    > > What function should I use? "erase" or "remove"? On the other hand, if

    my
    > > vector is very larger (say 50000 elements). What function is efficient

    to
    > do
    > > the above action?

    >
    > Use erase.
    >
    > vector::iterator i = find(v.begin(), v.end(), 2);
    > v.erase(i);


    I think you've missed that he has more than one element to erase. Therefore
    the code above would only work in a loop and therefore be less efficient
    than std::remove.

    >
    > Anyone know if v.erase(v.end()) is undefined or has no effect?


    Undefined.

    john
    John Harrison, Apr 28, 2004
    #5
  6. Pat

    Siemel Naran Guest

    "John Harrison" <> wrote in message
    news:c6olt0$ejgt1$1@ID-
    > "Pat" <> wrote in message news:408fd6f2$-cable.com...


    > > (front) 1 2 3 4 2 5 7 1 (end),
    > > (front) 1 3 4 5 7 1 (end)


    > std::remove(v.begin(), v.end(), 2);
    >
    > would seem to be right.


    But this changes it from to

    (front) 1 2 3 4 2 5 7 1 (end),
    (front) 1 3 4 5 7 1 2 2 (end)

    Non-member remove can't actually remove elements because it doesn't have the
    original container, can't update the container size, etc.
    Siemel Naran, Apr 28, 2004
    #6
  7. Pat

    Siemel Naran Guest

    "John Harrison" <> wrote in message
    news:c6onfh$edblg$1@ID-
    > "Siemel Naran" <> wrote in message


    > > vector::iterator i = find(v.begin(), v.end(), 2);
    > > v.erase(i);

    >
    > I think you've missed that he has more than one element to erase.

    Therefore
    > the code above would only work in a loop and therefore be less efficient
    > than std::remove.


    You're right. Each call to erase is O(N), so worst case to remove all
    occurrences of an element is O(N^2). To make it more efficient save the
    result of v.erase, but only the find part is more efficient, and the whole
    thing is still O(N^2).

    vector::iterator i = v.begin();
    while (
    i = find(i, v.end(), 2);
    if (i == v.end()) break;
    v.erase(i);
    ++i;
    }


    > > Anyone know if v.erase(v.end()) is undefined or has no effect?

    >
    > Undefined.


    OK.
    Siemel Naran, Apr 28, 2004
    #7
  8. Pat

    tom_usenet Guest

    On Thu, 29 Apr 2004 00:08:25 +0800, "Pat" <> wrote:

    >Hi,
    >
    >I use "vector<int> v" in my program. If "v" contains the following:
    >
    >(front) 1 2 3 4 2 5 7 1 (end),
    >
    >I want to remove some element, say "2", and I want the resultant "v" to be
    >as follows:
    >
    >(front) 1 3 4 5 7 1 (end)
    >
    >What function should I use? "erase" or "remove"? On the other hand, if my
    >vector is very larger (say 50000 elements). What function is efficient to do
    >the above action?


    v.erase(
    std::remove(v.begin(), v.end(), 2),
    v.end()
    );

    That's an O(v.size()) 1 pass algorithm, and about as good as you'll
    get efficiency-wise.

    Tom
    --
    C++ FAQ: http://www.parashift.com/c -faq-lite/
    C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
    tom_usenet, Apr 28, 2004
    #8
  9. Pat

    Chris Theis Guest

    "Siemel Naran" <> wrote in message
    news:5wRjc.59158$um3.1139778@bgtnsc04-

    [SNIP]
    > vector::iterator i = v.begin();
    > while (
    > i = find(i, v.end(), 2);
    > if (i == v.end()) break;
    > v.erase(i);
    > ++i;
    > }
    >
    >


    This is basically what the combination of erase & remove does - check out a
    common implementation of the remove function. So why not use it for
    clarity┬┤s sake?

    Best regards
    Chris
    Chris Theis, Apr 28, 2004
    #9
  10. Pat

    Siemel Naran Guest

    "Chris Theis" <> wrote in message
    > "Siemel Naran" <> wrote in message


    > news:5wRjc.59158$um3.1139778@bgtnsc04-
    >
    > [SNIP]
    > > vector::iterator i = v.begin();
    > > while (
    > > i = find(i, v.end(), 2);
    > > if (i == v.end()) break;
    > > v.erase(i);
    > > ++i;
    > > }
    > >
    > >

    >
    > This is basically what the combination of erase & remove does - check out

    a
    > common implementation of the remove function. So why not use it for
    > clarity┬┤s sake?


    Right, we should use that method.
    Siemel Naran, Apr 29, 2004
    #10
  11. Pat

    Pat Guest

    Thanks all of you.

    Pat

    "tom_usenet" <> ???
    news: ???...
    > On Thu, 29 Apr 2004 00:08:25 +0800, "Pat" <> wrote:
    >
    > >Hi,
    > >
    > >I use "vector<int> v" in my program. If "v" contains the following:
    > >
    > >(front) 1 2 3 4 2 5 7 1 (end),
    > >
    > >I want to remove some element, say "2", and I want the resultant "v" to

    be
    > >as follows:
    > >
    > >(front) 1 3 4 5 7 1 (end)
    > >
    > >What function should I use? "erase" or "remove"? On the other hand, if my
    > >vector is very larger (say 50000 elements). What function is efficient to

    do
    > >the above action?

    >
    > v.erase(
    > std::remove(v.begin(), v.end(), 2),
    > v.end()
    > );
    >
    > That's an O(v.size()) 1 pass algorithm, and about as good as you'll
    > get efficiency-wise.
    >
    > Tom
    > --
    > C++ FAQ: http://www.parashift.com/c -faq-lite/
    > C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
    Pat, Apr 29, 2004
    #11
    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. Vivi Orunitia
    Replies:
    11
    Views:
    4,451
    Martijn Lievaart
    Feb 4, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    513
    Maitre Bart
    Feb 11, 2004
  3. Steven T. Hatton
    Replies:
    4
    Views:
    3,874
    Rob Williscroft
    Dec 5, 2004
  4. Replies:
    4
    Views:
    786
    Daniel T.
    Feb 16, 2006
  5. wolverine
    Replies:
    2
    Views:
    440
    Marcus Kwok
    Jul 24, 2006
Loading...

Share This Page