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 don't
yet know the full design of the library we want to standardize, but a simple
step we already know is needed is to allow the output of that library to be
passed to existing functions in the standard library that already take an
iterator-pair range.
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:
range must be an array, or have begin() and
end() methods, or the expressions begin(range)
and end(range) must be valid with namespace std
as an associated namespace. These functions must return types that can
initialize variables in the same auto-typed declaration.
(This implies they must return the same type.)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.
The term "Range" is ambiguous between two different meanings. We have "Containers" (loosely), which own the values they refer to. We have "Lightweight Ranges" which only refer to values and don't own them, and we have the union of the two concepts, which Elements of Programming refers to as "Linearizable". "Range" could refer either to "Lightweight Range" or the union concept. To avoid that ambiguity, SG9 voted to call the concept in this paper (the union concept) "Traversable".
Traversable template argumentThere are many sorts of range types, so container methods taking ranges
have to be templated. C++ provides two ways to define templates taking any
object as an input parameter: "const Traversable&" or
"Traversable&&" (where Traversable is a
template argument). This section discusses my choice to use
"Traversable&&".
Methods taking Traversable arguments are overloaded with
other methods taking more precise argument types. Using "const
Traversable&" would naturally leave Container&
arguments for the const Container& overload, but it would
incorrectly capture DerivedFromContainer arguments, just like
"Traversable&&" would.
"Traversable&&" has the benefit that it 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 Traversable&&.
The enable_if
logic is specified as:
Several functions in the standard library take a template argument named "
Traversable". These functions shall not participate in overload resolution ifTraversableis not deduced to a range type. Further, if the function is a container or string’s constructor or operator=, anddecay<Traversable>::typeis 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
Traversable'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, and SG9 agreed.
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.
N3257
modified the definition of the range-based for loop in order to make user
code work when an unconstrained begin() or end()
template is found by ADL. We'd like to follow that behavior in the
implementations of each of the functions proposed in this paper, but
specifying the fallback behavior in a concept definition is messy. The best
solution would be to make std::begin() and
std::end() Just Work, but I was unable to find a technique that
could remove them from the overload set when std was an
associated namespace of the argument type and no more-specialized
begin() was defined. The technique I was using resulted in an
infinite template instantiation recursion in deducing the return type of
begin, which is a hard error in clang, and possibly undefined
behavior in the standard.
This proposal defines std::traversable_begin() and
std::traversable_end() functions in order to simplify the
specification of the concept, but a future revision could find wording to
leave those functions notional instead of defined for users to call.
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 to keep
this first proposal simple and because we don't yet know the more detailed
concepts needed for a full range library, even though we do know the simple
Traversable concept needed for the container methods.
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 N3513
by renaming "Range" to "Traversable" and by specifying the requirements to
search for begin() functions in the same way as the range-based
for loop.
N3513 updated 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.
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 Traversable type (Traversable objects) refer to a
sequence of other objects using a pair of iterators accessed by
std::traversable_begin() and std::traversable_end() functions. Traversable
objects may or may not contain and own these other objects.
This subclause provides definitions for Traversable types and
expressions. In this subclause, t is an instance of a
Traversable type T. i is an instance of
I, known as T's iterator type. V is
T'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 Traversable type if it satisfies the requirements in Table 29
when the expressions are evaluated in the context described below.
| Expression | Return type |
|---|---|
std::traversable_begin(t) | I |
std::traversable_end(t) | I |
*i | implicitly convertible to V |
[ Note: It is unspecified whether a library component that has a
Traversable requirement includes the header <iterator> to
declare std::traversable_begin and
std::traversable_end. — end note ]
Several functions in the standard library take a template argument named
"Traversable". These functions shall not participate in overload
resolution if Traversable is not deduced to a Traversable
type. Further, if the function is a container or string’s constructor or
operator=, and decay<Traversable>::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 Traversable'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 Traversable 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 Traversable, if
Traversable's iterator type does not satisfy at least the Input Iterator
requirements ([input.iterators]), the program is ill-formed, no diagnostic
required. If a Traversable object t is passed such that
[std::traversable_begin(t),std::traversable_end(t)) is not a valid range
([iterator.requirements.general]), the behavior is undefined.
template<class Traversable>
explicit basic_string(Traversable&&, const Allocator& = Allocator());
template<class Traversable>
basic_string& operator=(Traversable&&);
template<class Traversable>
basic_string& operator+=(Traversable&&);
template<class Traversable>
basic_string& append(Traversable&&);
template<class Traversable>
basic_string& assign(Traversable&&);
template<class Traversable>
iterator insert(const_iterator p, Traversable&&);
template<class Traversable>
basic_string& replace(const_iterator, const_iterator, Traversable&&);template<typename Traversable>
explicit basic_string(Traversable&& range, const Allocator& a = Allocator());Effects: Same as basic_string(std::traversable_begin(range), std::traversable_end(range), a).
template<typename Traversable>
basic_string& operator=(Traversable&& range);Effects: this->assign(std::forward<Traversable>(range).
Returns: *this.
template<class Traversable>
basic_string& operator+=(Traversable&& range);Effects: Calls append(std::forward<Traversable>(range)).
Returns: *this.
template<class Traversable>
basic_string& append(Traversable&& range);Effects: Calls append(std::traversable_begin(range), std::traversable_end(range)).
Returns: *this.
template<class Traversable>
basic_string& assign(Traversable&& range);Effects: Calls assign(std::traversable_begin(range), std::traversable_end(range)).
Returns: *this.
template<class Traversable>
iterator insert(const_iterator p, Traversable&& range);Effects: insert(p, std::traversable_begin(range), std::traversable_end(range)).
Returns: An iterator which refers to the copy of the first inserted
character, or p if [std::traversable_begin(range),std::traversable_end(range)) is an empty
range.
template<class Traversable>
basic_string& replace(const_iterator i1, const_iterator i2,
Traversable&& range);Requires: [std::traversable_begin(),i1), [i1,i2), and [std::traversable_begin(range),std::traversable_end(range)) are valid ranges.
Effects: Calls replace(i1 - std::traversable_begin(), i2 - i1, std::traversable_begin(range), std::traversable_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
Traversable object ([range.requirements.implementations]) whose value
type is implicitly convertible to value_type and for which [std::traversable_begin(r),std::traversable_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(std::traversable_begin(r), std::traversable_end(r)) | |
| a = r; | X& | Requires: T is CopyInsertable into X and CopyAssignable. Assigns the range [std::traversable_begin(r),std::traversable_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, std::traversable_begin(r), std::traversable_end(r)). |
| a.assign(r) | void | a.assign(std::traversable_begin(r), std::traversable_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 Traversable object
([range.requirements.implementations]) whose value type is implicitly
convertible to value_type and for which [std::traversable_begin(r),std::traversable_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(std::traversable_begin(r), std::traversable_end(r)). | same as X(std::traversable_begin(r), std::traversable_end(r)). | |
| a = r | X& | Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [std::traversable_begin(r),std::traversable_end(r)) into a. All existing elements of a are either assigned to or destroyed. | NlogN in general (where N has the value distance(std::traversable_begin(r), std::traversable_end(r)) + a.size()); linear if [std::traversable_begin(r),std::traversable_end(r)) is sorted with value_comp(). |
| a.insert(r) | void | Equivalent to a.insert(std::traversable_begin(r), std::traversable_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 Traversable object ([range.requirements.implementations]) whose
value type is implicitly convertible to value_type and for which
[std::traversable_begin(r),std::traversable_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(std::traversable_begin(r), std::traversable_end(r)). | Same as X(std::traversable_begin(r), std::traversable_end(r)). |
| a = r | X& | Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [std::traversable_begin(r),std::traversable_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(std::traversable_begin(r), std::traversable_end(r)). | Same as a.insert( std::traversable_begin(r), std::traversable_end(r)). |
template <class Traversable>
explicit deque(Traversable&&, const Allocator& = Allocator());
template <class Traversable>
deque& operator=(Traversable&&);
template <class Traversable>
void assign(Traversable&&);
template <class Traversable>
iterator insert(const_iterator position, Traversable&&);
template <class Traversable>
iterator insert(const_iterator position, Traversable&&); template <class Traversable>
explicit forward_list(Traversable&&, const Allocator& = Allocator());
template <class Traversable>
forward_list& operator=(Traversable&&);
template <class Traversable>
void assign(Traversable&&);
template <class Traversable>
iterator insert_after(const_iterator position, Traversable&& range);template <class Traversable>
iterator insert_after(const_iterator position, Traversable&& range);Effects: insert_after(p, std::traversable_begin(range), std::traversable_end(range)).
Returns: An iterator pointing to the last inserted element or
position if [std::traversable_begin(range),std::traversable_end(range)) is an empty
range.
template <class Traversable>
explicit list(Traversable&&, const Allocator& = Allocator());
template <class Traversable>
list& operator=(Traversable&&);
template <class Traversable>
void assign(Traversable&&);
template <class Traversable>
iterator insert(const_iterator position, Traversable&& range);template <class Traversable>
iterator insert(const_iterator position, Traversable&&); template <class Traversable>
explicit vector(Traversable&&, const Allocator& = Allocator());
template <class Traversable>
vector& operator=(Traversable&&);
template <class Traversable>
void assign(Traversable&&);
template <class Traversable>
iterator insert(const_iterator position, Traversable&& range);template <class Traversable>
iterator insert(const_iterator position, Traversable&&); template <class Traversable>
vector(Traversable&&, const Allocator& = Allocator()));
template <class Traversable>
vector operator=(Traversable&&);
template <class Traversable>
void assign(Traversable&&);
template <class Traversable>
iterator insert(const_iterator position, Traversable&& range); template <class Traversable>
explicit map(Traversable&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Traversable>
map& operator=(Traversable&&);
template <class Traversable>
void insert(Traversable&&); template <class Traversable>
explicit multimap(Traversable&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Traversable>
multimap& operator=(Traversable&&);
template <class Traversable> void insert(Traversable&&); template <class Traversable>
explicit set(Traversable&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Traversable>
set& operator=(Traversable&&);
template <class Traversable>
void insert(Traversable&&); template <class Traversable>
explicit multiset(Traversable&&,
const Compare& = Compare(),
const Allocator& = Allocator());
template <class Traversable>
multiset& operator=(Traversable&&);
template <class Traversable>
void insert(Traversable&&); template <class Traversable>
explicit unordered_map(Traversable&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Traversable>
unordered_map& operator=(Traversable&&);
template <class Traversable> void insert(Traversable&&); template <class Traversable>
explicit unordered_multimap(Traversable&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Traversable>
unordered_multimap& operator=(Traversable&&);
template <class Traversable> void insert(Traversable&&); template <class Traversable>
explicit unordered_set(Traversable&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Traversable>
unordered_set& operator=(Traversable&&);
template <class Traversable> void insert(Traversable&&); template <class Traversable>
explicit unordered_multiset(Traversable&&,
size_type = see below,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class Traversable>
unordered_multiset& operator=(Traversable&&);
template <class Traversable> void insert(Traversable&&);template <class C> auto traversable_begin(C&& c) -> see below;Returns: std::forward<C>(c).begin() if that
expression is well-formed. Otherwise,
begin(std::forward<C>(c)).
Remarks: If std::forward<C>(c).begin() and
begin(std::forward<C>(c)) are not valid expressions, this
function shall not participate in overload resolution.
[ Note: This function (and similarly traversable_end
below) does not simply call begin(std::forward<C>(c))
(respectively end(std::forward<C>(c))) unqualified because
that wouldn't prefer member functions in the same way as the range-based
for loop, which would result in ambiguities in the presence of other
libraries defining unconstrained begin() functions like the
std::begin() above. — end note ]
template <class C> auto traversable_end(C&& c) -> see below;Returns: std::forward<C>(c).end() if that
expression is well-formed. Otherwise,
end(std::forward<C>(c)).
Remarks: If std::forward<C>(c).end() and
end(std::forward<C>(c)) are not valid expressions, this
function shall not participate in overload resolution.
I'd like to thank Daniel Krügler for help with the wording in this paper, although any remaining mistakes are mine.