C ++ 11에서 COW std :: string 구현의 적법성

C ++ 11에서 COW std :: string 구현의 적법성

---

copy-on-write가 std::stringC ++ 11에서 준수를 구현하는 실용적인 방법이 아니라는 것을 알고 있었지만 최근에 토론에서 나왔을 때 나는 그 진술을 직접적으로 뒷받침 할 수 없다는 것을 알았습니다.

C ++ 11이 COW 기반 구현을 인정하지 않는 것이 맞 std::string습니까?

그렇다면이 표준이 새로운 표준 어딘가에 명시 적으로 명시되어 있습니까?

또는 std::stringCOW 기반 구현을 배제하는 새로운 요구 사항의 결합 된 효과라는 점에서이 제한이 암시 std::string됩니다. 이 경우 'C ++ 11은 COW 기반 std::string구현을 효과적으로 금지합니다'라는 장 및 구절 스타일 도출에 관심이 있습니다 .

---

표준 21.4.1 p6에 따라 반복자 / 참조 무효화는 다음에 대해서만 허용되므로 허용되지 않습니다.

— const가 아닌 basic_string에 대한 참조를 인수로 사용하는 표준 라이브러리 함수에 대한 인수입니다.

— operator [], at, front, back, begin, rbegin, end 및 rend를 제외한 비 const 멤버 함수 호출.

COW 문자열의 경우, non-const를 호출 operator[]하면 위의 단락에서 허용하지 않는 사본 (및 무효화 참조)을 작성해야합니다. 따라서 C ++ 11에서 COW 문자열을 갖는 것은 더 이상 합법적이지 않습니다.

---

Dave S 와 gbjbaanb 의 답변 은 정확합니다 . (그리고 Luc Danton도 정확하지만 COW 현을 금지하는 원래 규칙보다는 COW 현을 금지하는 부작용이 더 많습니다.)

그러나 혼란을 없애기 위해 추가 설명을 추가하겠습니다. 다양한 의견 은 GCC bugzilla에 대한 나의 의견에 연결되며 다음 예제를 제공합니다.

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

이 예제의 요점은 GCC의 참조 카운트 (COW) 문자열이 C ++ 11에서 유효하지 않은 이유를 설명하는 것입니다. C ++ 11 표준을 사용하려면이 코드가 올바르게 작동해야합니다. 코드의 어떤 것도 pC ++ 11에서 무효화 될 수 없습니다 .

