2

基本的に、各ノードが要素と要素自体の関数 ( < x,f(x) > ) で構成されるリストであるコンテナーを探しています。ここで、x と f(x) は整数です。

このコンテナを使用すると、順序が f(x) によって提供される順序付きの方法で挿入できます。STLにそのようなものはありますか？

4

3 に答える 3

3

std::mapを使用f(x)してキーとして使用できます。

#include <map>

int f(int);

int n = ....;
std::map<int,int> m;
m.insert(std::make_pair(f(n), n));

int i = ...;
m[f(i)] = i;

別のオプションは、他の回答で提案されているように、適切なコンパレーター関数でstd::setを使用することです。ただし、コンパレータが厳密な弱い順序付けを実装していることを確認する必要があります。これは、関数の特性によって異なりますf(int)。

于 2012-07-22T15:49:33.040 に答える
2

この時点でstd::set、カスタム コンパレータを使用した astd::mapと にマップf(x)するa の使用を示唆する 2 つの異なる回答がありますx。私は実際には 3 番目のオプションを選択しstd::set< std::pair<int,int> >ます(f(x),x)。

に対する利点std::map<>は、同じ情報を保持している間、 がx変更されないことを保証するため、マップを反復処理すると常に のペアが生成されるという不変条件が保証されることです(f(x),x)。std::set<int, cmp>where cmpisよりも優れている点fは、値がコンテナーに存在する場合に、関数を 1 回だけ計算する必要があることです ( のコストに応じて、影響がある場合とない場合がありますf)。

このアプローチと他のアプローチ (正または負の可能性があります) とのその他の違いはx、同じ へのマッピングの複数の値を自然に許可することですf(x)。順序std::pair<>は辞書式であるため、コンテナーはそのようなすべてのペアを次の順序で格納します。は最初に によって決定され、次にf(x)によって決定さxれxます。f(x)(0,1), (0,3), (1,2)f(1) == f(3) == 0f(2) == 1

このような重複を許可できない場合 (つまり、値ごとに 1 つの要素のみを使用する場合)、各ペアf(x)の値のみをテストするカスタム コンパレータを追加できます。first

于 2012-07-22T16:18:54.687 に答える
2

できると思います

int foo(int x );

struct mycustomcompare {
  bool operator() (const int& lhs, const int& rhs) const
  {return foo(lhs) < foo(rhs);}
};


int main()
{
    std::set<int,mycustomcompare> myset;
    myset.insert( 1 );
    myset.insert( 2 );
}

もちろん、foo(2) と foo(3) が同じ値を返す場合、そのうちの 1 つだけが挿入されます。ドメインに問題がある場合は、マルチセットを使用できます

int foo(int x )
{
    return x % 2 ==0;
}

struct mycustomcompare {
  bool operator() (const int& lhs, const int& rhs) const
  {return foo(lhs) < foo(rhs);}
};


int main()
{
    std::multiset<int,mycustomcompare> myset;
    myset.insert( 1 );
    myset.insert( 2 );
    myset.insert( 3);
    myset.insert( 4);
    myset.insert( 5);
    myset.insert( 6);

}

上記の例では、すべての奇数要素がセットの前半に含まれます。または、単純にベクトルを使用して、比較関数でソートすることもできます

int foo(int x )
{
    return x % 2 ==0;
}

struct mycustomcompare 
{
    bool operator() (const int& lhs, const int& rhs) const
    {return foo(lhs) < foo(rhs);}
};


int main()
{

    std::vector<int> myvector;

    myvector.push_back( 5);
    myvector.push_back( 1 );
    myvector.push_back( 6);
    myvector.push_back( 2 );
    myvector.push_back( 3);
    myvector.push_back( 4);

    std::sort( myvector.begin() , myvector.end() , mycustomcompare() );
}

f(x) の評価が高価な場合は、比較オブジェクトに状態を追加することもできます。

于 2012-07-22T15:49:15.340 に答える