Как избежать дублирования пар / найти пару в мультикарте?
У меня есть некоторый (рабочий) код, который использует multimap<string,string>, Я хотел бы изменить его, чтобы запретить повторяющиеся значения на одном и том же ключе (очевидно, что разные значения на одном и том же ключе подходят, иначе я бы не использовал мультикарту).
Удивительно, но тип не казаться иметь встроенный способ избежать дублирования или найти пару ключ-значение (только чтобы найти ключ). Но я полагаю, что кто-то на SO должен иметь готовый обходной путь. Кто-нибудь?
Решение
std::map<std::string, std::set<std::string>> может показаться, что в свойствах, которые вы ищете unordered_map а также unordered_set).
Другие решения
Вот что я придумал:
template<class K, class V>
typename multimap<K, V>::const_iterator find_pair(const multimap<K, V>& map, const pair<K, V>& pair)
{
typedef multimap<K, V>::const_iterator it;
std::pair<it,it> range = map.equal_range(pair.first);
for (it p = range.first; p != range.second; ++p)
if (p->second == pair.second)
return p;
return map.end();
}
template<class K, class V>
bool insert_if_not_present(multimap<K, V>& map, const pair<K, V>& pair)
{
if (find_pair(map, pair) == map.end()) {
map.insert(pair);
return true;
}
return false;
}
(Это неэффективно, когда к одному ключу прикреплено большое количество значений, но в моем случае очень мало значений для каждого ключа.)
Я бы предложил вам обернуть вашу мультикарту в класс и просто выполнить проверку в методе, где вы добавляете что-то на карту. Остальные функции просто перейдут к методам мультикарты. Он содержит много кода, но если вам когда-нибудь понадобится выполнить другие виды проверок, это будет проще.
Кажется, что
std::set<std::pair<std::string,std::string>>>
будет иметь именно те свойства, которые вы ищете.
Однако это не карта и не мультикарта. Вы можете сохранить как мультикарту, так и набор ключей, пар значений или создать этот набор только для проверки согласованности.
Я хотел бы использовать этот набор и создать адаптер для него для интерфейса с несколькими картами. Возможно, это не самое простое решение для реализации, но с лучшей производительностью.
См. Вопросы «шаблона проектирования адаптера» для справок.
[ОБНОВИТЬ]
См мой рабочий пример в качестве отправной точки.
Например. Как перебрать все значения ключа — смотрите:
typedef std::set<std::pair<std::string, std::string> > ssset;
ssset::iterator get_key(ssset& s, std::string key)
{
ssset::iterator it = s.lower_bound(std::make_pair(key, ""));
if (it != s.end() && it->first == key) return it;
return s.end();
}
for (ssset::iterator it = get_key(s, "abc"); it != s.end() && it->first == "abc"; ++it)
std::cout << it->first << "->" << it->second << std::endl;