Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Durability of string's reverse iterators for self appending

The question:

Suppose I have a string, and I want to generate a new string that has the original string and its reverse concatenated.

Is the following guaranteed to work?

auto pq = [](std::string &s){
    s.reserve(2*s.size());
    s.append(s.rbegin(), s.rend());
};

I see that reserve is supposed to set capacity appropriately. But, does applying append against the reverse iterators cause invalidation of those iterators?

Additional background:

My copy for C++.11 (which has the same language as the C++.17 draft), says in §[string.capacity]

void reserve(size_type res_arg=0);

  1. The member function reserve() is a directive that informs a basic_string object of a planned change in size, so that it can manage the storage allocation accordingly.
  2. Effects: After reserve(), capacity() is greater or equal to the argument of reserve. [ Note: Calling reserve() with a res_arg argument less than capacity() is in effect a non-binding shrink request. A call with res_arg <= size() is in effect a non-binding shrink-to-fit request. — end note ]
  3. Throws: length_error if res_arg > max_size().227

227) reserve() uses allocator_traits::allocate() which may throw an appropriate exception.

While, §[string.append] says

basic_string&
append(const charT* s, size_type n);

  1. Requires: s points to an array of at least n elements of charT.
  2. Throws: length_error if size() + n > max_size().
  3. Effects: The function replaces the string controlled by *this with a string of length size() + n whose first size() elements are a copy of the original string controlled by *this and whose remaining elements are a copy of the initial n elements of s.
  4. Returns: *this.
like image 960
jxh Avatar asked Mar 06 '23 04:03

jxh


2 Answers

This is not the overload of std::string::append you actually call. The one you call is template<class InputIterator> basic_string& append(InputIterator first, InputIterator last);. There, the standard says ([string.append]/21) it is equivalent to constructing a new string before appending:

Effects: Equivalent to append(basic_­string(first, last, get_­allocator())).

Note that here, the constructor call basic_­string(first, last, get_­allocator()) creates a temporary string before the call to a different overload of append, so whatever re-allocation happens in the other append is irrelevant. That means that, even without calling reserve first, this should be safe.

Note that there is no guarantee that string is implemented exactly this way; the standard says "Equivalent to", not "Implemented as". The implementation can do anything which has the same results, but in this case "the same results" means that it still needs to work with iterators derived from the same string this is called on.

like image 75
Daniel H Avatar answered Apr 27 '23 01:04

Daniel H


EDIT

I do not believe this answer is correct anymore, see comments. But for the sake of preserving valuable comments I am leaving the answer there.

The most straightforward of append would look something like:

template<class T>
void string::append(T begin, T end) {
    reserve(size() + std::distance(end, begin));
    while (; begin != end; ++begin) {
       *this += *begin;
    }
}

Since iterators should not be invalidated after the reserve, begin will still be valid for dereferencing and incrementing during the whole function.

In the example above, reserve is guaranteed to be no-op from the latest draft I have access to (http://eel.is/c++draft/string.capacity):

(24.3.2.4) void reserve(size_type res_arg);

#Effects: A directive that informs a basic_­string of a planned change in size, so that the storage allocation can be managed accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve()

like image 23
SergeyA Avatar answered Apr 27 '23 01:04

SergeyA