The STL brought the notion of a range to C++, expressed as a
pair of iterators. C++11 added the range-based for loop, which iterates
over a single object for which `begin(x)`

and `end(x)`

return that pair of iterators. The Boost.Range library extends this
to a full library of algorithms based on ranges as single objects. We'd like
to be able to experiment with such a library in a series of Technical
Specifications between now and C++17, but the LWG preference is that TSes
shouldn't change the definitions of any existing types, so we need to add a
minimal amount of range-object support to the C++14 standard library so that
range TSes can interoperate. This paper attempts to add that support.

I drew inspiration from two places in adding this support. First, the range-based for loop ([stmt.ranged]) defines the minimal interface for a range object:

`begin(range)`

and`end(range)`

, with`std::begin`

and`std::end`

in the candidate set, return types that can initialize variables in the same`auto`

-typed declaration. (Note that [stmt.ranged] specifies individual cases for arrays, objects with`.begin()`

and`.end()`

members, and objects for which`begin()`

and`end()`

can be found via ADL, but`std::begin()`

and`std::end()`

include code for arrays and objects with`.begin()`

and`.end()`

members, so this library-oriented proposal simply relies on them.)- The type returned by
`begin(range)`

and`end(range)`

supports`operator*`

,`operator++`

, and`operator!=`

in the pattern defined by Input Iterators. This proposal slightly strengthens that into a requirement that`begin(range)`

and`end(range)`

actually return an Input Iterator type, although the`enable_if`

logic for implementations is only required to check for the presence of`operator*`

.

Second, many container methods have an overload taking an
`initializer_list<value_type>`

argument. This proposal takes
that as a good indication of the methods that can usefully take a range
argument and adds such an overload parallel to each one of those. This is
the same as the set of methods taking a templated Iterator pair except for
one `priority_queue`

constructor.

`Range`

template argumentThere are many sorts of range types, so container methods taking ranges either have to be templated, or we'd need to define a single range type with a templated converting constructor. I proposed such a type in N3350, but the exact set of methods that the type needs is somewhat contentious, so this paper proposes templating the methods instead.

A templated method could either take a `const Range&`

or a
`Range&&`

(where `Range`

is a template
argument). Both of these can capture arguments that should implicitly
convert to the argument types of another overload of the same method, so we
need some `enable_if`

logic for both. ```
const
Range&
```

would naturally leave `Container&`

arguments for the `const Container&`

overload, but it would
incorrectly capture `DerivedFromContainer`

arguments, just like
`Range&&`

would. `Range&&`

lets us
allow library authors to move elements from rvalue arguments. Because the
necessary `enable_if`

logic seems similar in both cases, I chose
to take `Range&&`

.

The `enable_if`

logic is
specified as:

Several functions in the standard library take a template argument named "

`Range`

". These functions shall not participate in overload resolution if`Range`

is not deduced to a range type. Further, if the function is a container or string’s constructor or operator=, and`decay<Range>::type`

is the type of the container or a type derived from the container type, the function shall not participate in overload resolution.Additionally, implementations may exclude these functions from overload resolution if Range's iterator type is not an Input Iterator type ([input.iterators]) or its value type is not convertible to the container’s value type, but the extent to which they do so is unspecified.

Even with this text, *range types that define an implicit conversion
to the container type with a non-default allocator, comparator, or hash
instance* are going to have strange behavior when a conversion is
requested. With current language rules, it appears that copy-initialization
will call the conversion operator, but direct-initialization will call the
templated range constructor, losing any custom allocator, comparator, or
hash instance the conversion operator attempts to set. It's possible to
work around this by explicitly passing them to the range constructor, but
it's unlikely users will know to do so. I believe such types are rare
enough that this surprise is acceptable.

The proposed text also says that ranges
passed as rvalues are "left in an unspecified state after the call."
When a range is just a reference to
objects owned elsewhere, this text doesn't allow moving those objects, since
that leaves more than just the *range* in an unspecified state.
However, if the implementation can detect that the range owns the objects it
iterates over, this wording allows those objects to be moved. I leave the
technique for detecting this as a QoI issue.

Boost has a fairly extensive collection of range-based algorithms, but they can't quite interoperate perfectly with standard containers because the containers are missing appropriate constructors. This paper allows the following code (adapted from the Boost.Range docs) to work:

```
#include <boost/range/adaptor/replaced.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <deque>
#include <iostream>
#include <vector>
int main() {
using namespace boost::adaptors;
std::deque<int> input{1,2,3,2,5,2,7,2,9};
std::vector<int> output{
input | replaced(2, 10) | reversed};
boost::copy(output, std::ostream_iterator<int>(std::cout, ","));
}
```

