Difference between partition() and remove() functions in C++

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

The remove doesn't actually remove any e开发者_如何转开发lements of the containers but puts the 'removed' elements at the beginning of the sequence of elements and partition does the same thing as well.

---

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

---

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.

---

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]

---

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

---

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.