如何从特定位置开始在 map/multimap 中搜索

Question

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

在下面的示例中，我想找到总和为 b 的前两个数字。并且 return 他们的价值。

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

How to search in a map starting from specific position

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

如果你需要这样的操作，那么你需要使用另一种数据结构。应该可以通过使用父节点指针扩充（平衡）搜索树来实现。缺点当然是增加了内存使用和修改树结构的操作的持续开销。

not from the beginning to the end.

地图查找不从范围的 "the beginning" 开始。他们从树的根部开始。

Answer 2

如果您使用的是有序映射（听起来您就是这样），那么它已经使用 std::find 进行了二进制搜索。此函数 return 是一种迭代器类型，因此假设您正在寻找某个键 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;

您的代码未编译的原因可能是因为您尝试 return 一对迭代器，它不会完全打印输出那么好。相反，调用 itr->second 允许您检索与所需键关联的值。

如何从特定位置开始在 map/multimap 中搜索

How to search in a map/multimap starting from specific position

c++

search

dictionary

stl

binary-search