文字列の前向き・後ろ向き

昨日の子ネタに続いて，本日は前向き文字列と後ろ向き文字列に関する内容になっています．

前向き・後ろ向きという表現については，名前がないと不便なので，本記事のためだけに用意した造語です．前向き文字列というのは，前から順に参照する文字列を意味していて，例えば str[i] としたとき，(i+1) 文字目が出てくるような文字列だと考えてください．後ろ向き文字列の場合は逆で，n 文字の文字列に対して str[i] としたとき，(n-i) 文字目が出てくる文字列です．

marisa-trie の実装にあたり，ポイントの一つになるのがキーの前向き・後ろ向きです．一つ目のトライは前向き，二つ目のトライは後ろ向き，最後に TAIL を構築するときは前向きになるので，トライを構築するコードを前向き・後ろ向きで用意するか，文字列の前向き・後ろ向きを切り替える必要があります．

とはいえ，ライブラリの核に相当するコードを二種類用意するなんてとんでもないし，文字列の向きを変更する度に新しい領域を確保するのは時間的にも空間的にもコストが大きくなります．

そこで，marisa-trie の実装では，marisa::String と marisa::RString というクラスを用意しました．中身はシンプルなもので，実際に使うのは，(i+1) 番目の文字を取り出す operator[]() と，長さを返す length() に，部分文字列を切り出す substr() 程度です．

後は，marisa::String と marisa::RString をテンプレート引数として受け取るように構築用の関数を実装して終わりになります．前述の分け方にしたがうと，実は，「トライを構築するコードを前向き・後ろ向きで用意する」上に，「文字列の前向き・後ろ向きを切り替える」ようになっています．ただし，実装はほとんど同じになり※，文字列の切り替えについては，最初に受け取った文字列の領域をそのまま流用できるので，どちらも大きな問題にはなりません．

※ 違う部分については，marisa::String と marisa::RString で別々に実装できます．

class String {
 public:
  String();
  explicit String(const char *str);
  String(const char *ptr, std::size_t length);

  String(const String &str);
  String &operator=(const String &str);

  UInt8 operator[](std::size_t i) const;

  String substr(std::size_t pos, std::size_t length) const;

  const char *ptr() const;
  std::size_t length() const;

 private:
  const char *ptr_;
  std::size_t length_;
};

class RString {
 public:
  RString();
  explicit RString(const String &str);

  RString(const RString &str);
  RString &operator=(const RString &str);

  UInt8 operator[](std::size_t i) const;

  RString substr(std::size_t pos, std::size_t length) const;

  const char *ptr() const;
  std::size_t length() const;

 private:
  const char *ptr_;
  std::size_t length_;
};