Partition Algorithms

Partitioning Without Random Access Iterators

Is it possible to use the partition() algorithm with containers that do not support random access iterators?

Abstract art representing computer programming

Yes, you can use the partition() algorithm with containers that do not support random access iterators, such as linked lists.

The C++ standard library's partitioning algorithms are designed to work with any container that meets the requirements of bidirectional iterators.

Requirements for Partitioning

The partition() algorithm requires bidirectional iterators because it needs to traverse the container from both ends to swap elements. Containers like std::list, which provide bidirectional iterators, are compatible with partition().

Here’s an example using std::list:

#include <algorithm>
#include <iostream>
#include <list>

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

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

  std::partition(A.begin(), A.end(), isEven);

  std::cout << "After partitioning: ";
  for (int x : A) {
    std::cout << x << ", ";
  }
}
After partitioning: -6, 2, 4, 1, 7, 5,

In this example, std::partition works with std::list because std::list provides bidirectional iterators. The elements are rearranged such that even numbers come before odd numbers.

Why Random Access Iterators Aren't Required

Random access iterators allow direct access to any element in the container using indexing, which is not necessary for partitioning. The partition() algorithm only requires bidirectional iterators to move forward and backward through the container, making swaps where necessary.

Practical Use

Here’s a practical example with std::list showing a more complex partitioning scenario:

#include <algorithm>
#include <iostream>
#include <list>

int main() {
  std::list<int> A = {3, 6, 1, 5, 8, 2, 7};

  auto isLessThanFive = [](int x) { return x < 5; };

  auto partition_point = std::partition(
    A.begin(), A.end(), isLessThanFive);

  std::cout << "Elements less than 5: ";
  for (auto it = A.begin();
    it != partition_point; ++it) {
    std::cout << *it << ", ";
  }
  std::cout << "\nElements 5 or greater: ";
  for (auto it = partition_point;
    it != A.end(); ++it) {
    std::cout << *it << ", ";
  }
}
Elements less than 5: 3, 1, 2,
Elements 5 or greater: 6, 5, 8, 7,

Conclusion

Using partition() with containers that support bidirectional iterators, like std::list, is straightforward.

Ensure your container provides at least bidirectional iterators to take advantage of the partitioning algorithms in the C++ standard library.

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