std::equal_range

来自cppreference.com
< cpp‎ | algorithm

该页由英文版wiki使用Google Translate机器翻译而来。

该翻译可能存在错误或用词不当。鼠标停留在文本上可以看到原版本。你可以帮助我们修正错误或改进翻译。参见说明请点击这里.

点击这里参见该页的英文版本

 
C++
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
(C++11)
二分查找操作
equal_range
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

重排
数值操作
C 库
 
定义于头文件 <algorithm>
template< class ForwardIt, class T >

std::pair<ForwardIt,ForwardIt>
    equal_range( ForwardIt first, ForwardIt last,

                 const T& value );
 (1)
template< class ForwardIt, class T, class Compare >

std::pair<ForwardIt,ForwardIt>
    equal_range( ForwardIt first, ForwardIt last,

                 const T& value, Compare comp );
 (2)
返回一个范围，等于在已排序的范围value[first, last)包含的所有元素。范围是指由两个迭代器指向的第一个元素是“不低于”比value和其他指标的第一个元素，一个“更大的，比value”。可能可以得到第一个迭代器与lower_bound()，第二 - upper_bound().
原文：
Returns a range containing all elements equal to value in the sorted range [first, last). The range is defined by two iterators, one pointing to the first element that is not less than value and another pointing to the first element greater than value. The first iterator may be alternatively obtained with lower_bound(), the second - with upper_bound().
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。
operator<的第一个版本使用比较的元素，第二个版本使用给定的比较函数comp.
原文：
The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

目录

[编辑] 参数

first, last -
检查的元素
原文：
the range of elements to examine
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。
value -
值进行比较的元素
原文：
value to compare the elements to
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。
comp - 比较函数对象（即满足比较（Compare）要求的对象），若首个参数小于第二个，则返回 ​true 。

比较函数的签名应等价于如下者：

 bool cmp(const Type1 &a, const Type2 &b);

签名不需要拥有 const & ，但函数对象必须不修改传递给它的对象。
类型 Type1 与 Type2 必须使得 T 类型的对象能隐式转换到 Type1 与 Type2 两者，且 ForwardIt 类型的对象能在解引用后隐式转换到 Type1 与 Type2 两者。 ​

类型要求
-
ForwardIt 必须满足 ForwardIterator 的要求。

[编辑] 返回值

std::pair含有对限定想要的范围内的迭代器，指向的第一个元素是“不”比value和第二指向的第一个元素的第一“更大的”比value.
原文：
std::pair containing a pair of iterators defining the wanted range, the first pointing to the first element that is not less than value and the second pointing to the first element greater than value.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。
如果有任何元素，“不低于”比value，last返回的第一个元素。同样，如果没有任何元素“更大的”比value，last返回的第二个元素
原文：
If there are no elements not less than value, last is returned as the first element. Similarly if there are no elements greater than value, last is returned as the second element
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

[编辑] 复杂度

first和last之间的距离在对数
原文：
Logarithmic in the distance between first and last
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

[编辑] 可能的实现

版本一 
template<class ForwardIt, class T 
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}
版本二 
template<class ForwardIt, class T, class Compare>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value, Compare comp);
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

[编辑] 示例

#include <algorithm>
#include <vector>
#include <iostream>
 
struct S
{
    int number;
    char name;
 
    S ( int number, char name  )
        : number ( number ), name ( name )
    {}
 
    // only the number is relevant with this comparison
    bool operator< ( const S& s ) const
    {
        return number < s.number;
    }
};
 
 
int main()
{
    std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {3,'F'}, {4,'G'} };
 
    S value ( 2, '?' );
 
    auto p = std::equal_range(vec.begin(),vec.end(),value);
 
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->name << ' ';
}

输出： 

B C D

[编辑] 另请参阅

 返回指向第一个不小于给定值的元素的迭代器
(函数模板) [编辑]
返回指向第一个大于给定值的元素的迭代器
(函数模板) [编辑]
判断一个元素是否在区间内
(函数模板) [编辑]
来自“http://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/equal_range&oldid=37830”