並べ替えの STLアルゴリズム | Programming Place Plus C++編【標準ライブラリ】 第22章

C++編【標準ライブラリ】 第22章 並べ替えの STLアルゴリズム

先頭へ戻る

この章の概要

この章の概要です。


並べ替えの STLアルゴリズム

この章では、STLアルゴリズムの中から、要素の順序を変更するものを取り上げます。

なお、変更を行う STLアルゴリズム(第20章)と同じく、並べ替えの STLアルゴリズムは、連想コンテナに対しては使用できません

reverse

reverse関数は、指定の範囲内の要素の並び順を逆転させます。

namespace std {
    template <typename BidirectionalIterator>
    void reverse(BidirectionalIterator first, BidirectionalIterator last);
}

2つの引数で対象範囲を指定します。

なお、対象が std::list の場合には、reverseメンバ関数があるので、そちらを使った方が効率的です。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::reverse(v.begin(), v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

4
3
2
1
0

reverse_copy

reverse_copy関数は、指定した範囲内の要素の並び順を逆転させたものを、もう1つの範囲へコピーします。つまり、reverse関数と copy関数(第20章)が組み合わされたものです。

namespace std {
    template <typename BidirectionalIterator, typename OutputIterator>
    OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
}

第1,2引数でコピー元の範囲を、第3引数でコピー先の範囲の先頭を指定します。戻り値は、最後にコピーされた要素の次を指すイテレータです。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::vector<int> result(v.size());

    std::reverse_copy(v.begin(), v.end(), result.begin());
    std::for_each(result.begin(), result.end(), Println);
}

実行結果

4
3
2
1
0

rotate

rotate関数は、指定の範囲内の要素を、指定の要素が先頭に来るように回転させます。

namespace std {
    template <typename ForwardIterator>
    void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
}

第1引数と第3引数が対象の範囲です。第2引数には、新しく先頭に来る要素を指すイテレータを指定します。第2引数に指定したイテレータが、対象範囲内に含まれていない場合の動作は未定義なので注意して下さい

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::rotate(v.begin(), v.begin() + 2, v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

2
3
4
0
1

C++11(戻り値の変更)

C++11 で、rotate関数の戻り値の型が変更になっています。

namespace std {
    template <typename ForwardIterator>
    ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
}

返される値は、first + (last - middle) の結果です。

rotate_copy

rotate_copy関数は、指定の範囲内の要素を、指定の要素が先頭に来るように回転させたものを、もう1つの範囲へコピーします。つまり、rotate関数と copy関数(第20章)が組み合わされたものです。

namespace std {
    template <typename ForwardIterator, typename OutputIterator>
    OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
}

第1,3引数でコピー元の範囲を、第4引数でコピー先の範囲の先頭を指定します。第2引数には、新しく先頭に来る要素を指すイテレータを指定します。第2引数に指定したイテレータが、コピー元範囲に含まれていない場合の動作は未定義なので注意して下さい。戻り値は、最後にコピーされた要素の次を指すイテレータです。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::vector<int> result(v.size());

    std::rotate_copy(v.begin(), v.begin() + 2, v.end(), result.begin());
    std::for_each(result.begin(), result.end(), Println);
}

実行結果

2
3
4
0
1

partition

partition関数は、指定した範囲内の要素のうち、指定の条件を満たす要素を前方に集めます。

namespace std {
    template <typename BidirectionalIterator, typename Predicate>
    BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); 
}

第1、2引数に対象の範囲を指定します。第3引数には、単項叙述関数を指定し、前方に集める条件を記述します。戻り値は、条件が一致しなかった最初の要素を指すイテレータです。

関数の適用前の相対的な位置関係は維持されません。例えば、{0, 1, 2, 3, 4} というデータ列に対して、奇数を前方に集めた場合に、3 の方が 1 より前に来たり、2 が 4 より後に来たりする可能性があります。これが問題であれば、位置関係を維持する stable_partition関数を使用して下さい。

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

namespace {
    bool IsEven(int elem)
    {
        return elem % 2 == 0;
    }
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::partition(v.begin(), v.end(), IsEven);
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
4
2
3
1

C++11(イテレータの変更)

C++11 では、partition関数が使用するイテレータのカテゴリが変更されました。これまでは、2つの範囲を表現するために双方向イテレータ(第14章)が使われていましたが、前方イテレータ(第14章)に変更になっています。この変更は、無用な制約を緩和するものです。

namespace std {
    template <typename ForwardIterator, typename Predicate>
    ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); 
}

