Discussion on: The big STL Algorithms tutorial: partitioning operations

[Sandor Dargo]

Thanks for your kind words, I'm glad you liked the article.

You made an interesting point. I saw that, but I interpreted it differently. It starts with "examines the partitioned range", so if that doesn't apply, the rest is irrelevant.

Then cplusplus.com says that "invalid arguments cause undefined behavior".

So I made an experiment

#include <iostream>
#include <algorithm>
#include <vector>

enum class Transmission {Automatic, Manual};

struct Car {
  int horsePower;
  Transmission transmission;
};

int main() {
  std::vector cars {
    Car{100, Transmission::Automatic},
    Car{80, Transmission::Manual},
    Car{250, Transmission::Manual},
    Car{120, Transmission::Automatic},
  };

  auto isManual = [](const Car& car ){ return car.transmission == Transmission::Manual;};

  std::cout << std::boolalpha;

  std::cout << '\n';
  std::cout << "cars is_partitioned? " << std::is_partitioned(
    cars.begin(), cars.end(), isManual) << '\n';


  auto partitionPoint = std::partition_point(cars.begin(), cars.end(), isManual);
  std::cout << "partitionPoint " << partitionPoint->horsePower <<'\n';

  std::cout << "cars is_partitioned? " << std::is_partitioned(
    cars.begin(), cars.end(), isManual) << '\n';

}
/*
cars is_partitioned? false
partitionPoint 120
cars is_partitioned? false
*/

The first element that doesn't satisfy isManual is actually the very first element Car{100, Transmission::Automatic}, yet what was returned is Car{120, Transmission::Automatic} which is the last one. Or did I make a mistake somewhere?

[Pierre Gradot]

Your code seems fine to me. And clearly this doesn't match the behavior described on cppreference.com.

There is something more on cplusplus.com:

The elements in the range shall already be partitioned, as if partition had been called with the same arguments.

I would then imagine the return value to be "unspecified". "Undefined behavior" is something much more serious. Problem: cplusplus.com don't really explain what an "invalid argument" is: a range that is not partitioned? two random pointers as iterators?

Google doesn't give a lot of results for "std::partition_point undefined behavior"... It could be a good question for stackoverflow ;)

[Sandor Dargo]

Having a look at available draft standard from 2017 this seems undefined to me.

The requirements on partition_point say:

Requires: ForwardIterator’s value type shall be convertible to Predicate’s argument type. [first, last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.

The definition of undefined behaviour is (emphasis mine, page 19):

behavior for which this International Standard imposes no requirements [ Note: Undefined behavior may be expected when this International Standard omits any explicit definition of behavior or when a program uses an erroneous construct or erroneous data. Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). Many erroneous program constructs do not engender undefined behavior; they are required to be diagnosed. Evaluation of a constant expression never exhibits behavior explicitly specified as undefined (8.20). — end note ]

If this is still not convincing enough unspecified behaviour talks about correct data (emphasis mine, page 19):

behavior, for a well-formed program construct and correct data, that depends on the implementation [ Note: The implementation is not required to document which behavior occurs. The range of possible behaviors is usually delineated by this International Standard. — end note ]

It might be a bit strong to have UB for this, but it's not extraordinary. If you take sorted-range algorithms for example binary_search, whenever when you don't pass in a sorted range, the behaviour is undefined according to Nico Josuttis' book on the standard library, section 11.10. This is not much different, but sadly the book says nothing explicit about this case.