std :: map: обратные векторы, состоящие из ключей, имеющих равные значения

Question

У меня есть объект std::map. Ключами являются идентификаторы объектов (целые числа) и значения их двумерных позиций (векторов). Цель состоит в том, чтобы идентифицировать, какие объекты находятся в в том же положении.

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].

Это решение ориентировано на простоту; это приемлемое решение, если вам нужно это сделать и не заботясь о производительности, использовании памяти или использовании сторонних библиотек, таких как 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; 
}