ISO/IEC JTC1 SC22 WG21 N3456=12-0146

Date:

Jeffrey Yasskin <jyasskin@google.com>

Range arguments for container constructors and methods, with wording

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'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:

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 Range template argument

There 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:

If … are called with a type Range that does not qualify as a range, or the value type of this range is not convertible to value_type, then these functions and constructor shall not participate in overload resolution. If the constructor or operator= are called with a type Range such that typename remove_cv<typename remove_reference<Range>::type>::type is the type of the container or a type derived from the container type, this constructor and function shall also not participate in overload resolution.

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. This wording isn't present for the std::string range operations because char-like types don't benefit from moving over copying.

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

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.

Wording

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

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

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

Add a paragraph to [string.require]

5 Constructors and member functions taking a Range template argument shall not participate in overload resolution unless Range is a range type (23.2.1) with a value type implicitly convertible to charT.

Add overloads to [string.cons]

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

16 Requires: range is a valid range.

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

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

31 Requires: range is a valid range.

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

33 Returns: *this.

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

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

9 Requires: range is a valid range.

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

11 Returns: *this.

Add an overload to [string::append]

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

21 Requires: range is a valid range.

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

23 Returns: *this.

Add an overload to [string::assign]

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

17 Requires: range is a valid range.

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

19 Returns: *this.

Add an overload to [string::insert]

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

29 Requires: range is a valid range.

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

31 Returns: An iterator which refers to the copy of the first inserted character, or p if range is empty.

Add an overload to [string::replace]

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

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

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

38 Returns: *this.

Add a section "23.2.1 Range requirements [container.requirements.range]"

1 Ranges are objects which refer to a sequence of other objects using a pair of iterators accessed by begin() and end() functions. Ranges may or may not contain and own these objects.

2 In Table 96, R denotes a range class that refers to objects of type T. a denotes an lvalue of type R.

Table 96 — Range requirements
ExpressionReturn type
using std::begin; begin(a)input iterator type whose value type is T
using std::end; end(a)input iterator type whose value type is T

3 In a context where namespace std is an associated namespace, begin(a) returns an iterator referring to the first element in the range. end(a) returns an iterator which is the past-the-end value for the range. A type is known as a range type if common_type<decltype(begin(a)), decltype(end(a))>::type is an InputIterator type (24.2.3). This type is known as the iterator type of the range a. The value type of this iterator is also the value type of the range. [Note: These requirements are intended to match the requirements on _RangeT in the range-based for loop (6.5.4). — end note ]

4 a is a valid range if and only if [begin(a),end(a)) is a valid range.

5 A range a is empty if and only if begin(a) == end(a).

Modify [sequence.reqmts]p3

3 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 valid range (23.2.1) 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 101 — Sequence container requirements (in addition to container)

ExpressionReturn typeAssertion/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);iteratora.insert(p, begin(r), end(r)).
a.assign(r)voida.assign(begin(r), end(r)).

Add a bullet to [sequence.reqmts]p13

Modify [associative.reqmts]p8

8 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 valid range (23.2.1) 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 103 — Associative container requirements (in addition to container)

ExpressionReturn typeAssertion/note
pre-/post-condition		Complexity
X(r);Same as X(begin(r), end(r)).same as X(begin(r), end(r)).
a = rX& 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)voidEquivalent to a.insert(begin(r), end(r)).

Add a paragraph [associative.reqmts]p9

9 For every associative container defined in this Clause, if the constructor

template <class Range>
      explicit X(Range&& range,
        const Compare& = Compare(),
        const Allocator& alloc = Allocator())

or the member functions of the form:

template <class Range> // such as insert(), operator=() rt fx2(Range&& range);

are called with a type Range that does not qualify as a range (23.2.1), or the value type of this range is not convertible to value_type, then these functions and constructor shall not participate in overload resolution. If the constructor or operator= are called with a type Range such that typename remove_cv<typename remove_reference<Range>::type>::type is the type of the container or a type derived from the container type, this constructor and function shall also not participate in overload resolution. Further, 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]

Modify [unord.req]p11

11 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 valid range (23.2.1) 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 104 — Unordered associative container requirements (in addition to container)

ExpressionReturn typeAssertion/note
pre-/post-condition		Complexity
X(r)XSame as X(begin(r), end(r)).Same as X(begin(r), end(r)).
a = rX& 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)voidSame as a.insert(begin(r), end(r)).Same as a.insert( begin(r), end(r)).

Add a paragraph [unord.req]p12

12 For every unordered associative container defined in this Clause, if the constructor

template <class Range>
explicit X(Range&& range,
  size_type = see below,
  const hasher& hf = hasher(),
  const key_equal& eql = key_equal(),
  const allocator_type& a = allocator_type())

or the member functions of the form:

template <class Range> // such as insert(), operator=()
rt fx2(Range&& range);

are called with a type Range that does not qualify as a range (23.2.1), or the value type of this range is not convertible to value_type, then these functions and constructor shall not participate in overload resolution. If the constructor or operator= are called with a type Range such that typename remove_cv<typename remove_reference<Range>::type>::type is the type of the container or a type derived from the container type, this constructor and function shall also not participate in overload resolution. Further, 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]

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

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

Add an insert overload to [deque.modifiers]

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

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

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

Add an insert_after overload to [forwardlist.modifiers]

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

16 Remarks: This signature shall not participate in overload resolution unless Range is a range type whose value type is implicitly convertible to value_type. If the range is passed as an rvalue, it is left in an unspecified state after the call.

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

18 Returns: An iterator pointing to the last inserted element or position if range is empty.

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

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

Add an insert overload to [list.modifiers]

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

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

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

Add an insert overload to [vector.modifiers]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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