この変更は、VisualStudio 2015 は対応されていません。

stable_partition

stable_partition関数は、指定した範囲内の要素のうち、指定の条件を満たす要素を前方に集めます。

namespace std {
    template<typename BidirectionalIterator, typename Predicate>
    BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
}

第1、2引数に対象の範囲を指定します。第3引数には、単項叙述関数を指定し、前方に集める条件を記述します。戻り値は、条件が一致しなかった最初の要素を指すイテレータです。

partition関数と違い、関数の適用前の相対的な位置関係が維持されます。

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

namespace {
    bool IsEven(int elem)
    {
        return elem % 2 == 0;
    }
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::stable_partition(v.begin(), v.end(), IsEven);
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
2
4
1
3


sort

sort関数は、指定した範囲内の要素をソートします。

namespace std {
    template <typename RandomAccessIterator>
    void sort(RandomAccessIterator first, RandomAccessIterator last);

    template <typename RandomAccessIterator, typename Compare>
    void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
}

第1、2引数が対象の範囲です。

1つ目の形式の場合、要素の比較に <演算子を用いて、結果として、昇順にソートされます。

2つ目の形式の場合、第3引数に比較を行うための関数や関数オブジェクトを指定します。

sort関数は、一般的にクイックソート(アルゴリズムとデータ構造編【整列】第6章)によって実装されます。そのため、平均的な計算量は O(n log n) ですが、O(n2) のような悪い性能にもなり得ます。また、安定でないソートです。

一定した計算量が必要な場合には、partial_sort関数を、安定なソートが必要な場合には、stable_sort関数を使って下さい。

実装に用いるアルゴリズムが明確に定められている訳ではありません。

また、sort関数が使うイテレータはランダムアクセスイテレータ(第14章)なので、std::list には使用できません。std::list が対象の場合には、メンバ関数版の sort(第6章)を使います。なお、メンバ関数版の sort は、安定なソートです。

1つ目の形式は、次のように使用します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(3);
    v.push_back(2);
    v.push_back(4);
    v.push_back(0);
    v.push_back(1);

