Hatena::ブログ(Diary)

Life like a clown このページをアンテナに追加 RSSフィード Twitter

2010-03-05

イテレータの比較

プログラマーの力量を見極める--面接官になったら尋ねるべき質問実例集 - ZDNet Japan の中の「ループを使わずに配列の順序を逆にする。」と言う問題で,「再帰を使って記述しろ」と言う意味なのかなぁと以下のようなコードを思いついたのですが,ここで一つ疑問が(やっている事自体は,ホワイトボードプログラミング と同じです).

template <class InIter>
void reverse(InIter head, InIter tail) {
    if (head >= tail) return;
    std::swap(*head, *tail);
    ::reverse(++head, --tail);
}

疑問と言うのは,「イテレータって(不等号による)比較演算は可能なのだろうか?」と言うものでした.そこで,手元のリファレンスを見ると,どうやら「ランダムアクセスイテレータ」であれば可能なようです.

ランダムアクセス反復子

双方向反復子とも似ているが,シーケンス内の任意のインデックスにアクセスするための添字 ([]) 演算子もサポートする.また,整数を足したり引いたりして,ランダムアクセス反復子を一気に動かすこともできる.2 つのランダムアクセス反復子で減算を行うと,それらの差分が整数で得られる.したがって,ランダムアクセス反復子は従来のポインタのようなものであり,ポインタはランダムアクセス反復子として使用できる.

C++ ライブラリ クイックリファレンス p.251

簡単なテストコードは以下の通り.コードのコメントにも書いていますが,ランダムアクセスイテレータではないイテレータを指定すると,コンパイルエラーになります(正確には,>= 演算子が定義されていないイテレータ).

#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <deque>
#include <list>

int main(int argc, char* argv[]) {
    std::ostream_iterator<int> output(std::cout, " ");
    
    // 配列
    int v1[] = {1, 3, 5, 7, 9, 11, 13};
    output = std::copy(v1, v1 + sizeof(v1) / sizeof(int), output);
    std::cout << std::endl;
    ::reverse(v1, v1 + sizeof(v1) / sizeof(int) - 1);
    output = std::copy(v1, v1 + sizeof(v1) / sizeof(int), output);
    std::cout << std::endl << std::endl;
    
    // std::vector
    std::vector<int> v2(v1, v1 + sizeof(v1) / sizeof(int));
    output = std::copy(v2.begin(), v2.end(), output);
    std::cout << std::endl;
    ::reverse(v2.begin(), --v2.end());
    output = std::copy(v2.begin(), v2.end(), output);
    std::cout << std::endl << std::endl;
    
    // std::deque
    std::deque<int> v3(v2.begin(), v2.end());
    output = std::copy(v3.begin(), v3.end(), output);
    std::cout << std::endl;
    ::reverse(v3.begin(), --v3.end());
    output = std::copy(v3.begin(), v3.end(), output);
    std::cout << std::endl << std::endl;
    
    // std::list はコンパイル・エラー
    //std::list<int> v4(v3.begin(), v3.end());
    //::reverse(v4.begin(), --v4.end());
    
    return 0;
}
[clown@stinger example]$ ./a
1 3 5 7 9 11 13 
13 11 9 7 5 3 1 

13 11 9 7 5 3 1 
1 3 5 7 9 11 13 

1 3 5 7 9 11 13 
13 11 9 7 5 3 1 

begin()/end() を指定するのではなく,begin() と最後の要素へのイテレータを指定する形になるので混乱を招きそうです.特別な理由がない限りは,std::reverse(v.begin(), v.end()) などで良いだろうとは思います.

尚,std::swap() を使わずに ホワイトボードプログラミング と同じような見た目にする場合は,下記のような感じでしょうか.

template <class InIter>
void reverse(InIter head, InIter tail) {
    if (head >= tail) return;
    typename std::iterator_traits<InIter>::value_type tmp = *head;
    *head = *tail;
    *tail = tmp;
    ::reverse(++head, --tail);
}

元の「ループを使わずに配列を反転させろ」と言う問いは,未だにどうすれば良いのかよく分かりません.