在 std::map 中搜索限制搜索值的键

Question

假设我有 std::map<std::pair<int, int>, int>，映射中的键是一对两个整数值。

是否可以找到一个键来限制我正在寻找的值？

例如：如果地图包含：

key = {4, 9}

我可以根据x大于4且x小于9找到这个key吗？其中 x 是一些整数值。

我希望它有意义。

Answer 1

可以使用std::find_if算法。查看 this example on ideone

#include <algorithm>
#include <iostream>
#include <map>
#include <tuple>

int main() {
  std::map<std::pair<int, int>, int> m { { {1,3}, 4 }, { {6, 10}, 5 }, { {123, 126}, 111 } };
  int x = 8;

  auto result = std::find_if(std::begin(m), std::end(m), [x](const auto& v) {
      return v.first.first < x && x < v.first.second;
  });

  if(result != std::end(m)) {
      std::cout << "FOUND x " << result->second;
  }

  return 0;
}

Map可以看作是vector对，可以在算法库的函数中使用。 Find_if returns 元素的迭代器，如果它匹配谓词（签名 bool pred(const Type &a);）。在您的情况下，Type 是 std::pair<std::pair<int,int>, int>。

Answer 2

一个 std::map has a find() 函数，只查找完全匹配，因为键被视为单个值（即使由多个元素组成，如您的地图）。

然而，对于您的问题，有两种候选解决方案，具体取决于您要实现的目标：

1) 使用equal_range()

equal_range() 将为您提供由两个迭代器定义的范围。第一个指向一个不小于key的元素，第二个指向第一个大于key的元素。

因此，如果您要查找与确切键相关的边界，它可能就是您要查找的内容：

auto r2 = m.equal_range ({1,2});
if (r2.first!=m.end()) {
    std::cout<<"Found range1 -> "<< r2.first->second << std::endl;
}
if (r2.second!=m.end()) {
    std::cout<<"Found range2 -> "<< r2.second->second << std::endl;
}
//attention the r2.first==r2.second if exact value not found.

如果您仅使用该对的第一个组件来查找边界，它不会为您提供部分搜索。但是你可以用它来搜索对 (x, 0)；这将比遍历整个地图更有效。

auto r3 = m.equal_range ({x,0});
for (auto r=r3.first; r!=m.end() && r->first.first==x; r++) {
    std::cout<<"In range -> "<< r->second << std::endl;
}
std::cout<<"That's all I found for <<x<<std::endl;

这里是online demo.

2) 使用地图中的地图

如果您的问题与部分键有关，您只知道第一个元素，那么使用 std::map<int, std::map<int, int>>.

可能更容易

然后将简化对部分键的搜索：

auto r3 = m.find (x);   // look for first component
if (r3==m.end()) 
    std::cout<<"r3 not found"<<std::endl; 
else for (auto r : r3->second) {  // iterate on second component
    std::cout<<"In range -> "<< r.second << std::endl;
}

然而，这种简单性是以搜索完整密钥的更高成本为代价的，因为您需要首先查找第一个组件，然后再查找第二个。

Demo code

Answer 3

如果间隔不重叠，你可以这样做by using a slightly different map, utilising a transparent comparator:

std::map<std::pair<int, int>, int, std::less<>> themap;

好消息是现在比较是透明的，所以我们可以设计自己的类型来为我们做正确的事情：

struct target
{
    int value;
};
constexpr bool operator<(target a, std::pair<int, int> b) noexcept {
    return a.value <= b.first;
}
constexpr bool operator<(std::pair<int, int> a, target b) noexcept {
    return a.second <= b.value;
}

themap.find(target{value});

在 std::map 中搜索限制搜索值的键

Search in std::map for key that bounds the search value

c++

stdmap

1) 使用equal_range()

2) 使用地图中的地图