まずは、basic_string::substrなんて使わないよねという話です。

“abc def ghi”のような文字列を空白で区切って{“abc”, “def”, “ghi”}のようにしたいとします。普段、私はこんなことにsubstrを使わないのですが、がんばって書いてみました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <string>
#include <deque>
 
std::deque<std::string> Parse(std::string const& src)
{
    auto left = src.find(' ');
    if (left == std::string::npos)
    {
        return {src};
    }
    else
    {
        auto right = src.find_first_not_of(' ', left);
 
        auto ret = Parse(src.substr(right));
        ret.push_front(src.substr(0, left));
        return ret;
    }
}

なぜ、substrを使わないかと言えば、2つの理由があります。

  • 文字列のコピーが作られる。
  • 切り出し位置の指定を数値で行う（イテレータで指定できない）。

上の例は、再帰呼出のたびにも実のコピーが作られるので、さすがにありえないです。実は、最初に次に示すRangeを使ったものを作り、次にそれをsubstrを使った上のコードへ移植したからです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <string>
#include <deque>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
 
std::deque<std::string> Parse(boost::iterator_range<std::string::const_iterator> const& src)
{
    using namespace boost;
 
    auto left = find(src, ' ');
    if (left == end(src))
    {
        return {copy_range<std::string>(src)};
    }
    else
    {
        auto right = std::find_if(left, end(src), [](char c) {return c != ' ';});
        auto ret = Parse(make_iterator_range(right, end(src)));
        ret.emplace_front(begin(src), left);
        // emplace_frontはpush_front(std::string(begin(src), left))と同じ意味
        return ret;
    }
}

最初のコードでは、再帰呼出のたびにstringオブジェクトが作られていましたが、iterator_rangeではそのようなことはありません。iterator_rangeは[先頭, 末尾)のイテレータのペアを保持しているという理解で構いません。

2つのコードの違いの肝は次のあたりです。

「だからsubstrなんてなくても平気」という話ではありません、今日は。そんな文字列解析を手で書くなんて面倒なので、相応のものを使いましょう。正規表現？Boost.StringAlgo？いえいえ、Boost.Spiritです。

1
2
3
4
5
6
7
8
9
10
11
12

#include <string>
#include <deque>
#include <boost/spirit/include/qi.hpp>
 
std::deque<std::string> Parse(std::string const& src)
{
    using namespace boost::spirit::qi;
 
    std::deque<std::string> ret;
    parse(src.begin(), src.end(), *(char_ - ' ') % +lit(' '), ret);
    return ret;
}

せっかくなので、速度を測ってみることにしました。以下のコードは上3つに対し共通で使っています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <boost/progress.hpp>
#include <boost/for_each.hpp>
 
std::deque<std::string> ParseWithTime(std::string const& src)
{
    boost::progress_timer t(std::clog);
    return Parse(src);
}
 
int main()
{
    std::string s;
    std::getline(std::cin, s);
    auto x = ParseWithTime(s);
    BOOST_FOREACH(auto const& t, x) // for (auto const& t : x)
    {
        std::cout << t << std::endl;
    }
}

こんな結果でした。左端の列は入力に与えたテキストの量です（英語版Wikipediaなどから適当に切り貼りして作りました）。NAと書いた部分はCore dump吐いたので計測できませんでした。

[KiB]substriterator_rangeSpirit
640.160.030.01
961.010.030.02
1281.810.050.02
256NA0.090.03
512NA0.190.06
1024NA0.370.11

最初のコードがいかにだめか、あらためてよく分かりますね。

スポンサード リンク

この記事のカテゴリ

  • ⇒ Boost.勉強会#5行ってきたのでSpirit使うのです