Accessing map value by index

Question

If I have a structure like

std::map<string, int> myMap;
myMap["banana"] = 1;
myMap["apple"] = 1;
myMap["orange"] = 1;

How can I access myMap[0]?

I know that the map sorts internally and I'm fine with this, I want to get a value in the map by index. I've tried myMap[0] but I get the error:

Error   1   error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion)   

I realise I could do something like this:

string getKeyAtIndex (map<string, int>& myMap, int index){
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = -1;
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) {
        counter++;
        
        if (counter == index)
            return it->first;
    }
}

But surely this is hugely inefficient? Is there a better way?

Formerly

Answer 1

Your map is not supposed to be accessed that way, it's indexed by keys not by positions. A map iterator is bidirectional, just like a list, so the function you are using is no more inefficient than accessing a list by position. If you want random access by position then use a vector or a deque.

Your function could be written with help from std::advance(iter, index) starting from begin():

auto it = myMap.begin();
std::advance(it, index);
return it->first;

Carefree

What if I used map<int, int, greater<int>> m; And I want to get the second largest element of the map after doing so? If I can access by index that would be very convenient, otherwise I have to put it in a for loop. – Broker

Answer 2

There may be an implementation specific (non-portable) method to achieve your goal, but not one that is portable.

In general, the std::map is implemented as a type of binary tree, usually sorted by key. The definition of the first element differs depending on the ordering. Also, in your definition, is element[0] the node at the top of the tree or the left-most leaf node?

Many binary trees are implemented as linked lists. Most linked lists cannot be directly accessed like an array, because to find element 5, you have to follow the links. This is by definition.

You can resolve your issue by using both a std::vector and a std::map:

1. Allocate the object from dynamic memory.
2. Store the pointer, along with the key, into the std::map.
3. Store the pointer in the std::vector at the position you want it at.

The std::map will allow an efficient method to access the object by key.
The std::vector will allow an efficient method to access the object by index. Storing pointers allows for only one instance of the object instead of having to maintain multiple copies.

Electrophoresis

And then what do you do with the vector when you need to insert a new element into the map? – Cadmus

An interesting alternative is to store a vector of iterators to your map in addition to the map. That way, you can access both the key and the value of each element of your map by index without storing either of them again. Of course, you'd still need to keep the vector synchronized to the map - append iterator on insertion, remove iterator (O(N)) before deletion. – Cannelloni

Answer 3

Well, actually you can't. The way you found is very unefficient, it have a computational complexity of O(n) (n operations worst case, where n is the number of elements in a map).

Accessing an item in a vector or in an array have complexity O(1) by comparison (constant computational complexity, a single operation).

Consider that map is internally implemented as a red black tree (or avl tree, it depends on the implementation) and every insert, delete and lookup operation are O(log n) worst case (it requires logarithm in base 2 operations to find an element in the tree), that is quite good.

A way you can deal with is to use a custom class that have inside both a vector and a map. Insertion at the end of the class will be averaged O(1), lookup by name will be O(log n), lookup by index will be O(1) but in this case, removal operation will be O(n).

Lundell

Answer 4

Previous answer (see comment): How about just myMap.begin();

You could implement a random-access map by using a vector backing-store, which is essentially a vector of pairs. You of course lose all the benefits of the standard library map at that point.

Seraphine

I see now... You want random access. Index 0 was just an example, not the actual goal. – Seraphine

Answer 5

std::map is an ordered container, but it's iterators don't support random access, but rather bidirectional access. Therefore, you can only access the nth element by navigating all its prior elements. A shorter alternative to your example is using the standard iterator library:

 std::pair<const std::string, int> &nth_element = *std::next(myMap.begin(), N);

This has linear complexity, which is not ideal if you plan to frequently access this way in large maps.

An alternative is to use an ordered container that supports random access. For example, boost::container::flat_map provides a member function nth which allows you exactly what you are looking for. Edit: this type of container is now available in the C++ standard library starting with C++23, as std::flat_map.

Letterpress

Answer 6

you can use some other map like containers .
keep a size fields can make binary search tree easy to random access .
here is my implementation ...
std style , random access iterator ...
size balanced tree ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
and B+tree ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

Rothschild

Welcome to SO! Try to avoid link only answers because the link can be broken in future, just include some snippets of that link in your answer, you can maintain the link, but please, include something more on your answer, and try to explain why you think it's a good idea. – Reneerenegade

Answer 7

std::map<string,int>::iterator it = mymap.begin() + index;

Approval

Hi, and welcome to Stack Overflow! Could you maybe edit your answer to include an explanation of how/why it works, and/or why it improves on the existing answers that have already been there for a while? – Porterporterage

Answer 8

Another approach worth considering would be writing a template function for all possible maps:

template<typename K, typename V> V getValueAtIndex(map<K, V> &mapRef, int index) {
    for (const auto& entry : mapRef) {
        if (index == 0) {
            return entry.second;
        }
        index--;
    }   

    V defaultValue;
    return defaultValue;
}

I assumed here that you know that value is in map. The defaultValue there is basically to prevent compiler warning. Function could be modified to take some actual default value and return it in case index is negative or bigger than map size but I don't think it's useful in this case.

Here is some example usage of above function:

map<string, int> fruitsCount;
fruitsCount["apple"] = 5;  // index 0
fruitsCount["banana"] = 3; // index 1
fruitsCount["cherry"] = 7; // index 2

auto middleValue = getValueAtIndex(fruitsCount, 1); // check index 1
cout << "middleValue: " << middleValue << endl; // prints middleValue: 3

Of course you need to remember that map is sorted by key, so if I would change the order of fruitsCount initialization the result would still be the same.

Sudor