サイズの大きい構造体を高速にソートするテクニック

　誰もが思いつくと感じているが、一応実装を記す。メモリを多くするとideoneでＳＥＧＶったけど気にしない。メモリが壊れているかもしれないけれど眠いので今は調べない。私製のテストフレームワークを用いている部分はコメントアウトした。気にしないで欲しい。
http://ideone.com/z95Ye

　要するに構造体を丸ごとコピーしてソートするのではなくポインタ経由で比較データにアクセスしてポインタ値のみをソートするという方法である。アルゴリズムの教科書の小ネタやソートの高速化の課題として書かれていそうな題材である。
　このソースコードの場合、ideoneではポインタ経由ソートのほうが約１０倍高速である。

#include <iostream>
#include <algorithm>
#include <functional>
 
struct vbdata{
        int prio;
        char data[1024];
        vbdata() : prio(rand()){
 
        }
        ~vbdata(){}
        friend bool operator<(const vbdata &x,const vbdata &y){
                return x.prio < y.prio;
        }
        friend bool operator>(const vbdata &x,const vbdata &y){
                return x.prio > y.prio;
        }
};
 
 
template<class T>
struct pointer_less: public std::binary_function<T*,T*,bool>{
        bool operator()(const T *x,const T *y){
                return *x < *y;
        }
};
 
#include <boost/scoped_array.hpp>
#include <boost/timer.hpp>
 
void vbsort_test(size_t size){
        using namespace boost;
        using namespace std;
        //RANKING_OBJ_DEFINE;
        srand(0);
 
        {
                size_t i;
                scoped_array<vbdata> a(new vbdata[size]);
                scoped_array<vbdata *> b(new vbdata *[size]);
                for(i=0;i<size;i++){
                        b[i] = &a[i]; 
                }
                pointer_less<vbdata> l;
                //less<vbdata *> l;
                boost::timer t;
                //RANKING_TIMER_DEFINE("ptr sort");
                std::sort(&b[0],&b[size],l);
                /*for(i=0;i<size;i++){
                        vbdata& d=*(b[i]);
                        cout << d.prio << endl;
                }*/
                cout << t.elapsed() << endl;
        }
 
 
        srand(0);
 
        {
                scoped_array<vbdata> a(new vbdata[size]);
                boost::timer t;
                //RANKING_TIMER_DEFINE("def sort");
                std::sort(&a[0],&a[size]);
                /*for(size_t i=0;i<size;i++){
                        vbdata& d=a[i];
                        cout << d.prio << endl;
                }*/
                cout << t.elapsed() << endl;
        }
 
}
int main(){
 vbsort_test(1024*32);
}