efficient way to get key from std::map value

Question

I have a map as below :

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

how to get key when input is value

EX :

input : 1

output : one

Note : In my case value is unique

Answer 1

A one-to-one mapping is actually quite easy, the fastest way to do it is to probably maintain two maps, one for each direction. It becomes more complicated if it's not one-to-one since you'll need to provide a way to get a collection of values or key, rather than a single one. Happily, you only have the one-to-one requirement.

One of the maps is the one you have now, the other will map the values to a given key, soboth would be:

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

and these would be maintained within a bidimap class of some sort.

Whenever you insert to, or delete from, your bidimap, you have to perform the equivalent operation on both internal maps.

For example, here's some pseudo-code. It maintains the two maps and ensures that they'e kept in sync for whatever operations you have that change the keys and values:

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]

Obviously, there's plenty of other stuff you could add but that should form the basis. In any case, you've probably got enough work ahead of you turning that into a C++ class :-)

---

If you don't want to roll your own solution, then Boost has a very good one that you can pretty well use as is. Boost.Bimap provides a fully-templated bi-directional map that you should be able to use with minimal code, such as the following complete program:

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

It creates a bi-directional mapping between the textual form of a number and the integral value, then does a few lookups (in both directions) to show that it works:

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 2

I do notice that this has the "stdmap" tag, so this may not be appropriate. However Boost has boost::bimap<> which will allow you to do what you want: it allows lookup by either key or value.

Answer 3

how to get key when input is value

1. First, there is no guarantee that value is unique. I realize that you are saying it is unique. Still, conceptually speaking, this is something to keep in mind when looking at the problem.

2. Second, std::map is not sorted by value. Hence, the most efficient algorithm to look for a value will be O(N) on an average.

Answer 4

Try boost Bimap. all the things you are trying to do can simply be done by it.

1 --> one 2 --> two ... one --> 1 two --> 2 ...

here is a link where a working example is present. here