tags:

views:

121

answers:

5

What is the difference between the partition and remove functions in C++?

THe remove doesn't actually remove any elements of the containers but puts the 'removed' elements at the beginning of the sequence of elements and partition does the same thing as well.

+1  A: 

From The C++ Standard Library: A Tutorial and Reference

remove() - Removes elements with a given value, logically only by overwriting them with the following elements that were not removed. Do not change the number of elements in the ranges on which they operate. Instead, they return the position of the new "end" of the range

partition() - Changes the order of the elements so that elements that match a criterion are at the front

stable_partition() - Same as partition() but preserves the relative order of matching and nonmatching elements

DumbCoder
nice explanation.
Chubsdad
A: 

partition - "groups" the elements of a container according to a certain predicate (e.g. odd and even numbers in a std::vector)

remove - removes a certain value from a container; indeed elements are moved to the end of the initial container, an iterator to the new end is returned and the "removed" elements are still accessible

EDIT:

remove - removes a certain value from a container; elements are NOT moved to the end of the initial container as stated above, an iterator to the new end is returned but iterators in the range [newEnd, last) are still dereferenceable hence accessible BUT the elements they point to are unspecified.

celavek
Thats wrong, remove overwrites the 'removed' elements by the following ones, so not all of them might be accessible afterwards ...
MartinStettner
Would like to know what is wrong with my answer if possible. Maybe I'll learn something in the process.
celavek
@MartinStettner I think you are wrong. From documentation "Remove removes from the range [first, last) all elements that are equal to value. That is, remove returns an iterator new_last such that the range [first, new_last) contains no elements equal to value. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove is stable, meaning that the relative order of elements that are not equal to value is unchanged." http://www.sgi.com/tech/stl/remove.html
celavek
@Marius, from your STL docs quote: "The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified."That is what's wrong in your answer. There are no elements moved to the end of the container, not necessarily anyway.
haffax
@MartinSttetner @haffax indeed i was wrong. Edited the answer to reflect that. Thanks.
celavek
+7  A: 

remove_if doesn't put the removed elements anywhere; the elements after the new end will have their old values, so some of the removed elements might be missing, and some of the preserved elements might be duplicated. This is faster than partition, and can be done with forward iterators while partition requires bidirectional iterators.

Update: in C++0x, partition will only require forward iterators, but will be even slower if the iterators aren't bidirectional.

Mike Seymour
If `partition` requires bidirectional iterators, how come it works on a `forward_list`?
FredOverflow
@FredOverflow: because C++0x changes the contract of `partition` to take forward iterators.
Mike Seymour
+3  A: 

If I understood it right, remove does not actually swap any elements but simply moves elements for which the predicate (in case of remove_if) is false to the beginning of the sequence. If you have

a = [1,1,1,2,3]

and call remove(a.begin(),a.end(),1), you'll have

a = [2,3,1,2,3]

afterwards. remove returns an iterator to the third element in this case (if I remember correctly ...)

partition on the other hand retains all original elements of the sequence but changes their order such that elements for which the given predicate is true are placed in front of elements for which it isn't.

partition(a.begin(), a.end(), not_equal<int>(1)) yields

a = [2,3,1,1,1]

MartinStettner
Note that it is not guaranteed what `std::remove()`'s leaves behind _after_ the new end iterator it returns. While the result you show is likely, it's not guaranteed.
sbi
I thought `std::remove` was guaranteed to leave the elements behind the new end iterator unchanged (they also would remain accessible). But I might be proven wrong by the standard :) ...
MartinStettner
The standard doesn't specify what happens to the elements after the end of the new range. While it's hard to imagine that any sensible implementation would touch them, there's no guarantee.
Mike Seymour
One could imagine std::remove_if doing smart things on a std::list. Swapping nodes may be significantly cheaper than assigning their value_types.
MSalters
@Martin: Also, it's imaginable that some implementation __moves__ values in a `std::vector<std::string>` because that's cheaper than copying them. Or maybe it even __swaps_ them, leaving it to the caller whether to destroy the remaining objects.
sbi
+6  A: 

remove [...] puts the 'removed' elements at the beginning of the sequence

What? No. Both remove_if and partition put the "good" elements first. partition puts the "bad" elements after that, whereas remove_if does not specify what comes after it -- it might be the bad elements, but it might also be copies of any (either good or bad) elements.

For example, if you partition 1 2 3 4 5 on even, you might get 2 4 5 3 1 (note that each element occurs exactly once), whereas if you remove_if the odd elements, you might get 2 4 3 4 5 (note the duplicates).

FredOverflow
thanks, I understood that
David Willis