読者です 読者をやめる 読者になる 読者になる

methaneのブログ

このブログに乗せているサンプルコードはすべてNYSLです。

std::equal_range()の型縛り

program C++

この記事の内容は全部うそです。5/29の日記を参照してください。(5/29)

さて,saが構築できたところで,検索しようと思う.各文字の出現回数を保存すれば元文書は消しても良いのだが,それは後回し.
のstd::equal_range()は,順列に並んでいるリストから,指定した値と等しい範囲を返してくれる.(http://www.sgi.com/tech/stl/equal_range.html)

template <class ForwardIterator, class T, class StrictWeakOrdering>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
            StrictWeakOrdering comp);

関数の意図としては目的にズバリで,suffixの先頭が検索語に一致する範囲を見つけられそう.だが,型が合わない.検索語は文字列型だが,検索対象はsaだ.saの先にdocがあるから、文字列と部分文字列の比較ができれば良いのだが,docをあとで消すことを考えると文字列型に依存したくない.文字を一つずつ取り出せるインタフェースを作って,そのインタフェースを提供するsa用のラッパとstring用のラッパを作ろう.
でも,それだけはいけない.equal_rangeの中では,if (comp(*first, value)) のようなことをしているので,参照解決したらインデックスではなく先ほどのラッパを返すイテレータを自作しなければならない.
せこせことランダムアクセスイテレータに必要そうなoperatorを全部定義して,ビルド・・・通らない.iterator_trais(http://www.sgi.com/tech/stl/iterator_traits.html)が無いと怒られる.そうか,そんなものがあったな・・・.
ここで一息ついて,見直してみる.ちょっと乱雑になってきている.文字列ラッパ+イテレータラッパ以外にも,実装方法はある.

  • std::equal_range()をより広い範囲(typeid(*iter) != typeid(value))にも適用できるように拡張したオリジナルequal_range()を作る.
  • compをオリジナルの関数オブジェクトにして,メンバに検索語を持たせる.vlaueが-1の時は検索語で,value >= 0の時は[doc.begin() + sa[value], doc.end())というsuffixだと認識するようにする.

こう書いてみると,後者が一番すっきり実装できることが判る.イテレータ自作は止めて,今日はここまで.

そういえば,イテレータとか,面倒なルールに従ったユーザー定義型を実装するためのヘルパーがいろいろboostに合った気がする.それも調べておこう.