アリスは同じ鞄を抱えない

更にアリプラシリーズ。

同じ鞄をプレゼントした場合は、アリスは貰わない…と言いますから、同じ鞄なんだからなんでもう一度プレゼントするの？というコードです。

// for アリスは同じ鞄を抱えない
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

class Bag {
protected:
	bool used;
public:
	virtual bool getUsed() { return used; }  
	virtual void Used() { this->used = true; }  
};

class Prada : public Bag {};
class Tiffany : public Bag {};

class Alice
{
private:
	list<Bag*> bags;
public:
	Alice() {
	}
	void Present( Bag *bag ) 
	{
		if ( find(bags.begin(),bags.end(),bag) == bags.end() &&
             dynamic_cast<Prada*>(bag) != NULL ) {
			bags.push_back( bag );
		}
	}
	int CountBags() 
	{
		return bags.size();
	}
};

int main(void)
{
	Alice alice;
	
	cout << "alice has " << alice.CountBags() << " bags." << endl;
	Bag *bag = new Prada();
	alice.Present(bag);
	cout << "alice has " << alice.CountBags() << " bags." << endl;
	alice.Present(new Tiffany());
	cout << "alice has " << alice.CountBags() << " bags." << endl;
	alice.Present(bag); // 同じものをプレゼントする
	cout << "alice has " << alice.CountBags() << " bags." << endl;
	alice.Present(new Prada());
	cout << "alice has " << alice.CountBags() << " bags." << endl;

	return 0;
}

実行するとこんな感じ。

D:\work\blog\src\alice>a
alice has 0 bags.
alice has 1 bags.
alice has 1 bags.
alice has 1 bags.
alice has 2 bags.

プレゼントすると、一度、タンス(bags)を find 関数で照合します。何故か知らないけど、タンス(bags)にあったものが再び Present される訳で、変なのという感じなのですが、bags には追加しません。
データベースで言うところの、同じ名前だったらデータベースに insert しない処理ってのと同じですね。

SELECT @COUNT = count(*) FROM bags WHERE ...
IF @COUNT = 0 THEN
  INSERT bags VALUES ( ... )
END IF

のようなものです。重複チェックをして挿入ってな具合。これは、bags にある量が多くなるとだんだんと遅くなっていきます。いわゆる O(n) の確率。ただし、find のアルゴリズムを変えていけば O(log n) だっけ? になります。ハッシュテーブルとかバイナリツリーとかを使います。大変ですよね。不安ですね。

しかし、ちょっと工夫すると、一発で貰った鞄かどうかが分かります。Bag クラス自体にマーキングを示す mark 変数を用意して、これに自分のポインターを入れておきます。そうすると、mark を調べるだけで一発で分かりますよね。

class Bag {
protected:
	void *_mark;
public:
	Bag() : _mark(NULL) {}
	virtual void setMark( void *mark ) {
		_mark = mark;
	}
	virtual void *getMark() {
		return _mark;
	}
};

特性を知って、ちょっとクラスに工夫を加えるとうまくいくっていうパターンです。