Range Component

Ranges are a common concept in the C++ standard, and in the case of all the algorithms available, one usually has to supply a start and end to a range as adjacent arguments. This can be tiresome, and in the common case, unnecessary.

The range component works as a high level view. Rather than holding onto the container, it simply holds the start and end iterators to represent a range. The range component implements the interface and behavior discussed within N3350. Some decisions pertaining to open questions were made, and these are discussed below.

The range component resides in the <core/range.hpp>.

class is_range<R>

Type trait for determining if a type can return a value when std::begin and std::end are called on it.

class range<T>

Represents an open-ended range of [begin, end). The category of range depends on the category of its iterator. All the type aliases within the range depend on the use of std::iterator_traits<T>.

The type T is actually an Iterator type.

type iterator_category

Represents std::iterator_traits<T>::iterator_category

type difference_type

Represents std::iterator_traits<T>::difference_type

type value_type

Represents std::iterator_traits<T>::value_type

type reference

Represents std::iterator_traits<T>::reference

type pointer

Represents std::iterator_traits<T>::pointer

type iterator

Represents T.

range(std::pair<iterator, iterator> pair) noexcept

Constructs a range with the first and second members of the pair to be the begin and end of the range respectively.

range(iterator begin, iterator end) noexcept

Constructs a range with the given iterators.

range(range const& that)

Constructs a range with a copy of the iterators stored in that.

range(range&& that) noexcept

Constructs a range by moving the iterators stored in that.


Constructs a range by default constructing both its begin and end iterators. The resulting range will be empty.

Postcondition:begin() == end()
range& operator=(range const&)
range& operator=(range&&)

Assigns the contents of the incoming range to *this.

reference operator[](difference_type idx) const
Requires:iterator_category be random_access_iterator_tag.
iterator begin() const
Returns:beginning of the range
iterator end() const
Returns:end of the range.
reference front() const
Returns:the value returned by dereferencing begin()
reference back() const
Requires:iterator_category be bidirectional_iterator_tag.
Returns:the value returned by dereferencing the iterator before end()
bool empty() const
Returns:begin() == end()
difference_type size() const

Will return the number of elements between begin() and end().

Requires:iterator_category be forward_iterator_tag
Returns:std::distance(begin(), end())
range slice(difference_type start, difference_type stop) const

Slicing a range has the most complex behavior out of all the range member functions. This is due to the behavior mimicking the slice behavior exhibited by the python language’s slicing syntax.

If start is negative, the begin marker is end() - start. If stop is negative, the end marker is end() - stop. If start is positive, the begin marker is begin() + start. If stop is positive, the end marker is begin() + stop.

If start and stop are positive, and stop is less than or equal to start, an empty range is returned.

If start and stop are negative and stop is less than or equal to start, an empty range is returned.

If start is positive and stop is negative and abs(stop) + start is greater or equal to size(), an empty range is returned.

If start is negative and stop is positive and size() + start is greater or equal to stop, an empty range is returned.

These first two conditions can be computed cheaply, while the third and fourth are a tad more expensive. However they are required in all computations, no matter the iterator_category. slice() does not compute size() until after checking the first two conditions.

Some optimizations are taken to insure that finding the begin and end iterators is at most an O(N) operation, rather than O(2N), as it could be in some cases.

Requires:iterator_category be forward_iterator_tag.
range slice(difference_type start) const
Requires:iterator_category be forward_iterator_tag.
Returns:An open ended range of [begin() + start, end()).
std::pair<range, range> split(difference_type idx) const
Requires:iterator_category be forward_iterator_tag.
void pop_front(difference_type n)
void pop_front()

Moves the start of the range ‘forward’ by n, via std::advance. The overload which takes no arguments moves the range forward by 1.

void pop_back(difference_type n)
void pop_back()
Requires:iterator_category be bidirectional_iterator_tag.
void pop_front_upto(difference_type n)

Moves the start of the range by n elements. A negative argument causes no change.

void pop_back_upto(difference_type n)

Moves the end of the range backwards by n elements. A negative argument causes no change.

Requires:iterator_category be bidirectional_iterator_tag.
void swap(range& that) noexcept

Swaps the begin and end of *this, with that.

range<T> make_range(T begin, T end)

Creates a range from the iterators begin and end.

range<T> make_range(Range&&)

Constructs a range from the given type by calling std::begin and std::end.

range<std::istream_iterator<T, CharT, Traits>> make_range(std::basic_istream<CharT, Traits>& stream)

Constructs a range for iterating an istream. An example of usage is:

auto istream_range = make_range<double>(stream);
range<std::istreambuf_iterator<CharT, Traits>> make_range(std::basic_streambuf<CharT, Traits>* buffer)

Constructs a range for iterating a streambuf. An example of usage is:

auto streambuf_range = make_range(stream.rdbuf());


void swap(range<Iterator>& lhs, range<Iterator>& rhs)

Answers to Open Questions

There are several questions raised in N3350. The decisions related to these are discussed below.


The author of N3350 mentions that they would like to be able to pass a single argument to a make_range() that is just the beginning of a range, where the end of the range is a default constructed iterator. This would make it helpful with iterators such as istream_iterator. The author is concerned that this will make the use of make_range() potentially confusing.

It was decided that the author’s concerns are valid, however the ability to create an istream_iterator range (and istreambuf_iterator range) is a desirable feature. An overload for make_range is provided to take an istream and istreambuf to create a proper range.

Inherit from std::pair<Iterator, Iterator>

The author of N3350 mentions inheriting from std::pair<Iterator, Iterator>. Rather than rely on inheritance to represent a range, it was decided to allow a range to be constructed implicitly with a std::pair.

Remove member functions and replace as free algorithms

The author of N3350 mentions that it might be worth placing some member functions such as pop_* and range<T>::slice() as non member functions, at the cost of some Iterator copying.

It was decided that this was unnecessary, and the member functions will stay.

Range Category

The author of N3350 proposes defining range categories.

It was decided that these add nothing of use.

Split takes arbitrary number of indices

The author of N3350 mentions taking an arbitrary number o indices and returning an N + 1 element tuple<>. The author mentions that this would be tricky with negative indices and bidirectional iterators.

It was decided that this is an unnecessary complication of the range component’s internals.