1

このようなマップを定義しました

typedef   std::vector< int > aVector;
typedef std::map< int, aVector > aMap;
aMap theMap;

マップに最終的にこのような要素が含まれていると仮定します

10 [0 3 7] size=3
12 [40 2 30 3 10] size=5
20 [5 10] size=2
25 [6] size=1

ベクトルのサイズでソートしたい (例: theMap->second.size())。したがって、結果は次のようになります

5 3 2 1

それを行う最も速い方法は何ですか？基本的な考え方は、サイズを別のベクトルにプッシュしてから、次のように sort() を呼び出すことです。

aVector v, sorted;
aMap::iterator it = theMap.begin();
for (; it != theMap.end(); ++it) {
  v.push_back(it->second.size());
}
// using std sort!!

より良いオプションはありますか？

4

3 に答える 3

1

ベクトルをキーとして配置し、キーのサイズを比較するカスタムのキー比較関数/ファンクターを使用してみませんか?

この例はhttp://www.cplusplus.com/reference/map/map/map/ ?にあります。

私は現在 C++ コンパイラにアクセスしていませんが、次のようになります。

#include <map>

struct aComparisonStruct {
    bool operator() (const aVector& lhs, const aVector& rhs) const {
        return lhs.size > rhs.size;
    }
};

int main () {
    typedef std::vector<int> aVector;
    typedef std::map<aVector, int, aComparisonStruct> aMap;

    // Use your map

    return 0;
}

ただし、問題があります。単一のキー存在のプロパティを使用できなくなり、同じベクトルを複数回追加することはできなくなります。多分別の実装がより適切でしょうか？

また、ポインターをキーとして使用する方が確実に優れていますが、コンパイルできないため、ポインターと参照を混同して、おそらく機能しないものを提供したくありません。

于 2013-06-23T19:13:30.320 に答える
1

std::map特定の順序ですばやく検索したりstd::hash_map、管理したりする必要がある場合、非常に一般的なタスクがあります。このような状況では、メイン コレクションに「インデックス」コレクションを使用できます。 

aMap theMap;
std::map<size_t, std::list<aMap::iterator> > sizes;

// add item
auto r = theMap.insert(key, std::vector<int>());
if (!r->second)
{
    sizes[r->first->second.size()].remove(r->first);
}
r->first->second->push_back(item);
sizes[r->first->second.size()].push_back(r->first);
于 2013-06-23T20:07:56.783 に答える