30

我在我的 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

有没有一种干净的方法可以做到这一点？

谢谢你。

4

9 回答 9

80

我来这里是为了寻找这个答案，但我发现这个距离函数需要 2 个迭代器并返回一个索引

cout << distance(mymap.begin(),mymap.find("198765432"));

希望这会有所帮助：D

于 2014-08-09T18:26:10.247 回答
8

Astd::map并没有真正的索引，而是有一个键/值对的迭代器。这类似于索引，因为它表示集合中的排序位置，但它不是数字。要获取键/值对的迭代器，请使用该find方法

std::map<string, int>::iterator it = myMap.find("myKey");
于 2013-07-25T16:01:50.027 回答
8

大多数时候，当您使用索引和地图时，这通常意味着您的地图在一些插入后是固定的。如果这个假设适用于您的用例，您可以使用我的答案。

如果您的映射已经固定（之后您不会添加/删除任何键），并且您想要查找键的索引，只需创建一个从键映射到索引的新映射。

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++;
}

从此key2index地图中，您可以尽可能多地查询密钥。只需致电key2index['YourKey']获取您的索引。

这种方法相对于distance函数的好处是访问时间复杂度。O(1)如果您经常查询，它会非常快。

额外部分

如果你想做相反的事情，你想从索引中访问键，然后执行以下操作。

创建一个数组或向量来存储整个地图的键。然后您可以通过指定索引来访问密钥。

vector<int> keys;
for (pair<K,V> entry : yourMap) {
    keys.push_back(entry.first);
}

要访问地图的索引i，请使用yourMap[keys[i]]. 这也O(1)明显更快，因为它只使用数组/向量，而不是地图。

于 2016-02-14T07:28:01.900 回答
2

好吧 - map 将键和数据保持为一对，因此您可以通过将映射的迭代器解引用到对或直接到对的第一个元素中来提取键。

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;
}
于 2014-04-09T11:30:20.727 回答
1

地图中没有索引之类的东西。地图不被存储（至少不是必需的；实际上它们不是在大多数实现中）作为“对”的序列。

然而，无论实现如何，std::map 都不会对具有索引的容器进行建模。

根据您要问这个问题的内容，“索引”可以是迭代器（如其他人所建议的那样）或键本身。

但是，你问这个问题听起来很奇怪。如果您能给我们提供更多详细信息，我们可能会为您指出解决问题的更好方法。

于 2013-07-25T16:01:47.707 回答
1

采用

int k = distance(mymap.begin(), mymap.find(mykey));

它将为您提供关键元素的索引。

于 2021-09-02T10:30:11.720 回答
0

地图的语义不包括索引。要理解这一点，您可以注意到地图通常以树的形式实现。因此，其中的元素没有索引（尝试以自然的方式为树定义索引）。

于 2013-07-25T16:03:54.230 回答
0

Map 是一种键值对数据结构，其内部数据以树结构的形式存在。有上面提到的 O(n) 解决方案。“ distance(mymap.begin(),mymap.find("198765432")) ”不会给你带来正确的答案。根据您的要求，您必须为 O log(n) 竞争操作构建自己的分段树类型数据结构。

于 2014-11-12T05:02:16.697 回答
0

一个用例：如果您想知道在向量上前进时有多少项目更小或相等。约束：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

似乎 std:distance 需要 O(n) 时间。我可以使用 set.lower_bound() 并向后计数直到 set.begin() 来实现相同的效果。有没有人有比要求 O(n) 更好的解决方案，也许使用额外的数据结构？

好的，再想一想，这里是针对这个特定问题存储索引（基于 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;     
}
于 2020-04-19T17:00:30.377 回答