Document number: N1857=05-0117

Howard E. Hinnant
2005-08-26

Rvalue Reference Recommendations for Chapter 21

Introduction
21.2 - String classes
21.3 - Class template basic_string

Introduction

This paper recommends proposed wording with respect to the rvalue reference for the C++0X working draft. This paper restricts its scope to Chapter 21 "Strings library" for the purpose of breaking the library work associated with the rvalue reference up into manageable chunks. This paper largely follows the lead of N1771: Impact of the rvalue reference on the Standard Library, but adds more detail as appropriate.

With the exception of this introduction, all non-proposed wording will have a background color and formatting that

looks like this, so that motivation and description is more easily distinguished from proposed wording.

In the proposed wording below, text to be inserted is formatted like this, while wording to be deleted is formatted like ~~this~~.

21.2 - String classes

The recommended changes for chapter 21 have several purposes:

Make basic_string cheaply move constructible and move assignable.

Allow swaping of basic_strings to work with rvalues.

Optimize operator+.

Allow I/O with basic_strings to work with rvalue streams.

-3- Header <string> synopsis

namespace std {
  // 21.1, character traits:
  template<class charT>
    struct char_traits;
  template <> struct char_traits<char>;
  template <> struct char_traits<wchar_t>;

  // 21.3, basic_string:
  template<class charT, class traits = char_traits<charT>,
           class Allocator = allocator<charT> >
    class basic_string;

  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(basic_string<charT,traits,Allocator>&& lhs,
                const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                basic_string<charT,traits,Allocator>&& rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(basic_string<charT,traits,Allocator>&& lhs,
                basic_string<charT,traits,Allocator>&& rhs);
  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const charT* lhs,
                const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(const charT* lhs,
                basic_string<charT,traits,Allocator>&& rhs);
  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(charT lhs, const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(charT lhs, basic_string<charT,traits,Allocator>&& rhs);
  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                const charT* rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(basic_string<charT,traits,Allocator>&& lhs,
                const charT* rhs);
  template<class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>
      operator+(const basic_string<charT,traits,Allocator>& lhs, charT rhs);
  template<class charT, class traits, class Allocator>&&
    basic_string<charT,traits,Allocator>
      operator+(basic_string<charT,traits,Allocator>&& lhs, charT rhs);

  template<class charT, class traits, class Allocator>
    bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator==(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator==(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);
  template<class charT, class traits, class Allocator>
    bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator!=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);

  template<class charT, class traits, class Allocator>
    bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator< (const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);
  template<class charT, class traits, class Allocator>
    bool operator< (const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator> (const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);
  template<class charT, class traits, class Allocator>
    bool operator> (const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  template<class charT, class traits, class Allocator>
    bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator<=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);
  template<class charT, class traits, class Allocator>
    bool operator<=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                    const basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
    bool operator>=(const basic_string<charT,traits,Allocator>& lhs,
                    const charT* rhs);
  template<class charT, class traits, class Allocator>
    bool operator>=(const charT* lhs,
                    const basic_string<charT,traits,Allocator>& rhs);

  // 21.3.7.8:
  template<class charT, class traits, class Allocator>
     void swap(basic_string<charT,traits,Allocator>& lhs,
               basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
     void swap(basic_string<charT,traits,Allocator>&& lhs,
               basic_string<charT,traits,Allocator>& rhs);
  template<class charT, class traits, class Allocator>
     void swap(basic_string<charT,traits,Allocator>& lhs,
               basic_string<charT,traits,Allocator>&& rhs);

  template<class charT, class traits, class Allocator>
   basic_istream<charT,traits>&
    operator>>(basic_istream<charT,traits>&& is,
               basic_string<charT,traits,Allocator>& str);
  template<class charT, class traits, class Allocator>
   basic_ostream<charT, traits>&
    operator<<(basic_ostream<charT, traits>&& os,
               const basic_string<charT,traits,Allocator>& str);
  template<class charT, class traits, class Allocator>
   basic_istream<charT,traits>&
     getline(basic_istream<charT,traits>&& is,
             basic_string<charT,traits,Allocator>& str,
             charT  delim);
  template<class charT, class traits, class Allocator>
   basic_istream<charT,traits>&
     getline(basic_istream<charT,traits>&& is,
             basic_string<charT,traits,Allocator>& str);

  typedef basic_string<char> string;
  typedef basic_string<wchar_t> wstring;
}

21.3 - Class template `basic_string`

-7- ...

...
class basic_string {
  ...
  basic_string(const basic_string& str);
  basic_string(basic_string&& str);
  ...
  basic_string& operator=(const basic_string& str);
  basic_string& operator=(basic_string&& str);
  ...
  basic_string& assign(const basic_string& str);
  basic_string& assign(basic_string&& str);
  ...
  void swap(basic_string&& str);
  ...
};

21.3.1 - `basic_string` constructors

basic_string needs a move construtor and move assignment operator. Additionally the member function assign which simply takes another basic_string has functionality identical to operator= and so can also behave as the move assignment operator.

Insert after paragraph 5:

basic_string(basic_string&& str);

-6- Effects: Constructs an object of class basic_string having the value of the rvalue basic_string referred to by str. The allocator is move constructed from the allocator contained by str. str is left in a valid state with an undefined value.

-7- Throws: Nothing if the allocator's move constructor does not throw.

Insert after paragraph 19:

basic_string&
operator=(basic_string&& str);

-20- Effects: Assigns to this the value of str, leaving str in a valid but undefined state. [Note: a valid implementation is swap(str) --end note.]

-21- Throws: Nothing.

-22- Returns: *this.

21.3.5.3 - `basic_string::assign`

Insert after paragraph 1:

basic_string&
assign(basic_string&& str);

-2- Effects: Assigns to this the value of str, leaving str in a valid but undefined state. [Note: a valid implementation is swap(str) --end note.]

-3- Throws: Nothing.

-4- Returns: *this.

21.3.5.8 - `basic_string::swap`

Why swap needs modification is worthy of some discussion. The current shrink-to-fit idiom is:
string s;
...
string(s).swap(s);
Note that this idiom isn't strictly needed for basic_string because of its special reserve semantics. Nonetheless it is a popular idiom. This paper proposes to also allow the following idioms to accomplish the same thing:
s.swap(string(s));
swap(s, string(s));
swap(string(s), s);
That is, this paper proposes more flexibility with the syntax of swap. It is perfectly safe and reasonable to swap an lvalue with an rvalue. And that is what is being proposed herein. It will still not be allowed to swap two rvalues using the namespace scope swap function (what would be the point?).
swap(string(s), string(s));  // error, no matching function call
It will however be allowed to swap an rvalue with an rvalue using the member swap function:
string(s).swap(string(s));  // ok, but useless
Even though this is useless, it is allowed in order to enable:
s.swap(string(s));
In order to disable swaping two rvalues with the member swap we would need to adopt N1784 which allows overloading on the lvalue-rvalue-ness of the implicit object parameter. The syntax might look something like:
...
class basic_string {
  ...
  void swap(basic_string&  str) &;
  void swap(basic_string&& str) &;
  void swap(basic_string&  str) &&;
  ...
};
That is, when member swap is called with an lvalue basic_string, both lvalue and rvalue basic_string arguments are allowed. However when member swap is called with an rvalue basic_string, only lvalue basic_string arguments are allowed.

This paper provides no recommendation concerning N1784 and merely hopes to clarify how N1784 might affect the standard library. This paper currently simply recommends the member function:
 void swap(basic_string&& s);
and the non-member functions:
template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>& lhs,
             basic_string<charT,traits,Allocator>& rhs);
template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>&& lhs,
             basic_string<charT,traits,Allocator>& rhs);
template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>& lhs,
             basic_string<charT,traits,Allocator>&& rhs);

