sortとpriority_queueの並び変え順序
こんにちは。
だいぶ昔から気になってはいたのですが、C++ STLではsortとpriority_queueで並び替えられる順序が違うのが気になっています。
sortもpriority_queueも並べ替え順序の初期値はstd::lessになっているはずなんですが、次のプログラムを実行すると、逆の並び順になります。
ソースコード
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v;
priority_queue<int> que;
srand((unsigned long)time(NULL));
for(int i=0; i<10; i++) {
int x = rand() % 100;
v.push_back(x);
que.push(x);
}
std::sort(v.begin(), v.end());
for(int i=0; i<10; i++) {
printf("%2d %2d\n", v[i], que.top());
que.pop();
}
}
実行結果
13 98
16 88
26 82
37 62
44 57
57 44
62 37
82 26
88 16
98 13
一方、Javaで同じようなプログラムを組むと、同じ順番でソートされる。
(Java7のコードなのでgenericsが省略されていることに注意)
ソースコード
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
public class SortVsQueue {
public static void main(String... args) {
new SortVsQueue();
}
public SortVsQueue() {
PriorityQueue<Integer> que = new PriorityQueue<>();
List<Integer> list = new ArrayList<>();
Random rand = new Random(System.currentTimeMillis());
for(int i=0; i<10; i++) {
int x = rand.nextInt(100);
list.add(x);
que.add(x);
}
Collections.sort(list);
for(int i=0; i<10; i++) {
System.out.printf("%2d %2d\n", list.get(i), que.poll());
}
}
}
実行結果
17 17
20 20
22 22
27 27
46 46
53 53
66 66
74 74
90 90
98 98
僕の気持ちとしてはJavaの実装の方が普通のような気がするのですが、C++の方はどうしてこのような気持ち悪い実装になっているのでしょうか?
理由は不明ですが、初心者のうちはDijkstra法とかのプログラムでpriority_queueを使うとソートにstd::greaterを指定していなくて、うまく動かないなんてこともありますから、注意したいですね。