名稱空間
變體
操作

std::set_intersection

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

OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, InputIt2 last2,

                           OutputIt d_first );
 (1) (C++20 起為 constexpr)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_intersection( ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,

                             ForwardIt3 d_first );
 (2) (C++17 起)
template< class InputIt1, class InputIt2,

          class OutputIt, class Compare >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, InputIt2 last2,

                           OutputIt d_first, Compare comp );
 (3) (C++20 起為 constexpr)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_intersection( ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,

                             ForwardIt3 d_first, Compare comp );
 (4) (C++17 起)

構造一個始於 d_first 的有序範圍，該範圍由在兩個有序範圍 [first1, last1) 和 [first2, last2) 中都存在的元素組成。

如果 [first1, last1) 包含 m 個彼此等價的元素，且 [first2, last2) 包含 n 個與它們等價的元素，則將前 std::min(m, n) 個元素從 [first1, last1) 複製到輸出範圍，並保留順序。

1) 如果 [first1, last1) 或 [first2, last2) 未按照 operator<(直到 C++20)std::less{}(從 C++20 開始) 排序，則行為未定義。
3) 如果 [first1, last1) 或 [first2, last2) 未按照 comp 排序，則行為未定義。
2,4) 同 (1,3)，但按 policy 執行。
僅當滿足所有以下條件時，這些過載才參與過載決議

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 為 true。

 (C++20 前)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 為 true。

 (C++20 起)

如果輸出範圍與 [first1, last1) 或 [first2, last2) 重疊，則行為未定義。

目錄

[edit] 引數

first1, last1 - 定義第一個要檢查的已排序元素範圍的迭代器對。
first2, last2 - 定義第二個要檢查的已排序元素範圍的迭代器對。
d_first - 輸出範圍的起始
policy - 要使用的 執行策略
comp - 比較函式物件（即滿足 Compare 要求的物件），如果第一個引數“小於”（即“排在”第二個之前），則返回 ​true。

比較函式的簽名應等效於以下內容

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

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

型別要求
-
InputIt1, InputIt2 必須滿足 LegacyInputIterator 的要求。
-
OutputIt 必須滿足 LegacyOutputIterator 的要求。
-
ForwardIt1, ForwardIt2, ForwardIt3 必須滿足 LegacyForwardIterator 的要求。
-
Compare 必須滿足 Compare 的要求。

[edit] 返回值

構造範圍的末尾後的迭代器。

[edit] 複雜度

給定 N1 為 std::distance(first1, last1)，N2 為 std::distance(first2, last2)

1,2) 最多 2⋅(N1+N2)-1 次比較，使用 operator<(直到 C++20)std::less{}(從 C++20 開始)。
3,4) 最多 2⋅(N1+N2)-1 次呼叫比較函式 comp。

[edit] 異常

帶有模板引數 ExecutionPolicy 的過載按如下方式報告錯誤

  • 如果作為演算法一部分呼叫的函式執行時丟擲異常，並且 ExecutionPolicy 是標準策略之一，則呼叫 std::terminate。對於任何其他 ExecutionPolicy，行為是實現定義的。
  • 如果演算法未能分配記憶體，則丟擲 std::bad_alloc。

[edit] 可能的實現

set_intersection (1) 
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1 && first2 != last2)
    {
        if (*first1 < *first2)
            ++first1;
        else
        {
            if (!(*first2 < *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}
set_intersection (3) 
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2)
    {
        if (comp(*first1, *first2))
            ++first1;
        else
        {
            if (!comp(*first2, *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

[edit] 示例

執行此程式碼
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v1{7, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> v2{5, 7, 9, 7};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_intersection;
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
 
    for (int n : v_intersection)
        std::cout << n << ' ';
    std::cout << '\n';
}

輸出

5 7 7

[edit] 缺陷報告

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

缺陷報告 應用於 釋出時的行為 正確的行為
LWG 291 C++98 未指定如何處理輸入範圍中的等價元素 已指定

[edit] 另請參閱

 計算兩個集合的並集
(函式模板) [編輯]
(C++20)
 計算兩個集合的交集
(演算法函式物件)[編輯]
取自“https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/set_intersection&oldid=180581”