\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年1月17日 星期六

c++ rope 基本應用

rope(粗繩)是一個很強大的字串處理物件,聽說是為了與string(細繩)做對比才叫做rope的,其底層是一棵持久化平衡樹,因此在做合併或在中間插入的期望時間是logn

再使用rope前必須在前置作以下的處理

#include<ext/rope>
using namespace __gnu_cxx;

定義一個元素為char的rope:
rope<char> r;

其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:
crope r;


當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)

對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀

2 則留言:

  1. 習題 UVa 12538 - Version Controlled IDE

    數值版本只能自己來了嗎?

    回覆刪除
  2. 其實rope也能做數值資料結構的處理
    但是相對於字符會比較不容易
    改天來把rope的操作做完整的介紹

    回覆刪除