如何使用c ++避免地图中的重复值

Question

我正在尝试使用地图在cpp中编写程序...

我的目标是避免在地图中重复相同的值.

如果密钥相同,我们可以使用map来避免重复密钥.为了允许重复密钥,我们使用multimaps

如果值相同,我们如何避免？

我编写的程序允许重复值

typedef std::map<int, std::string> MyMap;

int main()
{
    MyMap map;
    MyMap::iterator mpIter;

    int key;
    string value;

    int count;
    for(count = 0; count < 3;count++)
    {
        cin >> key;
        cin >> value;

        std::pair<MyMap::iterator, bool> res = map.insert(std::make_pair(key,value));
    }

    for (mpIter=map.begin(); mpIter != map.end(); ++mpIter)
         cout  << " "  << (*mpIter).second << endl;
}

Answer 1

将值作为键的一部分和/或使用集合，但这可能无法真正解决问题。如果您想要的话，不可能轻松定义具有唯一键和值的容器。但是，您仍然可以构建一个。这是一个非常简单的例子来说明需要什么：

// Assuming keys are KEY and values are VAL

class MyMap  {
public:
   std::set<KEY> keyset;
   std::set<VAL> valset;

   std::map<KEY,VAL> theRealMap;

   // assuming existence of  function HAS(S,V) 
   // which returns true if v is in set S
   bool MyInsert(KEY ky, VAL val) {
       if (HAS(keyset,  ky) return false;
       if (HAS(valset, val) return false;
       keyset.insert(ky);
       valset.insert(vl);
       return theRealMap.insert(std::pair<KEY,VAL>(ky, val));
   }
:
:

由于这是一个示例，因此不应复制。您可能希望包含 std:map 提供的功能。一种简单的方法是使用 std::map 作为基类，但您需要隐藏（通过设为私有）或为每个插入变体实现类似的代码，否则您可能会无意中插入可能不唯一的插入。

注意：这需要单个地图大小的两倍。您可以通过使用 RealMap 而不是单独的键集来节省一些空间。另一种方法是搜索地图，但这会牺牲时间换取空间。这是你的决定。

Answer 2

一种方法是维护一个单独的std::set值。当您将一个值插入到集合中时，它会返回一个std::pair<iterator, bool>. 如果该值尚未在集合中，则为该bool值。这告诉您将值放入地图中是否true安全。

然而，首先，您需要确保它key是唯一的，因为相同的值key可能已经插入了不同的值：

typedef std::map<int, std::string> MyMap;

int main()
{
    MyMap map;
    MyMap::iterator mpIter;

    int key;
    string value;
    int count;

    // keep track of values with a std::set
    std::set<std::string> values;

    for(count = 0; count < 3; count++)
    {
        cin >> key;
        cin >> value;

        auto found = map.find(key);

        if(found != map.end()) // key already in map
            continue; // don't add it again

        // now try to add it to the set
        // only add to the map if its value is not already in the set
        if(values.insert(value).second)
            map.insert(std::make_pair(key, value));
    }

    for(mpIter = map.begin(); mpIter != map.end(); ++mpIter)
        cout << " " << (*mpIter).second << endl;
}