通过索引访问地图值

Question

如果我有这样的结构

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

如何访问 myMap[0]？

我知道地图在内部进行排序，我对此很满意，我想通过索引获取地图中的值。我尝试过 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)   

我意识到我可以做这样的事情：

string getKeyAtIndex (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;
    }
}

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

Answer 1

您的

map

不应该以这种方式访问，它是按键而不是按位置进行索引的。

map

迭代器是双向的，就像

list

一样，因此您使用的函数并不比按位置访问

list

低效。如果您想按位置随机访问，请使用

vector

或

deque

。

您的函数可以在

std::advance(iter, index)

的帮助下编写，从

begin()

开始：

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

Answer 2

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

一般来说，

std::map

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

许多二叉树都是作为链表实现的。大多数链表无法像数组一样直接访问，因为要找到元素 5，您必须沿着链接进行操作。这是根据定义。

您可以同时使用

std::vector

和

std::map

来解决您的问题：

1. 从动态内存中分配对象。
2. 将指针和钥匙一起存放到

   std::map

   中。
3. 将指针存储在

   std::vector

   中您想要的位置 在。

std::map

将允许一种有效的方法通过键访问对象。

std::vector

将允许一种有效的方法通过索引访问对象。 存储指针仅允许对象的一个实例，而不必维护多个副本。

Answer 3

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

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

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

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

Answer 4

之前的回答（见评论）：

myMap.begin();

怎么样？

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

Answer 5

std::map

是一个有序容器，但它的迭代器不支持随机访问，而是支持双向访问。因此，您只能通过导航第 n 个元素的所有先前元素来访问它。您的示例的更短替代方案是使用标准迭代器库：

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

这具有线性复杂度，如果您计划在大型地图中频繁访问这种方式，这并不理想。

另一种方法是使用支持随机访问的有序容器。例如，

boost::container::flat_map

提供了一个成员函数

nth

，它可以让你准确地找到你想要的东西。

Answer 6

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

Answer 7

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