不思議な現象に出くわしたので、エントリにしてみるテスト。

C++でプログラミングしていて、ヘッダにクラスのコンストラクタの定義を含めず、宣言だけを書くというのはよくあることだと思います。 次のようなヘッダファイルを考えてみます。

sym.h:

ifndef SYM_H

define SYM_H

class Sym {
public:
  Sym();


}; // Sym

endif // SYM_H

実装は sym.cc に書きます。

include "sym.h"

Sym::Sym() {
}


int main() {
  Sym sym;
  return 0;
}

これらをg++でコンパイルして、生成されるオブジェクトファイルを覗いてみると、驚きました。

% nm sym | c++filt
0000200c D NXArgc
00002008 D _NXArgv
00001fde T Sym::Sym()
00001fd6 T Sym::Sym()
00002000 D __progname
00001fc8 t __dyld_func_lookup
00001000 A __mh_execute_header
00002004 D environ
         U _exit
00001fe6 T _main
00002010 d dyld_mach_header
00001fb4 t dyld_stub_binding_helper
00001f74 T start

なんで Sym::Sym()が2つ存在するんだ?

そして、ヘッダファイルに定義も含めると、1つになります。

ifndef SYM_H

define SYM_H

class Sym {
public:
  Sym() {}
}; // Sym

endif // SYM_H

nm sym | c++filt
0000200c D NXArgc
00002008 D _NXArgv
00001fb6 T Sym::Sym()
         U __gxx_personality_v0
00002000 D ___progname
00001f90 t __dyld_func_lookup
00001000 A __mh_execute_header
00002004 D environ
         U _exit
00001f9e T _main
00002010 d dyld_mach_header
00001f7c t dyld_stub_binding_helper
00001f3c T start

なぜだー。Mac OS X / Linux で確認しています。

使えるメモリが極めて限られている状況だと、こういう小さなところでも無駄は減らしたい。でもヘッダファイルに実装を書きまくるのは、できれば避けたいものです。

原因が分かるかたいらっしゃれば、ご教授ください ＞＜

---

再現するためのコード一式を、symbols.zip に固めました。 Makefile中の CXXFLAGS += -DCOMPILE_BY_SPLIT のところを無効にするとヘッダファイルでコンストラクタの定義を行い、有効にすると.ccの中で定義する、というふうにしています。

I wrote a C++ wrapper library for Gainer, based on its Ruby library (gainer-ruby). The code is submitted to CodeRepos as Gainer++, here.

So Far

It supports following functions:

• mode switch by constructor
• analog inputs
• digital inputs

It has some examples, like blinking LED on Gainer I/O module (gainer-led.cc).

---

Feel free to use, modify, and commit to it.

昨日のつづき。 今日のコミットで、以下の動作が確認できました。

• コンストラクタでのモード切り替え
• アナログ入力
• デジタル入力

アナログ入力の確認中に、どうも値がヘンなことになってて30分くらい悩んだのですが、によると、アナログ端子はアンテナみたいになるので値が不定になるよ、とのこと。そんなことも知らない素人です。

gainer-ruby のコードでは、デジタル入力が1ポートしか取れないことになっていたので、ビット演算したりして4ポートぶんとれるようにしました。

それにしてもプロトコルの仕様が知りたいよ、とうろうろしていたら、ちゃーんと公開されてました。さすが。ちゃんと調べなきゃですね。

Gainerを、C++から使えるようなラッパを書いています。 Rubyから扱えるgainer-rubyのコードをC++に書き移して、Gainer++としてCodeReposに登録しておきました。コードはこちら。

まだI/Oポート周りのコードを移していないのですが、Gainer I/OモジュールのLEDを点灯させるサンプルプログラム (gainer-rubyのページにあるもの) は動いています。(gainer-led.cc)

せっかくより書き易いRubyのライブラリがあるのにC++で書くなんて逆行してるよ! と自分でもつっこまざるを得ないのですが、Gainerをより低レイヤ (CoreMIDIとか)と連携させてみたい、というのが動機です。

つかったりコード直したりしてみてくださいね。

関連

• GAINER wiki:Tutorial/Basic/Common/03/ja
• dandelion’s log:GainerをC++で扱ってみる

TopCoderの問題では、よく文字列をスペースで区切る必要があります。

