Как мне наиболее эффективно вставить список пар?

Question

Предположим, у меня есть

(A,B)
(A,C)
(A,D)
(B,C)
(B,D)
(C,D)
(D,E)

в текстовом файле.Я извлеку его с помощью регулярных выражений.

Я хотел бы вставить данные в контейнер так, чтобы он выглядел следующим образом.

A->B,C,D
B->C,D
C->D
D->E

Какой контейнер я использую?

Мне нужно иметь возможность просматривать данные как с левой, так и с правой стороны контейнера, т. Е. С помощью ввода значения.Поэтому я должен иметь возможность искать / искать

A, B, C, D в

A->B,C
B->C,D
C->D
D->E

и B, C в

A->B,C

Answer 1

std :: multimap приходит на ум ... По сути, это карта, но допускает дублирование в ключе карты (т. Е. Вы можете иметь несколько ключей "A", каждый из которых отображается на "B",«C» или «D», чтобы продолжить пример).

РЕДАКТИРОВАТЬ: В ответ на комментарий Криса: вы вставляете элементы в мультикарту так же, как карта -вы создаете std::pair объект, содержащий ключ и значение, затем insert, который в мультикарте:

std::multimap<char, char> myMap;
myMap.insert(std::pair<char, char>('A', 'B'));
myMap.insert(std::pair<char, char>('A', 'C'));
myMap.insert(std::pair<char, char>('A', 'D'));
myMap.insert(std::pair<char, char>('B', 'C'));
// ... etc

Предполагая, что здесь вы буквально исследуете символы, и AB, C и т. Д. Не являются заменой для чего-то другого.Если они являются резервными, настройте их соответствующим образом.

Затем вы можете запросить мультикарту для всех значений под клавишей 'A' следующим образом:

typedef std::multimap<char, char>::iterator mmIter; // For brevity...
std::pair<mmIter, mmIter> iters = myMap.equal_range('A');
// Iterate over values for key
for (mmIter iter = iters.first ; iter != iters.second; ++iter)
{
    // Print out value.
    cout << " " << (*iter).second;
}

multimap.equal_range возвращает pair, содержащий итераторы для первой записи, соответствующей ключу, и запись, следующую непосредственно за последней записью, соответствующей ключу.Поэтому их можно использовать для итерации записей, как показано.

EDIT 2 только что понял, что вы на самом деле подразумевали под своим комментарием.Multimap изначально не поддерживает двунаправленную операцию (то есть поиск по значению, а также по ключу), поэтому вам может потребоваться поддерживать два мультикарты - по одному для каждого направления.Хотя это может быть трудной задачей - может быть сложно обеспечить правильную синхронизацию этих двух файлов.

В качестве альтернативы, я уверен, что есть некоторый класс Boost , который будет служить цели (яна самом деле не знаю - я сам не использую Boost, но уверен, что кто-то другой сможет предоставить более подробную информацию).

Answer 2

Предполагая, что вам нужно искать данные на правой стороне, используя 'ключ' на левой стороне, я бы использовал мультикарту для хранения этих значений.

Другой альтернативой будет что-то вроде std::map<keytype, std::vector<valuetype> >.