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