通過索引

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 = 0; 
    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低效。你的功能可以從std::advance(iter, index)幫助編寫，從begin()開始。如果您想按位置隨機訪問，請使用vector或deque。

Answer 2

呃，實際上你不行。您發現的方式效率很低，它的計算複雜度爲O（n）（n操作最壞的情況，其中n是地圖中元素的數量）。

通過比較（恆定的計算複雜度，單個操作）來訪問向量或數組中的項目具有複雜度O（1）。

考慮到map在內部是作爲紅黑樹（或avl樹，它取決於實現）實現的，每個插入，刪除和查找操作都是O（log n）最差的情況（它需要以2爲底的操作對數在樹中找到一個元素），這是相當不錯的。

你可以處理的一種方法是使用一個自定義類，它既包含向量又包含地圖。 在類末尾的插入將平均爲O（1），按名稱查找將爲O（log n），按索引查找將爲O（1），但在這種情況下，刪除操作將爲O（n）。

Answer 3

以前的答案（見註釋）：如何只myMap.begin();

您可以通過使用矢量後備存儲，這基本上是對的載體實現隨機存取地圖。當然，你當然會失去標準庫地圖的所有好處。

Answer 4

可能有一個實現特定的（非便攜式）方法來實現您的目標，但不是一個便攜式的。

通常，std::map被實現爲一種二叉樹，通常按鍵排序。第一個元素的定義因順序而異。另外，在您的定義中，元素[0]是樹頂部的節點還是最左邊的葉節點？

很多二叉樹被實現爲鏈表。大多數鏈接列表不能像數組那樣直接訪問，因爲要查找元素5，必須遵循鏈接。這是根據定義。

您可以同時使用std::vector和std::map解決您的問題：

1. 從動態內存分配的對象。
2. 將指針和鑰匙一起存儲到std::map中。
3. 將指針存儲在std::vector的所需位置 處。

std::map將允許一個有效的方法通過鍵訪問對象。
std::vector將允許有效的方法通過索引訪問對象。 存儲指針只允許對象的一個​​實例，而不必維護多個副本。

Answer 5

你可以使用一些其他的地圖像容器。
保留大小字段可以使二叉查找樹容易隨機存取。
這裏是我的執行...
STD風格，隨機訪問迭代器......
大小平衡樹...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
和B +樹...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h