GCC의 이전 참조 횟수 std::string구현을 사용하면 해당 코드 p 가 무효화되어 매달려있는 포인터가되기 때문에 정의되지 않은 동작 이 있습니다. (무슨 일 때이다 s2구성되어 그것과 데이터를 공유 s하지만, 비아 비 CONST 참조 구하기 s[0]때문에, 데이터는 비공유 요구 s기준이 때문에 "이 기록 복사"않는 s[0]잠재적으로 기록하는 데 사용될 수 s후, s2진행 범위를 벗어난으로 표시된 배열을 파괴합니다 p.

C ++ 03 표준에서는 명시 적으로 21.3 [lib.basic.string] p5에서 해당 동작 을 허용합니다. 여기서 data()첫 번째 호출에 대한 호출 이후에 operator[]()포인터, 참조 및 반복자가 무효화 될 수 있습니다. 따라서 GCC의 COW 문자열은 유효한 C ++ 03 구현이었습니다.

C ++ 11 표준은 더 이상 호출을 operator[]()수행하는지 여부에 관계없이 포인터, 참조 또는 반복자를 무효화 할 수있는 호출이 없기 때문에 더 이상 해당 동작을 허용하지 않습니다data() .

따라서 위의 예 는 C ++ 11에서 작동 해야 하지만 libstdc ++의 종류의 COW 문자열에서는 작동 하지 않으므로 C ++ 11에서는 해당 종류의 COW 문자열이 허용되지 않습니다.

---

그것은 CoW가 더 빠른 문자열을 만드는 데 허용되는 메커니즘입니다 ...

그것은 멀티 스레딩 코드를 느리게 만듭니다 (많은 문자열을 사용할 때 유일한 쓰기로 성능을 저하시키는 지 확인하는 모든 잠금). 이것이 CoW가 몇 년 전에 사망 한 주된 이유였습니다.

다른 이유는 []다른 사람이 변경하지 않을 것으로 예상되는 문자열을 덮어 쓰기위한 보호없이 연산자가 문자열 데이터를 반환하기 때문입니다. 동일하게 적용 c_str()하고 data().

빠른 구글은 멀티 스레딩이 기본적으로 효과적으로 허용되지 않는 이유 라고 말합니다 (명시 적으로 아님).

제안은 말한다 :

신청

모든 반복자와 요소 액세스 작업을 동시에 안전하게 실행할 수 있도록 제안합니다.

순차 코드에서도 작업의 안정성을 높이고 있습니다.

이 변경으로 인해 COW (Copy-On-Write) 구현이 효과적으로 허용되지 않습니다.

뒤에

COW (Copy-On-Write) 구현에서 전환으로 인한 성능의 잠재적 인 최대 손실은 매우 큰 읽기 전용 문자열을 가진 응용 프로그램의 메모리 소비가 증가한다는 것입니다. 그러나 이러한 응용 분야에서는 로프가 더 나은 기술 솔루션이라고 생각하며 라이브러리 TR2에 로프 제안을 포함시킬 것을 권장합니다.

로프 는 STLPort 및 SGI STL의 일부입니다.

---

21.4.2에서 basic_string 생성자 및 대입 연산자 [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2 효과 : basic_string표 64에 표시된대로 클래스의 객체를 구성합니다. [...]

표 64는이 (복사) 생성자를 통해 객체를 생성 한 후 this->data()값이 다음과 같이 문서화 되어 있습니다.

str.data ()로 첫 번째 요소를 가리키는 배열의 할당 된 사본의 첫 번째 요소를 가리 킵니다.

There are similar requirements for other similar constructors.

---

Since it is now guaranteed that strings are stored contiguously and you are now allowed to take a pointer to the internal storage of a string, (i.e. &str[0] works like it would for an array), it's not possible to make a useful COW implementation. You would have to make a copy for way too many things. Even just using operator[] or begin() on a non-const string would require a copy.

---

Is COW basic_string prohibited in C++11 and later?

Regarding

” Am I correct that C++11 does not admit COW based implementations of std::string?

Yes.

Regarding

” If so, is this restriction explicitly stated somewhere in the new standard (where)?

거의 직접적으로,COW 구현에서 문자열 데이터의O ( n ) 물리적 복사를필요로하는 다수의 연산에 대한 일정한 복잡성의 요구에 의해.

예를 들어 멤버 함수의 경우

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

... COW 구현에서 문자열 값을 공유 해제하기 위해 문자열 데이터 복사를 트리거 할 수있는 C ++ 11 표준은

C ++ 11 §21.4.5 / 4 :

" 복잡성 : 일정 시간.

… 그러한 데이터 복사, 따라서 COW를 배제합니다.

C++03 supported COW implementations by not having these constant complexity requirements, and by, under certain restrictive conditions, allowing calls to operator[](), at(), begin(), rbegin(), end(), or rend() to invalidate references, pointers and iterators referring to the string items, i.e. to possibly incur a COW data copying. This support was removed in C++11.

---

Is COW also prohibited via the C++11 invalidation rules?

In another answer which at the time of writing is selected as solution, and which is heavily upvoted and therefore apparently believed, it's asserted that

” For a COW string, calling non-const operator[] would require making a copy (and invalidating references), which is disallowed by the [quoted] paragraph above [C++11 §21.4.1/6]. Hence, it's no longer legal to have a COW string in C++11.

That assertion is incorrect and misleading in two main ways:

• It incorrectly indicates that only the non-const item accessors need to trigger a COW data copying.
  But also the const item accessors need to trigger data copying, because they allow client code to form references or pointers that (in C++11) it's not permitted to invalidate later via the operations that can trigger COW data copying.
• It incorrectly assumes that COW data copying can cause reference invalidation.
  But in a correct implementation COW data copying, un-sharing the string value, is done at a point before there are any references that can be invalidated.

To see how a correct C++11 COW implementation of basic_string would work, when the O(1) requirements that make this invalid are ignored, think of an implementation where a string can switch between ownership policies. A string instance starts out with policy Sharable. With this policy active there can be no external item references. The instance can transition to Unique policy, and it must do so when an item reference is potentially created such as with a call to .c_str() (at least if that produces a pointer to the internal buffer). In the general case of multiple instances sharing ownership of the value, this entails copying the string data. After that transition to Unique policy the instance can only transition back to Sharable by an operation that invalidates all references, such as assignment.

So, while that answer's conclusion, that COW strings are ruled out, is correct, the reasoning offered is incorrect and strongly misleading.

I suspect the cause of this misunderstanding is a non-normative note in C++11's annex C:

C++11 §C.2.11 [diff.cpp03.strings], about §21.3:

Change: basic_string requirements no longer allow reference-counted strings
Rationale: Invalidation is subtly different with reference-counted strings. This change regularizes behavor (sic) for this International Standard.
Effect on original feature: Valid C ++ 2003 code may execute differently in this International Standard

여기에 근거은 기본을 설명 하는 이유 중 하나는 C ++ 03 특별 COW 지원을 제거하기로 결정했다. 이 근거는 왜 ,없는 방법 표준을 효과적으로 COW 구현을 허용하지 않습니다. 이 표준은 O (1) 요구 사항을 통한 COW를 허용하지 않습니다.

간단히 말해 C ++ 11 무효화 규칙은의 COW 구현을 배제하지 않습니다 std::basic_string. 그러나 그들은 g ++의 표준 라이브러리 구현 중 하나에서와 같이 합리적으로 효율적인 무제한 C ++ 03 스타일 COW 구현을 배제합니다. 특수한 C ++ 03 COW 지원 const은 무효화에 대한 미묘하고 복잡한 규칙을 희생 하면서 특히 항목 접근자를 사용하여 실질적인 효율성을 허용했습니다 .

"처음 호출"COW 지원을 포함하는 C ++ 03 §21.3 / 5 :

” References, pointers, and iterators referring to the elements of a basic_string sequence may be invalidated by the following uses of that basic_string object:
— As an argument to non-member functions swap() (21.3.7.8), operator>>() (21.3.7.9), and getline() (21.3.7.9).
— As an argument to basic_string::swap().
— Calling data() and c_str() member functions.
— Calling non-const member functions, except operator[](), at(), begin(), rbegin(), end(), and rend().
— Subsequent to any of the above uses except the forms of insert() and erase() which return iterators, the first call to non-const member functions operator[](), at(), begin(), rbegin(), end(), or rend().

These rules are so complex and subtle that I doubt many programmers, if any, could give a precise summary. I could not.

---

What if O(1) requirements are disregarded?

If the C++11 constant time requirements on e.g. operator[] are disregarded, then COW for basic_string could be technically feasible, but difficult to implement.

Operations which could access the contents of a string without incurring COW data copying include:

• Concatenation via +.
• Output via <<.
• Using a basic_string as argument to standard library functions.

The latter because the standard library is permitted to rely on implementation specific knowledge and constructs.

Additionally an implementation could offer various non-standard functions for accessing string contents without triggering COW data copying.

A main complicating factor is that in C++11 basic_string item access must trigger data copying (un-sharing the string data) but is required to not throw, e.g. C++11 §21.4.5/3 “Throws: Nothing.”. And so it can't use ordinary dynamic allocation to create a new buffer for COW data copying. One way around this is to use a special heap where memory can be reserved without being actually allocated, and then reserve the requisite amount for each logical reference to a string value. Reserving and un-reserving in such a heap can be constant time, O(1), and allocating the amount that one has already reserved, can be noexcept. In order to comply with the standard's requirements, with this approach it seems there would need to be one such special reservation-based heap per distinct allocator.

---

^{Notes:
¹ The const item accessor triggers a COW data copying because it allows the client code to obtain a reference or pointer to the data, which it's not permitted to invalidate by a later data copying triggered by e.g. the non-const item accessor.}

참고URL : https://stackoverflow.com/questions/12199710/legality-of-cow-stdstring-implementation-in-c11