おしえて

templateを使ったXOR swapのバグなのか，あるいは別の何か

解決済

質問者：nasanaut
質問日時：2017/01/07 17:10
回答数：3件

selection sortを復習しようと思って以下の簡単なC++のコードを書いた結果謎の挙動をします．実行環境はUbuntu 16.04 64bit Linux gcc 5.4です．

#include <iostream>
using namespace std;

template<typename T> void myswap(T& lhs, T& rhs)
{
lhs ^= rhs;
rhs ^= lhs;
lhs ^= rhs;

// T tmp = lhs;
// lhs = rhs;
// rhs = tmp;
}

template<typename T> void sort(T* array, int n)
{
for(int i = 0; i < n; i++){
T min_val = array[i];
int min_ind = i;
for(int j = i + 1; j < n; j++){
if(array[j] < min_val){
min_val = array[j];
min_ind = j;
}
}
myswap(array[i], array[min_ind]);
}
}

int main()
{
int array[10] = { 1, 4, 6, 8, 2, 9, 0, 3, 7, 6 };
sort(array, 10);
for(int i = 0; i < 10; i++) cout << array[i] << " "; cout << endl;

return 0;
}

このコードを走らせると
0 1 2 3 4 6 6 7 0 0

というアウトプットが出ます．

XORスワップではなくて，コメントアウトしてあるコードを使うと期待通り
0 1 2 3 4 5 6 7 8 9

と正しくソートされたアウトプットが出ます．そうするとスワップのコードが違うと思うのですが間違いが見つけられません．何かコメント頂けたら嬉しいです．

XOR swapではないスワップをしたアウトプットは0 1 2 3 4 6 6 7 8 9です．タイポすいません．

補足日時：2017/01/08 05:53
通報する

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

ベストアンサー優先
最新から表示
回答順に表示

No.1ベストアンサー

回答者：お茶碗持つ方
回答日時：2017/01/07 18:18

型不特定変数のポインターにビット演算を行なっています。

整数値同士の交換なら XOR を相互に施すと交換した値になるのですが、lhs と rhs はTへのポインターですから元来ビット演算できない筈です。

アドレスを整数値として扱うことが判っている処理系ならばこれでもいいかもしれませんが、できたとしてもそれは偶々で、処理系依存のバグの副作用を利用したにすぎません。

トリッキーなコーディングは、他人への可読性が悪くなる上に自分自身も思い込みによる見落としを起こす要因にもなります。

ここまでトリッキーなコーディングをするなら、いっそのことアセンブラを覚えて
#pragma _asm
で実装した方が効率の良いプログラムが書けます。プロセッサのレジスタレベルまで遡っての理解を要求しているため読む人もそれなりのスキルがある人が注意深く読むのでバグが発見しやすくなると思います。