C++

參考

<algorithm>

function template
<algorithm>

std::set_symmetric_difference

預設 (1)
template <class InputIterator1, class InputIterator2, class OutputIterator>  OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,                                           InputIterator2 first2, InputIterator2 last2,                                           OutputIterator result);
自定義 (2)
template <class InputIterator1, class InputIterator2,          class OutputIterator, class Compare>  OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,                                           InputIterator2 first2, InputIterator2 last2,                                           OutputIterator result, Compare comp);
兩個已排序範圍的對稱差集
構造一個以 result 指向的位置開始的已排序範圍，包含兩個已排序範圍 [first1,last1) 和 [first2,last2) 的*對稱差集*。

兩個集合的*對稱差集*是由存在於其中一個集合但不存在於另一個集合中的元素組成的。在每個範圍的等價元素中，被丟棄的是那些在呼叫前原始順序中較早出現的元素。複製元素的原始順序也得以保留。

第一個版本使用 operator< 比較元素，第二個版本使用 comp 比較元素。兩個元素 a 和 b 被認為是等價的，當滿足 (!(a<b) && !(b<a)) 或 (!comp(a,b) && !comp(b,a)) 時。

範圍中的元素應已根據相同的標準（operator< 或 comp）排序。生成的範圍也根據此標準進行排序。

此函式模板的行為等同於
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
                                           InputIterator2 first2, InputIterator2 last2,
                                           OutputIterator result)
{
  while (true)
  {
    if (first1==last1) return std::copy(first2,last2,result);
    if (first2==last2) return std::copy(first1,last1,result);

    if (*first1<*first2) { *result=*first1; ++result; ++first1; }
    else if (*first2<*first1) { *result = *first2; ++result; ++first2; }
    else { ++first1; ++first2; }
  }
}

引數

first1, last1
輸入迭代器，指向第一個已排序序列的起始和結束位置。使用的範圍是 [first1,last1)，它包含 first1 和 last1 之間的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2, last2
輸入迭代器，指向第二個已排序序列的起始和結束位置。使用的範圍是 [first2,last2)。
result
輸出迭代器，指向儲存結果序列的範圍的起始位置。
目標型別的元素應當能夠接受來自其他範圍的元素賦值。
comp
二元函式，接受輸入迭代器所指型別的兩個引數，並返回一個可轉換為 bool 的值。返回的值指示第一個引數是否被認為在該函式定義的特定*嚴格弱序*中排在第二個引數之前。
該函式不得修改其任何引數。
這可以是一個函式指標或函式物件。

這些範圍不應重疊。

返回值

指向所構造範圍結束位置的迭代器。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
// set_symmetric_difference example
#include <iostream>     // std::cout
#include <algorithm>    // std::set_symmetric_difference, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  std::vector<int>::iterator it;

  std::sort (first,first+5);     //  5 10 15 20 25
  std::sort (second,second+5);   // 10 20 30 40 50

  it=std::set_symmetric_difference (first, first+5, second, second+5, v.begin());
                                               //  5 15 25 30 40 50  0  0  0  0
  v.resize(it-v.begin());                      //  5 15 25 30 40 50

  std::cout << "The symmetric difference has " << (v.size()) << " elements:\n";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

輸出
The symmetric difference has 6 elements:
 5 15 25 30 40 50


複雜度

線性時間，最多為 2*(count1+count2)-1（其中 countX 是 firstX 和 lastX 之間的距離）：比較和賦值元素。

資料競爭

訪問範圍 [first1,last1) 和 [first2,last2) 中的物件。
修改 result 和返回的迭代器之間的範圍內的物件。

異常

如果任何元素比較、元素賦值或迭代器操作丟擲異常，則丟擲異常。
請注意，無效引數會導致未定義行為。

另見

set_union
兩個已排序範圍的並集 （函式模板）
set_intersection
兩個已排序範圍的交集 （函式模板）
set_difference
兩個已排序範圍的差集 （函式模板）
merge
合併已排序的範圍 （函式模板）