トップ > C++ > C++ではまって、うさみみ先生ににやにやされたので、はまったところをまとめておく

C++ではまって、うさみみ先生ににやにやされたので、はまったところをまとめておく

C++

講師はid:mickey24先生。

離散最適化理論の授業でグラフ理論な話が出てきたので、路(path)をツリー構造で表わしたいなーとか思った*1。なので、木構造を作ることにした。最初のプログラムはこんな感じ。

木構造自体はこの辺でやっていたので、これを参考にTreeを継承したりなどした。


vector<Optim::Tree> tmp;
tmp.push_back(l1);
tmp.push_back(l2);
t1.addTree(tmp);
t1.print(&cout);

がこんなのを走らせると


t1
   l1
   l2

こうなって欲しいのに


t1
l1
l2

となって継承したほうのprintがうまく使われていない、ということが分かる。virtual使っているからうまくいくはずなんだが、、、と思っていたんだけど、そうではないらしい。
で、「.」で呼び出すか、ポインタで呼び出すかでどちらが呼ばれるかが違う、ということをid:mickey24先生に教えてもらった。先生がまとめてくれている。



    

        
これより、Tree型のvectorにLeafのオブジェクトを代入したら、

b = i;

b.message(); // これはbaseのものが呼ばれる


    


「基底クラスのポインタ変数に派生クラスのオブジェクトを代入した場合、そのポインタ経由でオーバーライドしたメソッドを呼び出せるけど、基底クラスの通常変数に派生クラスのオブジェクトを代入した場合はそうならない」ということらしい。Javaの場合のポリモーフィズムとかとは違うようである。見事に罠にはまった。
なので


vector<Optim::Tree*> tmp;

という感じにするといいらしい。vectorの要素にOptim::Tree型のポインタが入っている、と考える。
で、どういう風にすればベクターにつっこんでいけるかというと、こんな感じでやる。


Optim::Tree t1("t1");
Optim::Leaf l1("l1");
Optim::Tree t2("t2");
Optim::Leaf l2("l2");

vector<Optim::Tree*> tmp;
tmp.push_back(&l1);
tmp.push_back(&l2);

オブジェクトのアドレスを入れていく(ポインタにはオブジェクトじゃなくてオブジェクトのアドレスを代入する)。
しかしながら、ここにも罠が潜んでいた!!「l1，l2の変数の寿命が切れるとtmpの要素が指しているオブジェクトも死ぬので注意．」というのだ!!
…で最初は意味が分からないので、具体的に説明してもらった。ベクトルの中にはポインタがつっこんであって、実態(なんて言えばいいんだろ)は別のところにある。で、その実態を消してしまうと、ベクトルの要素はもうないものを差してしまうことになる。
コードで説明してみる(というか先生が出してくれた例)。


こんな感じでaddしていくと、tmpの10個の要素のポインタは全部無効になり、tmpの中身がなくなっちゃうってことになってしまう。中身を見ようとすると、(中身はなくなっていないらしく)無効な(不正な)ポインタが残っている。この不正なポインタを見ようとしたときの動作は「未定義」らしい。これはvector.size();とかやっても気づかないので大変厄介である。。。

  

言語の仕様的に「未定義」なことをした場合は何が起こっても不思議じゃないらしく



    

  • プログラムが落ちたりとか
    • 

  • HDDのファイルが消えたりとか
    • 

  • そもそもバグ見つけにくい
    • 

などがあるらしく、ちっともよいことがない。Segmentation Faultなどのエラーを出してプログラムが落ちたりするようだ*2。
で、こういう嫌なことが起きないようにするためにはどうすればいいか、というところなんだけどboostのshared_ptrというのを使うと解決できるらしい。数日前にid:syowyouさんに教えてもらっていた。この使い方については後日またやってみることにしよう。とりあえず今回はこのboostのshared_ptrというのを使わないで、どうすればこういう未定義な問題を防げるか、ということについて考える。




    
newとdelete

    
そもそもid:syou6162はゆとりなので、GCがあるようなJavaとかRubyとかRしか触ったことがなく、なんで人間様がdeleteるのをわざわざ覚えておかないといけないのだ、と思うような感じの人である。
で、適当にSTLのvectorとかを使ったりしていたんだけ、そういうものはdeleteしなくてもよかったりするので、どれに対してdeleteしないといけないのかが分かっていなかった。




    
newの真実

    
Javaとかだとnewした場合、オブジェクトが返ってくるので、当然C++もそうなんだろうと思っていた。が、違った。C++でnewした場合は「ポインタ」が返ってくるらしい。だから