Javaとかだと、あっさりString#splitがあるのでラクすぎるのですが、C++だとそうもいかない。 でも、Boost String Algorithms Library が使えれば、 splitが用意されているので

string "yey i'll be splitted";
vector  out;
boost::algorithm::split(out, string, boost::algorithm::is_space());

なんてするだけで、スペースで区切った文字列の配列を得ることができて、ちょう便利です。

果たして、TopCoderの環境でも、これが使えるのか試してみました。

Boostのバージョンを確かめる

stringを返すようなProblem StatementをPracticeから探します。 そんで、

include

...
return BOOST_LIB_VERSION;
...

とかして、Compile → Test し、結果を確認。1_32が返されてきました。1.32か。

splitしてみる

なにはともあれ、上で書いたようなsplitのコードを Compile してみます。

/usr/include/boost/config/compiler/gcc.hpp:92:7: warning: #warning “Unknown compiler version – please run the configure tests and report the results”

というwarningがでますが、ちゃんとmakeできた模様。やった。 TopCoderのコンパイルファームにてBoostをビルドした環境 (gcc on ???) が、確認されていないプラットフォームだったのではないでしょうか。

まとめ

TopCoderの環境でも、文字列の分割にBoostがつかえることが分かりました。バージョンは2007.09.21 現在で 1.32でした。

他にも文字列の分割方法はいろいろあるので、あとでまとめておこうと思います。

TopCoder::SRM::351 に取り組んでいました。先週は参加できなかったので、2週間ぶりです。

いつもどおり、250点問題を無難にこなしたあと、500点問題へ。 なんとかの一つ覚えみたいに、幅優先探索で挑んでみたのですが、どうしてもできない。 なんでかなぁといろいろ試してみたところ、STLの使い方に問題があったのでした。

やりたいこと

struct Combi {
  int g, s, b;

  Combi(int gg, int ss, int bb) : g(gg), s(ss), b(bb) {}
};

みたいな構造体を、コンテナに入れたい。

トラブル : std::set に insert できない、std::map で find できない

operator <がないよ、とコンパイラに諭されてしまいます。

ならばと、3つのメンバg, s, b について

bool operator <(const Combi &rhs) const {
  return g < rhs.g || s < rhs.s || b < rhs.b;
}

みたいなoperatorを書いてみたところ、コンパイルは通るのですが、insert/find ともに結果が妙なことになってしまいます。どうも、operator <のせいで、異なる値を持つ2つのオブジェクトが同一視されてしまうようなのです。

異なる値をもつオブジェクトをsetにinsertしようとしても、同じオブジェクトと見なされてinsertできない、あるいは要素xがないはずのmapにfind(x)をかけても見つかってしまうという。

---

うーん、とそんなところで悩んでいろいろしているうちに時間切れに… どんなよい刀でも、手に馴染んでいなければ自分を切ってしまうということですね。

しかし、なぜ同一視されてしまうのだろう…

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

原因

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

詳細

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

ダメなコード

 1 #include 
 2 #include 
 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だとあるんだけれど。

を読んでいます。 契約による設計という考えに触発され、自分でもやってみようと思いたちました。

単純なマクロ

さっそく、C++でやってみようということで、

#define REQUIRE
#define ENSURE

といった空マクロを用意しました。

int square10(int x) { // 10 以下の正数のみを対象とする二乗関数
  REQUIRE {
    assert(0 < x);
    assert(10 > x);
  }


int ret(x * x);


ENSURE {
    assert(x == sqrt(ret));
  }
  return ret;
}

と、一応は書けます。

しかし、本来ならヘッダファイル内の宣言に含めて インターフェイスとしてクライアントに提示したいものです。 さらに欲を言えば、Doxygenなどで自動的に抽出してほしい。

実現のために

1. それぞれの関数の入口/出口に、制約条件をチェックするhookを仕掛ける
2. 制約条件を関数/クラス宣言内に書ける
3. Doxygenのタグを拡張

といったことが必要になりそうです。

1を実現するには、auto変数をうまく利用すればいいんじゃない? と思いました。 2を実現するには、それぞれの制約条件を表現するクラスを、クラス内クラスとして定義すればよさそう。 3はどうしたらいいんだろう…

