从 std::map 值中获取键的有效方法

Question

我有一张地图如下：

std::map< std::string ,int> mapobj;
mapobj["one"] = 1;
mapobj["two"] = 2;
mapobj["three"] =3 ;

当输入为值时如何获取键

EX :

输入：1

输出：一个

注意：在我的例子中，值是唯一的

Answer 1

how to get key when input is value

首先，不能保证值是唯一的。我知道你说它是独一无二的。尽管如此，从概念上讲，这是在查看问题时要记住的事情。
其次，std::map没有按值排序。因此，查找值的最有效算法平均为 O(N)。

Answer 2

一对一映射实际上很容易，最快的方法可能是维护两个映射，每个方向一个。如果它不是一对一的，它会变得更加复杂，因为您需要提供一种方法来获取值或键的集合，而不是单个值或键。幸运的是，您只有一对一的要求。

其中一个映射是您现在拥有的映射，另一个映射会将值映射到给定的键，所以两者都是：

std::map<std::string, int> forwardmapobj;
std::map<int, std::string> reversemapobj;

并且这些将在某种 bidimap class 中维护。

无论何时向 bidimap 插入或删除 bidimap，都必须对两个内部映射执行等效操作。

例如，这里有一些伪代码。它维护两个映射并确保它们在您更改键和值的任何操作中保持同步：

class biDiMap:
    map<string, int> forwardMap
    map<int, string> reverseMap

    void add(string key, int val):
        if exists forwardMap[key]: throw exception 'duplicate key'
        if exists reverseMap[val]: throw exception 'duplicate value'
        forwardMapObj[key] = val
        reverseMapObj[val] = key

    void delKey(string key):
        if not exists forwardMap[key]: throw exception 'no such key'
        delete reverseMap[forwardMap[key]]
        delete forwardMap[key]

    void delVal(int val):
        if not exists reverseMap[val]: throw exception 'no such value'
        delete forwardMap[reverseMap[val]]
        delete reverseMap[val]

    int getValFor(string key): return forwardMap[key]

    string getKeyFor(int val): return reverseMap[val]

显然，您可以添加很多 other 内容，但这应该构成基础。无论如何，在将其转换为 C++ class :-)

之前，您可能已经足够工作了

如果您不想推出自己的解决方案，那么 Boost 有一个非常好的解决方案，您可以按原样使用。 Boost.Bimap 提供了一个完全模板化的双向地图，您应该可以用最少的代码使用它，例如下面的完整程序：

#include <iostream>
#include <string>
#include <boost/bimap.hpp>

using std::string;
using std::cout;
using std::exception;
using boost::bimap;

int main()
{
    typedef bimap<string, int> SiMap;
    typedef SiMap::value_type SiEntry;

    SiMap bidi;
    bidi.insert(SiEntry("ninety-nine", 99));
    int i = 0;
    for (string str: {"one", "two" , "three", "four", "five", "six"}) {
        bidi.insert(SiEntry(str, ++i));
    }

    cout << "The number of entries is " << bidi.size() << "\n\n";

    for (auto i = 1; i <= 7; i += 3) {
        try {
            cout << "Text for number " << i << " is " << bidi.right.at(i) << "\n";
        } catch (exception &e) {
            cout << "Got exception looking up number " << i << ": " << e.what() << "\n";
        }
    }
    cout << "\n";

    for (auto str: {"five", "ninety-nine", "zero"}) {
        try {
            cout << "Number for text '" << str << "' is " << bidi.left.at(str) << "\n";
        } catch (exception &e) {
            cout << "Got exception looking up text '" << str << "': " << e.what() << "\n";
        }
    }
    cout << "\n";

    return 0;
}

它在数字的文本形式和整数值之间创建双向映射，然后进行一些查找（在两个方向上）以表明它有效：

The number of entries is 7

Text for number 1 is one
Text for number 4 is four
Got exception looking up number 7: bimap<>: invalid key

Number for text 'five' is 5
Number for text 'ninety-nine' is 99
Got exception looking up text 'zero': bimap<>: invalid key

Answer 3

我确实注意到它有 "stdmap" 标签，所以这可能不合适。但是 Boost 有 boost::bimap<> 可以让你做你想做的事：它允许通过键或值进行查找。

Answer 4

尝试提升 Bimap。您尝试做的所有事情都可以简单地由它完成。

1 --> 一个 2 --> 两个 ... 一 --> 1 两个 --> 2 ...

这里有一个 link，其中有一个工作示例。 here

从 std::map 值中获取键的有效方法

efficient way to get key from std::map value

c++

performance

stdmap