名稱空間
變體
操作

std::set_symmetric_difference

來自 cppreference.com
< cpp‎ | 演算法
 
C++
 
演算法庫
有約束演算法與針對範圍的演算法 (C++20)
有約束的演算法，例如 ranges::copy、 ranges::sort 等……
執行策略 (C++17)
排序及相關操作
劃分操作
排序操作
二分搜尋操作
（於已劃分範圍上）
集合操作（於已排序範圍上）
set_symmetric_difference

歸併操作（於已排序範圍上）
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比較操作
(C++20)
排列操作
C 庫
數值操作
未初始化記憶體上的操作
 
定義於標頭檔案 <algorithm>
template< class InputIt1, class InputIt2, class OutputIt >

OutputIt set_symmetric_difference
    ( 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_symmetric_difference
    ( 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_symmetric_difference
    ( 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_symmetric_difference
    ( ExecutionPolicy&& policy,
      ForwardIt1 first1, ForwardIt1 last1,
      ForwardIt2 first2, ForwardIt2 last2,

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

計算兩個已排序範圍的對稱差集：在其中一個範圍中找到但不在兩個範圍中都找到的元素將被複制到從 d_first 開始的範圍中。輸出範圍也是有序的。

如果 [first1, last1) 包含 m 個彼此等價的元素，並且 [first2, last2) 包含 n 個與它們等價的元素，那麼這些元素中的 std::abs(m - n) 將被複制到輸出範圍，並保持順序

  • 如果 m > n，則從 [first1, last1) 中複製這些元素的最後 m - n 個。
  • 如果 m < n，則從 [first2, last2) 中複製這些元素的最後 n - m 個。
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) 重疊，則行為未定義。

目錄

[編輯] 引數

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 的要求。

[編輯] 返回值

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

[編輯] 複雜度

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

1,2) 使用 operator<(直到 C++20)std::less{}(C++20 起) 最多進行 2⋅(N1+N2)-1 次比較。
3,4) 最多進行 2⋅(N1+N2)-1 次比較函式 comp 的應用。

[編輯] 異常

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

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

[編輯] 可能實現

set_symmetric_difference (1) 
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
                                  InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
 
        if (*first1 < *first2)
            *d_first++ = *first1++;
        else
        {
            if (*first2 < *first1)
                *d_first++ = *first2;
            else
                ++first1;
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}
set_symmetric_difference (3) 
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
                                  InputIt2 first2, InputIt2 last2,
                                  OutputIt d_first, Compare comp)
{
    while (first1 != last1)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
 
        if (comp(*first1, *first2))
            *d_first++ = *first1++;
        else
        {
            if (comp(*first2, *first1))
                *d_first++ = *first2;
            else
                ++first1;
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}

[編輯] 示例

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

輸出

1 2 3 4 6 8 9 10

[編輯] 缺陷報告

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

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

[編輯] 另請參閱

 如果一個序列是另一個序列的子序列，則返回 true
(函式模板) [編輯]
 計算兩個集合的差集
(函式模板) [編輯]
 計算兩個集合的並集
(函式模板) [編輯]
 計算兩個集合的交集
(函式模板) [編輯]
(C++20)
 計算兩個集合的對稱差
(演算法函式物件)[編輯]
取自 "https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/set_symmetric_difference&oldid=180591"