lower_bound 和 upper_bound 问题

梦里梦外; 2022-06-02 09:21 120阅读 0赞

## 写在前面 ##

今天遇到的map的问题遇到了对于lower\_bound 和upper\_bound。在这里做一个总结。

首先是在map当中 自带了成员函数用于查找：

查找
    count 
    返回匹配特定键的元素数量 
    (公开成员函数) 
    find 
    寻找带有特定键的元素 
    (公开成员函数) 
    equal_range 
    返回匹配特定键的元素范围 
    (公开成员函数) 
    lower_bound 
    返回指向首个不小于给定关键的元素的迭代器 
    (公开成员函数) 
    upper_bound 
    返回指向首个大于给定关键的元素的迭代器 
    (公开成员函数)

同时在STL算法库当中也有同名的差找算法：

二分搜索操作（在已排序范围上）
    定义于头文件 <algorithm>
    lower_bound 
    返回指向第一个不小于给定值的元素的迭代器 
    (函数模板) 
    upper_bound 
    返回指向第一个大于给定值的元素的迭代器 
    (函数模板) 
    binary_search 
    判断一个元素是否在区间内 
    (函数模板) 
    equal_range 
    返回匹配特定键值的元素区间 
    (函数模板)

函数的意思和作用大致相同但是函数的参数和具体的使用方式还是有很大的不同应该注意。

先说说map中的成员函数 参数只有一个key：

iterator lower_bound( const Key& key );
    const_iterator lower_bound( const Key& key ) const;
    //返回指向首个不小于 key 的元素的迭代器 即大于等于
    //指向首个不小于 key 的元素的迭代器。若找不到这种元素，则返回尾后迭代器end。
    //复杂度 与容器大小成对数
    
    iterator upper_bound( const Key& key );
    const_iterator upper_bound( const Key& key ) const;
    //返回指向首个大于 key 的元素的迭代器。 注意与上者的区别
    //指向首个大于 key 的元素的迭代器。若找不到这种元素，则返回尾后
    //复杂度 与容器大小成线性
    
    std::pair<iterator,iterator> equal_range( const Key& key );
    std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;
    //返回容器中所有拥有给定关键的元素范围。范围以二个迭代器定义，一个指向首个不小于 key 的元素，另一个指向首个大于 key 的元素。首个迭代器可以换用 lower_bound() 获得，而第二迭代器可换用 upper_bound() 获得。[lower_bound(),upper_bound()) key在这个左闭右开的区间
    //含一对定义所需范围的迭代器的 std::pair ：第一个指向首个不小于 key 的元素，第二个指向首个大于 key 的元素。若无元素不小于 key ，则将尾后（见 end() ）迭代器作为第一元素返回。类似地，若无元素大于 key ，则将尾后迭代器作为第二元素返回。

对于算法当中的：

template< class ForwardIt, class T >
    ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
    template< class ForwardIt, class T, class Compare >
    ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
    //返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。
    //第一版本用 operator< 比较元素，第二版本用给定的比较函数 comp 。
    
    
    template< class ForwardIt, class T >
    ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
    template< class ForwardIt, class T, class Compare >
    ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
    //返回指向范围 [first, last) 中首个大于 value 的元素的迭代器，或若找不到这种元素则返回 last 。范围 [first, last) 必须已相对于表达式 element < value 或 comp(element, value) 划分。完全排序的范围满足此判别标准。