std::equal_range

来自cppreference.com

This page has been machine-translated from the English version of the wiki using Google Translate.

The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here.

Click here for the English version of this page

 
C++
 
算法库
功能
Original:
Functions
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
修改序列操作
Original:
Non-modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
all_of
any_of
none_of		（C++11）
（C++11）
（C++11）
for_each
count
count_if
mismatch
equal
修改序列操作
Original:
Modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
分区操作
Original:
Partitioning operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
is_partitioned（C++11）
partition
partition_copy（C++11）
排序操作（排序的区间）
Original:
Sorting operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
is_sorted（C++11）
is_sorted_until（C++11）
sort
二进制搜索操作（排序的区间）
Original:
Binary search operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
binary_search
equal_range
设置操作（排序的区间）
Original:
Set operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
堆的操作
Original:
Heap operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
最小/最大操作
Original:
Minimum/maximum operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
数字操作
Original:
Numeric operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
C库
Original:
C library
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
 
Defined in header <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().
Original:
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().
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
operator<的第一个版本使用比较的元素，第二个版本使用给定的比较函数comp.
Original:
The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

目录

[编辑] 参数

first, last -
检查的元素
Original:
the range of elements to examine
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
value -
值进行比较的元素
Original:
value to compare the elements to
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

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

The signature does not need to have const &, but the function must not modify the objects passed to it.
The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2. ​

Type requirements
-
ForwardIt must meet the requirements of ForwardIterator.

[编辑] 返回值

std::pair含有对限定想要的范围内的迭代器，指向的第一个元素是“不”比value和第二指向的第一个元素的第一“更大的”比value.
Original:
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.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
如果有任何元素，“不低于”比value，last返回的第一个元素。同样，如果没有任何元素“更大的”比value，last返回的第二个元素
Original:
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
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[编辑] 复杂性

first和last之间的距离在对数
Original:
Logarithmic in the distance between first and last
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[编辑] 可能的实现

First version 
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));
}
Second version 
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 << ' ';
}

Output: 

B C D

[编辑] 另请参阅
返回一个迭代器的第一个元素“不低于”大于给定值
Original:
returns an iterator to the first element not less than the given value
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

（函数模板） [edit]
返回一个迭代器的第一个元素“更大的”超过一定值
Original:
returns an iterator to the first element greater than a certain value
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

（函数模板） [edit]
确定一个元素是否存在在一定的范围内
Original:
determines if an element exists in a certain range
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

（函数模板） [edit]
来自“http://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/equal_range&oldid=30128”