 void swap(basic_string<charT,traits,Allocator>&& s);

21.3.7 - `basic_string` non-member functions

21.3.7.1 - `operator+`

The changes to operator+ represent an optimization opportunity.

The basic idea is that if in a string + string operation, if one of the strings is an rvalue, then it is faster to simply append (or insert) to that rvalue and return it (by reference), rather than create a new string to hold the concatenation. By doing so, expressions involving several + operations effectively only create a single temporary in which the capacity is allowed to accumulate over the entire expression.

Because of the (proposed) overloading (pseudo-code):
string   operator+(const string& , const string& );
string&& operator+(      string&&, const string& );
string&& operator+(const string& ,       string&&);
string&& operator+(      string&&,       string&&);
it is guaranteed that if an rvalue argument is given to operator+, then it will bind to a string&&. And if an lvalue (or const rvalue) argument is given to operator+, it will bind to a const string&. The second overload might be implemented as:
string&&
operator+(string&& x, const string& y)
{
    return x += y;
}
That is, since x is an rvalue, it is safe to modify it. And x may already have sufficient capacity to perform the concatenation, and so a call to the string's allocator may be avoided. And finally, x may be returned by rvalue reference (instead of by value) as this will be faster, even if the return by value is optimized with a move construction of x.

In contrast, when concatenating two lvalues (the first - and existing - overload), the function must create a new string to hold the concatenation and return it by value.

Consider an expression which performs several string concatenations:
string s1, s2, s3, s4, s5;
string r = s1 + s2 + s3 + s4 + s5;
The first concatenation (of s1 and s2) will use the overload taking two lvalues, and return a temporary by value. All other concatenations will use the second overload, binding the temporary returned from the previous concatenation to the lhs argument. And once this temporary is returned from the first concatenation, it continues to exist throughout the entire chain. It is passed by reference throughout the expression, accumulating capacity along the way. In essence, the above expression executes as if the client had coded:
string s1, s2, s3, s4, s5;
string temp = s1 + s2;
temp += s3;
temp += s4;
temp += s5;
string r = move(temp);
Contrast the above with the expanded pseudo-code which results from current (copy semantics) implementations:
string s1, s2, s3, s4, s5;
string temp1 = s1 + s2;
string temp2 = temp1 + s3;
string temp3 = temp2 + s4;
string r = temp3 + s5;
That is, currently a concatenation expression constructs (and destructs) a number of temporaries that scales linearly with the number of + operations in the expression. And capacity is not passed from temporary to temporary. The proposed (move-optimized) code limits the number of temporaries to just one, and will accumulate capacity in that single temporary at a geometric growth rate.

template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>
    operator+(const basic_string<charT,traits,Allocator>& lhs,
              const basic_string<charT,traits,Allocator>& rhs);

-1- Returns: basic_string<charT,traits,Allocator>(lhs).append(rhs).

template<class charT, class traits, class Allocator>&&
  basic_string<charT,traits,Allocator>
    operator+(basic_string<charT,traits,Allocator>&& lhs,
              const basic_string<charT,traits,Allocator>& rhs);

-2- Returns: lhs.append(rhs).

template<class charT, class traits, class Allocator>&&
  basic_string<charT,traits,Allocator>
    operator+(const basic_string<charT,traits,Allocator>& lhs,
              basic_string<charT,traits,Allocator>&& rhs);

-3- Returns: rhs.insert(0, lhs).

template<class charT, class traits, class Allocator>&&
  basic_string<charT,traits,Allocator>
    operator+(basic_string<charT,traits,Allocator>&& lhs,
              basic_string<charT,traits,Allocator>&& rhs);

-4- Returns: lhs.append(rhs). [Note: or equivalently rhs.insert(0, lhs) --end note]

template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>
    operator+(const charT* lhs,
              const basic_string<charT,traits,Allocator>& rhs);

-5- Returns: basic_string<charT,traits,Allocator>(lhs) + rhs.

-6- Remarks: Uses traits::length().


template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>&&
    operator+(const charT* lhs,
              basic_string<charT,traits,Allocator>&& rhs);

-7- Returns: rhs.insert(0, lhs).

-8- Remarks: Uses traits::length().

template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>
    operator+(charT lhs,
              const basic_string<charT,traits,Allocator>& rhs);

-9- Returns: basic_string<charT,traits,Allocator>(1, lhs) + rhs.


template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>&&
    operator+(charT lhs,
              basic_string<charT,traits,Allocator>&& rhs);

-10- Returns: rhs.insert(0, 1, lhs).

template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>
    operator+(const basic_string<charT,traits,Allocator>& lhs,
              const charT* rhs);

-11- Returns: lhs + basic_string<charT,traits,Allocator>(rhs).

-12- Remarks: Uses traits::length().


template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>&&
    operator+(basic_string<charT,traits,Allocator>&& lhs,
              const charT* rhs);

-13- Returns: lhs.append(rhs).

-14- Remarks: Uses traits::length().

template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>
    operator+(const basic_string<charT,traits,Allocator>& lhs,
              charT rhs);

-15- Returns: lhs + basic_string<charT,traits,Allocator>(1, rhs).


template<class charT, class traits, class Allocator>
  basic_string<charT,traits,Allocator>&&
    operator+(basic_string<charT,traits,Allocator>&& lhs,
              charT rhs);

-16- Returns: lhs.append(1, rhs).

21.3.7.8 - `swap`

template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>& lhs,
             basic_string<charT,traits,Allocator>& rhs);
