2

私は Composite クラス ( QObjectQt に似ています) をコーディングしていますが、現時点では、子をstd::vector. 各 Composite インスタンスには名前があり、この名前は、このインスタンスの兄弟である他のすべてのインスタンス間で一意である必要があります。同じ親を共有するインスタンス間で、より適切に表現する必要があります。

新しいインスタンスが 内にプッシュされるたびに、vectorその名前が 内のインスタンスの 1 つによって既に使用されているかどうかを確認する必要があります。使用されているvector場合は、番号を追加して名前を変更する必要があります。

私が思いついたコードは非常にばかげており、子の数が一定になると非常に遅くなります。

ここにクラスがあります：

class Composite
{
public:
    Composite(const std::string &name, Composite *ancestor=NULL);
    ~Composite();

private:
    std::string name;
    Composite *ancestor;
    std::vector<Composite*> descendants;

public:
    void setName(const std::string &name);
};

これはコンストラクタとsetName実装です:

Composite::Composite(const std::string &name, Composite *ancestor)
{
    this->ancestor = ancestor;
setName(name);
if (ancestor!=NULL)
    ancestor->descendants.push_back(this);

}

.

void Composite::setName(const std::string &name)
{
    this->name = name;

    if (ancestor!=NULL)
    {
        CompositeList::iterator dIt;
        for( dIt=ancestor->descendants.begin(); dIt!=ancestor->descendants.end(); dIt++)
        {
            if ((*dIt)==this)
            {
                continue;
            }
            else if (this->name == (*dIt)->getName())
            {
                 int trailingNumber = stringToInt(getTrailingNumber(this->name));
                 std::string cleanName = removeTrailingNumber(this->name);
                 this->name = cleanName+intToString(trailingNumber+1);
            }
        }
    }
}

これはごく少数の子供にとっては問題ないかもしれませんが、数百人になると、setName関数は本当に遅くなります。次の状況を想像してください。

Composite *parent = new Composite("pippo");

for (int i=0; i<10000; i++)
{
    Composite("ClashingName", parent);
}

1 回目は問題なく、2 回目は名前が ClashingName0 で変更され、3 回目は名前が最初に ClashingName0 に変更され、2 番目のインスタンスとの衝突が検出され、名前が ClashingName1 に設定されます...それは指数関数的であり、そのループの終わりに来ると、許容できない時間が経過します。

ここでの本当の問題は、衝突する名前を効率的に見つけて、まだ使用されていない新しい名前を効率的に割り当てる方法です。どんな std コンテナでも問題なく、私のコンパイラは C++11 をサポートしていますが、私が取り組んでいるプロジェクトが信じられないほど小さいため (基本的にはこのクラスです)、Boost を使用できない/使用したくありません。

私は C++ のベテラン ユーザーではありません。 maporを使用することを考えていましunordered_mapたが、ここで専門家の提案に本当に飢えています。

4

3 に答える 3

2

IMO、オブジェクトの保存方法を変更する必要があります。次のようなもの：

std::map<std::string, std::vector<Composite> >

マップのキーはプレフィックスであり、ベクトル内のインデックスは n 番目のCompositeオブジェクトです。渡された名前を分割するカスタム ルックアップ関数を提供する必要があります。

std::string query = "pipo_10";

ルックアップ関数では、

Composite* lookup(std::string const& key)
{
  // split the key to get the prefix and the index
  // lookup in the map using the prefix
  // return the index
}

編集 1: すべての文字列操作を保存するには、独自のカスタム キーを定義できます。これは単なるペア (たとえば、std::pair<std::string, int>プレフィックスとインデックス) であり、ルックアップではこのキーの値を使用するだけです。

EDIT 2：これについてもう少し考えて、マップのマップを持っている方が良いです。

std::map<std::string, std::map<int, Composite> >

これで、インデックスはベクトル内のインデックスではなく、2 番目のマップ内のルックアップになります。これにより、削除がより適切に処理されます。キーは、前に述べたように複合キー (ペア) になります。

@Stevesの提案をクレジット..

std::map<std::pair<std::string, int>, Composite>

lower_bound()トリックを使用して、指定されたの最後のインデックスを見つけますComposite

于 2012-06-27T12:01:04.080 に答える
1

or のどちらmapかunordered_mapが仕事をし、count関数を使用して名前がマップにあるかどうかをテストし、find関数 oroperator[]にアクセスします。

unordered_map全体的に少し速くなる可能性があります。

maporを使用して、最後に衝突した名前を 1 回の検索で検索できるため、 ...のそれぞれを順番に検索するのではなく、厄介な"ClashingName"例をより適切に処理できます。lower_boundupper_boundClashingName0ClashingName9999

mapデフォルトでは辞書順でソートされるため、ClashingName10が前になることに注意してくださいClashingName9。また、特に末尾に数字が含まれる名前を誰かが提供した場合にどうなるかという問題もあります。

Nim の提案でこれを修正しstring, intます。マップ キーとして のペアを使用し、必要に応じてそのペアから名前を作成します。繰り返しになりますが、誰かが数字で終わる名前を提供した場合、何か特別なことをしなければなりません。名前"Clash10"が 2 回出現しない("Clash", 10)ように注意してください("Clash1", 0)。簡単なオプションは、提供された名前から 1 文字を禁止し、それを区切り文字として使用することです。

于 2012-06-27T12:06:09.227 に答える
0

オブジェクトごとに追加のマップを気にしない場合は、次のようにすることができます。

// inside Composite definiton
std::map<std::string, int> names_of_descendants;

次に、単純に：

void Composite::setName(const std::string &name)
{
    if (ancestor)
    {
        // for the first usage of certain name, map's operator[]
        // will insert default constructed int (0) in the map
        this->name = name + ancestor->names_of_descendants[name];

        // increment the value for this name, for the next call of setName
        ++names_of_descendants[name];
    }
}

子孫を格納するためのベクトルを保持できます。

于 2012-06-27T12:15:20.090 に答える