ISO/IEC JTC1 SC22 WG21 N????

Date:

Jeffrey Yasskin <jyasskin@google.com>

Traversable arguments for container constructors and methods, wording revision 4

Skip table of contents

Overview

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:

Second, many container methods have a pair of overloads, one taking an initializer_list<value_type> argument, and the other taking two Iterators with a templated type. 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 of those pairs. One priority_queue constructor takes a templated Iterator pair without accepting an initializer_list, and dynarray's constructor takes an initializer_list without accepting general iterators. These should be reconciled in a future paper or issue.

On Naming

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".

The Traversable template parameter

There 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 parameter). This section discusses my choice to use "Traversable&&".

Methods taking Traversable parameters are overloaded with other methods taking more precise parameter 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 parameter named "Traversable". These functions shall not participate in overload resolution if any of the following conditions is satisfied:

Access checking is performed as if in a context unrelated to Traversable. Only the validity of the immediate context of the described expressions is considered.

Further, if the function is a class type's constructor or operator=, and decay<Traversable>::type is the class type or a type derived from the class type, the function shall not participate in overload resolution. Implementations may also 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 type of elements in the sequence ([iterator.requirements]) the function modifies or creates, 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.

That pesky ADL problem

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::range_begin() and std::range_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.

Examples

Using Boost.Range with standard containers

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.

N3430's split() without a conversion operator

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.

Paper revision history

This paper updates N3686 by:

N3686 updated 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.

Wording

Clause 17, Library introduction

Modify [utility.requirements]

[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.

Add a sub-section under [utility.requirements], "# Traversable requirements [range.requirements]"

Objects of Traversable type (Traversable objects) refer to a sequence of other objects using a pair of iterators accessed by std::range_begin() and std::range_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 denotes a value of a (possibly const) Traversable type T. i denotes a value of type (possibly const) I, known as T's iterator type. V denotes 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]

Add a sub-section under [range.requirements], "#.1 Functions taking Traversable types [range.requirements.implementations]"

T is a Traversable type if it satisfies the requirements in Table XX.

Table XX — Traversable requirements
ExpressionReturn type
std::range_begin(t)I
std::range_end(t)I
*iimplicitly convertible to V

[ Note: It is unspecified whether a library component that has a Traversable requirement includes the header <iterator> to declare std::range_begin and std::range_end. — end note ]

Several functions in the standard library take a template parameter named "Traversable". These functions shall not participate in overload resolution if any of the following conditions is satisfied:

Access checking is performed as if in a context unrelated to Traversable. Only the validity of the immediate context of the described expressions is considered.

Further, if the function is a class type's constructor or operator=, and decay<Traversable>::type is the class type or a type derived from the class type, the function shall not participate in overload resolution. Implementations may also 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 type of elements in the sequence ([iterator.requirements]) the function modifies or creates, 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]

Add a sub-section under [range.requirements], "#.2 Passing Traversable arguments [range.requirements.calls]"

In calls to functions taking template parameters 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::range_begin(t),std::range_end(t)) is not a valid range ([iterator.requirements.general]), the behavior is undefined.

Clause 21, Strings library

Add to the std::basic_string definition in [basic.string]

    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&&);

Add overloads to [string.cons]

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

Effects: Equivalent to basic_string(std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range)), a).

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

Effects: Equivalent to return this->assign(std::forward<Traversable>(range)).

Add an overload to [string::op+=]

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

Effects: Equivalent to return append(std::forward<Traversable>(range)).

Add an overload to [string::append]

template<class Traversable>
  basic_string& append(Traversable&& range);

Effects: Equivalent to return append(std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range))).

Add an overload to [string::assign]

template<class Traversable>
  basic_string& assign(Traversable&& range);

Effects: Equivalent to return assign(std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range))).

Add an overload to [string::insert]

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

Effects: Equivalent to return insert(p, std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range))).

Add an overload to [string::replace]

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

Effects: Equivalent to return replace(i1, i2, std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range))).

Clause 23, Containers library

