boost::lambda で suffix sort
先日 C++ の Duck Typing のサンプルコードを書いたら、「何この Syntax」みたいなことを言われたので、さらにきつそうなのハードディスクからサルベージしてさらしてみる。要 Boost。
STL の std::sort と boost::lambda をフル活用して suffix sort をしているわけだが、template なので入力は char*、std::string に限らず、random access な iterator で各要素同士を比較できればOK(要するに std::vector
ちなみに、もともとこのコードは自作した suffix sort が正しいかどうかの比較用だったりする。main は今書いたけど。
#include <boost/lambda/lambda.hpp> #include <boost/lambda/bind.hpp> #include <boost/lambda/algorithm.hpp> #include <boost/scoped_array.hpp> #include <iostream> #include <algorithm> #include <string> template<typename TextIterator, typename IndexIterator> void suffix_sort(TextIterator first, TextIterator last, IndexIterator sa) { using namespace boost::lambda; size_t n = std::distance(first, last); for (int i = 0; i < n; i++) { sa[i] = i; } std::sort(sa, sa + n, bind(ll::lexicographical_compare(), ret<TextIterator>(_1 + first), last, ret<TextIterator>(_2 + first), last)); } int main(int argc, char** argv) { std::string text = "abracadabra"; int n = text.length(); boost::scoped_array<int> sa(new int[n]); suffix_sort(text.begin(), text.end(), sa.get()); for (int i = 0; i < n; i++) { std::cout << i << '\t' << sa[i] << '\t' << text.substr(sa[i]) << std::endl; } return 0; }