4

二重索引付けを可能にするコンテナーをセットアップするための (C++ での) 最良の方法は何ですか? 具体的には、オブジェクトのリストがあり、それぞれがキーでインデックス付けされています (キーごとに複数の可能性があります)。これはマルチマップを意味します。ただし、これに伴う問題は、オブジェクトの位置を見つけるためのルックアップが線形よりも悪い可能性があることです。データの重複は避けたいので、各オブジェクトが独自の座標を維持し、マップ内で自分自身を移動する必要があるのは悪いことです (自分のオブジェクトを移動すると、メンバー関数内でデストラクタが間接的に呼び出される可能性があることは言うまでもありません!)。オブジェクトポインターと座標の両方でインデックスを維持し、オブジェクト自体が安定した参照/ポインターを保証するコンテナーが望ましいです。次に、各オブジェクトはイテレータをインデックス (座標を含む) に格納し、十分に抽象化して、そしてそれがどこにあるかを知ってください。Boost.MultiIndex は最良のアイデアのように思えますが、非常に恐ろしく、実際のオブジェクトを const にする必要はありません。

あなたは何をお勧めします？

編集: Boost Bimap は良さそうですが、安定したインデックス作成を提供しますか? つまり、座標を変更しても、他の要素への参照は有効なままでなければなりません。インデックス作成にポインターを使用する理由は、オブジェクトには固有の順序付けがなく、オブジェクトが変更されてもポインターが一定のままである可​​能性があるためです (IIRC が安定したインデックス作成を提供する Boost MultiIndex での使用を許可します)。

4

3 に答える 3

5

あなたの書き込みに基づいて、いくつかの仮定を立てています。

  • キーは安価にコピーして比較できます
  • システムにはオブジェクトのコピーが 1 つだけ存在する必要があります
  • 同じキーが多くのオブジェクトを参照する場合がありますが、特定のキーに対応するオブジェクトは 1 つだけです (1 対多)。
  • 特定のキーに対応するオブジェクトと、特定のオブジェクトに対応するキーを効率的に検索できるようにする必要があります。

私はお勧めします：

  • リンク リストまたはその他のコンテナを使用して、システム内のすべてのオブジェクトのグローバル リストを維持します。オブジェクトはリンク リストに割り当てられます。
  • std::multimap<Key, Object *>キーをオブジェクト ポインターにマップし、リンク リスト内の単一の正規の場所を指すものを作成します。
  • 次のいずれかを実行します。
    • std::map<Object *, Key>特定のオブジェクトに添付されたキーを検索できるものを作成します。キーが変更されたときにコードがこのマップを更新していることを確認してください。(これはstd::multimap、多対多の関係が必要な場合にも使用できます。)
    • Objectcurrent を含むメンバー変数を に追加しますKey(O(1) ルックアップを許可します)。キーが変更されたときにコードがこの変数を更新していることを確認してください。

あなたの記事では「座標」がキーとして言及されているので、「3D 座標が既に使用されているかどうかを見つける最速の方法」の提案を読むことにも興味があるかもしれません。

于 2008-09-18T17:56:39.060 に答える
2

1 つのオプションは、shared_ptrs を参照する 2 つの std::map を使用することです。このようなものはあなたを動かすかもしれません:

template<typename T, typename K1, typename K2>
class MyBiMap
{
public:
    typedef boost::shared_ptr<T> ptr_type;

    void insert(const ptr_type& value, const K1& key1, const K2& key2)
    {
        _map1.insert(std::make_pair(key1, value));
        _map2.insert(std::make_pair(key2, value));
    }

    ptr_type find1(const K1& key)
    {
        std::map<K1, ptr_type >::const_iterator itr = _map1.find(key);
        if (itr == _map1.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

    ptr_type find2(const K2& key)
    {
        std::map<K2, ptr_type >::const_iterator itr = _map2.find(key);
        if (itr == _map2.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

private:
    std::map<K1, ptr_type > _map1;
    std::map<K2, ptr_type > _map2;
};

編集:マルチマップの要件に気付きましたが、これはまだアイデアを表現しているため、そのままにしておきます。

于 2008-09-18T18:21:22.370 に答える
2

あなたがそれで何をしているのか正確に理解するのは難しいですが、ブーストバイマップがあなたが望むものであるようです. 特定のユースケースを除いて、基本的にマルチインデックスをブーストし、使いやすくします。これにより、最初の要素または 2 番目の要素に基づく高速検索が可能になります。マップ内のオブジェクトの位置を住所で調べるのはなぜですか? 抽象化を使用して、すべての作業を任せてください。注意: マップ内のすべての要素の反復は O(N) であるため、O(N) (悪くはない) が保証され、あなたが考えている方法で検索することができます。

于 2008-09-18T17:44:00.523 に答える