Modify [sequence.reqmts]

In Tables 100 and 101, 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, 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&&.

Add rows to Table 100 — Sequence container requirements (in addition to container)

ExpressionReturn typeAssertion/note
pre-/post-condition
X(r);Equivalent to X(std::range_begin(r), std::range_end(r))
a = r; X&Requires: T is CopyInsertable into X and CopyAssignable. Assigns the range [std::range_begin(r),std::range_end(r)) into a. All existing elements of a are either assigned to or destroyed. Returns: *this.
a.insert(p, r);iteratora.insert(p, std::range_begin(r), std::range_end(r)).
a.assign(r)voida.assign(std::range_begin(r), std::range_end(r)).

Modify [associative.reqmts]

In Table 102, 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, 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.

Add rows to Table 102 — Associative container requirements (in addition to container)

ExpressionReturn typeAssertion/note
pre-/post-condition		Complexity
X(r);Same as X(std::range_begin(r), std::range_end(r)).same as X(std::range_begin(r), std::range_end(r)).
a = rX& Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [std::range_begin(r),std::range_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::range_begin(r), std::range_end(r)) + a.size()); linear if [std::range_begin(r),std::range_end(r)) is sorted with value_comp().
a.insert(r)voidEquivalent to a.insert(std::range_begin(r), std::range_end(r)).

Modify [unord.req]

In table 103: 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, 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.

Add rows to Table 103 — Unordered associative container requirements (in addition to container)

ExpressionReturn typeAssertion/note
pre-/post-condition		Complexity
X(r)XSame as X(std::range_begin(r), std::range_end(r)).Same as X(std::range_begin(r), std::range_end(r)).
a = rX& Requires: value_type is CopyInsertable into X and CopyAssignable. Effects: Assigns the range [std::range_begin(r),std::range_end(r)) into a. All existing elements of a are either assigned to or destroyed. Same as a = X(r).
a.insert(r)voidSame as a.insert(std::range_begin(r), std::range_end(r)).Same as a.insert( std::range_begin(r), std::range_end(r)).

Add to the std::deque definition in [deque.overview]

    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&&);

Add an insert overload to [deque.modifiers]

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

Add to the std::forward_list definition in [forwardlist.overview]

    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);

Add an insert_after overload to [forwardlist.modifiers]

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

Effects: Equivalent to return insert_after(position, std::range_begin(std::forward<Traversable>(range)), std::range_end(std::forward<Traversable>(range))).

Add to the std::list definition in [list.overview]

    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);

Add an insert overload to [list.modifiers]

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

Add to the std::vector definition in [vector.overview]

    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);

Add an insert overload to [vector.modifiers]

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

Add to the std::vector<bool> definition in [vector.bool]

    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);

Add to the std::map definition in [map.overview]

    template <class Traversable>
      explicit map(Traversable&&,
        const Compare& = Compare(),
        const Allocator& = Allocator());
    template <class Traversable>
      explicit map(Traversable&& t, const Allocator& a)
        : map(std::forward<Traversable>(t), Compare(), a) { }
    template <class Traversable>
      map& operator=(Traversable&&);
    template <class Traversable>
      void insert(Traversable&&);

Add to the std::multimap definition in [multimap.overview]

    template <class Traversable>
      explicit multimap(Traversable&&,
        const Compare& = Compare(),
        const Allocator& = Allocator());
    template <class Traversable>
      explicit multimap(Traversable&& t, const Allocator& a)
        : multimap(std::forward<Traversable>(t), Compare(), a) { }
    template <class Traversable>
      multimap& operator=(Traversable&&);
    template <class Traversable> void insert(Traversable&&);

Add to the std::set definition in [set.overview]

    template <class Traversable>
      explicit set(Traversable&&,
        const Compare& = Compare(),
        const Allocator& = Allocator());
    template <class Traversable>
      explicit set(Traversable&& t, const Allocator& a):
        set(std::forward<Traversable>(t), Compare(), a) { }
    template <class Traversable>
      set& operator=(Traversable&&);
    template <class Traversable>
      void insert(Traversable&&);