Tree *tp = new Tree("t1");

というようなプログラムは正しい(いままではなんとなくでやっていた)。で、こういう書き方もある。


Optim::Leaf l("l3");

なんとなく「これは変数の宣言だけしているんだろうなー」と思っていたら、これまたそうではなかった。コンストラクタによって初期化されている、ということだった!!!しかし、思い返すと


ifstream fin("file");

というようなことをやっていたので、よくよく考えると使っていたのであった。そういうわけで、newする書き方なのかそうでない書き方なのかは全然違うので、きちんと意図を持ってcodingしないといけないんだなーということを知った。






    
deleteとメモリリーク

    
のようなプログラムがあったとき、注意しなければいけないのはtmpがdeleteされたり、要素をerace、clearしたりしても、ポインタが差し示しているオブジェクトは「自動的にdeleteされない」ということだ。どうしてやらないといけないか、というとプログラマがeraceするときとかに、Treeのデストラクタでvectorの各要素をdeleteしてやらなければならない。これまたdeleteされなかったりするとメモリリークになってしまったりして(ry。
で、そうなってくると「vector自体はdeleteしなくていいんかいな?」と思えてきて、何に対してdeleteすればいいかが分からなくなった。
結論からいくと「newで生成されたポインタ変数に対してはdeleteが必要なのか」ということらしい。








    
最終的なコード

    
こんな感じになりますた。


#include <string>
#include <set>
#include <vector>
#include <map>
#include <iostream>

namespace Optim {
  class Tree
  {
  public:
	Tree(std::string name) {
	  this->name = name;
	};
	virtual ~Tree(){};
	void addTree(Tree *t) {
	  (this->children).push_back(t);
	};
	virtual void print(std::ostream *os, int indent = 0) {
	  std::string ret = "";
	  for(int i=0;i < indent;i++){
		ret += " ";
	  }
	  std::cout << ret << this->name << std::endl;
	  for(std::vector<Tree*>::iterator it = (this->children).begin(); it != (this->children).end(); ++it) {
		(*it)->print(os, indent+1);
	  }
	};
  private:
	std::string name;
	std::vector<Tree*> children;
  };
  class Leaf : public Tree
  {
  public:
	Leaf(std::string name) : Tree(name) {
	  this->name = name;
	}
	virtual ~Leaf(){
	};
	void print(std::ostream *os, int indent = 0) {
	  std::string ret = "";
	  for(int i=0;i < indent;i++){
		ret += " ";
	  }
	  *os << ret << this->name << std::endl;
	};
  private:
	std::string name;
  };
};


int main(int argc, char *argv[])
{
  using namespace std;

  Optim::Tree t1("t1");
  Optim::Tree t2("t2");
  Optim::Tree t3("t3");
  Optim::Leaf l1("l1");
  Optim::Leaf l2("l2");
  Optim::Leaf *l3 = new Optim::Leaf("l3");

  vector<Optim::Tree*> tmp;
  vector<Optim::Tree*> tmp2;
  vector<Optim::Tree*> tmp3;
  tmp.push_back(&l1);
  tmp2.push_back(&l2);
  t2.addTree(new Optim::Leaf("l4"));
  t3.addTree(new Optim::Leaf("l5"));
  t2.addTree(&l2);
  tmp.push_back(&t2);
  tmp3.push_back(l3);
  tmp2.push_back(&t3);
  t2.addTree(&t3);
  t1.addTree(&t2);
  t1.print(&cout);
  cout << endl;
  return 0;
}

よし、ツリー構造できたー。


/tmp% ./a.out
t1
 t2
  l4
  l2
  t3
   l5

というわけで、土曜日くらいまでにグラフ構造から路をこういう感じの木で表わせるようになっときたいと思います。





*1:隣接行列とか使えばよろしいんですが、C++の練習もかねてグラフでやることにした


*2:配列の範囲外参照とかするとよくセグフォする、らしい