c++ - 如何避免重复对/在多图中找到一对？

Question

我有一些（工作）代码使用multimap<string,string>. 我想将其更改为不允许同一键上的重复值（显然同一键上的不同值很好，否则我不会使用多映射）。

令人惊讶的是，该类型似乎没有内置方法来避免重复，也没有找到键值对（仅查找键）。但我认为 SO 上的某个人必须有现成的解决方法。任何人？

Answer 1

这是我想出的：

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

（当单个键上附加大量值时，这效率不高，但在我的情况下，每个键上的值很少。）

Answer 2

std::map<std::string, std::set<std::string>>似乎具有您正在寻找的属性exactamondo（尽管复杂性不如unordered_mapand unordered_set）。

Answer 3

看起来

      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;

Answer 4

我对您的建议是将您的多图包装在一个类中，并简单地在您将某些内容添加到地图中的方法中进行验证。其余的函数将简单地传递给多图的方法。它制作了很多样板代码，但如果您需要进行其他类型的验证，这种方式会更容易。