Behaviour of std::partition when called on empty container?

Question

I ran into a problem when calling std::partition on an empty container (std::list).

std::list<int>::iterator end_it = std::partition(l.begin(), l.end(), SomeFunctor(42));
std::list<int>::iterator it = l.begin();

while (it != end_it)
{
  // do stuff
}

If the list is empty, std::partition returns an iterator, that is not equal to l.end(). Is this the default behaviour?

Answer 1

Am I missing something, or shouldn't:

std::list<int>::iterator end_it = l.begin();

be:

std::list<int>::iterator end_it = l.end();

But actually I think the return value of partition() is undefined for an empty set of values. The return value is defined to be:

An iterator i such that for any iterator j in the range [first, i), pred(j) != false, and for any iterator k in the range [i, last), pred(j) == false.

IMHO, the predicate cannot be applied to an end iterator, as it would not be dereferrencable.

Answer 2

This page shows the code that std::partition is behaving like.

Answer 3

No, std::partition should return the end iterator, and for me (gcc-4.4.2) it does.

I think you have a bug somewhere. Either in your code or in the compiler.

Answer 4

Stating the partition precondition that the range [first, last) should be a valid range, SGI says:

The range [i,j) is a valid range if both i and j are valid iterators, and j is reachable from i [2].

Which makes it ok to use partition on an empty range.

Of course, sgi is not the standard. But it's pretty close :)

Answer 5

Right now, there really is no good answer. The Library Working Group of the C++ committee issue number 1205 covers exactly this question. That issue includes both a primary and an alternative proposed resolution but neither has been accepted or rejected yet (and I don't like either one).

Since the standard doesn't give an unambiguous definition of the result of applying an algorithm to an empty range, I'd say the result of doing so is currently undefined. I think there's some hope that it'll be defined in the next version of the standard, but for now it's really not. Even when it is, from a practical viewpoint it'll probably be better to avoid it at least for a while, because it may be a while before compilers conform in this respect (though it should usually be a fairly easy fix).

Edit, mostly in response to Martin B's comment: the issue is listed for [alg.partitions], which includes both std::partition and std::stable_partition. Unfortunately, the proposed wording does not seem to directly address either one. The paragraph it cites is (at least in N2960) in the description of std::is_paritioned, which is pretty much what Martin B described, even though he used the wrong name for it. Worse, the primary proposed resolution is in the form of non-normative notes.

As I said, though, I don't really like either proposed resolution. The primary tries to place requirements in non-normative notes. Such notes are fine if they clarify requirements that are really already present elsewhere, but might be hard to find. In this case, I'm pretty sure the requirements really aren't present. The alternative resolution is better, but fails to address the core question of whether an empty range is a valid range.

IMO, a better resolution would start at §24.1/7. This already tells us that: "A range [i, i) is an empty range;..." I think it should add normative language to explicitly state that an empty range either is or is not a valid range. If it's not a valid range, nothing else needs to be added -- it's already explicit that applying an algorithm to an invalid range gives undefined behavior.

If an empty range is valid, then normative wording needs to be added to define the results for applying each algorithm to an empty range. This would answer the basic question, then state what that answer implies for each specific algorithm.