Partitioning Without Random Access Iterators

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:

1#include <algorithm>
2#include <iostream>
3#include <list>
4
5int main() {
6  std::list<int> A = {1, -6, 7, 2, 5, 4};
7
8  auto isEven = [](int x) { return x % 2 == 0; };
9
10  std::partition(A.begin(), A.end(), isEven);
11
12  std::cout << "After partitioning: ";
13  for (int x : A) {
14    std::cout << x << ", ";
15  }
16}

1After 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:

1#include <algorithm>
2#include <iostream>
3#include <list>
4
5int main() {
6  std::list<int> A = {3, 6, 1, 5, 8, 2, 7};
7
8  auto isLessThanFive = [](int x) { return x < 5; };
9
10  auto partition_point = std::partition(
11    A.begin(), A.end(), isLessThanFive);
12
13  std::cout << "Elements less than 5: ";
14  for (auto it = A.begin();
15    it != partition_point; ++it) {
16    std::cout << *it << ", ";
17  }
18  std::cout << "\nElements 5 or greater: ";
19  for (auto it = partition_point;
20    it != A.end(); ++it) {
21    std::cout << *it << ", ";
22  }
23}

1Elements less than 5: 3, 1, 2,
2Elements 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.