• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <algorithm>

    std::equal

    namespace std {
      template <class InputIterator1, class InputIterator2>
      bool equal(InputIterator1 first1,
                 InputIterator1 last1,
                 InputIterator2 first2);           // (1) C++03
    
      template <class InputIterator1, class InputIterator2>
      constexpr bool equal(InputIterator1 first1,
                           InputIterator1 last1,
                           InputIterator2 first2); // (1) C++20
    
      template <class InputIterator1, class InputIterator2, class BinaryPredicate>
      bool equal(InputIterator1 first1,
                 InputIterator1 last1,
                 InputIterator2 first2,
                 BinaryPredicate pred);            // (2) C++03
    
      template <class InputIterator1, class InputIterator2, class BinaryPredicate>
      constexpr bool equal(InputIterator1 first1,
                           InputIterator1 last1,
                           InputIterator2 first2,
                           BinaryPredicate pred);  // (2) C++20
    
      template <class InputIterator1, class InputIterator2>
      bool equal(InputIterator1 first1,
                 InputIterator1 last1,
                 InputIterator2 first2,
                 InputIterator2 last2);            // (3) C++14
    
      template <class InputIterator1, class InputIterator2>
      constexpr bool equal(InputIterator1 first1,
                           InputIterator1 last1,
                           InputIterator2 first2,
                           InputIterator2 last2);  // (3) C++20
    
      template <class InputIterator1, class InputIterator2, class BinaryPredicate>
      bool equal(InputIterator1 first1,
                 InputIterator1 last1,
                 InputIterator2 first2,
                 InputIterator2 last2,
                 BinaryPredicate pred);            // (4) C++14
    
      template <class InputIterator1, class InputIterator2, class BinaryPredicate>
      constexpr bool equal(InputIterator1 first1,
                           InputIterator1 last1,
                           InputIterator2 first2,
                           InputIterator2 last2,
                           BinaryPredicate pred);  // (4) C++20
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
      bool equal(ExecutionPolicy&& exec,
                 ForwardIterator1 first1,
                 ForwardIterator1 last1,
                 ForwardIterator2 first2);         // (5) C++17
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                class BinaryPredicate>
      bool equal(ExecutionPolicy&& exec,
                 ForwardIterator1 first1,
                 ForwardIterator1 last1,
                 ForwardIterator2 first2,
                 BinaryPredicate pred);            // (6) C++17
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
      bool equal(ExecutionPolicy&& exec,
                 ForwardIterator1 first1,
                 ForwardIterator1 last1,
                 ForwardIterator2 first2,
                 ForwardIterator2 last2);          // (7) C++17
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
                class BinaryPredicate>
      bool equal(ExecutionPolicy&& exec,
                 ForwardIterator1 first1,
                 ForwardIterator1 last1,
                 ForwardIterator2 first2,
                 ForwardIterator2 last2,
                 BinaryPredicate pred);            // (8) C++17
    }
    

    概要

    2つのイテレータ範囲を等値比較する。

    2つのイテレータ範囲が異なる要素数であった場合、falseを返す。

    2つのイテレータ範囲が要素数および各要素が等値であった場合、trueを返す。

    戻り値

    last2 が与えられている形式の場合、もし last1 - first1 != last2 - first2 であれば、false を返す。
    そうでない場合、[first1,last1) 内のイテレータ i について、*i == *(first2 + (i - first1)) もしくは pred(*i, *(first2 + (i - first1))) != false が全てのイテレータ i について満たされているのであれば true を返す。
    そうでない場合は false を返す。

    計算量

    last2 が与えられていない形式では、last2 = first2 + (last1 - first1)であるとして説明する。

    • (1), (2), (3), (4) : InputIterator1InputIterator2 が共にランダムアクセスイテレータの要件を満たす場合で、かつ、last1 - first1 != last2 - first2 の場合、1 度も比較または述語は適用されない。そうでない場合、最大で min(last1 - first1, last2 - first2) 回の比較または述語が適用される。
    • (5), (6), (7), (8) : ForwardIterator1ForwardIterator2 が共にランダムアクセスイテレータの要件を満たす場合で、かつ、last1 - first1 != last2 - first2 の場合、1 度も比較または述語は適用されない。そうでない場合、O(min(last1 - first1, last2 - first2)) 回の比較または述語が適用される。

    備考

    • ランダムアクセスイテレータの範囲を使用する場合、状況によっては(1) (2)のバージョンよりも、(3) (4)を使用する方が効率がよくなることが期待できる。ランダムアクセスイテレータはイテレータ同士の差を定数時間で求められるため、イテレーションを行うことなく2つの範囲の要素数が異なることを検出できるためである

    #include <algorithm>
    #include <iostream>
    #include <vector>
    #include <array>
    #include <iterator>
    
    int main() {
      std::vector<int>   v  = { 1,2,3,4,3,2 };
      std::array<int, 6> v2 = { 1,2,3,4,2,1 };
    
      // コンテナの中身が同じかどうか調べる
      bool result = std::equal(std::begin(v), std::end(v), std::begin(v2), std::end(v2));
      std::cout << std::boolalpha << result << std::endl;
    
      // x±1 の誤差を許すようにする
      bool result2 = std::equal(std::begin(v), std::end(v), std::begin(v2), std::end(v2),
                                [](int x, int y) { return x - 1 <= y && y <= x + 1; });
      std::cout << std::boolalpha << result2 << std::endl;
    }
    

    出力

    false
    true
    

    実装例

    template<class InputIterator1, class InputIterator2>
    bool equal(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2) {
      for ( ; first1 != last1; ++first1, ++first2)
        if (!bool(*first1 == *first2))
          return false;
      return true;
    }
    
    template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    bool equal(InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, BinaryPredicate pred) {
      for ( ; first1 != last1; ++first1, ++first2)
        if (!bool(pred(*first1, *first2)))
          return false;
      return true;
    }
    
    # if __cplusplus >= 201402L
    
    template<class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
    inline bool equal_impl(RandomAccessIterator1 first1, RandomAccessIterator1 last1,
                           RandomAccessIterator2 first2, RandomAccessIterator2 last2,
                           BinaryPredicate pred,
                           random_access_iterator_tag, random_access_iterator_tag) {
      if (last1 - first1 != last2 - first2)
        return false;
      return std::equal(first1, last1, first2, pred);
    }
    
    template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    bool equal_impl(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred,
                    input_iterator_tag, input_iterator_tag) {
      for ( ; first1 != last1 && first2 != last2; ++first1, ++first2)
        if (!bool(pred(*first1, *first2)))
          return false;
      return first1 == last1 && first2 == last2;
    }
    
    template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    inline bool equal(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred) {
      return equal_impl(first1, last1, first2, last2, pred,
                        typename iterator_traits<InputIterator1>::iterator_category(),
                        typename iterator_traits<InputIterator2>::iterator_category());
    }
    
    template<class InputIterator1, class InputIterator2>
    inline bool equal(InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2) {
      return std::equal(first1, last1, first2, last2, equal_to<>());
    }
    
    # endif
    

    バージョン

    言語

    • C++98
    • C++14: 2つ目の終端のイテレータlast2を実引数に取るオーバーロードの追加。

    処理系(last2を受け取るバージョン)

    参照