• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    function template
    <algorithm>

    std::set_difference

    namespace std {
      template <class InputIterator1, class InputIterator2, class OutputIterator>
      OutputIterator
        set_difference(InputIterator1 first1,
                       InputIterator1 last1,
                       InputIterator2 first2,
                       InputIterator2 last2,
                       OutputIterator result); // (1) C++03
    
      template <class InputIterator1, class InputIterator2, class OutputIterator>
      constexpr OutputIterator
        set_difference(InputIterator1 first1,
                       InputIterator1 last1,
                       InputIterator2 first2,
                       InputIterator2 last2,
                       OutputIterator result);  // (1) C++20
    
      template <class InputIterator1, class InputIterator2, class OutputIterator,
                class Compare>
      OutputIterator
        set_difference(InputIterator1 first1,
                       InputIterator1 last1,
                       InputIterator2 first2,
                       InputIterator2 last2,
                       OutputIterator result,
                       Compare comp);           // (2) C++03
    
      template <class InputIterator1, class InputIterator2, class OutputIterator,
                class Compare>
      constexpr OutputIterator
        set_difference(InputIterator1 first1,
                       InputIterator1 last1,
                       InputIterator2 first2,
                       InputIterator2 last2,
                       OutputIterator result,
                       Compare comp);           // (2) C++20
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                class ForwardIterator>
      ForwardIterator
        set_difference(ExecutionPolicy&& exec,
                       ForwardIterator1 first1,
                       ForwardIterator1 last1,
                       ForwardIterator2 first2,
                       ForwardIterator2 last2,
                       ForwardIterator result); // (3) C++17
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                class ForwardIterator, class Compare>
      ForwardIterator
        set_difference(ExecutionPolicy&& exec,
                       ForwardIterator1 first1,
                       ForwardIterator1 last1,
                       ForwardIterator2 first2,
                       ForwardIterator2 last2,
                       ForwardIterator result,
                       Compare comp);           // (4) C++17
    }
    

    概要

    2つのソート済み範囲[first1, last1)[first2, last2)の差集合を得る

    事前条件

    • 結果の範囲は両方の入力の範囲と重なっていてはならない

    効果

    [first1,last1) から、[first2,last2) に存在していない要素を result へコピーする。構築された範囲はソートされている。

    戻り値

    構築された範囲の終端

    計算量

    最大で 2 * ((last1 - first1) + (last2 - first2)) - 1 回の比較を行う

    備考

    [first1,last1)m 個、[first2,last2)n 個の等価な要素を含んでいる場合、[first1,last1) から最後の max(m-n, 0) 要素が出力の範囲へコピーされる。

    #include <iostream>
    #include <set>
    #include <algorithm>
    #include <iterator>
    
    int main()
    {
      std::multiset<int> a = {1, 2, 3, 4, 5, 6};
      std::multiset<int> b = {2, 3, 4};
      std::multiset<int> result;
    
      // a - bの差集合を作る
      std::set_difference(a.begin(), a.end(),
                          b.begin(), b.end(),
                          std::inserter(result, result.end()));
    
      std::for_each(result.begin(), result.end(), [](int x) {
        std::cout << x << std::endl;
      });
    }
    

    出力

    1
    5
    6
    

    参照