# Range Concept

## Summary

Requirements for type representing a recursively divisible set of values.

## Requirements

The following table lists the requirements for a Range type `R`.

Range Concept
Pseudo-Signature | Semantics
--- | ---
`R::R( const R& )` | Copy constructor.
`R::~R()` | Destructor.
`bool R::empty() const` | True if range is empty.
`bool R::is_divisible() const` | True if range can be partitioned into two subranges.
`R::R( R& r, split )` | Split `r` into two subranges.

## Description

A Range can be recursively subdivided into two parts. It is recommended that the division be into nearly equal parts, but it is not required. Splitting as evenly as possible typically yields the best parallelism. Ideally, a range is recursively splittable until the parts represent portions of work that are more efficient to execute serially rather than split further. The amount of work represented by a Range typically depends upon higher level context, hence a typical type that models a Range should provide a way to control the degree of splitting. For example, the template class `blocked_range` has a grainsize parameter that specifies the biggest range considered indivisible.

The constructor that implements splitting is called a splitting constructor. If the set of values has a sense of direction, then by convention the splitting constructor should construct the second part of the range, and update the argument to be the first half. Following this convention causes the`parallel_for`, `parallel_reduce` and `parallel_scan` algorithms, when running sequentially, to work across a range in the increasing order typical of an ordinary sequential loop.

## Example

The following code defines a type `TrivialIntegerRange` that models the Range concept. It represents a half-open interval [lower,upper) that is divisible down to a single integer.

    struct TrivialIntegerRange {
        int lower;
        int upper;
        bool empty() const {return lower==upper;}
        bool is_divisible() const {return upper>lower+1;}
        TrivialIntegerRange( TrivialIntegerRange& r, split ) {
            int m = (r.lower+r.upper)/2;
            lower = m;
            upper = r.upper;
            r.upper = m;
        }
    };

`TrivialIntegerRange` is for demonstration and not very practical, because it lacks a grainsize parameter. Use the library class `blocked_range` instead.

## Model Types

Type `blocked_range` models a one-dimensional range.

Type `blocked_range2`d models a two-dimensional range.

Type `blocked_range3d` models a three-dimensional range.

The Container Range Concept models a container as a range.

Parent topic: Algorithms

- blocked_range Template Class
- blocked_range2d Template Class
- blocked_range3d Template Class

## See Also

parallel_for Template Function
parallel_reduce Template Function
parallel_scan Template Function
Container Range Concept