This prints "`9,10,7,10,5,10,3,10,1,`".

You'll note that this paper doesn't propose any new algorithm overloads
taking ranges, so the above example still needs to call
`boost::copy`

instead of `std::copy`

. That's because a
TS can add new functions in its own namespace, so we can go through several
revisions getting them exactly right, rather than needing to debate a whole
algorithms library for C++14.

The primary discomfort the LWG had with the `split()`

proposal
was that its implicit conversion operator to any container type was just a
hack around the lack of range support (Portland
discussion). This paper delivers enough range support to remove
`split()`

's conversion operator.

```
vector<string> v{std::split("a,b,c", ",")};
deque<string> d{std::split("a,b,c", ",")};
set<string> s{std::split("a,b,c", ",")};
list<string> l{std::split("a,b,c", ",")};
vector<string_ref> v2{std::split("a,b,c", ",")}; // No data copied.
assert(v.size() == 3); // "a", "b", "c"
```

Conversion to either `string`

or `string_ref`

is
accomplished by having `split()`

's result's iterator return proxy
objects that are implicitly convertible to either type. The `enable_if`

logic specifically allows
implicit conversions to the container's `value_type`

so that this
works.

This paper updates N3456 by moving the range requirements out of [containers] and into the library's introduction ([utility.requirements]).

The most recent version of this paper is maintained on GitHub.

Wording changes are being maintained at https://github.com/google/cxx-std-draft/compare/range-args and a snapshot of the changes, relative to N3485, is copied below. An early implementation is at https://github.com/google/libcxx/compare/range-args. Patches and pull requests are welcome against both.

As an editorial matter, several of these new functions could be specified more concisely using [structure.specifications]'s "equivalent to" wording. They're specified more verbosely in order to match the existing functions around them.

[utility.arg.requirements] describes requirements on types and expressions used to instantiate templates defined in the C++ standard library. [swappable.requirements] describes the requirements on swappable types and swappable expressions. [nullablepointer.requirements] describes the requirements on pointer-like types that support null values. [hash.requirements] describes the requirements on hash function objects. [allocator.requirements] describes the requirements on storage allocators. [range.requirements] describes the requirements on range types.

Objects of `Range`

type (`Range`

objects) refer to a
sequence of other objects using a pair of iterators accessed by
`begin()`

and `end()`

functions. `Range`

objects may or may not contain and own these other objects.

This subclause provides definitions for `Range`

types and
expressions. In this subclause, `r`

is an instance of a
`Range`

type `R`

. `i`

is an instance of
`I`

, known as `R`

's iterator type. `V`

is
`R`

's and `I`

's value type.

[Note: These requirements are intended to match the requirements on
`_RangeT`

in the range-based for loop ([stmt.ranged]). —endnote]

R is a `Range`

type if it satisfies the requirements in Table 29
when the expressions are evaluated in the context described below.

Expression | Return type |
---|---|

`begin(r)` | `I` |

`end(r)` | `I` |

`*i` | implicitly convertible to `V` |

The context in which `begin(r)`

and `end(r)`

are
evaluated shall ensure that a unary non-member function named "begin" or "end"
respectively is selected via overload resolution ([over.match]) on a candidate
set that includes:

- the three begin or end function templates defined in <iterator> ([iterator.range]) and
- the lookup set produced by argument-dependent lookup ([basic.lookup.argdep]).

[Note: If R is an array of fundamental type and the declarations from the header <iterator> are in scope, the overall lookup set described above is equivalent to that of the qualified name lookup applied to the expression std::begin(r) or std::end(r) as appropriate. — end note ]

[ Note: It is unspecified whether a library component that has a
`Range`

requirement includes the header <iterator> to ensure an
appropriate evaluation context. — end note ]

Several functions in the standard library take a template argument named
"`Range`

". These functions shall not participate in overload
resolution if `Range`

is not deduced to a `Range`

type. Further, if the function is a container or string’s constructor or
`operator=`

, and `decay<Range>::type`

is the type of
the container or a type derived from the container type, the function shall not
participate in overload resolution.

Additionally, implementations may exclude these functions from overload
resolution if `Range`

's iterator type is not an Input Iterator type
([input.iterators]) or its value type is not convertible to the container's
value type, but the extent to which they do so is unspecified.

If the `Range`

is passed as an rvalue, it
is left in an unspecified state after the call. [Footnote: This allows
implementations to detect arguments that are containers and move, instead of
copying, their contents. -- end footnote]

In calls to functions taking template arguments named `Range`

, if
`Range`