template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>&& lhs,
             basic_string<charT,traits,Allocator>& rhs);
template<class charT, class traits, class Allocator>
   void swap(basic_string<charT,traits,Allocator>& lhs,
             basic_string<charT,traits,Allocator>&& rhs);

-1- Effects: lhs.swap(rhs).

21.3.7.9 - Inserters and extractors

This section enables basic_string I/O to work with rvalue streams as motivated in N1690. For example clients may want to write a string to a log file, constructing, opening, writing, closing and destructing the ofstream object all with a single statement:
string s;
...
ofstream("LogFile", ios::app) << s;
istreams may also be useful to the client in an rvalue form. They could for example be used to parse one string into another string:
string input("one 1");
string word;
int i;
istringstream(input) >> word >> i;  // word == "one", i == 1
The use of the istringstream in the above example becomes an implementation detail not worthy of even an identifier. It is simply a tool created and discarded to split input into word and i.

template<class charT, class traits, class Allocator>
 basic_istream<charT,traits>&
  operator>>(basic_istream<charT,traits>&& is,
             basic_string<charT,traits,Allocator>& str);

...

template<class charT, class traits, class Allocator>
 basic_ostream<charT, traits>&
  operator<<(basic_ostream<charT, traits>& os,
             const basic_string<charT,traits,Allocator>& str);

