std::unique

ヘッダー `<algorithm>` で定義
template< class ForwardIt > ForwardIt unique( ForwardIt first, ForwardIt last );	(1)	(C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt > ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(C++17以降)
template< class ForwardIt, class BinaryPred > ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPred p );	(3)	(C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(C++17以降)

範囲[first, last) から、同値な要素の連続した各グループから最初の要素以外をすべて削除し、範囲の新しい終端を示すイテレータを返します。

1) 要素は operator== を使用して比較されます。

operator== が同値関係を確立しない場合、動作は未定義です。

3) 要素は、指定された二項述語 p を使用して比較されます。

p が同値関係を確立しない場合、動作は未定義です。

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以降)

シフトは、コピー代入(C++11まで)ムーブ代入(C++11以降) によって行われます。
削除操作は安定しています。削除されない要素の相対順序は変わりません。
削除操作によって、[first, last) の基になるシーケンスは短縮されません。返されたイテレータを result とすると、

[result, last) のすべてのイテレータは、依然としてデリファレンス可能です。

[result, last) の各要素は、有効だが未指定の状態を持ちます。これは、ムーブ代入がその範囲内に元々あった要素から移動することで要素を削除できるためです。

(C++11以降)

[edit] パラメータ

first, last	-	処理する要素の範囲を定義するイテレータのペア
policy	-	使用する実行ポリシー
p	-	要素が等しいと見なされる場合に true を返す二項述語。述語関数のシグネチャは、以下と同等である必要がある。 bool pred(const Type1 &a, const Type2 &b); シグネチャは const & を持つ必要はないが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関わらず、(おそらく const の) `Type1` と `Type2` のすべての値を受け入れられる必要がある (したがって、Type1 & は許可されない。また、`Type1` の場合、ムーブがコピーと同等でない限り、Type1 も許可されない。(C++11以降))。 Type1 と Type2 の型は、ForwardIt 型のオブジェクトをデリファレンスして、両方に暗黙的に変換できる必要があります。
型要件
- `ForwardIt` は LegacyForwardIterator の要件を満たさなければなりません。
- デリファレンスされた `ForwardIt` の型は、MoveAssignable の要件を満たす必要があります。

[edit] 戻り値

範囲の新しい終端を示す ForwardIt。

[edit] 計算量

std::distance(first, last) を $\scriptsize N$ $N$ とする

1,2)

max(0,N-1)

回の operator== による比較。

3,4)

max(0,N-1)

回の述語 p の適用。

[edit] 例外

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

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

[edit] 実装例

libstdc++、libc++、および MSVC STL の実装を参照してください。

unique (1)

template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last)
        if (!(*result == *first) && ++result != first)
            *result = std::move(*first);
 
    return ++result;
}

unique (3)

template<class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last)
        if (!p(*result, *first) && ++result != first)
            *result = std::move(*first);
 
    return ++result;
}

[edit] 注記

unique の呼び出しの後には、通常、コンテナから要素を実際に削除するために、コンテナの erase メンバ関数が呼び出されます。

[edit] 例

このコードを実行

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    // a vector containing several duplicate elements
    std::vector<int> v{1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    auto print = [&](int id)
    {
        std::cout << "@" << id << ": ";
        for (int i : v)
            std::cout << i << ' ';
        std::cout << '\n';
    };
    print(1);
 
    // remove consecutive (adjacent) duplicates
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print(2);
 
    // sort followed by unique, to remove all duplicates
    std::sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
    print(3);
 
    last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print(4);
}

出力

@1: 1 2 1 1 3 3 3 4 5 4
@2: 1 2 1 3 4 5 4
@3: 1 1 2 3 4 4 5
@4: 1 2 3 4 5

[edit] 不具合報告

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 202	C++98	要素が非同値関係で比較される場合、動作は不明瞭でした。	この場合の動作は未定義となる

[edit] 関連項目

adjacent_find	等しい（または指定された述語を満たす）最初の2つの隣接する項目を見つける (関数テンプレート) [編集]
unique_copy	連続する重複を含まない要素の範囲のコピーを作成する (関数テンプレート) [編集]
removeremove_if	特定の基準を満たす要素を削除する (関数テンプレート) [編集]
unique	連続する重複した要素を削除する (`std::list<T,Allocator>` のパブリックメンバ関数) [編集]
unique	連続する重複した要素を削除する (`std::forward_list<T,Allocator>` のパブリックメンバ関数) [編集]
ranges::unique (C++20)	範囲内の連続する重複要素を削除する (アルゴリズム関数オブジェクト)[編集]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作