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

更にアリプラシリーズ。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 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;
}

実行するとこんな感じ。

1
2
3
4
5
6
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 しない処理ってのと同じですね。

1
2
3
4
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 を調べるだけで一発で分かりますよね。

1
2
3
4
5
6
7
8
9
10
11
12
class Bag {
protected:
    void *_mark;
public:
    Bag() : _mark(NULL) {}
    virtual void setMark( void *mark ) {
        _mark = mark;
    }
    virtual void *getMark() {
        return _mark;
    }
};

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

カテゴリー: C++ パーマリンク