Partition Algorithms

# Partitioning Without Random Access Iterators

## Is it possible to use the partition() algorithm with containers that do not support 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:

#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.

This Question is from the Lesson:

### Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them

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

This Question is from the Lesson:

### Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them

Part of the course:

## Professional C++

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

Free, unlimited access

### This course includes:

• 124 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
Free, Unlimited Access

### Professional C++

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