2

私は関数型プログラミングのバックグラウンドを持っており、（効率的な）C++データ構造には慣れていません。に示されているような複数の要素を保持するデータ構造が必要ですstruct element。コレクションでは、フィールドIDは一意である必要があります。

集合論のように非常に高速な集合比較を実行したい。たとえば、集合{x1,x2,x3}を比較するとき{x4,x5}に、交差集合{x5}（または{x2}この場合は等しい）を決定し、たとえばのような他の集合から集合を減算したい{x1,x2,x3} \ {x5} = {x1,x3}。

C ++の世界に...「集合論的」データ構造はありますか？

struct element {
int id;
float value;
};

struct element x1 = {1, 1.0};
struct element x2 = {2, 2.0};
struct element x3 = {3, 3.0};

struct element x4 = {3, 3.1};
struct element x5 = {2, 2.0};
4

3 に答える 3

5

動的セットを実装するがありstd::setます (動的とは、要素を挿入または削除できることを意味します)。構造で機能させるelementには、 のみを見るカスタム比較関数が必要ですid。または、 を使用することもできますstd::map<int, float>。これは、問題により適している可能性があります。

2 つの集合の交点を見つけるには、std::set_intersectionアルゴリズムを使用します。std::setこれには、 orへのイテレータの範囲を含む、ソートされた範囲が必要std::mapです。違いについては、 を使用しますstd::set_difference。

于 2011-12-10T19:36:24.210 に答える
1

セットを扱うときは本当に優れたデータ構造がありますが、すべてのニーズに適しているわけではないので、これについて言及したいだけです.

ただし、次のような要件がある場合は、覚えておくことができます。

1) 要素がどのセットに属しているかを問い合わせる

2) 異なるセットの結合

どちらも準対数時間、つまりほぼ一定です。Disjoint set データ構造と呼ばれる http://en.wikipedia.org/wiki/Disjoint-set_data_structure

于 2011-12-10T19:40:29.740 に答える
1 
struct element {
    int id;
    float value;

    element(int id_=0, float value_=0.0) : id(id_), value(value_) {}

    bool& operator==(const element& e) const
    {
        return id==e.id && value==e.value;
    }
};

element e1(1,1.0);

std::set<element> set_;
set_.insert(e1);

実行できる操作の std アルゴリズムをチェックアウトします。 http://www.cplusplus.com/reference/algorithm/

于 2011-12-10T19:40:40.997 に答える