Get index of element in C++ map

Question

I have a std::map called myMap in my C++ application, and I want to get an element using either myMap.find(key) or myMap[key]. However, I would also like to get the index of that element in the map.

std::map<string, int> myMap;
// Populate myMap with a bunch of items...
myElement = myMap["myKey"];
// Now I need to get the index of myElement in myMap

Is there a clean way to do that?

Thank you.

Solution 1

A std::map doesn't really have an index, instead it has an iterator for a key / value pair. This is similar to an index in that it represents a position of sorts in the collection but it is not numeric. To get the iterator of a key / value pair use the find method

std::map<string, int>::iterator it = myMap.find("myKey");

Solution 2

I came here seeking for this answer but i found this distance function takes 2 iterators and returns an index

cout << distance(mymap.begin(),mymap.find("198765432"));

hope this helps :D

Solution 3

Most of the time when you are working with indices and maps, it usually means that your map is fixed after some insertions. If this assumption holds true for your use case, you can use my answer.

If your map is already fixed (you wouldn't add/delete any key afterward), and you want to find an index of a key, just create a new map that maps from key to index.

std::map<string, int> key2index; // you can use unordered_map for it to be faster
int i = 0;
for (pair<K, V> entry : yourMap) {
    key2index[entry.first] = i++;
}

From this key2index map you can query the key as often as you can. Just call key2index['YourKey'] to get your index.

The benefit of this method over distance function is access time complexity. It's O(1) and very fast if you do query often.

Extra Section

If you want to do the opposite, you want to access key from index then do the following.

Create an array or vector that stores keys of your entire map. Then you can access the key by specifying the index.

vector<int> keys;
for (pair<K,V> entry : yourMap) {
    keys.push_back(entry.first);
}

To access an index i of your map, use yourMap[keys[i]]. This is also O(1) and significantly faster because it's using only an array/vector, not a map.

Solution 4

Well - map is keeping the key and the data as a pair so you can extract key by dereferecing the map's iterator into pair or directly into pair's first element.

std::map<string, int> myMap;
std::map<string, int>::iterator it;

for(it=myMap.begin();it!=myMap.end();it++)
{
    std::cout<<it->first<<std::endl;
}

Solution 5

There is no such thing as an index in a map. Maps are not stored (not necessarly, at least; and indeed they are not in most implementations) as a sequence of "pairs".

Regardless of the implementation, however, std::map does not model a container having an index.

Depending on what you are asking this question for, the "index" can be an iterator (as suggested by others) or the key itself.

However, it sounds strange you asked this question. If you could give us a bit more details we would probably be able to point you to a better solution to your problem.

View more solutions