如何从特定位置开始搜索地图/多图

Question

我想搜索地图/多图，但不是全部。相反，我想从一个特定的位置开始。

在下面的例子中，我想找到总和b的两个第一个数字。并返回他们的价值。

multimap<int, int> a;
a.insert(make_pair(2, 0));
a.insert(make_pair(2, 1));
a.insert(make_pair(5, 2));
a.insert(make_pair(8, 3));

int b = 4;

for(auto it = a.begin(); it != a.end(); ++it) {
    auto it2 = a.find(b - it->first); //Is there an equivalent that starts from "it+1"?
    if(it2 != a.end()) {
        cout << it->second << ", " << it2->second << endl;
        break;
    }
}

输出：

0, 0

期望的输出：

0, 1

是否有可能在地图中实现特定的位置搜索？

Answer 1

如何从特定位置开始搜索地图

你可以使用std::find。但这并不理想，因为与地图查找的对数复杂度相比，它具有线性复杂性。 std::map的接口不支持查找操作。

如果需要此类操作，则需要使用其他数据结构。应该可以通过用父节点指针扩充（平衡）搜索树来实现。缺点当然是增加内存使用和修改树结构的操作的不断开销。

不是从开始到结束。

地图查找不会从范围的“开头”开始。它们从树的根开始。

Answer 2

如果你使用的是有序地图（它听起来像你），那么它已经使用std::find进行二进制搜索。此函数返回迭代器类型，因此假设您正在查找某个键x的值，请考虑以下行：

std::map<char,int> mymap;
mymap['x'] = 24;
std::map<char,int>::iterator itr = mymap.find('x');
std::cout << "x=" << itr->second << std::endl;

你的代码没有编译的原因可能是因为你试图返回一个对迭代器，它不会完全打印输出那么好。相反，调用itr->second可以检索与所需键关联的值。