C++ 通过索引访问地图值

Accessing map value by index

提问by Sam

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]?

如何访问 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:

我知道地图在内部进行排序，我对此很好，我想通过索引在地图中获得一个值。我试过 myMap[0] 但我收到错误：

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?

但这肯定是非常低效的吗？有没有更好的办法？

回答by K-ballo

Your mapis not supposed to be accessed that way, it's indexed by keys not by positions. A mapiterator is bidirectional, just like a list, so the function you are using is no more inefficient than accessing a listby position. Your function could be written with help from std::advance( iter, index )starting from begin(). If you want random access by position then use a vectoror a deque.

您map不应该以这种方式访问​​，它是由键而不是位置索引的。一个map迭代器是双向的，就像一个list，所以你正在使用的功能并不比访问效率较低list的位置。您的函数可以std::advance( iter, index )从begin(). 如果您想按位置随机访问，请使用 avector或 a deque。

回答by Thomas Matthews

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

可能有一种特定于实现的（不可移植的）方法来实现您的目标，但不是可移植的。

In general, the std::mapis 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?

一般来说，std::map被实现为一种二叉树，通常按键排序。第一个元素的定义因排序而异。另外，在您的定义中， element[0] 是树顶部的节点还是最左侧的叶节点？

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.

许多二叉树被实现为链表。大多数链表不能像数组一样直接访问，因为要找到元素 5，您必须遵循链接。这是根据定义。

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

您可以同时使用 astd::vector和 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::vectorat the position you want it at.

1. 从动态内存分配对象。
2. 将指针和密钥一起存储到std::map.
3. 将指针存储在std::vector您想要的位置。

The std::mapwill allow an efficient method to access the object by key.
The std::vectorwill 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.

这std::map将允许一种有效的方法来通过键访问对象。
这std::vector将允许一种有效的方法通过索引访问对象。存储指针只允许对象的一个​​实例，而不必维护多个副本。

回答by Salvatore Previti

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).

嗯，实际上你不能。您发现的方法非常低效，它的计算复杂度为 O(n)（n 次操作最坏的情况，其中 n 是映射中的元素数）。

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

通过比较（恒定计算复杂度，单个操作），访问向量或数组中的项目的复杂度为 O(1)。

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.

考虑到 map 在内部实现为红黑树（或 avl 树，这取决于实现）并且每个插入、删除和查找操作都是 O(log n) 最坏情况（它需要以 2 为底的操作中的对数才能找到元素在树中），这很好。

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).

您可以处理的一种方法是使用同时包含矢量和地图的自定义类。在类的末尾插入将平均 O(1)，按名称查找将是 O(log n)，按索引查找将是 O(1) 但在这种情况下，删除操作将是 O(n)。

回答by Michael Price

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

以前的答案（见评论）：怎么样只是 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.

您可以使用向量后备存储来实现随机访问映射，它本质上是一个成对向量。您当然会在那时失去标准库映射的所有好处。

回答by u5449098

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

您可以使用其他一些地图，如容器。
保持一个大小字段可以使二叉搜索树易于随机访问。
这是我的实现......
std 风格，随机访问迭代器......
大小平衡树......
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
和 B+tree ...
https： //github.com/mm304321141/zzz_lib/blob/master/bpptree.h

回答by Jorge Bellon

std::mapis 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::map是一个有序容器，但它的迭代器不支持随机访问，而是双向访问。因此，您只能通过导航其所有先前元素来访问第 n 个元素。您示例的一个较短的替代方法是使用标准迭代器库：

 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_mapprovides a member function nthwhich allows you exactly what you are looking for.

另一种方法是使用支持随机访问的有序容器。例如，boost::container::flat_map提供了一个成员函数nth，它可以让你准确地寻找你正在寻找的东西。