словарь — структура данных C ++ для хранения нескольких связей между двумя уникальными наборами элементов
Я работаю над проектом, в котором у меня есть два уникальных набора элементов. Любой из элементов в одном наборе может быть связан с любым из элементов в другом наборе.
Пример:
Набор 1: {A, B, C}
Набор 2: {1, 2, 3, 4}
Разрешенные отношения:
(А, 1) (А, 3)
(Б, 1) (Б, 4)
(С, 1) (С, 3) (С, 4)
Одно отношение представляется в виде двух заданных элементов в одной паре скобок.
В моем конкретном проекте элементы обоих наборов являются объектами, и я хотел бы, чтобы все ссылки на все сохраненные объекты разрешались в одном объекте (например, все отношения, содержащие A, будут ссылаться на один и тот же объект A, и то же самое относится к ссылки на другое множество на другой стороне отношений).
Я думал об использовании Boost bimap решить для этой проблемы. Я смотрел на потенциальные типы коллекций, используемых для левой и правой половин двуногих и для отношений между двумя наборами, и пытался решить, какие из них являются правильными.
Для левой и правой половин bimapЯ думал, что set_of CollectionType было бы правильно, так как мои два набора объектов, ну, в общем, наборы, и я не хочу дублировать копии любого элемента в моем bimap,
Однако, когда я попробовал это на практике, я не смог вставить отношение (B, 1) после того, как я вставил отношение (A, 1), так как вставка должна быть действительной в обоих слева и правильные взгляды, чтобы это произошло. Чтобы исправить эту проблему, я изменил CollectionType обеих половин быть multiset_of, Все значения вставлены правильно, однако означает ли это, что мой bimap теперь есть дубликаты элементов моих оригинальных наборов?
Чтобы попытаться исправить это, я начал смотреть на изменение типа коллекции отношений между двумя половинами bimap, Поскольку тип коллекции типа отношения по умолчанию равен типу левой половины bimapЯ понял что multiset_of неверно, и указал его как set_of, Однако я не уверен, что это решает мою первоначальную проблему наличия нескольких копий моих объектов из моих оригинальных наборов.
Все, что мне действительно нужно, это посмотреть на все объекты из набора 2, которые связаны с элементом из набора 1. Является ли повышение bimap правильный маршрут для меня? Являются ли типы коллекций и отношений, которые я выбрал, правильными? Кроме того, я пытаюсь настроить свою карту, чтобы иметь быстрое время поиска, не заботясь о времени вставки (удаление и модификация никогда не произойдут, карта инициализируется, а затем просто используется для поиска после этого). Должен ли я просто написать собственную структуру данных вместо этого?
Решение
Я полностью согласен с ответом Джерри. Если вы пытаетесь смоделировать граф, рассмотрите, например, использование списка смежности, списка ребер или матричного представления.
Ответ Пола был немного волнистым, так что вот пример использования Boost Multi Index:
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/ordered_index.hpp>
struct T1 {
std::string name;
bool operator<(T1 const& o) const { return name < o.name; }
};
struct T2 {
int id;
bool operator<(T2 const& o) const { return id < o.id; }
};
namespace bmi = boost::multi_index;
struct Relation {
T1 const* key1;
T2 const* key2;
std::string const& name() const { return key1->name; }
int id () const { return key2->id; }
friend std::ostream& operator<<(std::ostream& os, Relation const& r) {
return os << "(" << r.name() << ", " << r.id() << ")";
}
};
using RelationTable = bmi::multi_index_container<Relation,
bmi::indexed_by<
bmi::ordered_unique<bmi::tag<struct by_composite>,
bmi::composite_key<Relation,
bmi::const_mem_fun<Relation, std::string const&, &Relation::name>,
bmi::const_mem_fun<Relation, int, &Relation::id>
>
>
> >;
#include <set>
int main() {
using namespace std;
set<T1> set1 { {"A"}, {"B"}, {"C"} };
set<T2> set2 { {1}, {2}, {3}, {4} };
// convenient data entry helpers
auto lookup1 = [&set1](auto key) { return &*set1.find(T1{key}); }; // TODO error check?
auto lookup2 = [&set2](auto key) { return &*set2.find(T2{key}); };
auto relate = [=](auto name, auto id) { return Relation { lookup1(name), lookup2(id) }; };
// end helpers
RelationTable relations {
relate("A", 1), relate("A", 3),
relate("B", 1), relate("B", 4),
relate("C", 1), relate("C", 3), relate("C", 4),
};
for (auto& rel : relations)
std::cout << rel << " ";
}
Печать
(A, 1) (A, 3) (B, 1) (B, 4) (C, 1) (C, 3) (C, 4)
Другие решения
Это выглядит как проблема с графиком, которую лучше смоделировать более непосредственно:
struct nodeB;
struct nodeA {
char label;
std::vector<nodeB *> assocs;
};
struct nodeB {
int label;
std::vector<nodeA *> assocs;
};
Оттуда, я думаю, вы хотите, чтобы класс управлял коллекцией каждого типа и обрабатывал добавление узлов, чтобы гарантировать, что ваши инварианты поддерживаются должным образом.