    std::sort(v.begin(), v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
1
2
3
4

2つ目の形式の場合は、例えば次のように使います。

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

namespace {
    bool LessLength(const std::string& s1, const std::string& s2)
    {
        return s1.length() < s2.length();
    }

    void Println(const std::string& elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<std::string> v;
    v.push_back("aaaa");
    v.push_back("aaaaa");
    v.push_back("a");
    v.push_back("");
    v.push_back("aaa");

    std::sort(v.begin(), v.end(), LessLength);
    std::for_each(v.begin(), v.end(), Println);
}

実行結果


a
aaa
aaaa
aaaaa

stable_sort

stable_sort関数は、指定した範囲内の要素をソートします。

namespace std {
    template <typename RandomAccessIterator>
    void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

    template <typename RandomAccessIterator, typename Compare>
    void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
}

使い方は sort関数とまったく同じです。違いは、sort関数が(一般的には)クイックソートに基づいており、安定でないソートを行うのに対し、stable_sort関数は(一般的には)マージソート(アルゴリズムとデータ構造編【整列】第7章)に基づいており、安定なソートを行うことです

普通、クイックソートよりマージソートの方が遅いですが、クイックソートの方はデータの内容によって性能が上下しやすいという面があります(どの程度のふり幅があるかは実装次第です)。

partial_sort

partial_sort関数は、指定の範囲内の要素を、その範囲内の更に一部分に関してのみ、ソート済みの状態にします。

namespace std {
    template <typename RandomAccessIterator>
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

    template <typename RandomAccessIterator, typename Compare>
    void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
}

第1、3引数が対象範囲で、第2引数にソート済みになる範囲の末尾を指定します。

sort関数や、stable_sort関数と同様、比較関数を指定しない形式では <演算子を使った比較により、昇順にソートされます。比較関数を指定する場合は、その実装に従います。

この関数の動作は少し分かりづらいかも知れません。対象範囲全体(第1、3引数で指定)をソートしますが、ソート済みになるのは、第1、2引数で指定した範囲だけです。このような動作になっていることで、先頭の数個の要素だけがソートされていれば良いという場面においては、不必要なソート処理を省略することができて、パフォーマンスの向上が見込めます。

partial_sort関数は、一般的にはヒープソート(アルゴリズムとデータ構造編【整列】第8章)によって実装されます。

ヒープソートの計算量は O(n log n) です。また、安定でないソートです

もし、計算量を一定にしたいということを理由に、sort関数の代わりに使うのであれば、第2引数を、第3引数と同じにすれば、範囲全体をソートできます。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(3);
    v.push_back(2);
    v.push_back(4);
    v.push_back(0);
    v.push_back(1);

    std::partial_sort(v.begin(), v.begin() + 2, v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
1
4
3
2

nth_element

nth_element関数は、指定範囲内の要素をソートしたとき、指定の位置に正しい要素が来るようにします。このとき、ソート後に指定位置より前方にあるべき要素は実際にそうなり、後方にあるべき要素も後方に集まります。ただし、実際にソートが行われる訳ではありません。

namespace std {
    template <typename RandomAccessIterator>
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

    template <typename RandomAccessIterator, typename Compare>
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
}

第1、3引数が対象の範囲です。第2引数に、その範囲内の要素を指すイテレータを指定します。

この関数の動作は分かりづらいですが、例えば、上位n位までの要素が何であるかを、(その具体的な順位は考えずに)調べたり、n位に満たない要素が手前の方に 混入しないように切り分けるために使えます。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(2);
    v.push_back(1);
    v.push_back(3);
    v.push_back(4);
    v.push_back(0);

    std::nth_element(v.begin(), v.begin() + 2, v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

1
0
2
4
3

この使い方の場合、基準は (begin + 2) なので、先頭付近の3つの要素が、要素全体における上位3つになっています。この3つも、それ以外の2つについても、ソートされている保証はありません。

random_shuffle

random_shuffle関数は、指定した範囲内の要素を、乱数ジェネレータを用いてランダムに並び替えます。

C++14 で、この関数は非推奨となっています。

namespace std {
    template <typename RandomAccessIterator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); 

    template <typename RandomAccessIterator, typename RandomNumberGenerator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
}

1つ目の形式の場合は、対象範囲の指定だけです。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::random_shuffle(v.begin(), v.end());
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

4
1
3
2
0

2つ目の形式では、第3引数に乱数を生成するための関数オブジェクトを指定します。乱数を生成する際、rand(n) のように呼び出されます。ここで n は、iterator_traits<RandomAccessIterator>::difference_type型の値です。0以上 n未満の値を返すように実装して下さい

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

namespace {
    class Random {
    public:
        Random()
        {
            std::srand(static_cast<unsigned int>(std::time(NULL)));
        }

        unsigned int operator()(unsigned int max)
        {
            double tmp = static_cast<double>(std::rand()) / static_cast<double>(RAND_MAX);
            return static_cast<unsigned int>(tmp * max);
        }
    };

    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    Random r;
    std::random_shuffle(v.begin(), v.end(), r);
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
4
1
2
3

C++11(引数の変更)

C++11 になって、第3引数の型が変更されました。

namespace std {
    template <typename RandomAccessIterator, typename RandomNumberGenerator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& rand);
}

C++14(非推奨化)

C++14 になり、random_shuffle関数は非推奨となり、代わりに shuffle関数を使うことが推奨されています。

C++14 では、std::rand関数、std::srand関数についても非推奨となっており、これらと結びつきのある random_shuffle関数も非推奨となりました。

C++11 (shuffle)

C++11

C++11 で追加された shuffle関数は、指定した範囲内の要素を、指定の乱数ジェネレータを用いてランダムに並び替えます。

namespace std {
    template <typename RandomAccessIterator, typename UniformRandomNumberGenerator>
    void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g);
}

第1、2引数が対象の範囲です。第3引数には乱数ジェネレータを指定しますが、C++11 には標準の乱数生成クラスがあるので、それを使うのが普通です。

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

int main()
{
    std::vector<int> v = { 0, 1, 2, 3, 4 };

    std::shuffle(v.begin(), v.end(), std::mt19937());
    std::for_each(v.begin(), v.end(), [](int elem){ std::cout << elem << std::endl; });
}

実行結果

4
0
3
1
2


練習問題

問題① std::list に対して partial_sort関数を適用することはできませんし、std::list に同じことを行うメンバ関数もありません。この解決のために、一旦、std::vector に要素をコピーし、アルゴリズムの適用後に書き戻す方法があります。この方法で実装してみて下さい。


解答ページはこちら

参考リンク



更新履歴

'2018/4/5 VisualStudio 2013 の対応終了。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

'2017/3/25 VisualC++ 2017 に対応。

'2016/11/27 新規作成。



前の章へ(第21章 削除の STLアルゴリズム)

次の章へ(第23章 ソートされた範囲を扱う STLアルゴリズム)

C++編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS