アルゴリズム
アルゴリズム

C++03規格時点で存在したアルゴリズム関連ライブラリに対するC++11規格での変更点をまとめています。

概要
<algorithm>
<functional>
<iterator>

概要 †

当文書では、主にコンテナに対して適用可能なアルゴリズムを提供する <algorithm> と、アルゴリズムに関連する機能を提供する <functional> および <iterator> について、C++11規格での変更点をまとめている。

多くのアルゴリズムはアルゴリズム適用範囲を表す2つのイテレータを引数として受け取る。
1つ目のイテレータは適用範囲の開始位置を、2つ目のイテレータは終端位置をそれぞれ指す（終端位置自体は適用範囲に含まれない）。
当文書中では、この2引数をまとめてコンテナ範囲と呼ぶ。

アルゴリズムの中には関数オブジェクトを引数にとるものがあり、それらにはC++11規格の言語機能であるラムダ式によって作成された関数オブジェクトを渡すことも可能である。
例えば、 int 型の値を保持するコンテナクラス型（あるいは固定長配列型）のインスタンス nums の中から値が 0 以上 100 未満の要素を検索するコードは下記のように書くことができる。

auto itr = find_if(begin(nums), end(nums), [](int n){ return (n >= 0 && n < 100); });
if (itr != end(nums)) { /* 見つかった */ }

↑

<algorithm> †

文中の「x を満たす」とは、 if (x) にヒットする（即ち (x) != false である）ことを表す。

下記の関数が定義された。

// コンテナ範囲の全要素が pred(value) を満たすか否かを調べる。
// コンテナ範囲が空の場合は常に true を返す。
template<class InputIterator, class UnaryPredicate>
bool all_of(InputIterator first, InputIterator last, UnaryPredicate pred);

// コンテナ範囲の要素のうち1個以上が pred(value) を満たすか否かを調べる。
// コンテナ範囲が空の場合は常に false を返す。
template<class InputIterator, class UnaryPredicate>
bool any_of(InputIterator first, InputIterator last, UnaryPredicate pred);

// コンテナ範囲の全要素が pred(value) を満たさないか否かを調べる。
// コンテナ範囲が空の場合は常に true を返す。
template<class InputIterator, class UnaryPredicate>
bool none_of(InputIterator first, InputIterator last, UnaryPredicate pred);

// コンテナ範囲のうち pred(value) を満たさない最初の要素を検索する。
// 見つかればその要素を指すイテレータを返し、見つからなければ last を返す。
template<class InputIterator, class UnaryPredicate>
InputIterator find_if_not(InputIterator first, InputIterator last, UnaryPredicate pred);

// [first1, last1) のコンテナ範囲に対して、
// first2 から始まる同個数のコンテナ範囲がその順列となっているか否かを調べる。
// 即ち2コンテナ間で同値の要素が過不足なく存在すれば true を返す(順序は問わない)。
// 要素の比較には == 演算子を用いる。
template<class InputIterator1, class InputIterator2>
bool is_permutation(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

// 上記関数のオーバロード。
// 要素の比較に == 演算子ではなく pred(value1, value2) を満たすか否かを用いる。
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool is_permutation(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    BinaryPredicate pred);

// first から始まる num 個の要素を result から始まるコンテナ範囲へコピーし、
// コピー先のコピー終端位置を返す。
template<class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size num, OutputIterator result);

// [first, last) のコンテナ範囲のうち pred(value) を満たす要素を
// result から始まるコンテナ範囲へコピーし、コピー先のコピー終端位置を返す。
template<class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator copy_if(
    InputIterator first,
    InputIterator last,
    OutputIterator result,
    UnaryPredicate pred);

// [first, last) のコンテナ範囲を result から始まるコンテナ範囲へムーブし、
// ムーブ先のムーブ終端位置を返す。
// ムーブ元の各要素の状態は不定となる。
template<class InputIterator, class OutputIterator>
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);

// [first, last) のコンテナ範囲を result を終端とするコンテナ範囲へ後ろからムーブし、
// ムーブ先のムーブ先頭位置(ムーブ元の first に該当する位置)を返す。
// ムーブ元の各要素の状態は不定となる。
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 move_backward(
    BidirectionalIterator1 first,
    BidirectionalIterator1 last,
    BidirectionalIterator2 result);

// 乱数ジェネレータ urng を用いてコンテナ範囲をランダムに並べ替える。
template<class RandomAccessIterator, class URNG>
void shuffle(RandomAccessIterator first, RandomAccessIterator last, URNG&& urng);

// コンテナ範囲のうちすべての pred(value) を満たす要素が、
// すべての pred(value) を満たさない要素よりも前方にあるか否かを調べる。
// 満たす要素のみ、あるいは満たさない要素のみ存在する場合も true を返す。
// コンテナ範囲が空の場合は常に true を返す。
template<class InputIterator, class UnaryPredicate>
bool is_partitioned(InputIterator first, InputIterator last, UnaryPredicate pred);

// [first, last) のコンテナ範囲のうち
// pred(value) を満たす要素を result_true から始まるコンテナ範囲へ、
// pred(value) を満たさない要素を result_false から始まるコンテナ範囲へ
// それぞれコピーし、コピー先のコピー終端位置のペアを返す。
template<
    class InputIterator,
    class OutputIterator1,
    class OutputIterator2,
    class UnaryPredicate>
pair<OutputIterator1, OutputIterator2> partition_copy(
    InputIterator first,
    InputIterator last,
    OutputIterator1 result_true,
    OutputIterator2 result_false,
    UnaryPredicate pred);

// コンテナ範囲が is_partitioned(first, last, pred) を満たすものとして、
// pred(value) を満たさない最初の要素を検索する。
// コンテナ範囲が空の場合や、全要素が pred(value) を満たす場合は last を返す。
template<class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point(
    ForwardIterator first,
    ForwardIterator last,
    UnaryPredicate pred);

// コンテナ範囲が昇順にソートされているか否かを調べる。
// 要素数が2個未満の場合は常に true を返す。
// 要素の大小比較には < 演算子を用いる。
template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 未満であるものとする。
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

// コンテナ範囲のうち昇順にソートされていない最初の要素を検索する。
// 全要素が昇順にソートされている場合や要素数が2個未満の場合は last を返す。
// 要素の大小比較には < 演算子を用いる。
template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 未満であるものとする。
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(
    ForwardIterator first,
    ForwardIterator last,
    Compare comp);

// コンテナ範囲がヒープ構造を満たしているか否かを調べる。
// 即ちコンテナ範囲を c としたとき、その全要素について
// c[i] が c[i*2+1] 以上かつ c[i*2+2] 以上であれば true を返す。
// 要素数が2個未満の場合は常に true を返す。
// 要素の大小比較には < 演算子を用いる。
template<class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 未満であるものとする。
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

// コンテナ範囲のうちヒープ構造を満たしていない最初の要素を検索する。
// 全要素がヒープ構造を満たす場合や要素数が2個未満の場合は last を返す。
// 要素の大小比較には < 演算子を用いる。
template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(
    RandomAccessIterator first,
    RandomAccessIterator last);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 未満であるものとする。
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare comp);

// a と b のうち小さい方を第1要素、大きい方を第2要素とするペアを返す。
// 大小比較には < 演算子を用いる。
template<class T>
pair<const T&, const T&> minmax(const T& a, const T& b);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(a, b) を満たすか否かを用いる。
// comp(a, b) を満たすならば a は b より小さいものとする。
template<class T, class Compare>
pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);

// values の要素のうち最小値を第1要素、最大値を第2要素とするペアを返す。
// 大小比較には < 演算子を用いる。
template<class T>
pair<T, T> minmax(initializer_list<T> values);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 より小さいものとする。
template<class T, class Compare>
pair<T, T> minmax(initializer_list<T> values, Compare comp);

// コンテナ範囲の要素のうち最小値を指すイテレータを第1要素、
// 最大値を指すイテレータを第2要素とするペアを返す。
// 大小比較には < 演算子を用いる。
template<class ForwardIterator>
pair<ForwardIterator, ForwardIterator> minmax_element(
    ForwardIterator first,
    ForwardIterator last);

// 上記関数のオーバロード。
// 要素の大小比較に < 演算子ではなく comp(value1, value2) を満たすか否かを用いる。
// comp(value1, value2) を満たすならば value1 は value2 より小さいものとする。
template<class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator> minmax_element(
    ForwardIterator first,
    ForwardIterator last,
    Compare comp);

下記の関数オーバロードが定義された。

template<class T> T min(initializer_list<T> values);
template<class T, class Compare> T min(initializer_list<T> values, Compare comp);
template<class T> T max(initializer_list<T> values);
template<class T, class Compare> T max(initializer_list<T> values, Compare comp);

関数 swap が <utility> に移動した。
ただし既存の多くの処理系ではC++03規格以前のコードを利用できるように #include <algorithm> のみでも利用可能になっていると思われる。
関数 find_first_of の定義が変更され、検索対象となるコンテナ範囲（第1引数および第2引数）のイテレータ要件が ForwardIterator から InputIterator になった。
検索要素となるコンテナ範囲（第3引数および第4引数）のイテレータ要件は ForwardIterator のままである。
関数 fill_n および generate_n の定義が変更され、値設定範囲の終端を指すイテレータを戻り値として返すようになった。
関数 rotate の定義が変更され、元の先頭要素の移動先を指すイテレータを戻り値として返すようになった。

