名前空間
変種
操作

std::equal

From cppreference.com
< cpp‎ | algorithm
 
C++
コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ
 
アルゴリズムライブラリ
制約付きアルゴリズムとRangeアルゴリズム (C++20)
制約付きアルゴリズム、例: ranges::copy, ranges::sort, ...
実行ポリシー (C++17)
シーケンスを変更しない操作
一括操作
(C++17)
検索操作
(C++11)                (C++11)(C++11)
equal

シーケンスを変更する操作
コピー操作
(C++11)
(C++11)
(C++11)
スワップ操作
変換操作
生成操作
削除操作
順序変更操作
(C++17まで)(C++11)
(C++20)(C++20)
サンプリング操作
(C++17)

ソートおよび関連操作
パーティション操作
ソート操作
二分探索操作
(パーティション化された範囲)
集合操作 (ソート済み範囲)
マージ操作 (ソート済み範囲)
ヒープ操作
最小/最大操作
(C++11)
(C++17)
辞書順比較操作
(C++20)
順列操作
Cライブラリ
数値演算
未初期化メモリに対する操作
 
ヘッダー <algorithm> で定義
template< class InputIt1, class InputIt2 >

bool equal( InputIt1 first1, InputIt1 last1,

            InputIt2 first2 );
 (1) (C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >

bool equal( ExecutionPolicy&& policy,
            ForwardIt1 first1, ForwardIt1 last1,

            ForwardIt2 first2 );
 (2) (C++17以降)
template< class InputIt1, class InputIt2, class BinaryPred >

bool equal( InputIt1 first1, InputIt1 last1,

            InputIt2 first2, BinaryPred p );
 (3) (C++20 以降 constexpr)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class BinaryPred >
bool equal( ExecutionPolicy&& policy,
            ForwardIt1 first1, ForwardIt1 last1,

            ForwardIt2 first2, BinaryPred p );
 (4) (C++17以降)
template< class InputIt1, class InputIt2 >

bool equal( InputIt1 first1, InputIt1 last1,

            InputIt2 first2, InputIt2 last2 );
 (5) (C++14以降)
(C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >

bool equal( ExecutionPolicy&& policy,
            ForwardIt1 first1, ForwardIt1 last1,

            ForwardIt2 first2, ForwardIt2 last2 );
 (6) (C++17以降)
template< class InputIt1, class InputIt2, class BinaryPred >

bool equal( InputIt1 first1, InputIt1 last1,

            InputIt2 first2, InputIt2 last2, BinaryPred p );
 (7) (C++14以降)
(C++20 以降 constexpr)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class BinaryPred >
bool equal( ExecutionPolicy&& policy,
            ForwardIt1 first1, ForwardIt1 last1,

            ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );
 (8) (C++17以降)

[first1, last1) で定義される範囲と、first2 から始まる範囲が等しいかどうかをチェックする。

  • オーバーロード (1-4) では、2番目の範囲は std::distance(first1, last1) 個の要素を持つ。
  • オーバーロード (5-8) では、2番目の範囲は [first2, last2) である。
1,5) 要素は operator== を使用して比較される。
3,7) 要素は与えられた二項述語 p を使用して比較される。
2,4,6,8) (1,3,5,7) と同じだが、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 - 比較する2番目の要素の範囲を定義するイテレータのペア
policy - 使用する 実行ポリシー
p - 要素が等しいと見なされる場合に true を返す二項述語。

述語関数のシグネチャは、以下と同等である必要がある。

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

シグネチャは const & を持つ必要はないが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関わらず、(おそらく const の) Type1 と Type2 のすべての値を受け入れられる必要がある (したがって、Type1 & は許可されない。また、Type1 の場合、ムーブがコピーと同等でない限り、Type1 も許可されない。(C++11以降))。
型 Type1 と Type2 は、InputIt1 と InputIt2 の型のオブジェクトが参照解除され、それぞれ Type1 と Type2 に暗黙的に変換できるものでなければならない。

型要件
-
InputIt1, InputIt2 は LegacyInputIterator の要件を満たす必要がある。
-
ForwardIt1, ForwardIt2 は LegacyForwardIterator の要件を満たさなければなりません。
-
BinaryPred は BinaryPredicate の要件を満たす必要がある。

[編集] 戻り値

1-4) 2つの範囲の対応する各要素が等しい場合、true を返す。それ以外の場合は false を返す。
5-8) std::distance(first1, last1) と std::distance(first2, last2) が等しく、かつ2つの範囲の対応する各要素が等しい場合、true を返す。それ以外の場合は false を返す。

[編集] 計算量

std::distance(first1, last1) を N1 とし、std::distance(first2, last2) を N2 とする。

1) operator== を使用した比較は最大 N1 回。
2) operator== を使用した比較は O(N1)。
3) 述語 p の適用は最大 N1 回。
4) 述語 p の適用は O(N1)。
5-8) InputIt1 と InputIt2 が両方とも LegacyRandomAccessIterator であり、last1 - first1 != last2 - first2 が true の場合、比較は行われない。
それ以外の場合、min(N1,N2) を N とする。
5) operator== を使用した比較は最大 N 回。
6) operator== を使用した比較は O(N)。
7) 述語 p の適用は最大 N 回。
8) 述語 p の適用は O(N)。

[編集] 例外

ExecutionPolicy というテンプレートパラメータを持つオーバーロードは、次のようにエラーを報告します。

  • アルゴリズムの一部として呼び出された関数の実行が例外をスローし、ExecutionPolicy が 標準ポリシー のいずれかである場合、std::terminate が呼び出されます。その他の ExecutionPolicy の場合、動作は実装定義です。
  • アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。

