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

トップページ – C++編

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

この章の概要 🔗

この章の概要です。


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

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

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

reverse 🔗

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

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

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

なお、対象が 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関数は、指定した範囲内の要素の並び順を逆転させたものを、もう１つの範囲へコピーします。つまり、reverse関数と copy関数（第２０章）が組み合わされたものです。

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

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

#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);
}

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

#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関数は、指定の範囲内の要素を、指定の要素が先頭に来るように回転させたものを、もう１つの範囲へコピーします。つまり、rotate関数と copy関数（第２０章）が組み合わされたものです。

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

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

#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);
}

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

関数の適用前の相対的な位置関係は維持されません。たとえば、{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);
}

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

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);
}

第１、２引数が対象の範囲です。

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

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

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

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

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

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

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

#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

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

#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関数は（一般的には）マージソート📘（アルゴリズムとデータ構造編【整列】第７章）に基づいており、安定なソートをおこなうことです。

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

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);
}

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

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

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

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

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

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

#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);
}

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

この関数の動作は分かりづらいですが、たとえば、上位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) なので、先頭付近の３つの要素が、要素全体における上位３つになっています。この３つも、それ以外の２つについても、ソートされている保証はありません。

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);
}

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

#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

２つ目の形式では、第３引数に乱数を生成するための関数オブジェクトを指定します。乱数を生成する際、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 に要素をコピーし、アルゴリズムの適用後に書き戻す方法があります。この方法で実装してみてください。


解答ページはこちら。

参考リンク 🔗


更新履歴 🔗


前の章へ　（第２１章　削除の STLアルゴリズム）

次の章へ　（第２３章　ソートされた範囲を扱う STLアルゴリズム）

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

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る