's iterator type does not satisfy at least the Input Iterator
requirements ([input.iterators]), the program is ill-formed, no diagnostic
required. If a Range object `r`

is passed such that
`[begin(r),end(r))`

is not a valid range
([iterator.requirements.general]), the behavior is undefined.

```
template<class Range>
explicit basic_string(Range&&, const Allocator& = Allocator());
template<class Range>
basic_string& operator=(Range&&);
template<class Range>
basic_string& operator+=(Range&&);
template<class Range>
basic_string& append(Range&&);
template<class Range>
basic_string& assign(Range&&);
template<class Range>
iterator insert(const_iterator p, Range&&);
template<class Range>
basic_string& replace(const_iterator, const_iterator, Range&&);
```

```
template<typename Range>
explicit basic_string(Range&& range, const Allocator& a = Allocator());
```

Effects: Same as basic_string(begin(range), end(range), a).

```
template<typename Range>
basic_string& operator=(Range&& range);
```

Effects: *this = basic_string(std::forward<Range>(range)).

Returns: *this.

```
template<class Range>
basic_string& operator+=(Range&& range);
```

Effects: Calls append(std::forward<Range>(range)).

Returns: *this.

```
template<class Range>
basic_string& append(Range&& range);
```

Effects: Calls append(begin(range), end(range)).

Returns: *this.

```
template<class Range>
basic_string& assign(Range&& range);
```

Effects: Calls assign(begin(range), end(range)).

Returns: *this.

```
template<class Range>
iterator insert(const_iterator p, Range&& range);
```

Effects: insert(p, begin(range), end(range)).

Returns: An iterator which refers to the copy of the first inserted
character, or p if `[begin(range),end(range))`

is an empty
range.

```
template<class Range>
basic_string& replace(const_iterator i1, const_iterator i2,
Range&& range);
```

Requires: [begin(),i1), [i1,i2), and [begin(range),end(range)) are valid ranges.

Effects: Calls replace(i1 - begin(), i2 - i1, begin(range), end(range)).

Returns: *this.

In Tables 101 and 102, X denotes a sequence container class, a denotes a
value of X containing elements of type T, A denotes X::allocator_type if it
exists and std::allocator<T> if it doesn’t, i and j denote iterators
satisfying input iterator requirements and refer to elements implicitly
convertible to value_type, [i, j) denotes a valid range, r denotes a
`Range`

object ([range.requirements.implementations]) whose value
type is implicitly convertible to value_type and for which [begin(r),end(r)) is
a valid range ([iterator.requirements.general]), il designates an object
of type
initializer_list<value_type>, n denotes a value of X::size_type, p denotes a
valid const iterator to a, q denotes a valid dereferenceable const iterator to
a, [q1, q2) denotes a valid range of const iterators in a, t denotes an lvalue
or a const rvalue of X::value_- type, and rv denotes a non-const rvalue of
X::value_type. Args denotes a template parameter pack; args denotes a function
parameter pack with the pattern Args&&.

Expression | Return type | Assertion/note pre-/post-condition |
---|---|---|

X(r); | Equivalent to X(begin(r), end(r)) | |

a = r; | X& | Requires: T is CopyInsertable into X and CopyAssignable. Assigns the range [begin(r),end(r)) into a. All existing elements of a are either assigned to or destroyed. Returns: *this. |

a.insert(p, r); | iterator | a.insert(p, begin(r), end(r)). |

a.assign(r) | void | a.assign(begin(r), end(r)). |

In Table 103, X denotes an associative container class, a denotes a value of
X, a_uniq denotes a value of X when X supports unique keys, a_eq denotes a value
of X when X supports multiple keys, u denotes an identifier, i and j satisfy
input iterator requirements and refer to elements implicitly convertible to
value_type, [i,j) denotes a valid range, p denotes a valid const iterator to a,
q denotes a valid dereferenceable const iterator to a, [q1, q2) denotes a valid
range of const iterators in a, r denotes a `Range`

object
([range.requirements.implementations]) whose value type is implicitly
convertible to value_type and for which [begin(r),end(r)) is a valid range
([iterator.requirements.general]), il designates an object of type
initializer_list<value_type>, t denotes a value of X::value_type, k denotes a
value of X::key_type and c denotes a value of type X::key_compare. A denotes the
storage allocator used by X, if any, or std::allocator<X::value_type>
otherwise, and m denotes an allocator of a type convertible to A.

Expression | Return type | Assertion/note pre-/post-condition | Complexity |
---|---|---|---|

X(r); | Same as X(begin(r), end(r)). | same as X(begin(r), end(r)). | |

