获取 C++ 映射中元素的索引
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17863079/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Get index of element in C++ map
提问by SZH
I have a std::mapcalled myMapin my C++ application, and I want to get an element using either myMap.find(key)or myMap[key]. However, I would also like to get the index of that element in the map.
我在我的 C++ 应用程序中有一个std::map调用myMap，我想使用myMap.find(key)或获取一个元素myMap[key]。但是，我还想获取地图中该元素的索引。
std::map<string, int> myMap;
// Populate myMap with a bunch of items...
myElement = myMap["myKey"];
// Now I need to get the index of myElement in myMap
Is there a clean way to do that?
有没有干净的方法来做到这一点？
Thank you.
谢谢你。
采纳答案by JaredPar
A std::mapdoesn't really have an index, instead it has an iterator for a key / value pair. This is similar to an index in that it represents a position of sorts in the collection but it is not numeric. To get the iterator of a key / value pair use the findmethod
Astd::map并没有真正的索引，而是有一个用于键/值对的迭代器。这类似于索引，因为它表示集合中的排序位置，但它不是数字。要获取键/值对的迭代器，请使用该find方法
std::map<string, int>::iterator it = myMap.find("myKey");
回答by Mahmoud Aladdin
I came here seeking for this answer but i found this distance function takes 2 iterators and returns an index
我来这里寻找这个答案，但我发现这个距离函数需要 2 个迭代器并返回一个索引
cout << distance(mymap.begin(),mymap.find("198765432"));
hope this helps :D
希望这有帮助：D
回答by off99555
Most of the time when you are working with indices and maps, it usually means that your map is fixed after some insertions. If this assumption holds true for your use case, you can use my answer.
大多数情况下，当您使用索引和地图时，这通常意味着您的地图在一些插入后是固定的。如果这个假设适用于您的用例，您可以使用我的答案。
If your map is already fixed (you wouldn't add/delete any key afterward), and you want to find an index of a key, just create a new map that maps from key to index.
如果您的映射已经固定（之后您不会添加/删除任何键），并且您想找到键的索引，只需创建一个从键映射到索引的新映射。
std::map<string, int> key2index; // you can use unordered_map for it to be faster
int i = 0;
for (pair<K, V> entry : yourMap) {
key2index[entry.first] = i++;
}
From this key2indexmap you can query the key as often as you can. Just call key2index['YourKey']to get your index.
从此key2index映射中，您可以尽可能频繁地查询密钥。只需致电key2index['YourKey']以获取您的索引。
The benefit of this method over distancefunction is access time complexity. It's O(1)and very fast if you do query often.
这种方法优于distance函数的好处是访问时间复杂度。O(1)如果您经常查询，它会非常快。
Extra Section
额外部分
If you want to do the opposite, you want to access key from index then do the following.
如果你想做相反的事情，你想从索引访问密钥，然后执行以下操作。
Create an array or vector that stores keys of your entire map. Then you can access the key by specifying the index.
创建一个数组或向量来存储整个地图的键。然后您可以通过指定索引来访问密钥。
vector<int> keys;
for (pair<K,V> entry : yourMap) {
keys.push_back(entry.first);
}
To access an index iof your map, use yourMap[keys[i]]. This is also O(1)and significantly faster because it's using only an array/vector, not a map.
要访问i地图的索引，请使用yourMap[keys[i]]。这也O(1)明显更快，因为它只使用数组/向量，而不是地图。
回答by Stefano Falasca
There is no such thing as an index in a map. Maps are not stored (not necessarly, at least; and indeed they are not in most implementations) as a sequence of "pairs".
地图中没有索引这样的东西。映射不存储（至少不是必需的；实际上它们不是在大多数实现中）作为“对”序列。
Regardless of the implementation, however, std::map does not model a container having an index.
然而，无论实现如何， std::map 都不会对具有索引的容器进行建模。
Depending on what you are asking this question for, the "index" can be an iterator (as suggested by others) or the key itself.
根据您问这个问题的目的，“索引”可以是迭代器（如其他人所建议的）或键本身。
However, it sounds strange you asked this question. If you could give us a bit more details we would probably be able to point you to a better solution to your problem.
但是，你问这个问题听起来很奇怪。如果您能给我们提供更多详细信息，我们可能会为您指出更好的问题解决方案。
回答by user2614242
Well - map is keeping the key and the data as a pair so you can extract key by dereferecing the map's iterator into pair or directly into pair's first element.
好吧 - 地图将键和数据保持为一对，因此您可以通过将地图的迭代器解引用为对或直接解引用为对的第一个元素来提取键。
std::map<string, int> myMap;
std::map<string, int>::iterator it;
for(it=myMap.begin();it!=myMap.end();it++)
{
std::cout<<it->first<<std::endl;
}
回答by Sylvain Lobry
The semantic of a map does not include indexes. To understand that, you can note that Maps are typically implemented as trees. Therefore, elements in it do not have an index (try to define an index in a natural way for a tree).
地图的语义不包括索引。要理解这一点，您可以注意到 Maps 通常实现为树。因此，其中的元素没有索引（尝试以自然的方式为树定义索引）。
回答by Didar Alam
A use case: if you want to know how many items are smaller or equal as you progress on a vector. Constraint : i < = j, how many v[i]'s are smaller or equal to v[j]). let's insert it into a map or set.
一个用例：如果您想知道在向量上前进时有多少项更小或相等。约束：i < = j，有多少 v[i] 小于或等于 v[j]）。让我们将它插入到地图或集合中。
vector<int> v={1, 4, 2, 3};
set<int> s;
s = {1}; // 1's position is 1 (one based)
s = {1,4}; //4's positon is 2
s = {1, 2, 4} ;//2's position is 2
s = {1 , 2, 3, 4}; //3's positon is 3
it seems std:distance would need a O(n) time. I could achieve same affect using set.lower_bound() and counting backward till set.begin(). Does anyone have a better solution than requiring O(n) , perhaps using additional data structures?
似乎 std:distance 需要 O(n) 时间。我可以使用 set.lower_bound() 并倒数直到 set.begin() 来达到同样的效果。有没有人有比要求 O(n) 更好的解决方案，也许使用额外的数据结构？
OK, on a second thought here is a solution to store index (1 based) for this specific problem. However it may not solve the problem for get the correct index of items in the finished map.
好的，再想一想，这里是针对此特定问题存储索引（基于 1）的解决方案。然而，它可能无法解决在完成的地图中获取正确项目索引的问题。
vector<int> arr={1 , 1 , 2, 4, 2};
multimap<int, int> track;
for(auto a:arr)
{
auto it = track.insert(make_pair(a, 1)); //first item is 1
if(it!=track.begin())
{
--it;
int prev=it->second;
it++;
it->second+=prev;
}
cout<<a<<','<<it->second-1<<endl;
}
回答by soul_departed
Map is a key-value data structure which internally data in a tree structure. There are O(n) solution stated above. " distance(mymap.begin(),mymap.find("198765432")) " will not bring you the correct answer. For your requirement, you have to build your own segment tree type data structure for O log(n) competitive operations.
Map 是一种键值数据结构，内部数据以树形结构表示。上面有 O(n) 个解决方案。“ distance(mymap.begin(),mymap.find("198765432")) ”不会给你带来正确的答案。根据您的要求，您必须为 O log(n) 竞争操作构建自己的段树类型数据结构。
