std :: map：等しい値を持つキーで構成されるリターンベクトル

Question

私はstd::mapオブジェクトを持っています。キーはエンティティID（整数）で、2D位置（ベクトル）を評価します。目的は、同じエンティティ にあるエンティティを識別することです。

ID Position 
1 {2,3} 
5 {6,2} 
12 {2,3} 
54 {4,4} 
92 {6,2} 

等しい値を持つキーで構成されるベクトルのベクトルを取得する必要があります。私は同等のインデックスを見つけるために、最初のレベルのベクトルベクトルループにベクトルに2次元位置をコピーすることを知って、{1,12}、{5,92}

：上記の例の入力データの

出力第2レベルベクトル。次に、索引でベクトルを選択し、再び対応するキーを見つけるためにループすることによって、キーを見つけるために作業を戻します。

これをよりクリーンな方法で提案してください。

Answer 1

std::mapのポイントは、マッピングの効率的なキーを提供することです。

• がPositionからstd::vector<ID>に行く余分std::mapを持っている：複数の方法で達成することができる - 何が必要キーマッピングに追加値です。

• は、それらの位置に応じてエンティティを見つけるために、それが効率的になり空間分割データ構造（例えば四分木、空間ハッシュ、グリッド）のいくつかの並べ替えを使用します。

• 双方向マルチマップをboost::bimapのように使用してください。これにより、複数のデータ構造を使用することなく、値のコレクションに対して双方向マッピングを行うことができます。

"どうやって選ぶのですか？"

あなたの優先順位によって異なります。最大限のパフォーマンスを望むなら、のアプローチを試してみてください。多分、テンプレート化されたラッパーを使ってください。とプロファイル。あなたがエレガンス/清潔さを望むなら、boost::bimapが最も適切な解決策であるようです。

Answer 2

マップからのデータをstd::mutlimapに、Positionをキーに、IDを値として指定することができます。

std::pairが2次元の点のベクトルよりも優れているかどうかは不便です。

Answer 3

逆マッピングを行う必要があります。 multimapを含む多くの方法がありますが、作成後にマッピングを変更してマップ上を反復して逆マッピングを構築するという単純なアプローチがあります。逆マッピングでは、キーの値 - >リストをマッピングします。

std::unordered_mapのコードでは、std::pair<int, int>（元のマップの値）をstd::vector<int>（元のマップのキーのリスト）にマップしています。逆マップの建物はシンプルかつ簡潔である：

std::unordered_map<Point, std::vector<int>, hash> r; 
for (const auto& item : m) { 
    r[item.second].push_back(item.first); 
} 

（hashの定義のための完全な例を参照してください）。

キーが存在するかどうかを心配する必要はありません。 r[key]表記を使用してそのキーにアクセスしようとすると、そのキーが作成されます（そして、IDのベクトルは空のベクトルとして初期化されます）。

このソリューションは、シンプルさを重視しています。これを行う必要があり、パフォーマンス、メモリ使用、またはBoostのようなサードパーティライブラリを使用しない場合は、実行可能なソリューションです。

これらのことのいずれかを気にしたり、両方向で検索しながら地図を変更している場合は、おそらく他のオプションを調べる必要があります。

---

Live example

#include <iostream> 
#include <map> 
#include <unordered_map> 
#include <vector> 

// Define a point type. Use pair<int, int> for simplicity. 
using Point = std::pair<int, int>; 

// Define a hash function for our point type: 
struct hash { 
    std::size_t operator()(const Point& p) const 
    { 
     std::size_t h1 = std::hash<int>{}(p.first); 
     std::size_t h2 = std::hash<int>{}(p.second); 
     return h1^(h2 << 1); 
    } 
}; 

int main() { 
    // The original forward mapping: 
    std::map<int, Point> m = { 
     {1, {2, 3}}, 
     {5, {6, 2}}, 
     {12, {2, 3}}, 
     {54, {4, 4}}, 
     {92, {6, 2}} 
    }; 

    // Build reverse mapping: 
    std::unordered_map<Point, std::vector<int>, hash> r; 
    for (const auto& item : m) { 
     r[item.second].push_back(item.first); 
    } 

    // DEMO: Show all indices for {6, 2}: 
    Point val1 = {6, 2}; 
    for (const auto& id : r[val1]) { 
     std::cout << id << " "; 
    } 
    std::cout << "\n"; 

    // DEMO: Show all indices for {2, 3}: 
    Point val2 = {2, 3}; 
    for (const auto& id : r[val2]) { 
     std::cout << id << " "; 
    } 
    std::cout << "\n"; 
} 

Answer 4

This answer最善のようですが、私はとにかく自分のコードを提供します。

考える

#include <iostream> 
#include <map> 
#include <vector> 

// Some definiton of Vector2D 
struct Vector2D { int x; int y; }; 

// and some definition of operator< on Vector2D 
bool operator<(Vector2D const & a, Vector2D const & b) noexcept { 
    if (a.x < b.x) return true; 
    if (a.x > b.x) return false; 
    return a.y < b.y; 
} 

方法について：

template <typename M> 
auto calculate(M const & inputMap) -> std::vector<std::vector<typename M::key_type> > { 
    std::map<typename M::mapped_type, 
      std::vector<typename M::key_type> > resultMap; 
    for (auto const & vp : inputMap) 
     resultMap[vp.second].push_back(vp.first); 
    std::vector<std::vector<typename M::key_type> > result; 
    for (auto & vp: resultMap) 
     if (vp.second.size() > 1) 
      result.emplace_back(std::move(vp.second)); 
    return result; 
} 

はここにどのようにテスト：

int main() { 
    std::map<int, Vector2D> input{ 
     {1, Vector2D{2,3}}, 
     {5, Vector2D{6,2}}, 
     {13, Vector2D{2,3}}, 
     {54, Vector2D{4,4}}, 
     {92, Vector2D{6,2}} 
    }; 

    auto const result = calculate(input); 

    // Ugly print 
    std::cout << '{'; 
    static auto const maybePrintComma = 
     [](bool & print) { 
      if (print) { 
       std::cout << ", "; 
      } else { 
       print = true; 
      } 
     }; 
    bool comma = false; 
    for (auto const & v: result) { 
     maybePrintComma(comma); 
     std::cout << '{'; 
     bool comma2 = false; 
     for (auto const & v2: v) { 
      maybePrintComma(comma2); 
      std::cout << v2; 
     } 
     std::cout << '}'; 
    } 
    std::cout << '}' << std::endl; 
}