Add to the std::multiset definition in [multiset.overview]

    template <class Traversable>
      explicit multiset(Traversable&&,
        const Compare& = Compare(),
        const Allocator& = Allocator());
    template <class Traversable>
      explicit multiset(Traversable&& t, const Allocator& a)
        : multiset(std::forward<Traversable>(t), Compare(), a) { }
    template <class Traversable>
      multiset& operator=(Traversable&&);
    template <class Traversable>
      void insert(Traversable&&);

Add to the std::unordered_map definition in [unord.map.overview]

    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>
      explicit unordered_map(Traversable&& t,
        size_type n,
        const allocator_type& a)
        : unordered_map(std::forward<Traversable>(t), n, hasher(), a) { }
    template <class Traversable>
      explicit unordered_map(Traversable&& t,
        size_type n,
        const hasher& hf,
        const allocator_type& a):
        : unordered_map(std::forward<Traversable>(t), n, hf, key_equal(), a) { }
    template <class Traversable>
      unordered_map& operator=(Traversable&&);
    template <class Traversable> void insert(Traversable&&);

Add to the std::unordered_multimap definition in [unord.multimap.overview]

    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>
      explicit unordered_multimap(Traversable&& t,
        size_type n,
        const allocator_type& a)
        : unordered_multimap(std::forward<Traversable>(t), n, hasher(), a) { }
    template <class Traversable>
      explicit unordered_multimap(Traversable&& f,
        size_type n,
        const hasher& hf,
        const allocator_type& a)
        : unordered_multimap(std::forward<Traversable>(t), n, hf, key_equal(), a) { }
    template <class Traversable>
      unordered_multimap& operator=(Traversable&&);
    template <class Traversable> void insert(Traversable&&);

Add to the std::unordered_set definition in [unord.set.overview]

    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>
      explicit unordered_set(Traversable&& t,
        size_type n,
        const allocator_type& a)
        : unordered_set(std::forward<Traversable>(t), n, hasher(), a) { }
    template <class Traversable>
      explicit unordered_set(Traversable&& t,
        size_type n,
        const hasher& hf,
        const allocator_type& a)
        : unordered_set(std::forward<Traversable>(t), n, hf, key_equal(), a) { }
    template <class Traversable>
      unordered_set& operator=(Traversable&&);
    template <class Traversable> void insert(Traversable&&);

Add to the std::unordered_multiset definition in [unord.multiset.overview]

    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>
      explicit unordered_multiset(Traversable&& t,
        size_type n,
        const allocator_type& a);
        : unordered_multiset(std::forward<Traversable>(t), n, hasher(), a) { }
    template <class Traversable>
      explicit unordered_multiset(Traversable&& t,
        size_type n,
        const hasher& hf,
        const allocator_type& a)
        : unordered_multiset(std::forward<Traversable>(t), n, hf, key_equal(), a) { }
    template <class Traversable>
      unordered_multiset& operator=(Traversable&&);
    template <class Traversable> void insert(Traversable&&);

Clause 24, Iterators library

Add to [iterator.range]

template <class C> auto range_begin(C&& c) -> see below;

Returns: std::forward<C>(c).begin() if that expression is well-formed. Otherwise, begin(std::forward<C>(c)).

Remarks: This function shall not participate in overload resolution unless at least one of the expressions std::forward<C>(c).begin() and begin(std::forward<C>(c)) is well-formed when considered as an unevaluated operand.

[ Note: This function (and similarly range_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 range_end(C&& c) -> see below;

Returns: std::forward<C>(c).end() if that expression is well-formed. Otherwise, end(std::forward<C>(c)).

Remarks: This function shall not participate in overload resolution unless at least one of the expressions std::forward<C>(c).end() and end(std::forward<C>(c)) is well-formed when considered as an unevaluated operand.

Acknowledgements

I'd like to thank the ranges study group for picking a name for this concept, and Daniel Krügler for immense help with the wording in this paper, although any remaining mistakes are mine.