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

トップページC++編

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 と更新されており、今後も 3年ごとに更新されます。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要

この章の概要です。


並べ替えの 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

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

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

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


練習問題

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


解答ページはこちら

参考リンク


更新履歴

’2019/2/12 VisualStudio 2015 の対応終了。

’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 に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る