名稱空間
變體
操作

std::equal_range

來自 cppreference.com
< cpp‎ | 演算法
 
C++
 
演算法庫
有約束演算法與針對範圍的演算法 (C++20)
有約束的演算法，例如 ranges::copy、 ranges::sort 等……
執行策略 (C++17)
排序及相關操作
劃分操作
排序操作
二分搜尋操作
（於已劃分範圍上）
equal_range
集合操作（於已排序範圍上）
歸併操作（於已排序範圍上）
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比較操作
(C++20)
排列操作
C 庫
數值操作
未初始化記憶體上的操作
 
定義於標頭檔案 <algorithm>
(1)
template< class ForwardIt, class T >

std::pair<ForwardIt, ForwardIt>

    equal_range( ForwardIt first, ForwardIt last, const T& value );
 (C++20 起為 constexpr)
（直到 C++26）
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type >
constexpr std::pair<ForwardIt, ForwardIt>

    equal_range( ForwardIt first, ForwardIt last, const T& value );
 (C++26 起)
(2)
template< class ForwardIt, class T, class Compare >

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

                 const T& value, Compare comp );
 (C++20 起為 constexpr)
（直到 C++26）
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type,
          class Compare >
constexpr std::pair<ForwardIt, ForwardIt>
    equal_range( ForwardIt first, ForwardIt last,

                 const T& value, Compare comp );
 (C++26 起)

返回一個範圍，其中包含分割槽範圍 [first, last) 中所有與 value 等效的元素。

1) 等效性使用 operator< 檢查

返回 std::lower_bound(first, last, value) 和 std::upper_bound(first, last, value) 的結果。

如果滿足以下任何條件，則行為是未定義的：

  • 對於 [first, last) 中的任何元素 elem，bool(elem < value) 不意味著 !bool(value < elem)。
  • [first, last) 的元素 elem 不相對於表示式 bool(elem < value) 和 !bool(value < elem) 分割槽。
 (C++20 前)

等同於 std::equal_range(first, last, value, std::less{})。

 (C++20 起)
2) 等效性使用 comp 檢查
返回 std::lower_bound(first, last, value, comp) 和 std::upper_bound(first, last, value, comp) 的結果。
如果滿足以下任何條件，則行為未定義：
  • 對於 [first, last) 中的任何元素 elem，bool(comp(elem, value)) 不意味著 !bool(comp(value, elem))。
  • [first, last) 的元素 elem 不相對於表示式 bool(comp(elem, value)) 和 !bool(comp(value, elem)) 分割槽。

目錄

[edit] 引數

first, last - 定義要檢查的元素已分割槽範圍的迭代器對。
value - 用於比較元素的數值
comp - 二元謂詞，如果第一個引數排在第二個引數之前，則返回true。

謂詞函式的簽名應等效於以下內容：

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

雖然簽名不需要包含 const &，但函式不得修改傳遞給它的物件，並且必須能夠接受 Type1 和 Type2 型別（可能為 const）的所有值，無論其 值類別如何（因此，不允許使用 Type1 &，也不允許使用 Type1，除非對於 Type1，移動等同於複製(C++11 起)）。
型別 Type1 和 Type2 必須使型別 T 的物件可以隱式轉換為 Type1 和 Type2，並且型別 ForwardIt 的物件可以解引用，然後隱式轉換為 Type1 和 Type2。

型別要求
-
ForwardIt 必須滿足 LegacyForwardIterator 的要求。
-
Compare 必須滿足 BinaryPredicate 的要求。它不需要滿足 Compare。

[edit] 返回值

一個 std::pair，包含一對迭代器，其中

  • first 是指向範圍 [first, last) 中第一個不早於 value 的元素的迭代器（如果未找到此類元素，則為 last），以及
  • second 是指向範圍 [first, last) 中第一個晚於 value 的元素的迭代器（如果未找到此類元素，則為 last）。

[edit] 複雜度

給定 N 作為 std::distance(first, last)

1) 最多 2log2(N)+O(1) 次與 value 的比較，使用 operator<(C++20 前)std::less{}(C++20 起)。
2) 最多 2log2(N)+O(1) 次比較器 comp 的應用。

然而，如果 ForwardIt 不是 LegacyRandomAccessIterator，則迭代器增量次數與 N 成線性關係。值得注意的是，std::set 和 std::multiset 迭代器不是隨機訪問的，因此應優先使用它們的成員函式 std::set::equal_range（或 std::multiset::equal_range）。

[edit] 注意

儘管 std::equal_range 只要求 [first, last) 被分割槽，但此演算法通常用於 [first, last) 已排序的情況，這樣二分查詢對任何 value 都是有效的。

除了 std::lower_bound 和 std::upper_bound 的要求之外，std::equal_range 還要求 operator< 或 comp 是非對稱的（即，a < b 和 b < a 總是返回不同的結果）。

因此，二分查詢的中間結果可以被 std::lower_bound 和 std::upper_bound 共享。例如，std::lower_bound 呼叫的結果可以作為 first 引數用於 std::upper_bound 呼叫。

特性測試宏 值 標準 特性
__cpp_lib_algorithm_default_value_type 202403 (C++26) 演算法的列表初始化 (1,2)

[edit] 可能的實現

equal_range (1) 
template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type>
constexpr std::pair<ForwardIt, ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    return std::equal_range(first, last, value, std::less{});
}
equal_range (2) 
template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
constexpr 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));
}

[edit] 示例

執行此程式碼
#include <algorithm>
#include <complex>
#include <iostream>
#include <vector>
 
struct S
{
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator<(const S& s) const { return number < s.number; }
};
 
struct Comp
{
    bool operator()(const S& s, int i) const { return s.number < i; }
    bool operator()(int i, const S& s) const { return i < s.number; }
};
 
int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    const std::vector<S> vec{{1, 'A'}, {2, 'B'}, {2, 'C'},
                             {2, 'D'}, {4, 'G'}, {3, 'F'}};
    const S value{2, '?'};
 
    std::cout << "Compare using S::operator<(): ";
    const auto p = std::equal_range(vec.begin(), vec.end(), value);
 
    for (auto it = p.first; it != p.second; ++it)
        std::cout << it->name << ' ';
    std::cout << '\n';
 
    std::cout << "Using heterogeneous comparison: ";
    const auto p2 = std::equal_range(vec.begin(), vec.end(), 2, Comp{});
 
    for (auto it = p2.first; it != p2.second; ++it)
        std::cout << it->name << ' ';
    std::cout << '\n';
 
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto p3 = std::equal_range(nums.cbegin(), nums.cend(), {2, 0}, cmpz);
    #else
        auto p3 = std::equal_range(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz);
    #endif
 
    for (auto it = p3.first; it != p3.second; ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
}

輸出

Compare using S::operator<(): B C D 
Using heterogeneous comparison: B C D
(2,2) (2, 1)

[edit] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告 應用於 釋出時的行為 正確的行為
LWG 270 C++98 Compare 需要滿足 比較，且 T 需要
是 可小於比較的（需要嚴格弱序）		 只需要分割槽；
允許異構比較
LWG 384 C++98 最多允許 2log2(N)+1 次比較
這是無法實現的[1]		 修正為 2log2(N)+O(1)
  1. ↑ 將 equal_range 應用於單個元素的範圍需要 2 次比較，但複雜度要求最多隻允許 1 次比較。

[edit] 參閱

 返回一個指向第一個不小於給定值的元素的迭代器
(函式模板) [編輯]
 返回一個指向第一個大於某個值的元素的迭代器
(函式模板) [編輯]
 判斷一個元素是否存在於部分有序的範圍中
(函式模板) [編輯]
 將一個範圍的元素分成兩組
(函式模板) [編輯]
 判斷兩組元素是否相同
(函式模板) [編輯]
 返回與特定鍵匹配的元素範圍
(std::set<Key,Compare,Allocator> 的公開成員函式) [編輯]
 返回與特定鍵匹配的元素範圍
(std::multiset<Key,Compare,Allocator> 的公開成員函式) [編輯]
(C++20)
 返回與特定鍵匹配的元素範圍
(演算法函式物件)[編輯]
取自 "https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/equal_range&oldid=180598"