// <algorithm> 
// 默认(1)    
template <class ForwardIterator, class T>
    pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first,
        ForwardIterator last, const T& val);
// 自定义(2)    
template <class ForwardIterator, class T, class Compare>
    pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first,
        ForwardIterator last,
        const T& val,Compare comp);

二分法查找,返回范围中值等于给定值的元素组成的子范围。

该函数等价于:

template<class _FwdIt,
class _Ty,
class _Diff,
class _Pr> inline
pair<_FwdIt, _FwdIt>
    _Equal_range(_FwdIt _First, _FwdIt _Last,
        const _Ty& _Val, _Pr _Pred, _Diff *)
{    // find range equivalent to _Val, using _Pred
    _Diff _Count = 0;
    _Distance(_First, _Last, _Count);

    while (0 < _Count)
    {    // divide and conquer, check midpoint
        _Diff _Count2 = _Count / 2;
        _FwdIt _Mid = _First;
        _STD advance(_Mid, _Count2);

        if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
        {    // range begins above _Mid, loop
            _First = ++_Mid;
            _Count -= _Count2 + 1;
        }
        else if (_Pred(_Val, *_Mid))
            _Count = _Count2;    // range in first half, loop
        else
        {    // range straddles _Mid, find each end and return
            _FwdIt _First2 = _STD lower_bound(_First, _Mid, _Val, _Pred);
            _STD advance(_First, _Count);
            _FwdIt _Last2 = _STD upper_bound(++_Mid, _First, _Val, _Pred);
            return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
        }
    }

    return (pair<_FwdIt, _FwdIt>(_First, _First));    // empty range
}
  • firstlast

    分别指向序列中初始及末尾位置的正向迭代器(Forward Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    val

    用于查找的值,最后找到的子范围中所有元素等于该值。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 返回一个 std::pair 对象,其 firstsecond 成员都为迭代器,且分别指向输入序列中所有值等于 val 的元素所组成的子序列的起始及末尾(End,即最后一个元素之后的位置)位置。

    first 成员的值等同于 std::lower_bound 执行于同一输入序列后的返回。

    second 成员的值等同于 std::upper_bound 执行于同一输入序列后的返回。

  • 如果希望获得与自定义函数谓词、函数对象谓词、排序对象数组、lambda C++11 表达式、初始化列表 std::initializer_list 等相关的例子,请同时参照 std::sort

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
    
        void EqualRange_1() {
            // 构造一个 vector 对象
            CLASSFOO_VECTOR(int, foo, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
            // 调用 equal_range 前必须已经排过序,至少按指定元素划分过(Partitioned)
            std::sort(
                foo.begin(),
                foo.end());
    
            std::copy(
                foo.begin(),
                foo.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            std::pair<std::vector<int>::iterator,
                std::vector<int>::iterator> p;
            p = std::equal_range(foo.begin(), foo.end(), 7);
    
            // 输出范围对应的相对位置
            std::cout << p.first - foo.begin() << " " << p.second - foo.begin() << std::endl;
    
        }
    }
    int main()
    {
        ClassFoo::EqualRange_1();
        return 0;
    }

    -7 -5 -1 0 1 7 7 7 8 23 29 
    5 8

  • 复杂度

    O(2 * log2(N) + 1)N 等值为 std::distance(first,last)

    数据争用相关

    范围 [first,last) 中的元素都有可能被被访问过。

    异常安全性相关

    如果元素比较(Compare)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)