[編集] 可能な実装

equal (1) 
template<class InputIt1, class InputIt2>
constexpr //< since C++20
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2)
{
    for (; first1 != last1; ++first1, ++first2)
        if (!(*first1 == *first2))
            return false;
 
    return true;
}
equal (3) 
template<class InputIt1, class InputIt2, class BinaryPred>
constexpr //< since C++20
bool equal(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, BinaryPred p)
{
    for (; first1 != last1; ++first1, ++first2)
        if (!p(*first1, *first2))
            return false;
 
    return true;
}
equal (5) 
namespace detail
{
    // random-access iterator implementation (allows quick range size detection)
    template<class RandomIt1, class RandomIt2>
    constexpr //< since C++20
    bool equal(RandomIt1 first1, RandomIt1 last1, RandomIt2 first2, RandomIt2 last2,
               std::random_access_iterator_tag, std::random_access_iterator_tag)
    {
        if (last1 - first1 != last2 - first2)
            return false;
 
        for (; first1 != last1; ++first1, ++first2)
            if (!(*first1 == *first2))
                return false;
 
        return true;
    }
 
    // input iterator implementation (needs to manually compare with “last2”)
    template<class InputIt1, class InputIt2>
    constexpr //< since C++20
    bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
               std::input_iterator_tag, std::input_iterator_tag)
    {
        for (; first1 != last1 && first2 != last2; ++first1, ++first2)
            if (!(*first1 == *first2))
                return false;
 
        return first1 == last1 && first2 == last2;
    }
}
 
template<class InputIt1, class InputIt2>
constexpr //< since C++20
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
    details::equal(first1, last1, first2, last2,
                   typename std::iterator_traits<InputIt1>::iterator_category(),
                   typename std::iterator_traits<InputIt2>::iterator_category());
}
equal (7) 
namespace detail
{
    // random-access iterator implementation (allows quick range size detection)
    template<class RandomIt1, class RandomIt2, class BinaryPred>
    constexpr //< since C++20
    bool equal(RandomIt1 first1, RandomIt1 last1,
               RandomIt2 first2, RandomIt2 last2, BinaryPred p,
               std::random_access_iterator_tag, std::random_access_iterator_tag)
    {
        if (last1 - first1 != last2 - first2)
            return false;
 
        for (; first1 != last1; ++first1, ++first2)
            if (!p(*first1, *first2))
                return false;
 
        return true;
    }
 
    // input iterator implementation (needs to manually compare with “last2”)
    template<class InputIt1, class InputIt2, class BinaryPred>
    constexpr //< since C++20
    bool equal(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2, BinaryPred p,
               std::input_iterator_tag, std::input_iterator_tag)
    {
        for (; first1 != last1 && first2 != last2; ++first1, ++first2)
            if (!p(*first1, *first2))
                return false;
 
        return first1 == last1 && first2 == last2;
    }
}
 
template<class InputIt1, class InputIt2, class BinaryPred>
constexpr //< since C++20
bool equal(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, InputIt2 last2, BinaryPred p)
{
    details::equal(first1, last1, first2, last2, p,
                   typename std::iterator_traits<InputIt1>::iterator_category(),
                   typename std::iterator_traits<InputIt2>::iterator_category());
}

[編集] 備考

std::equal は、std::unordered_set、std::unordered_multiset、std::unordered_map、または std::unordered_multimap からのイテレータによって形成される範囲を比較するために使用すべきではない。これらのコンテナに要素が格納される順序は、両方のコンテナが同じ要素を格納していても異なる場合があるためである。

コンテナ全体または文字列ビュー(C++17以降)の等価性を比較する場合、通常は対応する型の operator== が推奨される。

逐次的な std::equal はショートサーキットを保証しない。例えば、両方の範囲の最初のペアの要素が等しくない場合でも、残りの要素が比較されることがある。非ショートサーキット比較は、範囲が std::memcmp または実装固有のベクトル化されたアルゴリズムで比較される場合に発生する可能性がある。

[編集] 例

以下のコードは std::equal を使用して、文字列が回文であるかどうかをテストする。

このコードを実行
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string_view>
 
constexpr bool is_palindrome(const std::string_view& s)
{
    return std::equal(s.cbegin(), s.cbegin() + s.size() / 2, s.crbegin());
}
 
void test(const std::string_view& s)
{
    std::cout << std::quoted(s)
              << (is_palindrome(s) ? " is" : " is not")
              << " a palindrome\n";
}
 
int main()
{
    test("radar");
    test("hello");
}

出力

"radar" is a palindrome
"hello" is not a palindrome

[編集] 関連項目

(C++11)
 特定の基準を満たす最初の要素を見つける
(関数テンプレート) [編集]
 ある範囲が別の範囲より辞書順で小さい場合に true を返す
(関数テンプレート) [編集]
 2つの範囲が異なる最初の位置を見つける
(関数テンプレート) [編集]
 要素の範囲の最初の出現を検索する
(関数テンプレート) [編集]
(C++20)
 2つの要素の集合が同じかどうかを判断する
(アルゴリズム関数オブジェクト)[編集]
 x == y を実装する関数オブジェクト
(クラステンプレート) [編集]
 特定のキーに一致する要素の範囲を返す
(関数テンプレート) [編集]
"https://ja.cppreference.dev/mwiki/index.php?title=cpp/algorithm/equal&oldid=180463" から取得
English 日本語 中文(简体) 中文(繁體)