NDEBUG環境では、制約条件のオブジェクトを生成しないように、マクロを使えばよさそうです。

例

#include 


// constrain macro.
#ifdef NDEBUG
#define CONSTRAIN(method)
#else // NDEBUG
#define CONSTRAIN(method) 
   method##_constrain _constrain(*this)
#endif // NDEBUG


class Bird {
public:
   Bird() : // awake and not flying at first.
      flying_(false),
      sleeping_(false) {}


void fly() {
      CONSTRAIN(fly);
      flying_ = true;
   }


void sleep() {
      CONSTRAIN(sleep);
      sleeping_ = true;
   }


friend class fly_constrain;
   friend class sleep_constrain;


private:
   bool flying_;
   bool sleeping_;


// ----------------------------------------------------------------
   // constrains
   class fly_constrain {
   public:
      fly_constrain(Bird &b) : bird_(b) {  // requirement
         assert(false == bird_.flying_);
         assert(false == bird_.sleeping_);
      };

  ~fly_constrain() {                   // ensure
     assert(true == bird_.flying_);
     assert(false == bird_.sleeping_);
  }

private:
      Bird &bird_;
   }; // fly_constrain


class sleep_constrain {
   public:
      sleep_constrain(Bird &b) : bird_(b) { // requirement
         assert(false == bird_.sleeping_);
         assert(false == bird_.flying_);
      };

  ~sleep_constrain() {                  // ensure
     assert(true == bird_.sleeping_);
     assert(false == bird_.flying_);
  }

private:
      Bird &bird_;
   }; // sleep_constrain


}; // Bird


// test
int main(int argc, char *argv[]) {
   Bird piyoko;


piyoko.fly();
   piyoko.sleep(); // cannot sleep while flying !


return 0;
}

実行結果

% c++ -Wall -g dbc.cxx
% ./a.out
dbc.cxx:57: failed assertion `false == bird_.flying_'
zsh: abort      ./a.out

鳥は飛びながら眠ることはできないという制約にひっかかっているの図です。

まとめ

C++でも契約による設計は実現できそうです。 しかしC++らしく手間がやたらとかかると。 CONSTRAINマクロは、メソッド名を自動抽出できればもう少しうまく書けそう。

他にも良いアイデアがあればぜひ教えてください。

参考リンク

• The Code Project::Design by Contract macros for C++ and link to Doxygen おおおっ!と思いましたが、VC限定なのですね。
• OnLamp::Using Design by Contract in C

---

プログラマの日々の鍛錬として、小さな関数を書く練習というのが有効だと思います。あちこちから探してきてちょこちょこと書いてみるつもり。

今日は p.p.181:

5 . 文字列の中で同じ文字が一番長く続くところを見つける

をやってみます。

アルゴリズム

文字列の終端まで最初から1文字ずつ読んでいって、状態を記録していくという単純なアプローチで。 状態は、

• 現在の文字
• 現在の文字へのポインタ
• 現在の文字が連続している回数
• これまでで最大の連続回数
• これまでで最大だったときの文字へのポインタ

だけあれば十分そう。

コード

/!
 *  文字列の中で同じ文字が一番長く続くところを見つける
 *
 *  [in] str 探索する文字列
 *  一番長く同じ文字が連続する部分文字列へのポインタ
 */
char *find_max_continuous_part(const char *str)
{
   / A1. [init] */
   char *cur = (char *)str;
   char *max_from = cur;
   int count = 0;
   int max_count = 0;
   char ch = cur[0];




/* A2. finish? /
   for (; *cur != ''; cur++)
   {
      / A3. continuous ? /
      if (cur == ch) // continuous
      {
         count++;
      }
      else /* A5 discontinuous */
      {
         if (count > max_count) // update
         {
            max_count = count;
            max_from = cur - count;
         }
         count = 1;
         ch = *cur;
      }
   }




if (count > max_count) // update
   {
      max_count = count;
      max_from = cur - count;
   }




return max_from;
}

実行例

./find_max_length_part hhhhaaaaaaabbccceeeeffffffffffffeeeaa




=> ffffffffffffeeeaa

所感

アルゴリズムを描くのに5分くらい。 コードは10分くらいで書けました。

初期化と、ループを抜けた後の処理 (update)に重複があるのが美しくありません。どう改善したらよいかな。

---