Partition Algorithms

Determining Partition Size

How can I determine the size of each partition after using the partition() function?

Abstract art representing computer programming

After using the partition() function, you can determine the size of each partition by examining the subrange returned by the function.

This subrange represents the second partition, where the predicate returned false. The elements before this subrange belong to the first partition.

Here’s an example to illustrate how you can find the size of each partition:

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

int main() {
  std::vector<int> A = {1, -6, 7, 2, 5, 4};

  auto isEven = [](int x) { return x % 2 == 0; };

  auto SecondSR = std::ranges::partition(A, isEven);

  // Size of the second partition
  std::cout << "Second Partition Size: "
            << SecondSR.size() << '\n';

  // Create a subrange for the first partition
  auto FirstSR = std::ranges::subrange(
    A.begin(), SecondSR.begin());

  // Size of the first partition
  std::cout << "First Partition Size: "
            << FirstSR.size() << '\n';

  // Output elements in both partitions
  std::cout << "First Partition: ";
  for (int x : FirstSR) std::cout << x << ", ";
  std::cout << "\nSecond Partition: ";
  for (int x : SecondSR) std::cout << x << ", ";
Second Partition Size: 3
First Partition Size: 3
First Partition: 4, -6, 2,
Second Partition: 7, 5, 1,

In this example:

  • The isEven predicate determines if an element is even.
  • std::ranges::partition() partitions the vector A into even and odd numbers.
  • SecondSR represents the subrange of odd numbers.
  • FirstSR is constructed using iterators from the beginning of A to the beginning of SecondSR.

By calculating the sizes of FirstSR and SecondSR, you get the sizes of the first and second partitions, respectively. This method allows you to work with partitions efficiently after using partition().

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved