0

次のタイプの stl マップがあります。

map<Object*, baseObject*>

どこ

class baseObject{
    int ID;
    //other stuff
};

オブジェクトのリスト (std::list< Object* >) を返したい場合、それを baseObject.ID の順に並べ替える最良の方法は何ですか?

私はすべての数字か何かを調べて立ち往生していますか? マップをブースト マップに変更しないことをお勧めしますが、リターン関数内で自己完結型の処理を実行することに必ずしも反対するわけではありません。

GetObjectList(std::list<Object*> &objects)
{
   //sort the map into the list
}

編集: obj->baseobj を反復して baseobj.ID->obj のマップにコピーする必要がありますか?

4

6 に答える 6

2

私がすることは、最初にキーをベクトルに抽出し（それらを返したいだけなので）、それをソートすることです：

std::vector<baseObject*> out;
std::transform(myMap.begin(), myMap.end(), std::back_inserter(out), [](std::pair<Object*, baseObject*> p) { return p.first; });
std::sort(out.begin(), out.end(), [&myMap](baseObject* lhs, baseObject* rhs) { return myMap[lhs].componentID < myMap[rhs].componentID; });

コンパイラがラムダをサポートしていない場合は、自由な関数または関数オブジェクトとして書き直してください。簡潔にするためにラムダを使用しました。

reserveパフォーマンスのために、ベクトルを徐々に拡張するのではなく、最初はベクトルに十分なスペースを確保したいと思います。

(また、コードをテストしていないことに注意してください。そのため、少しいじる必要があるかもしれません)

また、このマップが何を表しているのかはわかりませんが、キーと値の両方の型がポインターであるマップを保持すると、「悪い C++」の感覚が本当にチクチクします。手動のメモリ管理と混乱した (または存在しない) 所有権のセマンティクスのにおいがします。

a で出力を取得すると述べましたlistが、 avectorはほぼ確実にパフォーマンスの高いオプションであるため、それを使用しました。a が望ましい唯一の状況は、listそれを繰り返し処理するつもりがなく、リストの変更後もポインタとイテレータが有効であるという保証が必要な場合です。

于 2012-05-24T17:47:22.270 に答える
1

「baseObject.IDの順に並べ替える」と言ったことを実行する方法は次のとおりです。

typedef std::map<Object*, baseObject*> MapType;
MapType mymap; // don't care how this is populated
               // except that it must not contain null baseObject* values.

struct CompareByMappedId {
    const MapType &map;
    CompareByMappedId(const MapType &map) : map(map) {}
    bool operator()(Object *lhs, Object *rhs) {
        return map.find(lhs)->second->ID < map.find(rhs)->second->ID;
    }
};

void GetObjectList(std::list<Object*> &objects) {
    assert(objects.empty()); // pre-condition, or could clear it
    // or for that matter return a list by value instead.

    // copy keys into list
    for (MapType::const_iterator it = mymap.begin(); it != mymap.end(); ++it) {
        objects.push_back(it->first);
    }
    // sort the list
    objects.sort(CompareByMappedId(mymap));
}

これは必死に効率的ではありません。厳密に必要な以上にマップを検索し、でのリストノードの操作は、ポインターのランダムアクセスコンテナを操作する場合std::list::sortよりも少し遅くなる可能性があります。std::sortしかし、std::listそれ自体はほとんどの目的であまり効率的ではないため、セットアップには費用がかかると予想されます。

最適化する必要がある場合は、のペアのベクトルを作成できるため(int, Object*)、マップを1回繰り返すだけで、検索する必要はありません。ペアを並べ替えてから、各ペアの2番目の要素をリストに追加します。これは時期尚早の最適化かもしれませんが、実際には効果的なトリックです。

于 2012-05-24T18:10:45.677 に答える
1

私はあなたがうまくいくと思います：

GetObjectList(std::list<Object*> &objects)
{
  std::vector <Object*> vec;
  vec.reserve(map.size());
  for(auto it = map.begin(), it_end = map.end(); it != it_end; ++it)
    vec.push_back(it->second);
  std::sort(vec.begin(), vec.end(), [](Object* a, Object* b) { return a->ID < b->ID; });
  objects.assign(vec.begin(), vec.end());
}
于 2012-05-24T17:45:30.943 に答える
1

最初にstd::list、 ではなく を使用しstd::vectorます。特定の問題の時点​​で、2 つの操作を実行する必要があります。コンテナを生成し、条件に応じて並べ替えます。

// Extract the data:
std::vector<Object*> v;
v.reserve( m.size() );
std::transform( m.begin(), m.end(), 
                std::back_inserter(v),
                []( const map<Object*, baseObject*>::value_type& v ) {
                     return v.first;
                } );
// Order according to the values in the map
std::sort( v.begin(), v.end(), 
           [&m]( Object* lhs, Object* rhs ) {
               return m[lhs]->id < m[rhs]->id;
           } );

C++11 を使用しない場合は、ラムダの代わりにファンクターを作成する必要がありstd::listますstd::list<>::sort( Comparator )。これはおそらく非効率的であることに注意してください。パフォーマンスが問題になる場合 (これを機能させ、プロファイリングを行い、これが実際にボトルネックであることを認識した後)、中間の使用を検討することをお勧めしますmap<int,Object*>。

std::map<int,Object*> mm;
for ( auto it = m.begin(); it != m.end(); ++it )
   mm[ it->second->id ] = it->first;
}
std::vector<Object*> v;
v.reserve( mm.size() );                  // mm might have less elements than m!
std::transform( mm.begin(), mm.end(), 
                std::back_inserter(v),
                []( const map<int, Object*>::value_type& v ) {
                     return v.second;
                } );

繰り返しますが、これは元のバージョンよりも速くなったり遅くなったりする可能性があります... プロファイル。

于 2012-05-24T17:49:15.250 に答える
0

マップに何を保存しようとしているのか完全にはわかりませんが、おそらくここを見てください

std :: mapの3番目のテンプレート引数は、あまり機能的ではありません。おそらく、これを利用して、挿入時にマップに保存されているデータを並べ替えることができます。次に、リストにデータを入力するのは、マップイテレータの単純なループになります。

于 2012-05-24T18:02:52.543 に答える
0

オブジェクトのコンポーネント ID を使用した並べ替え基準を持つ新しいマップを作成します。最初のマップから 2 番目のマップを作成します (反復処理または std::copy in のみ)。次に、イテレータを使用してこのマップを順番に読み取ることができます。

これには、ベクターまたはリスト (定数時間ではなく log(n) 時間) を使用する場合の挿入に関してわずかなオーバーヘッドがありますが、ベクターまたはリストを作成した後に並べ替える必要がなくなります。

また、プログラムの後半でさらに要素を追加することができ、手段を必要とせずにその順序を維持できます。

于 2012-05-24T17:45:07.107 に答える