std::lower_bound() 与 std::map::lower_bound()

Question

算法库的lower_bound 函数采用前向迭代器并返回下界。它适用于矢量，但当我将它用于地图时，出现编译器错误。我的疑问是 std::map 支持双向迭代器，它显然可以充当前向迭代器，所以为什么 std::lower_bound(map.begin(),map.end(),int value) 不起作用，但是成员函数地图类，map.lower_bound(int value) 适用于地图？这是一些示例代码供参考

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    
    vector<int>v = {1,1,1,2,3,4,2,3,2,5,6,12,12,9};
    map<int,int>mp;
    for(auto x:v)mp[x]++;
    
    for(int i=0;i<15;i++){
    
    auto it = mp.lower_bound(i); // this works
 //   auto it = lower_bound(mp.begin(),mp.end(),i) //this doesn't work
    if(it!=mp.end())
    cout<<i<<" lower bound is "<<it->first<<" and its frequency in vector is "<<it->second<<endl;
    
    
    }
    
    
    return 0;
    }

Answer 1

您需要的一切都可以在文档中找到

• std::lower_bound
• std::map::lower_bound.

std::lower_bound

期望由迭代器给出的 T 类型的 N 个值的

sorted

范围和要搜索的

T

值。

• 如果迭代器是随机访问的，它是稍微修改的二进制搜索来获得指定的下界。因此，复杂度在 N 中是对数的。
• 如果迭代器只是双向的，那么复杂度是线性的

  N

  。

std::map<Key,Value>::lower_bound

期望

Key

键来搜索并且复杂度在

N

中是对数的，因为它在红黑树上执行二进制搜索，尽管这在技术上是一个实现细节。

所以，

std::lower_bound

对你不起作用，因为地图包含

pair<const Key,Value

>，而不仅仅是

Key

，以下将起作用

auto it = lower_bound(mp.begin(),mp.end(),std::pair<const int,int>{9,1});

但是复杂度是线性的，当然如果你只想使用键搜索，它不是很有用。

std::map::lower_bound

解决了这两个问题。虽然后者可以通过自定义

Compare

函数来解决。

这种模式对所有容器和算法都是通用的，例如通用

std::find

和专门的

container::find

为每个容器 better.

请不要使用

#include<bits/stdc++.h>

.

Answer 2

成员函数存在是因为算法的函数不起作用。

map

的元素类型是

pair<const K, T>

。该算法的功能不知道如何只比较值的关键部分。