通过索引

访问映射值如果我有一个像通过索引

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 = 0; 
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) { 
     counter++; 

     if (counter == index) 
      return it->first; 
    } 
}

但可以肯定，这是效率非常低？有没有更好的办法？

来源

2011-10-21 Sam

你的map不应该被这样访问，它的索引不是按位置键。一个map迭代器是双向的，就像list一样，所以您使用的函数不会比按位置访问list低效。你的功能可以从std::advance(iter, index)帮助编写，从begin()开始。如果您想按位置随机访问，请使用vector或deque。

来源

2011-10-21 23:54:18

呃，实际上你不行。您发现的方式效率很低，它的计算复杂度为O（n）（n操作最坏的情况，其中n是地图中元素的数量）。

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

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

你可以处理的一种方法是使用一个自定义类，它既包含向量又包含地图。在类末尾的插入将平均为O（1），按名称查找将为O（log n），按索引查找将为O（1），但在这种情况下，删除操作将为O（n）。

来源

2011-10-21 23:54:53

以前的答案（见注释）：如何只myMap.begin();

您可以通过使用矢量后备存储，这基本上是对的载体实现随机存取地图。当然，你当然会失去标准库地图的所有好处。

来源

2011-10-21 23:56:13

我现在看到的...你想随机访问。索引0只是一个例子，而不是实际的目标。 –

可能有一个实现特定的（非便携式）方法来实现您的目标，但不是一个便携式的。

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

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

您可以同时使用std::vector和std::map解决您的问题：

从动态内存分配的对象。
将指针和钥匙一起存储到std::map中。
将指针存储在std::vector的所需位置处。

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

来源

2011-10-22 00:26:11

然后当你需要在地图中插入一个新的元素时，你如何处理矢量？ – HighCommander4

一个有趣的替代方法是除地图之外还将迭代器矢量存储到您的地图中。这样，您就可以通过索引访问地图中每个元素的键和值，而无需再次存储它们中的任何一个。当然，你仍然需要保持矢量与地图同步 - 在插入时附加迭代器，删除前删除迭代器（O（N））。 – namey

你可以使用一些其他的地图像容器。
保留大小字段可以使二叉查找树容易随机存取。
这里是我的执行...
STD风格，随机访问迭代器......
大小平衡树...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
和B +树...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

来源

2015-10-15 10:16:12

欢迎来到SO！尽量避免仅链接的答案，因为链接将来可能会被破解，只需在答案中包含该链接的一些片段，即可保留该链接，但请您在答案中包含更多内容，并尝试解释为什么您认为它是一个好主意。 –

回答

相关问题