C++ Container question.

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" <Pat@Pat.com> wrote in message news:408fd6f2$1_3@rain.i-cable.com...[color=blue]
> 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[/color]
do[color=blue]
> the above action?
>
> Thanks for your help.
>
> Pat
>[/color]

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

"Pat" <Pat@Pat.com> wrote in message news:408fd6f2$1_3@rain.i-cable.com...
[color=blue]
> 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[/color]
do[color=blue]
> the above action?[/color]

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.

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:c6olt0$ejgt1$1@ID-196037.news.uni-berlin.de...[color=blue]
>
> "Pat" <Pat@Pat.com> wrote in message news:408fd6f2$1_3@rain.i-cable.com...[color=green]
> > 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[/color][/color]
be[color=blue][color=green]
> > as follows:
> >
> > (front) 1 3 4 5 7 1 (end)
> >
> > What function should I use? "erase" or "remove"? On the other hand, if[/color][/color]
my[color=blue][color=green]
> > vector is very larger (say 50000 elements). What function is efficient[/color][/color]
to[color=blue]
> do[color=green]
> > the above action?
> >
> > Thanks for your help.
> >
> > Pat
> >[/color]
>
> 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[/color]
than[color=blue]
> 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
>[/color]

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

"Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message
news:o9Rjc.59048$um3.1138131@bgtnsc04-news.ops.worldnet.att.net...[color=blue]
> "Pat" <Pat@Pat.com> wrote in message news:408fd6f2$1_3@rain.i-cable.com...
>[color=green]
> > 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[/color][/color]
be[color=blue][color=green]
> > as follows:
> >
> > (front) 1 3 4 5 7 1 (end)
> >
> > What function should I use? "erase" or "remove"? On the other hand, if[/color][/color]
my[color=blue][color=green]
> > vector is very larger (say 50000 elements). What function is efficient[/color][/color]
to[color=blue]
> do[color=green]
> > the above action?[/color]
>
> Use erase.
>
> vector::iterator i = find(v.begin(), v.end(), 2);
> v.erase(i);[/color]

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.
[color=blue]
>
> Anyone know if v.erase(v.end()) is undefined or has no effect?[/color]

Undefined.

john

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:c6olt0$ejgt1$1@ID-[color=blue]
> "Pat" <Pat@Pat.com> wrote in message news:408fd6f2$1_3@rain.i-cable.com...[/color]
[color=blue][color=green]
> > (front) 1 2 3 4 2 5 7 1 (end),
> > (front) 1 3 4 5 7 1 (end)[/color][/color]
[color=blue]
> std::remove(v.begin(), v.end(), 2);
>
> would seem to be right.[/color]

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.

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:c6onfh$edblg$1@ID-[color=blue]
> "Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message[/color]
[color=blue][color=green]
> > vector::iterator i = find(v.begin(), v.end(), 2);
> > v.erase(i);[/color]
>
> I think you've missed that he has more than one element to erase.[/color]
Therefore[color=blue]
> the code above would only work in a loop and therefore be less efficient
> than std::remove.[/color]

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;
}

[color=blue][color=green]
> > Anyone know if v.erase(v.end()) is undefined or has no effect?[/color]
>
> Undefined.[/color]

OK.

On Thu, 29 Apr 2004 00:08:25 +0800, "Pat" <Pat@Pat.com> wrote:
[color=blue]
>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?[/color]

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

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

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

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" <Christian.Theis@nospam.cern.ch> wrote in message[color=blue]
> "Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message[/color]
[color=blue]
> news:5wRjc.59158$um3.1139778@bgtnsc04-
>
> [SNIP][color=green]
> > vector::iterator i = v.begin();
> > while (
> > i = find(i, v.end(), 2);
> > if (i == v.end()) break;
> > v.erase(i);
> > ++i;
> > }
> >
> >[/color]
>
> This is basically what the combination of erase & remove does - check out[/color]
a[color=blue]
> common implementation of the remove function. So why not use it for
> clarity´s sake?[/color]

Right, we should use that method.

Thanks all of you.

Pat

"tom_usenet" <tom_usenet@hotmail.com> ???
news:c6uv80hfu1mj0pb6l8djuq7ib0oa025m0q@4ax.com ???...[color=blue]
> On Thu, 29 Apr 2004 00:08:25 +0800, "Pat" <Pat@Pat.com> wrote:
>[color=green]
> >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[/color][/color]
be[color=blue][color=green]
> >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[/color][/color]
do[color=blue][color=green]
> >the above action?[/color]
>
> 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[/color]