# blocked_range Template Class

## Summary

Template class for a recursively divisible half-open interval.

## Header

    #include "tbb/blocked_range.h"

## Syntax

    template<typename Value> class blocked_range;

## Description

A `blocked_range<Value>` represents a half-open range [i,j) that can be recursively split. The types of i and j must model the requirements in the following table. In the table, type `D` is the type of the expression `"j-i"`. It can be any integral type that is convertible to `size_t`. Examples that model the Value requirements are integral types, pointers, and STL random-access iterators whose difference can be implicitly converted to a `size_t`.

A `blocked_range` models the Range concept.

Value Concept for blocked_range
Pseudo-Signature | Semantics
--- | ---
`Value::Value( const Value& )` | Copy constructor.
`Value::~Value()` | Destructor.
`void operator=( const Value& )` ### Note The return type `void` in the pseudo-signature denotes that `operator=` is not required to return a value. The actual `operator=` can return a value, which will be ignored by `blocked_range` . | Assignment
`bool operator<( const Value& i, const Value& j )` | Value i precedes value j.
`D operator-( const Value& i, const Value& j )` | Number of values in range `[i,j)`.
`Value operator+( const Value& i, D k )` | kth value after i.

A `blocked_range<Value>` specifies a grainsize of type `size_t`. A `blocked_range` is splittable into two subranges if the size of the range exceeds grain size. The ideal grain size depends upon the context of the `blocked_range<Value>`, which is typically as the range argument to the loop templates `parallel_for`, `parallel_reduce`, or `parallel_scan`. A too small grainsize may cause scheduling overhead within the loop templates to swamp speedup gained from parallelism. A too large grainsize may unnecessarily limit parallelism. For example, if the grain size is so large that the range can be split only once, then the maximum possible parallelism is two.

Here is a suggested procedure for choosing grainsize:

1. Set the grainsize parameter to 10,000. This value is high enough to amortize scheduler overhead sufficiently for practically all loop bodies, but may be unnecessarily limit parallelism.
2. Run your algorithm on one processor.
3. Start halving the grainsize parameter and see how much the algorithm slows down as the value decreases.

A slowdown of about 5-10% is a good setting for most purposes.

### Tip

For a `blocked_range [i,j)` where`j<i`, not all methods have specified behavior. However, enough methods do have specified behavior that `parallel_for`, `parallel_reduce`, and `parallel_scan` iterate over the same iteration space as the serial loop `for( Value index=i; index<j; ++index )...`, even when `j<i`. If `TBB_USE_ASSERT` is nonzero, methods with unspecified behavior raise an assertion failure.

Example

A `blocked_range<Value>` typically appears as a range argument to a loop template. See the examples for `parallel_for`,`parallel_reduce`, and `parallel_scan`.

## Members

    namespace tbb {
        template<typename Value>
        class blocked_range {
        public:
            // types
            typedef size_t size_type;
            typedef Value const_iterator;

            // constructors
            blocked_range( Value begin, Value end,
                           size_type grainsize=1 );
            blocked_range( blocked_range& r, split );

            // capacity
            size_type size() const;
            bool empty() const;

            // access
            size_type grainsize() const;
            bool is_divisible() const;

            // iterators
            const_iterator begin() const;
            const_iterator end() const;
        };
    }

The following table provides additional information on the members of this template class.
Member | Description
--- | ---
size_type | The type for measuring the size of a `blocked_range`. The type is always a `size_t`.
const_iterator | The type of a value in the range. Despite its name, the type `const_iterator` is not necessarily an STL iterator; it merely needs to meet the Value requirements in the table above. However, it is convenient to call it `const_iterator` so that if it is a const_iterator, then the`blocked_range` behaves like a read-only STL container.
blocked_range( Value begin, Value end, size_t grainsize=1 ) | More Info
blocked_range( blocked_range& range, split ) | More Info
size_type size() const | Requirements :`end()<begin()` is false. Effects: Determines size of range. Returns `end()-begin()`
bool empty() const | Effects: Determines if range is empty. Returns: `!(begin()<end())`
size_type grainsize() const | Returns: Grain size of range.
bool is_divisible() const | Requirements: `!(end()<begin())` Effects: Determines if range can be split into subranges. Returns: True if `size()>grainsize();` false otherwise.
const_iterator begin() const | Returns: Inclusive lower bound on range.
const_iterator end() const | Returns: Exclusive upper bound on range.

Parent topic: Range Concept

- blocked_range( Value begin, Value end, size_t grainsize=1 )
- blocked_range( blocked_range& range, split )

## See Also

parallel_for Template Function
parallel_reduce Template Function
parallel_scan Template Function
TBB_USE_ASSERT Macro