C++ Container question.

[Pat]

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

 

[John Harrison]

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

 

[Siemel Naran]

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.

 

[John Harrison]

to

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]

to

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

 

[Siemel Naran]

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]

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

Undefined.

OK.

 

[tom_usenet]

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

 

[Chris Theis]

[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

 

[Siemel Naran]

[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.

 

[Pat]

Thanks all of you.

Pat

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