関数 random_shuffle の定義が一部変更された。

// C++03
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(
    RandomAccessIterator first,
    RandomAccessIterator last,
    RandomNumberGenerator& gen);

// C++11
// 第3引数の型が RandomNumberGenerator& から RandomNumberGenerator&& に変更
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(
    RandomAccessIterator first,
    RandomAccessIterator last,
    RandomNumberGenerator&& gen);

関数 partition の定義が変更され、コンテナ範囲と戻り値のイテレータ要件が BidirectionalIterator から ForwardIterator になった。

↑

<functional> †

文中で型名が unspecified となっているものは処理系依存の型であることを表す。
関数の戻り値等として変数に受け取りたい場合は下記のように auto を用いる。

auto less_than_zero = bind(less<int>(), std::placeholders::_1, 0);

名前空間 std::placeholders が定義された。
関数 bind の引数として用いるプレースホルダのインスタンスが定義されている。

namespace std
{
    namespace placeholders
    {
        extern unspecified _1;
        extern unspecified _2;
        extern unspecified _3;
        // ...
    }
}

下記のクラステンプレートが定義された。

// 2引数を受け取りビット演算を行う関数オブジェクトクラス群。
template<class T> struct bit_and;   // a & b
template<class T> struct bit_or;    // a | b
template<class T> struct bit_xor;   // a ^ b

// 関数オブジェクトまたは関数ポインタを保持する関数オブジェクトクラス。
template<class T> function; // 未定義
template<class Ret, class ...Args> class function<Ret (Args...)>;

// 型のハッシュ値計算処理を行う関数オブジェクトクラス。
template<class T> struct hash; // 未定義
template<> struct hash<bool>;
template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
template<> struct hash<char16_t>;
template<> struct hash<char32_t>;
template<> struct hash<wchar_t>;
template<> struct hash<short>;
template<> struct hash<unsigned short>;
template<> struct hash<int>;
template<> struct hash<unsigned int>;
template<> struct hash<long>;
template<> struct hash<unsigned long>;
template<> struct hash<long long>;
template<> struct hash<unsigned long long>;
template<> struct hash<float>;
template<> struct hash<double>;
template<> struct hash<long double>;
template<class T> struct hash<T*>;

// T が bind によって生成された関数オブジェクトの型であるか否かを提供する。
// 静的メンバ定数 value で判別結果の bool 値を取得できる。
template<class T> struct is_bind_expression;

// T が bind の引数として用いるプレースホルダの型であればそのオーダー値を、
// そうでなければ 0 を提供する。
// 静的メンバ定数 value で結果の int 値を取得できる。
template<class T> struct is_placeholder;

// is_placeholder<decltype(std::placeholders::_1)>::value == 1
// is_placeholder<decltype(std::placeholders::_2)>::value == 2
// is_placeholder<int>::value == 0

// 型 T の参照のように振る舞いつつ、アドレスベースのコピーが可能なクラス。
// テンプレート引数に参照を渡したい場合に ref や cref によって生成する。
template<class T> class reference_wrapper;

exception クラスを継承した bad_function_call クラスが定義された。

下記の関数が定義された。

// 引数を固定値あるいはプレースホルダで束縛した関数オブジェクトを作成する。
template<class Func, class ...Args>
unspecified bind(Func&& func, Args&&... args);

// 戻り値の型を明示するバージョン。
template<class Ret, class Func, class ...Args>
unspecified bind(Func&& func, Args&&... args);

// 型 T のメンバへのポインタから、第1引数に T& や T* 等をとる関数オブジェクトを作成する。
// メンバ関数へのポインタを渡すと、それを呼び出す関数オブジェクトになる。
// メンバ変数へのポインタを渡すと、その値を取得する関数オブジェクトになる。
template<class Ret, class T>
unspecified mem_fn(Ret T::* mfunc);

// value の参照を保持する reference_wrapper を作成する。
// テンプレート引数に参照を渡したい場合に用いる。
template<class T>
reference_wrapper<T> ref(T& value) noexcept;
template<class T>
reference_wrapper<T> ref(reference_wrapper<T>& value) noexcept;
template<class T> void ref(const T&&) = delete;

// value の const 参照を保持する reference_wrapper を作成する。
// テンプレート引数に const 参照を渡したい場合に用いる。
template<class T>
reference_wrapper<const T> cref(const T& value) noexcept;
template<class T>
reference_wrapper<const T> cref(reference_wrapper<const T>& value) noexcept;
template<class T> void cref(const T&&) = delete;

