Monthly Archive for May, 2007

TopCoder::SRM::348::500::LostParentheses で提出したコードがChallengeされて撃沈した件を調べていました。

原因

std::stringのコンストラクタの仕様を間違って捉えていた。

詳細

数字と+,-から成る文字列が与えられたときに、-でsplitするコードをどう書くか。 string::findを使って、順に部分文字列を取得しようと思いました。

ダメなコード

 1 #include <string>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 void split(const string &str) {
 6    string::size_type left(0);
 7    string::size_type right(str.find('-'));
 8 
 9    while (string::npos != right) {
10       cout << string(str, left, right) << endl; // XXX : まちがい
11 
12       left = right + 1;
13       right = str.find('-', left);
14    }
15 
16    cout << string(str, left, right) << endl;
17 }
18 
19 int main() {
20    const char *strs[] = {
21       "55-50+40",
22       "00009-00009+0009-09+09-09+09-09"
23    };
24 
25    for (int i=0; i<2; i++) {
26       cout << "str : " << strs[i] << endl;
27       split(strs[i]);
28       cout << endl;
29    }
30 
31    return 0;
32 }

ところが、これでは2つめのケースがおかしくなります。

実行結果

% ./strfind
str : 55-50+40
55
50+40

str : 00009-00009+0009-09+09-09+09-09
00009
00009+0009-09+09 <<<<
09+09-09+09-09
09+09-09
09

‘<<<<’の行が、ちゃんとsplitできていないことが分かります。

理由

標準C++ライブラリ string> によると、std::stringのコンストラクタで(別の文字列, 数値1、数値2) を渡すと別の文字列の数値1の位置から数値2の長さぶんだけコピーした文字列がつくられるとあります。ここを、別の文字列の数値1の位置から数値2の位置までの部分文字列をコピーした文字列がつくられると勘違いしていたのがまちがいのもとでした。

修正

問題の10行目を、

 cout << string(str, left, right-left) << endl; // XXX : OK

とするだけでOKでした。

所感

考えたアルゴリズム自体は、遠回りだけれど間違っていないものだっただけに、文字列処理のところでミスるなんていうのは痛いところです。もったいない。 C++の標準ライブラリのリファレンスがやっぱり手元に欲しいなとか思いました。 Mac OSXだとmanで引けないんだよなぁ。Ubuntu 7.04だとあるんだけれど。