C++0x More STL Algorithm

C++0x で追加される STL アルゴリズム

・find_if_not
　find_if の逆． pred(*i) == false のイテレータを返す

template<class InputIterator, class Predicate>
inline InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred)
{
    while (first != last && pred(*first))
        ++first;

    return first;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

int main()
{
    vector<int> v;

    v.push_back(2);
    v.push_back(4);
    v.push_back(6);
    v.push_back(3); // ※
    v.push_back(8);

    vector<int>::iterator it = find_if_not(v.begin(), v.end(), &is_even); // *it == 3

    return 0;
}

・all_of
　範囲全ての要素が pred(*i) == true なら true 、それ以外なら false を返す

template <class InputIterator, class Predicate>
inline bool all_of(InputIterator first, InputIterator last, Predicate pred)
{
    return find_if_not(first, last, pred) == last;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

// 正数？
bool is_plus(int value) { return value > 0; }

int main()
{
    vector<int> v;

    v.push_back(-2);
    v.push_back(2);
    v.push_back(4);

    bool even = all_of(v.begin(), v.end(), &is_even); // true
    bool plus = all_of(v.begin(), v.end(), &is_plus); // false

    return 0;
}

・none_of
　範囲全ての要素が pred(*i) == false なら true 、それ以外なら false を返す

template <class InputIterator, class Predicate>
inline bool none_of(InputIterator first, InputIterator last, Predicate pred)
{
    return find_if(first, last, pred) == last;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

// 正数？
bool is_plus(int value) { return value > 0; }

int main()
{
    vector<int> v;

    v.push_back(-1);
    v.push_back(1);
    v.push_back(3);

    bool even = none_of(v.begin(), v.end(), &is_even); // true
    bool plus = none_of(v.begin(), v.end(), &is_plus); // false

    return 0;
}

・any_of
　範囲内で pred(*i) == true のものがあったら true 、それ以外は false を返す

template <class InputIterator, class Predicate>
inline bool any_of(InputIterator first, InputIterator last, Predicate pred)
{
    return !none_of(first, last, pred);
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

// 正数？
bool is_plus(int value) { return value > 0; }

int main()
{
    vector<int> v;

    v.push_back(-1);
    v.push_back(1);
    v.push_back(3);

    bool even = any_of(v.begin(), v.end(), &is_even); // false
    bool plus = any_of(v.begin(), v.end(), &is_plus); // true

    return 0;
}

・copy_n
　先頭から N 個をコピー

template<class InputIterator, class Size, class OutputIterator>
inline OutputIterator copy_n(InputIterator first, Size n, OutputIterator result)
{
    for (; n > 0; --n)
        *result++ = *first++;

    return result;
}

#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int> c;
    copy_n(v.begin(), 3, back_inserter(c)); // c == 1, 2, 3

    return 0;
}

・copy_if
　指定範囲の pred(*i) == true の要素をコピー

template<class InputIterator, class OutputIterator, class Predicate>
inline OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred)
{
    while (first != last) {
        if (pred(*first))
            *result++ = *first;
        ++first;
    }
    return result;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int> c;
    copy_if(v.begin(), v.end(), back_inserter(c), &is_even); // c == 2, 4

    return 0;
}

・uninitialized_copy_n

　uninitialized_copy の N 個版． first から n 個を配置 new で初期化する

template<class InputIterator, class Size, class ForwardIterator>
inline ForwardIterator uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result)
{
    for (; n > 0; ++result, ++first, --n) {
        new (static_cast<void*>(&*result)) typename iterator_traits<ForwardIterator>::value_type(*first);
    }
    return result;
}

#include <iostream>
#include <algorithm>
#include <memory>

using namespace std;

class integer {
public:
    integer(int value) : value_(value) {}
    int get() const { return value_; }
private:
    int value_;
};

void disp(const integer& value)
{
    cout << value.get() << endl;
}

int main()
{
    const int size = 3;
    int ar[size] = {3, 1, 4};

    integer* par = (integer*)malloc(size * sizeof(int));

//  uninitialized_copy(ar, ar + size, par);
    uninitialized_copy_n(ar, size, par);

    for_each(par, par + size, &disp); // 3, 1, 4

    free(par);
    return 0;
}

・partition_copy
　指定範囲を pred(*i) == true の要素と、 pred(*i) == false の要素に分ける

template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
inline pair<OutputIterator1, OutputIterator2>
    partition_copy(InputIterator first, InputIterator last,
                   OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred)
{
    while (first != last) {
        if (pred(*first))
            *out_true++ = *first++;
        else
            *out_false++ = *first++;
    }

    return make_pair(out_true, out_false);
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int> evens;
    vector<int> odds;
    partition_copy(v.begin(), v.end(), back_inserter(evens), back_inserter(odds), &is_even);
        // evens == 2, 4
        // odds  == 1, 3, 5

    return 0;
}

・is_partitioned
　指定範囲が pred(*i) == true の要素と、 pred(*i) == false の要素に分かれていたら true 、それ以外は false を返す

template <class InputIterator, class Predicate>
inline bool is_partitioned(InputIterator first, InputIterator last, Predicate pred)
{
    return find_if(find_if_not(first, last, pred), last, pred) == last;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int> evens;
    vector<int> odds;
    partition_copy(v.begin(), v.end(), back_inserter(evens), back_inserter(odds), &is_even);

    bool partition1 = is_partitioned(v.begin(),     v.end(),     &is_even); // false
    bool partition2 = is_partitioned(evens.begin(), evens.end(), &is_even); // true
    bool partition3 = is_partitioned(odds.begin(),  odds.end(),  &is_even); // true

    partition(v.begin(), v.end(), &is_even);
    bool partition4 = is_partitioned(v.begin(), v.end(), &is_even); // true

    return 0;
}

・partition_point
　pred(*i) == true と pred(*i) == false で分かれている位置を返す( std::partition で分けられている必要がある)

template<class ForwardIterator, class Predicate>
inline ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred)
{
    typedef typename iterator_traits<ForwardIterator>::difference_type distance_type;

    distance_type len = distance(first, last);
    distance_type half;
    ForwardIterator middle;

    while (len > 0) {
        half = len >> 1;
        middle = first;

        advance(middle, half);
        if (pred(*middle)) {
            first = middle;
            ++first;
            len = len - half -1;
        }
        else {
            len = half;
        }
    }

    return first;
}

#include <vector>
#include <algorithm>

using namespace std;

// 偶数？
bool is_even(int value) { return value % 2 == 0; }

int main()
{
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    partition(v.begin(), v.end(), &is_even); // 4, 2, 3, 1, 5

    vector<int>::iterator it = partition_point(v.begin(), v.end(), &is_even); // *it == 3

    return 0;
}

・iota
　指定範囲の各要素を、インクリメントされた value で置き換える

template <class ForwardIterator, class T>
inline void iota(ForwardIterator first, ForwardIterator last, T value)
{
    while (first != last) {
        *first++ = value++;
    }
}

#include <vector>
#include <numeric>

using namespace std;

int main()
{
    vector<int> v(5);
    iota(v.begin(), v.end(), 1); // 1, 2, 3, 4, 5

    return 0;
}

# iota ってどういう意味だろ？読みはイオタ？

N2666 More STL algorithms (revision 2)(日本語訳)

C++0x言語拡張まとめ