Access to 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 is sorted inside, and I'm fine with that, I want to get the value on the map by index. I tried myMap [0] but I get an 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 understand that I can 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 is it really very inefficient? Is there a better way?

Answer 1

Your map should not be inverted in this way; it is indexed by keys not by position. The map iterator is bidirectional, like list , so the function you use is no more inefficient than accessing the list position by position. Your function can be written with std::advance( iter, index ) , starting with begin() . If you need random access by position, use vector or deque .

Answer 2

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

You can implement a random access map using a vector back-up memory, which is essentially a vector of pairs. At this point, you will of course lose all the benefits of the standard library.

Answer 3

Well, actually you can’t. The way you found it is very inefficient, has computational complexity O (n) (n worst case operations, where n is the number of elements on the map).

Access to an element in a vector or in an array has O (1) complexity for comparison (constant computational complexity, one operation).

Consider that the map is internally implemented as a red ebony (or avl tree, it depends on the implementation), and each insert, delete and search operation is O (log n) the worst case (this requires the logarithm in the operations of base 2 to find the element in the tree), which is not bad.

You can deal with using a custom class that has both a vector and a map. The insert at the end of the class will be averaged O (1), the search by name will be O (log n), the search by index will be O (1), but in this case the delete operation will be O (n).

Answer 4

To achieve your goal, there may be an implementation-specific (non-portable) method, but not portable.

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

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

You can solve your problem using both std::vector and std::map :

• Select an object from dynamic memory.
• Save the pointer with the key in std::map .
• Save the pointer to std::vector in the right place in.

std::map will allow an efficient method of accessing an object by key.
std::vector will allow an efficient method of accessing an object by index. Storing pointers allows you to use only one instance of an object, rather than supporting multiple copies.

Answer 5

You can use some other cards, such as containers.
save size fields can make the binary search tree easy for random access.
here is my implementation ...
std style, random access iterator ...
balanced tree size ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
and B + tree ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h