的std ::地圖：返回向量，由具有相等的值

Question

我有一個std::map對象密鑰。鍵是實體ID（整數）併爲它們的2D位置（向量）賦值。目的是識別哪些實體在 的相同位置。

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

我需要獲得由具有相同值的鍵組成的向量向量。

輸出，用於上述示例的輸入數據：{1,12}，{5,92}

我知道可以複製的2D位置的向量載體和環路中的第一級矢量找到的索引相等第二級矢量。然後通過索引選擇向量並再次循環找到相應的密鑰來找回密鑰。

請爲此建議一個更清潔的方法。

Answer 1

std::map的要點是提供一個有效的鍵值映射。你需要的是一個額外的價值關鍵映射 - 可以通過多種方式來實現：

• 有一個額外的std::map是去從Position到std::vector<ID>。

• 使用某種，使得它有效空間分割數據結構（例如四叉樹，空間散列，網格）的找到這取決於它們的位置的實體。

• 使用雙向多圖像boost::bimap。這將允許您在不需要使用多個數據結構的情況下對值集合進行雙向映射。

「我該如何選擇？」

這取決於你的優先權。如果你想獲得最大的性能，你應該嘗試所有的方法（也許使用某種模板包裝）和配置文件。如果你想要優雅/清潔，boost::bimap似乎是最合適的解決方案。

Answer 2

您可以將地圖中的數據放入std::mutlimap，其中Position爲關鍵字，ID爲值。

作爲一個方面說明我不知道如果std::pair可能比2D點向量更好。

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; 
}