下記の定義が非推奨となった。
- unary_function
- binary_function
- binder1st
- binder2nd
- bind1st
- bind2nd
- pointer_to_unary_function
- pointer_to_binary_function
- ptr_fun
- mem_fun_t
- mem_fun1_t
- const_mem_fun_t
- const_mem_fun1_t
- mem_fun
- mem_fun_ref_t
- mem_fun1_ref_t
- const_mem_fun_ref_t
- const_mem_fun1_ref_t
- mem_fun_ref
unary_function や binary_function を継承して実装されていた関数オブジェクトクラス（unary_negate や less 等）が、それらを継承せずに実装されるようになった。
処理内容に変更はない。

↑

<iterator> †

文中で型名が unspecified となっているものは処理系依存の型であることを表す。

すべてのイテレータの要件に、関数 swap による値の交換が可能であることが定められた。

下記のクラステンプレートが定義された。

// * 演算子による間接参照時にムーブを行うイテレータアダプタクラス。
// 間接参照以外は基となるイテレータそのものの動作を行う。
template<class Iterator>
class move_iterator;

下記の関数が定義された。

// コンテナ c の先頭要素を指すイテレータを取得する。
template<class Container>
auto begin(Container& c) -> decltype(c.begin());
template<class Container>
auto begin(const Container& c) -> decltype(c.begin());
template<class T, size_t N>
T* begin(T (&c)[N]);

// コンテナ c の終端位置を指すイテレータを取得する。
template<class Container>
auto end(Container& c) -> decltype(c.end());
template<class Container>
auto end(const Container& c) -> decltype(c.end());
template<class T, size_t N>
T* end(T (&c)[N]);

// イテレータ itr より count の数だけ前方のイテレータを取得する。
template<class BidirectionalIterator>
BidirectionalIterator prev(
    BidirectionalIterator itr,
    typename iterator_traits<BidirectionalIterator>::difference_type count = 1);

// イテレータ itr より count の数だけ進んだイテレータを取得する。
template<class ForwardIterator>
ForwardIterator next(
    ForwardIterator itr,
    typename iterator_traits<ForwardIterator>::difference_type count = 1);

// itr をラップする move_iterator を作成する。
template<class Iterator>
move_iterator<Iterator> make_move_iterator(const Iterator& itr);

クラステンプレート reverse_iterator のメンバ関数 operator[] の定義が変更され、戻り値の型が reference から処理系依存の型に変更された。
下記のクラステンプレートのコピー代入演算子の引数型が container_type::const_reference から const container_type::value_type& に変更された。
また、 container_type::value_type&& を引数にとるムーブ代入演算子が定義された。
- front_insert_iterator
- back_insert_iterator
- insert_iterator
クラステンプレート istream_iterator のコンストラクタの定義が下記のように変更された。
- 引数なしのデフォルトコンストラクタは value_type がリテラル型の場合に限り constexpr コンストラクタとなる。
- コピーコンストラクタは default 指定される。

クラステンプレート istreambuf_iterator のメンバ型の定義が一部変更された。

// C++03
typedef char_type* pointer;
typedef char_type& reference;

// C++11
typedef unspecified pointer;
typedef char_type   reference;

関数 inserter の定義が変更された。

// C++03
template<class Container, class Iterator>
insert_iterator<Container> inserter(Container& c, Iterator itr);

// C++11
// 第2引数の型が任意の型から Container::iterator に変更。
template<class Container>
insert_iterator<Container> inserter(Container& c, typename Container::iterator itr);

クラステンプレート reverse_iterator を引数にとる下記の関数の定義が変更された。

// C++03
template<class Iterator>
bool operator==(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
bool operator!=(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
bool operator<(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
bool operator<=(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
bool operator>(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
bool operator>=(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);
template<class Iterator>
typename reverse_iterator<Iterator>::difference_type operator-(
    const reverse_iterator<Iterator>& a,
    const reverse_iterator<Iterator>& b);

// C++11
// a と b が異なる iterator_type でもよくなった。
// operator- の戻り値の型が演算結果に依存するようになった。
template<class Iterator1, class Iterator2>
bool operator==(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
bool operator!=(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
bool operator<(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
bool operator<=(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
bool operator>(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
bool operator>=(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b);
template<class Iterator1, class Iterator2>
auto operator-(
    const reverse_iterator<Iterator1>& a,
    const reverse_iterator<Iterator2>& b) -> decltype(b.base() - a.base());

ルーチェ's Homepage

サイトツリー

最新の10件

Home / プログラミング / C++ / C++11 既存ライブラリ変更点 / アルゴリズム
アルゴリズム

概要 †

<algorithm> †

<functional> †

<iterator> †

ルーチェ's Homepage

サイトツリー

最新の10件

Home / プログラミング / C++ / C++11 既存ライブラリ変更点 / アルゴリズムアルゴリズム

概要 †

<algorithm> †

<functional> †

<iterator> †

Home / プログラミング / C++ / C++11 既存ライブラリ変更点 / アルゴリズム
アルゴリズム