在C ++ map中，是否有一种方法可以搜索给定值的键？

Question

在C++的 std::map 中，有没有一种方法可以根据映射值搜索键？例如：

我有这个映射表：

map<int,string> myMap;
myMap[0] = "foo";

有什么方法可以找到与值为“foo”的int相对应的内容吗？

cout << myMap.some_function("foo") <<endl;

Output: 0

- nelt22

---

仅通过迭代进行。 - πάντα ῥεῖ

不是真的。再建立一个相反方向的映射，并保持两者同步。 - Ed Heal

你可能会对Boost.Bimap感兴趣。 - P0W

Answer 1

std::map没有提供一种（快速）查找给定值的键的方法。

你需要的通常被称为“双射映射”，或简称为“bimap”。Boost有这样的数据结构。这通常是通过使用两个索引树“粘”在一起实现的（其中std::map只有一个用于键）。Boost还提供了更通用的类似用例的多索引。

如果您不想使用Boost，如果存储不是一个大问题，并且如果您可以承担额外的代码工作量，您可以简单地使用两个映射并手动将它们粘合在一起：

std::map<int, string> myMapForward;
std::map<string, int> myMapBackward;    // maybe even std::set

// insertion becomes:
myMapForward.insert(std::make_pair(0, "foo"));
myMapBackward.insert(std::make_pair("foo", 0));

// forward lookup becomes:
myMapForwar[0];

// backward lookup becomes:
myMapBackward["foo"];

当然，你可以将这两个映射包装在一个类中，并提供一些有用的接口，但这可能有点过度，而且使用具有相同内容的两个映射根本不是可选方案。正如下面所评论的那样，异常安全性也是此解决方案的问题。但在许多应用程序中，只需添加另一个反向映射就足够了。

请注意，由于std::map存储唯一键，因此该方法仅支持唯一值的后向查找，因为正向映射的值空间中的碰撞对应于后向映射的键空间中的碰撞。

- leemes

---

如果您想要强大的异常安全性，那么在第二次插入失败时需要撤销第一次插入。这里的内存使用和局部性并不理想。基于此，我建议使用boost multi-index。 - Maxim Egorushkin

@MaximYegorushkin 你说得对。我的回答的后半部分只是提供了一个“快速且不完善”的解决方案，适用于那些对 Boost 过敏的程序员，这似乎相当普遍。 - leemes

@MaximYegorushkin，感谢您指出这一点。我在我的答案中添加了一个提示。 - leemes

自从我上次遇到boost厌恶已经过了好几年了。或者说我很小心地找到了一份工作，只要正确且足够快就可以做任何事情。无论如何，我发现boost多索引库是boost中最有用的库之一。 - Maxim Egorushkin

只是提一下，如果您有非唯一值，可以使用std::multimap<string,int> myMapBackward。 - nbilal

@nbilal 对的，但是查找代码会扩展为类似于“find”或“equal_range”，具体取决于要求。如果数据是双射的，那么两个“map”就可以了。 - leemes

Answer 2

不是直接的方法。

一种选择是检查地图中的每个值，直到找到您要查找的内容。显然，这将是O(n)。

为了做到这一点，您可以编写一个for()循环，或者您可以使用std::find_if()。为了使用find_if()，您需要创建一个谓词。在C++11中，这可能是一个lambda：

typedef std::map <unsigned, Student> MyMap;
MyMap myMap; 

// ...

const string targetName = "Jones";
find_if (myMap.begin(), myMap.end(), [&targetName] (const MyMap::value_type& test)
{
  if (test.second.mName == targetName)
    return true;
});

如果您正在使用C++03，那么这可能是一个函数对象：

struct MatchName
: public std::unary_function <bool, MyMap::value_type>
{
  MatchName (const std::string& target) : mTarget (target) {}
  bool operator() (const MyMap::value_type& test) const
  {
    if (test.second.mName == mTarget)
      return true;
    return false;
  }
private:
  const std::string mTarget;
};


// ...

find_if (myMap.begin(), myMap.end(), MatchName (target));

另一种选择是构建索引。该索引可能是另一个映射，其中键是您想要查找的任何值，而值是指回主映射的某种索引。

假设您的主映射包含Student对象，其中包含名称和其他一些内容，并且此映射中的键是学生ID，即整数。如果您想查找具有特定姓氏的学生，则可以构建一个索引映射，其中键是姓氏（可能要在此处使用multimap），而值是学生ID。然后，您可以索引回主映射以获取其余Student属性。

第二种方法存在挑战。在添加或删除元素时，必须使主映射和索引（或指数）同步。您必须确保选择为索引中的值的索引不是可能更改的内容，例如指针。如果您正在进行多线程操作，则必须考虑如何保护映射和索引，而不会引入死锁或竞争条件。

- John Dibling

Answer 3

您可以通过迭代来实现，这将花费O(n)时间。或者您可以存储反向映射，这将花费O(n)空间。

通过迭代：

std::map<int, string> fmap;

for (std::map<int,string>::iterator it=fmap.begin(); it!=fmap.end(); ++it)
    if (strcmp(it->second,"foo"))
        break;

通过存储反向映射：

std::map<int, string> fmap;
std::map<string, int> bmap;

fmap.insert(std::make_pair(0, "foo"));
bmap.insert(std::make_pair("foo", 0));

fmap[0]; // original map lookup

bmap["foo"]; //reverse map lookup

- HelloWorld123456789

Answer 4

我能想到的唯一实现方法是通过迭代来完成。这很可能不是你想要的，但这是我能想到的最好的尝试。祝你好运！

- Evanias

Answer 5

不行，你不能这样做。你必须遍历映射表，将每个值与要匹配的项进行比较，并返回相应的键，但这会导致高时间复杂度，即O(n)。

- user2754122