Rope

튜토리얼 문서 원본

  Rope는 scalable string implementation이다: 문자열에 대한 연산들 중 몇 개에 대해서 강력한 성능을 제공한다.
할당(assignment), 연결(concatenation), 그리고 부분문자열(substring)에 해당하는 연산들은 문자열의 길이와 거의 독립적으로 빠르게 수행된다. Rope는 문자들의 Container로 취급되며, 거의 Sequence이다. 각각의 원소를 수정하는 연산은 느리다.

vector<char> 또는 string과 비교해 장점과 단점을 비교해보자.

장점:
1. Much faster concatenation and substring operations involving long strings.
2. Potentially much better space performance.
3. Assignment is simply a (possibly reference counted) pointer assignment. 
4. It is possible to view a function producing characters as a rope.

단점:
1. Single character replacements in a rope are expensive.
2. A rope can be examined a character at a time through a const_iterator in amortized constant time, as for vector<char>. However this is slower than for vector<char> by a significant constant factor (roughly a factor of 5 or 10 if little processing is done on each character and the string is long).
3. Iterators are on the order of a dozen words in size.

아래에 있는 것은 내가 작성한 예제 코드이다.

위의 코드를 실행시켰을 때에 얻을 수 있는 결과이다.

Rope를 이용하면 이 문제(UVA 12538)를 상당히 깔끔하게 해결할 수 있다.
직접 treap을 구현해서 해결할 수도 있겠지만...