STLアルゴリズム練習帳 by iijima

■要素の並べ替え
reverse, rotate, random_shuffle

STLにはシーケンスコンテナの要素を並べ替えるアルゴリズムがいくつか用意されている．
ここでは，「逆転」reverse，「回転」rotate，「シャッフル（撹拌）」random_shuffleを取り上げる．
reverse, rotateは双方向反復子を持つシーケンスコンテナ（vector, deque, list）に適用でき，
random_shuffleは，そのうちランダムアクセス反復子を持つシーケンスコンテナ（vector, deque）に適用できる．
また，文字列（std::stringオブジェクト）や配列も，ランダムアクセス反復子を持つシーケンスコンテナとして扱える．

【例題１】要素の順序を逆転する(reverse)
【例題２】要素の順序を回転する(rotate)
【例題３】要素の順序をシャッフルする(rondom_shuffle)


【例題１】要素の順序を逆転する(reverse)

要素を並べ替えずに逆順で出力するだけなら逆反復子（reverse iterator）を使うのが簡便．
ただし，組み込み配列には逆反復子はないので，ポインタを逆順に辿る．

// シーケンス生成用の関数オブジェクト（「■データコレクションの生成」参照）
template < typename T >
class Increment
{
    T val_;
public:
    Increment( const T& init ) : val_( init ){}
    T operator()(){ return val_++; }
};

// List 1
#include <vector>
#include <list>
#include <string>
#include <iostream>
#include <algorithm>

