Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Accessing map value by index

Tags:

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 (int index){     map<string, int>::const_iterator end = myMap.end();       int counter = 0;     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?

like image 261
Sam Avatar asked Oct 21 '11 23:10

Sam


People also ask

How do you find the index value of a map?

Index inside map() Function The index is used inside map() method to state the position of each element in an array, but it doesn't change the original array. Syntax: array. map(function(currentelement, index, arrayobj) { // Returns the new value instead of the item });

Do maps have indexes C++?

map's don't have an index, but an iterator.

What is the index on a map?

The index identifies quadrangle areas by map name and scale. A map is usually named after the most prominent city, town or natural landmark shown on it. Topographic map indexes are located at the first table in the Map Room (TOPO MAP INDEXES).


2 Answers

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; 
like image 144
K-ballo Avatar answered Sep 21 '22 14:09

K-ballo


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.

like image 36
Thomas Matthews Avatar answered Sep 19 '22 14:09

Thomas Matthews