DEV Community

Sandor Dargo
Sandor Dargo

Posted on • Originally published at sandordargo.com

The big STL Algorithms tutorial: partitioning operations

In this next part of the big STL algorithm tutorial, we cover the partitioning operations - except for ranges which will be covered in a different series.

  • is_partitioned
  • partition
  • partition_copy
  • stable_partition
  • partition_point

is_partitioned

std::is_partitioned checks whether a range is partitioned by a given predicate. But what does partitioned mean?

Let's say that you have a list of cars and each car - among others - has an attribute of transmission. A car's gearbox is either manual or automatic. If a range of cars is considered partitioned, then all the manual cars will appear before all automatic. Or the other way around, depending on how the predicate is written.

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

enum class Transmission {Automatic, Manual};

struct Car {
  int horsePower;
  Transmission transmission;
};

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

  std::vector partitionedCars {
    Car{80, Transmission::Manual},
    Car{100, Transmission::Automatic},
    Car{120, Transmission::Automatic},
  };

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

  std::cout << "unpartitionedCars is_partitioned? " << std::is_partitioned(
    unpartitionedCars.begin(), unpartitionedCars.end(), isManual) << '\n';
  std::cout << "partitionedCars is_partitioned? " << std::is_partitioned(
    partitionedCars.begin(), partitionedCars.end(), isManual) << '\n';
}
/*
unpartitionedCars is_partitioned? false
partitionedCars is_partitioned? true
*/
Enter fullscreen mode Exit fullscreen mode

As you can see, the usage is simple, first, you pass in the range by the usual begin/end iterator pairs, then your predicate as a lambda, functor or function pointer.

You'll always get a simple boolean as an answer.

partition

partition is a solicitation. Calling partition means that you ask for your range to be partitioned.

Just as for is_partitioned, you pass in two iterators defining a range and a unary predicate, but this time your range might be modified.

All the items satisfying the passed in predicate will be moved to the front and the non-satisfying items will come only after. It's worth to note that the original order between the satisfying/non-satisfying items is not necessarily kept. If you need that, you should use stable_partition.

As a result, you'll get an iterator pointing at the first element of the second group, so pointing at the first element not satisfying the predicate.

Let's see an example:

#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;};
  auto printCar = [&](const Car& car ){ std::cout << "Car: " << car.horsePower << " " << (isManual(car) ? "manual" : "automatic" ) << '\n';};

  std::cout << std::boolalpha;
  std::cout << "Cars:\n";
  for_each(cars.begin(), cars.end(), printCar);

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

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

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

}
/*
Cars:
Car: 100 automatic
Car: 80 manual
Car: 250 manual
Car: 120 automatic

cars is_partitioned? false

Cars:
Car: 250 manual
Car: 80 manual
Car: 100 automatic
Car: 120 automatic

cars is_partitioned? true
*/
Enter fullscreen mode Exit fullscreen mode

partition_copy

partition_copy has a very similar functionality compared to partition. The only difference is that it leaves the original input range intact and instead it copies the partitioned element into another range.

In fact, into two other ranges and it makes this algorithm quite interesting and requires a bit more attention.

The first two parameters are defining the inputs, then there are two other iterators taken.

The first output iterator (third parameter) should point at the beginning of the range where you want to copy the elements satisfying the predicate (the predicate is to be passed as a fifth parameter.)

The second output iterator (fourth parameter) points at the beginning of the range where you want to copy the elements not matching the predicate.

There are a couple of things you have to make sure

  • as usual, the output ranges are defined by only their beginning. You either have to make sure that they are big enough to accommodate all the items that will be copied into them, or you pass an inserter iterator (std::back_inserter)
  • the other noticeable items is that we have to output ranges and we have to make sure that there is no overlap between them. As we don't pass containers but iterators, we can easily pass iterators pointing to the same container, but if you don't like trouble, it's better to just create two different containers for the matching and non-matching elements and use them.

partition_copy returns a pair of iterators with the first pointing after the last matching copied element and the other pointing similarly after the last non-matching copied element.

