Boost.Range is a rich library that provides a flexible and convenient interface for common operations on C++ ranges. When discussing its utility, one function that often stands out is `is_sorted`, which checks if elements within a range are sorted according to a specified criterion. Interestingly, `Boost.Range` does not require forward iterators for its `is_sorted` function. This article explores why this is the case and provides a technical explanation and illustrations where applicable.

Iterators in C++

Before delving into specific details, it's vital to understand iterators in C++. Iterators are a generalization of pointers used to traverse containers. C++ provides several types of iterators:

1. Input Iterator: Allows reading from a sequence.
2. Output Iterator: Allows writing to a sequence.
3. Forward Iterator: Supports read/write access to a sequence.
4. Bidirectional Iterator: Extends the forward iterator by allowing reverse traversal.
5. Random Access Iterator: Provides access at arbitrary indices, similar to pointers.

The Boost.Range `is_sorted` algorithm is designed to work with a range defined by a pair of input iterators, which is less restrictive than using forward iterators. Understanding why this decision was made requires examining the requirements and functionality of the `is_sorted` algorithm.

The `is_sorted` Algorithm

The `is_sorted` algorithm is intended to determine whether a sequence of elements is sorted. Its signature in Boost.Range is typically:

• Single-Pass Requirement: The `is_sorted` function only needs to perform a single pass through the range. It evaluates whether each element is less than or equal to the next, thus not requiring the ability to revisit elements—hence no need for backward traversal or random access.
• Efficiency: Using input iterators reduces the algorithm's constraints and increases versatility. The algorithm remains effective and efficient as it only compares adjacent elements.
• Resource Constraints: Forward, bidirectional, and random access iterators may impose additional resource constraints (e.g., memory or processing due to copy operations) which aren't necessary for `is_sorted`.
• Simplified Semantics: By accepting input iterators (single-pass), the algorithm is applicable to both containers and more abstract input streams like pipeline structures or network streams.