a = r | X& | Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [begin(r),end(r)) into a. All existing elements of a are either assigned to or destroyed. | NlogN in general (where N has the value distance(begin(r), end(r)) + a.size()); linear if [begin(r),end(r)) is sorted with value_comp(). |

a.insert(r) | void | Equivalent to a.insert(begin(r), end(r)). |

In table 104: X is an unordered associative container class, a is an object
of type X, b is a possibly const object of type X, a_uniq is an object of type X
when X supports unique keys, a_eq is an object of type X when X supports
equivalent keys, i and j are input iterators that refer to value_type, [i, j) is
a valid range, p and q2 are valid const iterators to a, q and q1 are valid
dereferenceable const iterators to a, [q1, q2) is a valid range in a, r
denotes a `Range`

object ([range.requirements.implementations]) whose
value type is implicitly convertible to value_type and for which
[begin(r),end(r)) is a valid range ([iterator.requirements.general]), il
designates an object of type
initializer_list<value_type>, t is a value of type X::value_type, k is a
value of type key_type, hf is a possibly const value of type hasher, eq is a
possibly const value of type key_equal, n is a value of type size_type, and z is
a value of type float.

Expression | Return type | Assertion/note pre-/post-condition | Complexity |
---|---|---|---|

X(r) | X | Same as X(begin(r), end(r)). | Same as X(begin(r), end(r)). |

a = r | X& | Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [begin(r),end(r)) into a. All existing elements of a are either assigned to or destroyed. | Same as a = X(r). |

a.insert(r) | void | Same as a.insert(begin(r), end(r)). | Same as a.insert( begin(r), end(r)). |

```
template <class Range>
explicit deque(Range&&, const Allocator& = Allocator());
template <class Range>
deque& operator=(Range&&);
template <class Range>
void assign(Range&&);
template <class Range>
iterator insert(const_iterator position, Range&&);
```

```
template <class Range>
iterator insert(const_iterator position, Range&&);
```

```
template <class Range>
explicit forward_list(Range&&, const Allocator& = Allocator());
template <class Range>
forward_list& operator=(Range&&);
template <class Range>
void assign(Range&&);
template <class Range>
iterator insert_after(const_iterator position, Range&& range);
```

```
template <class Range>
iterator insert_after(const_iterator position, Range&& range);
```

Effects: insert_after(p, begin(range), end(range)).

Returns: An iterator pointing to the last inserted element or
`position`

if `[begin(range),end(range))`

is an empty
range.

```
template <class Range>
explicit list(Range&&, const Allocator& = Allocator());
template <class Range>
list& operator=(Range&&);
template <class Range>
void assign(Range&&);
template <class Range>
iterator insert(const_iterator position, Range&& range);
```

```
template <class Range>
iterator insert(const_iterator position, Range&&);
```

```
template <class Range>
explicit vector(Range&&, const Allocator& = Allocator());
template <class Range>
vector& operator=(Range&&);
template <class Range>
void assign(Range&&);
template <class Range>
iterator insert(const_iterator position, Range&& range);
```

```
template <class Range>
iterator insert(const_iterator position, Range&&);
```

```
template <class Range>
vector(Range&&, const Allocator& = Allocator()));
template <class Range>
vector operator=(Range&&);
template <class Range>
void assign(Range&&);
template <class Range>
iterator insert(const_iterator position, Range&& range);
```

```
template <class Range>
explicit map(Range&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Range>
map& operator=(Range&&);
template <class Range>
void insert(Range&&);
```

```
template <class Range>
explicit multimap(Range&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Range>
multimap& operator=(Range&&);
template <class Range> void insert(Range&&);
```

```
template <class Range>
explicit set(Range&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Range>
set& operator=(Range&&);
template <class Range>
void insert(Range&&);
```

```
template <class Range>
explicit multiset(Range&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Range>
multiset& operator=(Range&&);
template <class Range>
void insert(Range&&);
```

```
template <class Range>
explicit unordered_map(Range&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Range>
unordered_map& operator=(Range&&);
template <class Range> void insert(Range&&);
```

```
template <class Range>
explicit unordered_multimap(Range&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Range>
unordered_multimap& operator=(Range&&);
template <class Range> void insert(Range&&);
```

```
template <class Range>
explicit unordered_set(Range&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Range>
unordered_set& operator=(Range&&);
template <class Range> void insert(Range&&);
```

```
template <class Range>
explicit unordered_multiset(Range&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Range>
unordered_multiset& operator=(Range&&);
template <class Range> void insert(Range&&);
```

I'd like to thank Daniel Krügler for help with the wording in this paper, although any remaining mistakes are mine.