时间戳

首页 > 解决方案 > 是否可以通过 std::upper_bound 对 std::map 进行有效和部分搜索？

c++ - 是否可以通过 std::upper_bound 对 std::map 进行有效和部分搜索？

问题描述

我有一个std::map和两个键key_small, key_big来计算upper_bound. 据了解key_small <= key_big。这是我目前的做法：

#include <map>
#include <algorithm>

int main() {
  // Some example data
  std::map<int, char> data{{1, 'a'}, {2, 'b'}, {4, 'c'}, {5, 'd'}, {5, 'e'}};
  int key_small = 1,
      key_big = 3; // key_small <= key_big is always true

  auto it_1 = data.upper_bound(key_big);
  auto it_2 = data.upper_bound(key_small);

  // Do something with it_1, then do something with it_2
}

我想以it_1更it_2有效的方式进行计算。上面的计算it_2没有利用我已经计算过的事实it_1。它第二次搜索整个map。我试图解决这个问题是执行以下操作：

auto it_2 = (it_1 == data.end())
                    ? data.upper_bound(key_small)
                    : std::upper_bound(data.begin(), std::next(it_1), key_small);

第二个调用似乎忽略了底层数据结构。因此，它也是低效的。

有没有更好的计算方法it_2？在我看来，使用log(std::distance(data.begin(), it_1)比较应该可以找到第二个迭代器。我被告知这是可能的工作面试。

我不在乎该解决方案是否仅在 c++20 中可用。我也接受特定于 libstdc++ 或 libc++ 的解决方案。如果该解决方案也适用，那就太好了find。

标签： c++dictionaryfindstd

解决方案

是否可以通过 std::upper_bound 对 std::map 进行有效和部分搜索？

尽管std::upper_bound可以与非随机访问迭代器一起使用，但它与这些迭代器具有线性复杂性。所以，是的，可以这样做，但是这种线性搜索是否有效取决于特定情况，在最坏的情况下，它会比两次std::map::upper_bound查找慢。

如果distance(it_1, it_2) < log2(N)，那么它可能更有效。

有没有办法从计算 it_2 的两种方式中获益？

该接口不提供这样的算法。我不认为任何算法的最坏情况都比这两个查找要好。

推荐阅读