#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;};
  auto printCar = [&](const Car& car ){ std::cout << "Car: " << car.horsePower << " " << (isManual(car) ? "manual" : "automatic" ) << '\n';};

  std::cout << std::boolalpha;
  std::cout << "Cars:\n";
  for_each(cars.begin(), cars.end(), printCar);

  std::cout << '\n';


  std::vector<Car> manualCars;
  std::vector<Car> automaticCars;
  std::partition_copy(cars.begin(), cars.end(), std::back_inserter(manualCars), std::back_inserter(automaticCars), isManual);

  std::cout << "manual Cars:\n";
  for_each(manualCars.begin(), manualCars.end(), printCar);  
  std::cout << '\n';

  std::cout << "automatic Cars:\n";
  for_each(automaticCars.begin(), automaticCars.end(), printCar);  
  std::cout << '\n';
}
/*
Cars:
Car: 100 automatic
Car: 80 manual
Car: 250 manual
Car: 120 automatic

manual Cars:
Car: 80 manual
Car: 250 manual

automatic Cars:
Car: 100 automatic
Car: 120 automatic
*/
Enter fullscreen mode Exit fullscreen mode

I found no guarantees, but it seems (not only based on the above example) that the relative order of the elements is preserved. That's something that was explicitly not guaranteed for partition

stable_partition

What was clearly said for partition, namely that the relative order of the elements partitioned into their categories is not kept, stable_partition has this guarantee.

If two items belong to the same category, their relative order will be the same before and after partitioning.

Apart from that, there is no difference between partition and stable_partition, there is no difference in the way you have to use them.

#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;};
  auto printCar = [&](const Car& car ){ std::cout << "Car: " << car.horsePower << " " << (isManual(car) ? "manual" : "automatic" ) << '\n';};

  std::cout << std::boolalpha;
  std::cout << "Cars:\n";
  for_each(cars.begin(), cars.end(), printCar);

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

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

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

}
/*
Cars:
Car: 100 automatic
Car: 80 manual
Car: 250 manual
Car: 120 automatic

cars is_partitioned? false

Cars:
Car: 80 manual
Car: 250 manual
Car: 100 automatic
Car: 120 automatic

cars is_partitioned? true
*/
Enter fullscreen mode Exit fullscreen mode

If you check the results of the example with the provided results of partition you can also observe that the relative order was not kept before, but

now it is.

partition_point

partition_point as its name suggests will return you the dividing point between the matching and non-matching points.

In other words, partition_point comes with a contract asking for already partitioned inputs. As usual, calls with invalid arguments are subject to undefined behaviour.

partition_point returns an iterator past the end of the first partition, or the last element if all elements match the predicate. Just like partition or stable_partition.

#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';

  std::cout << '\n';
  auto partitionResult = std::partition(cars.begin(), cars.end(), isManual);
  auto partitionPoint = std::partition_point(cars.begin(), cars.end(), isManual);

  std::cout << "cars is_partitioned? " << std::is_partitioned(
    cars.begin(), cars.end(), isManual) << '\n';
  std::cout << "partitionResult == partitionPoint: " << (partitionResult == partitionPoint) << '\n';
}
/*
cars is_partitioned? false
cars is_partitioned? true
partitionResult == partitionPoint:true
*/
Enter fullscreen mode Exit fullscreen mode

Conclusion

Today, we learned about partitioning algorithms. They allow us to separate elements of a container based on any predicate we might want to define. Next time we are going to discuss sorting algorithms. Stay tuned!

Connect deeper

If you found interesting this article, please subscribe to my personal blog and let's connect on Twitter!

Top comments (4)

Collapse
 
pgradot profile image
Pierre Gradot

Great article :)

I see on cppreference for partition_point that the behavior doesn't seem to be undefined if the range is not partitioned.:

Examines the partitioned (as if by std::partition) range [first, last) and locates the end of the first partition, that is, the first element that does not satisfy p or last if all elements satisfy p.

That's not the point of the article but I have learned the purpose of std::back_inserter ^^

Collapse
 
sandordargo profile image
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
*/
Enter fullscreen mode Exit fullscreen mode

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?

Collapse
 
pgradot profile image
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 ;)

Thread Thread
 
sandordargo profile image
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.