template<class charT, class traits, class Allocator>
 basic_ostream<charT, traits>&
  operator<<(basic_ostream<charT, traits>&& os,
             const basic_string<charT,traits,Allocator>& str);

...

template<class charT, class traits, class Allocator>
 basic_istream<charT,traits>&
   getline(basic_istream<charT,traits>&& is,
           basic_string<charT,traits,Allocator>& str,
           charT  delim);

...

template<class charT, class traits, class Allocator>
 basic_istream<charT,traits>&
   getline(basic_istream<charT,traits>&& is,
           basic_string<charT,traits,Allocator>& str);

Rvalue Reference Recommendations for Chapter 21

Contents

Related papers

Introduction

21.2 - String classes

21.3 - Class template `basic_string`

21.3.1 - `basic_string` constructors

21.3.5.3 - `basic_string::assign`

21.3.5.8 - `basic_string::swap`

21.3.7 - `basic_string` non-member functions

21.3.7.1 - `operator+`

21.3.7.8 - `swap`

21.3.7.9 - Inserters and extractors

Rvalue Reference Recommendations for Chapter 21

Contents

Related papers

Introduction

21.2 - String classes

21.3 - Class template basic_string

21.3.1 - basic_string constructors

21.3.5.3 - basic_string::assign

21.3.5.8 - basic_string::swap

21.3.7 - basic_string non-member functions

21.3.7.1 - operator+

21.3.7.8 - swap

21.3.7.9 - Inserters and extractors

21.3 - Class template `basic_string`

21.3.1 - `basic_string` constructors

21.3.5.3 - `basic_string::assign`

21.3.5.8 - `basic_string::swap`

21.3.7 - `basic_string` non-member functions

21.3.7.1 - `operator+`

21.3.7.8 - `swap`