int main()
{
    std::vector< int > seq_v;
    std::generate_n( std::back_inserter( seq_v ), 10, Increment< int >( 1 ) );

    std::list< double > seq_l;
    std::generate_n( std::back_inserter( seq_l ), 10, Increment< double >( 1.5 ) );

    std::string str1; // 文字列
    std::generate_n( std::back_inserter( str1 ), 26, Increment< char >( 'a' ) );

    char str2[27];    // 配列
    std::generate( str2, str2 + 26, Increment< char >( 'A' ) );
    *(str2 + 26) = '\0';

    std::cout << "original:\n";
    std::copy( seq_v.begin(), seq_v.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::copy( seq_l.begin(), seq_l.end(), std::ostream_iterator< double >( std::cout, " " ) );
    std::cout << std::endl;

    std::cout << str1 << std::endl;

    std::cout << str2 << std::endl;

    std::cout << "reverse:\n";
    std::copy( seq_v.rbegin(), seq_v.rend(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::copy( seq_l.rbegin(), seq_l.rend(), std::ostream_iterator< double >( std::cout, " " ) );
    std::cout << std::endl;

    std::copy( str1.rbegin(), str1.rend(), std::ostream_iterator< char >( std::cout, "" ) );
    std::cout << std::endl;

    for( char* p = str2 + 25; p >= str2; --p ){
        std::cout << *p;
    }
    std::cout << std::endl;
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 10.5
abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
reverse:
10 9 8 7 6 5 4 3 2 1
10.5 9.5 8.5 7.5 6.5 5.5 4.5 3.5 2.5 1.5
zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA


逆順で出力するだけでなく，要素の並び順を逆転するにはどうするか．
次は逆順のシーケンスを別に作成し，それを元のシーケンスにコピーする例．

// List 2
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "original:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::vector< int > tmp( seq.rbegin(), seq.rend() ); // 逆順のシーケンス
    seq = tmp; // 元のシーケンスにコピー

    std::cout << "reverse:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
reverse:
10 9 8 7 6 5 4 3 2 1


一時的なコンテナオブジェクトの生成とコピーのコストを嫌うならば，次のようなアルゴリズムを書く。

// List 3
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "original:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::vector< int >::iterator it1 = seq.begin();
    std::vector< int >::iterator it2 = seq.end();
    for( ; it1 != it2 && it1 != --it2; ++it1 ){ // *
        int t = *it1;                           // *
        *it1  = *it2;                           // *
        *it2  = t;                              // *
    }                                           // *

    std::cout << "reverse:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
reverse :
10 9 8 7 6 5 4 3 2 1


なお，*印をつけた5行は，関数テンプレート"std::swap"（2つのオブジェクトの値を交換する）を使って
次のように書くこともできる．

    for( ; it1 != it2 && it1 != --it2; ++it1 ){
        std::swap( *it1, *it2 );
    }


STLにはシーケンスコンテナの要素の順序を逆転させるアルゴリズム関数 reverse が用意されている．

reverse関数のプロトタイプ：
template < typaname BidirectionalIterator >
void reverse( BidirectionalIterator beg, BidirectionalIterator end );


// List 4
#include <vector>
#include <list>
#include <string>
#include <iostream>
#include <algorithm>

int main()
{
    std::vector< int > seq_v;
    std::generate_n( std::back_inserter( seq_v ), 10, Increment< int >( 1 ) );

    std::list< double > seq_l;
    std::generate_n( std::back_inserter( seq_l ), 10, Increment< double >( 1.5 ) );

    std::string str1; // 文字列
    std::generate_n( std::back_inserter( str1 ), 26, Increment< char >( 'a' ) );

    char str2[27];    // 配列
    std::generate( str2, str2 + 26, Increment< char >( 'A' ) );
    *(str2 + 26) = '\0';

    std::cout << "original:\n";
    std::copy( seq_v.begin(), seq_v.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::copy( seq_l.begin(), seq_l.end(), std::ostream_iterator< double >( std::cout, " " ) );
    std::cout << std::endl;

    std::cout << str1 << std::endl;

    std::cout << str2 << std::endl;

    std::reverse( seq_v.begin(), seq_v.end() );
    std::reverse( seq_l.begin(), seq_l.end() );
    std::reverse( str1.begin(), str1.end() );
    std::reverse( str2, str2 + 26 );

    std::cout << "reverse:\n";
    std::copy( seq_v.begin(), seq_v.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::copy( seq_l.begin(), seq_l.end(), std::ostream_iterator< double >( std::cout, " " ) );
    std::cout << std::endl;

    std::cout << str1 << std::endl;

    std::cout << str2 << std::endl;
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 10.5
abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
reverse:
10 9 8 7 6 5 4 3 2 1
10.5 9.5 8.5 7.5 6.5 5.5 4.5 3.5 2.5 1.5
zyxwvutsrqponmlkjihgfedcba
ZYXWVUTSRQPONMLKJIHGFEDCBA


次は，シーケンスの前半分と後半分を別々に逆転させた例．

// List 5
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "original:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::vector< int >::iterator it = seq.begin();
    std::advance( it, 5 );           // イテレータを5前進
    std::reverse( seq.begin(), it ); // シーケンスの前半分を逆転
    std::reverse( it, seq.end() );   // シーケンスの後半分を逆転

    std::cout << "reverse:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
reverse:
5 4 3 2 1 10 9 8 7 6


【例題２】  要素の順序を回転する(rotate)

要素の順序を回転するアルゴリズム．
例えば，要素数10個の配列について，インデックス3の要素を先頭とし，
インデックス0〜2の要素をその順番を保ったまま末尾に連結した配列に変換する．

組み込み配列に対するシーケンスの順序回転アルゴリズムを実装した例．

// List 6
template < typename T >
void rotate_array( T* beg, T* mid, T* end )
{
    T* mem = new T[ mid - beg ];
    T* tmp = mem;
    T* pos;
    for( pos = beg; pos != mid; ){
        *tmp++ = *pos++;
    }
    for( pos = beg; mid != end; ){
        *pos++ = *mid++;
    }
    for( tmp = mem; pos != end; ){
        *pos++ = *tmp++;
    }
    delete[] mem;
}

#include <algorithm>
#include <iostream>

int main()
{
    int seq[10] = {1,2,3,4,5,6,7,8,9,10};

    std::cout << "original:\n";
    std::copy( seq, seq + 10, std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    rotate_array( seq, seq + 3, seq + 10 );

    std::cout << "rotate:\n";
    std::copy( seq, seq + 10, std::ostream_iterator< int >( std::cout, " " ) );
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
rotate:
4 5 6 7 8 9 10 1 2 3


STLのrotate関数を使えば，これと同じ結果が得られる．

rotate関数のプロトタイプ：
template < FowardIterator >
void rotate( FowardIterator beg, FowardIterator mid, FowardIterator end );

第1引数begと第3引数endで指定したシーケンスの範囲を，
第2引数midが指す要素を先頭とする並び順に変換する．

// List 7
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "original:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::vector< int >::iterator mid = seq.begin();
    std::advance( mid, 3 );
    std::rotate( seq.begin(), mid, seq.end() );

    std::cout << "rotate:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
}

実行結果：
original:
1 2 3 4 5 6 7 8 9 10
rotate:
4 5 6 7 8 9 10 1 2 3


【例題３】要素の順序をシャッフルする(rondom_shuffle)

1〜10の整数をランダムに並べたシーケンスを作ることを考える．
方法はいくつか考えられるが，次は，整数1〜10が昇順で並んだシーケンスを，
標準関数のrandで得られる疑似乱数を使ってシャッフルする方法の例．
ここで，srand関数とtime関数による疑似乱数列開始点の設定方法は常套的なもの．

// List 8
#include <cstdlib> // srand, rand
#include <ctime>   // time
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    typedef std::vector< int >   Sequence;
    typedef Sequence::size_type  SizeType;

    Sequence seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "before:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::srand( static_cast< unsigned >( std::time( 0 ) ) );
    for( SizeType i = 2; i <= seq.size(); ++i ){
        SizeType r = static_cast< SizeType >( i * static_cast< double >( std::rand() ) / RAND_MAX );
        std::swap( seq[r], seq[i-1] );
    }

    std::cout << "shuffle:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;
}

実行結果（例）：
before:
1 2 3 4 5 6 7 8 9 10
shuffle:
5 3 2 8 4 1 10 7 6 9


STLのrandom_shuffle関数は，疑似乱数に基づいてシーケンスをシャッフルする．

random_shuffle関数のプロトタイプ：
template < typename RandomAccessIterator >
void random_shuffle( RandomAccessIterator beg, RandomAccessIterator end );

template < typename RandomAccessIterator, typename UnaryFunc >
void random_shuffle( RandomAccessIterator beg, RandomAccessIterator end, UnaryFunc& op );

第1，第2引数でシャッフルするシーケンスの範囲を指定する．
1番目の形式の場合，疑似乱数発生にどのようなアルゴリズムが使われるかはライブラリの実装に依存する．
2番目の形式では，疑似乱数を発生させるルーチンを関数オブジェクトとしてユーザーが指定することができる．

1番目の形式の例：

// List 9
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "before:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::random_shuffle( seq.begin(), seq.end() );

    std::cout << "shuffle:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

}

実行結果（例）：
before:
1 2 3 4 5 6 7 8 9 10
shuffle:
9 2 10 3 1 6 8 4 5 7



2番目の形式の例：
random_shuffle関数の第3引数に渡す関数オブジェクトは，ptrdiff_t型の正の整数を引数(arg)として受け取り，
0 以上 arg 未満の整数をランダムに返すように定義する．
次は，疑似乱数を発生させるために標準ライブラリのrand関数を使った例．

// List 10
#include <cstddef> // ptrdiff_t
#include <cstdlib> // srand, rand
#include <ctime>   // time

class Random
{
public:
    Random( bool set_seed = false )
    {
        if( set_seed ){
            std::srand( static_cast< unsigned >( std::time( 0 ) ) );
        }
    }

    std::ptrdiff_t operator()( std::ptrdiff_t arg ) const
    {
        // 0 以上 arg 未満の整数を返す
        return static_cast< std::ptrdiff_t >( arg * static_cast< double >( std::rand() ) / RAND_MAX );
    }
};

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

int main()
{
    std::vector< int > seq;
    std::generate_n( std::back_inserter( seq ), 10, Increment< int >( 1 ) );

    std::cout << "original:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;

    std::random_shuffle( seq.begin(), seq.end(), Random( true ) );

    std::cout << "shuffle:\n";
    std::copy( seq.begin(), seq.end(), std::ostream_iterator< int >( std::cout, " " ) );
    std::cout << std::endl;
}

実行結果（例）：
original:
1 2 3 4 5 6 7 8 9 10
shuffle:
4 3 8 7 5 2 6 1 10 9