stable_sortとは、安定なソートを行う関数です。
安定であるとは、ソート対象の配列の要素の比較を行ったときに同位であった場合にはもとの順序を保存する、ということです。ものの本を読むと、std::stable_sortは、std::sortよりも「遅いことがある」と書いてあります。
今回は、大きな配列に対して安定なソートが必要になりました。どのくらい大きいかというと、実メモリに収まりきらない（ことがある）くらいです。で、やっぱり速いに越したことはないので、ちょっと実験してみました。
実験用のコードは後で示しますが、結果から言うと、普通のソート(std::sort)とくらべると、安定なソート(std::stable_sort)は、明らかに遅い。だいたい２割から５割くらい遅い。
ちょっと調べてみると理由はわかりました。stable_sortで使われているマージソートというアルゴリズムは、ソートの対象となる配列の半分くらいの大きさの一時的な記憶領域を必要とするから、だそうです。
ここで悩みどころです。
実は（というほどもったいぶった話でもありませんが）、通常のstd::sortを使って安定なソートをする簡単なトリックがあります。カギは、比較関数として、要素の比較を行って同位であった場合に、ソート前の配列内での要素の順序の比較結果を返すものを作ることです。
ソート前の配列内での要素の順序を保存する単純な方法としては、要素のデータ構造の中に、順序を保存するための領域を設ける、というものがあります。要素のデータ構造が大きなものであれば、このような余分な領域を設けるペナルティは、メモリ量の観点からは小さなものです。
要素のデータ構造がもっと大きくて、そのまま要素を並べ替えるのが非効率であるために、要素へのポインタの配列を作っておいてからソートしようなどと考えている場合には、この解決策はより魅力的なものになります。なぜなら、要素へのポインタの配列をソートするときに、ソート前の配列内での要素の順序の比較を行うには、ポインタの値の比較を行えばよいわけで、そうなると、先ほどの余分な領域が必要なくなるためです。
問題点としては、それなりに制約があること。前者の方法では、データ構造に余分な領域を設けてもよいか。後者の方法では、ポインタの比較に頼るため、一般的なコンテナには適用できません。適用可能なのは、生の配列、std::vectorとboost::arrayくらいでしょう。
以下、実験に使ったコードです。vcとg++でコンパイルできます。
（ちなみに、メモリ配置が影響しないか心配だったので、std::sortとstd::stable_sortの順序を入れ替えたものも作って実験してみました。結論としては、細かい数値はともかく、傾向は同じでした。）
----------------------------
#include ＜vector＞
#include ＜utility＞
#include ＜algorithm＞
#include ＜iostream＞
#include ＜stdlib.h＞
#include ＜time.h＞
#include ＜assert.h＞
int main(int argc, char* argv[])
｛
std::cout ＜＜ "size, simple sort, stable sort" ＜＜ std::endl;
size_t size = 6000;
for (size_t k = 0; k ＜ 30; ++k) ｛
size = (size_t)(size * 1.5);
std::vector＜std::pair＜int, int＞ ＞ values;
values.resize(size);
for (size_t i = 0; i ＜ values.size(); ++i) ｛
values[i] = std::pair＜int, int＞(rand(), i);
｝
std::vector＜std::pair＜int, int＞ ＞ v2(values);
time_t start1, end1;
time(&start1);
std::sort(values.begin(), values.end());
time(&end1);
time_t start2, end2;
time(&start2);
std::stable_sort(v2.begin(), v2.end());
time(&end2);
for (size_t i = 0; i ＜ values.size(); ++i) ｛
assert(v2[i] == values[i]);
｝
std::cout ＜＜ size ＜＜ ", " ＜＜ (end1 - start1) ＜＜ ", " ＜＜ (end2 - start2) ＜＜ std::endl;
｝
return 0;
｝
----------------------------
安定であるとは、ソート対象の配列の要素の比較を行ったときに同位であった場合にはもとの順序を保存する、ということです。ものの本を読むと、std::stable_sortは、std::sortよりも「遅いことがある」と書いてあります。
今回は、大きな配列に対して安定なソートが必要になりました。どのくらい大きいかというと、実メモリに収まりきらない（ことがある）くらいです。で、やっぱり速いに越したことはないので、ちょっと実験してみました。
実験用のコードは後で示しますが、結果から言うと、普通のソート(std::sort)とくらべると、安定なソート(std::stable_sort)は、明らかに遅い。だいたい２割から５割くらい遅い。
ちょっと調べてみると理由はわかりました。stable_sortで使われているマージソートというアルゴリズムは、ソートの対象となる配列の半分くらいの大きさの一時的な記憶領域を必要とするから、だそうです。
ここで悩みどころです。
実は（というほどもったいぶった話でもありませんが）、通常のstd::sortを使って安定なソートをする簡単なトリックがあります。カギは、比較関数として、要素の比較を行って同位であった場合に、ソート前の配列内での要素の順序の比較結果を返すものを作ることです。
ソート前の配列内での要素の順序を保存する単純な方法としては、要素のデータ構造の中に、順序を保存するための領域を設ける、というものがあります。要素のデータ構造が大きなものであれば、このような余分な領域を設けるペナルティは、メモリ量の観点からは小さなものです。
要素のデータ構造がもっと大きくて、そのまま要素を並べ替えるのが非効率であるために、要素へのポインタの配列を作っておいてからソートしようなどと考えている場合には、この解決策はより魅力的なものになります。なぜなら、要素へのポインタの配列をソートするときに、ソート前の配列内での要素の順序の比較を行うには、ポインタの値の比較を行えばよいわけで、そうなると、先ほどの余分な領域が必要なくなるためです。
問題点としては、それなりに制約があること。前者の方法では、データ構造に余分な領域を設けてもよいか。後者の方法では、ポインタの比較に頼るため、一般的なコンテナには適用できません。適用可能なのは、生の配列、std::vectorとboost::arrayくらいでしょう。
以下、実験に使ったコードです。vcとg++でコンパイルできます。
（ちなみに、メモリ配置が影響しないか心配だったので、std::sortとstd::stable_sortの順序を入れ替えたものも作って実験してみました。結論としては、細かい数値はともかく、傾向は同じでした。）
----------------------------
#include ＜vector＞
#include ＜utility＞
#include ＜algorithm＞
#include ＜iostream＞
#include ＜stdlib.h＞
#include ＜time.h＞
#include ＜assert.h＞
int main(int argc, char* argv[])
｛
std::cout ＜＜ "size, simple sort, stable sort" ＜＜ std::endl;
size_t size = 6000;
for (size_t k = 0; k ＜ 30; ++k) ｛
size = (size_t)(size * 1.5);
std::vector＜std::pair＜int, int＞ ＞ values;
values.resize(size);
for (size_t i = 0; i ＜ values.size(); ++i) ｛
values[i] = std::pair＜int, int＞(rand(), i);
｝
std::vector＜std::pair＜int, int＞ ＞ v2(values);
time_t start1, end1;
time(&start1);
std::sort(values.begin(), values.end());
time(&end1);
time_t start2, end2;
time(&start2);
std::stable_sort(v2.begin(), v2.end());
time(&end2);
for (size_t i = 0; i ＜ values.size(); ++i) ｛
assert(v2[i] == values[i]);
｝
std::cout ＜＜ size ＜＜ ", " ＜＜ (end1 - start1) ＜＜ ", " ＜＜ (end2 - start2) ＜＜ std::endl;
｝
return 0;
｝
----------------------------