如何收集同类型Map的值

Question

我们有一张映射，其键和值都是 int 类型。我们必须在映射中搜索特定值并将这些键收集到一个向量中。 代码快照就像

map<int,int>m;
map<int,int>::iterator itr;
vector<int> v;
m.insert(make_pair<int,int>(1,2));
m.insert(make_pair<int,int>(2,2));
m.insert(make_pair<int,int>(3,2));
m.insert(make_pair<int,int>(4,4));
m.insert(make_pair<int,int>(5,5));

当前代码就像：

for ( itr = m.begin(); itr != m.end(); ++itr )
{
    if ((*itr).second == 2 )
    v.push_back((*itr).first )
}

我们喜欢优化它。我们如何使用STL算法来做。

Answer 1

在我看来，你的处理方式是错误的，你可能想要一个多重地图。

std::multimap<int,int> m;
std::vector<int> v;
m.insert(std::make_pair<int,int>(2,1));
m.insert(std::make_pair<int,int>(2,2));
m.insert(std::make_pair<int,int>(2,3));
m.insert(std::make_pair<int,int>(4,4));
m.insert(std::make_pair<int,int>(5,5));

typedef std::multimap<int,int>::iterator iterator;
std::pair<iterator, iterator> bounds = m.equal_range(2);
for(iterator it = bounds.first; it != bounds.second; ++it)
   v.push_back(it->second);

Answer 2

您可以将键与值交换（=所有值都不同）吗？如果是这样，您可以使用 map.find() （时间复杂度为 O(log n)）来搜索项目。如果不是，您编写的代码就是正确的方法。

另一种方法是在地图填充值时创建向量，但这假设过滤标准在插入时已知。

Answer 3

假设你确实有很多这样的映射，那么有 boost multi_index，尽管它只是成对的整数，可能不再需要维护两个映射，后者是一个 multimap< ; int、int > 或 map< int，设置<整数> > 这将起作用

Answer 4

如果需求可以改变，即键-值可以交换，则可以使用map。 > 并通过将数据推入与键对应的向量来构建地图。这样就可以在构建地图本身时对其进行优化。

如果要求不能像OP在评论之一中所说的那样改变，那么我认为没有太大的优化空间。