std :: sortを使用した場合のコアダンプ

Question

最近、私はオンラインジャッジからC++の解決問題を書いています。 ソート時にコアダンプされます。とても奇妙に思える。オンライン裁判官がコードを受け入れるかどうかにかかわらず、なぜコアがダンプされるのか疑問に思う。私はstd :: sortを何度も使っている。

以下はコードです。

#include <stdio.h> 
#include <vector> 
#include <algorithm> 

using namespace std; 

struct Pair { 
    Pair(int xx, int yy) : x(xx), y(yy) {} 

    int x; 
    int y; 
}; 

int get_min(int a, int b) { 
    return (a <= b) ? a : b; 
} 

bool pool_compare(const Pair& a, const Pair& b) { 
    return a.x + a.y <= b.x + b.y; 
} 

void get_boundary(const vector<int>& nums1, const vector<int>& nums2, 
        const int k, int& p, int& q) { 
    q = 0; 
    p = 0; 
    int tail = get_min(k, nums1.size() + nums2.size()); 
    int cnt = 1; 

    while (cnt < tail) { 
     if (q + 1 >= nums2.size() || 
      nums1[p + 1] + nums2[q] <= nums1[p] + nums2[q + 1]) { 
      p++; 
     } 
     else { 
      q++; 
     } 
     if (p * q >= k) { 
      break; 
     } 
     cnt++; 
    } 
}     

vector<pair<int, int> > kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { 
    vector<pair<int, int> > ret; 
    if (0 == k) { 
     return ret; 
    } 

    int p = 0; 
    int q = 0; 
    get_boundary(nums1, nums2, k, p, q); 

    vector<Pair> pool; 
    for (int i = 0; i <= p; i++) { 
     for (int j = 0; j <= q; j++) { 
      pool.push_back(Pair(nums1[i], nums2[j])); 
     } 
    } 
    std::sort(pool.begin(), pool.end(), pool_compare); 

    k = get_min(pool.size(), k); 
    for (int i = 0; i < k; i++) { 
     ret.push_back(pair<int, int>(pool[i].x, pool[i].y)); 
    } 

    return ret; 
} 

int main() { 

    int a[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 
    vector<int> nums1(a, a + sizeof(a)/sizeof(int)); 

    int b[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 
    vector<int> nums2(b, b + sizeof(b)/sizeof(int)); 

    vector<pair<int, int> > r = kSmallestPairs(nums1, nums2, 1000); 
    for (size_t i = 0; i < r.size(); i++) { 
     printf("%d\t%d\n", r[i].first, r[i].second); 
    } 

    return 0; 
} 

コールスタックは以下にリストされていますが、あまり役立たないようです。

#0 0x0000000000400900 in pool_compare(Pair const&, Pair const&)() 
#1 0x00000000004025c3 in __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > > std::__unguarded_partition<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, Pair, bool (*)(Pair const&, Pair const&)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, Pair, bool (*)(Pair const&, Pair const&))() 
#2 0x0000000000401ac2 in void std::__introsort_loop<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, long, bool (*)(Pair const&, Pair const&)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, long, bool (*)(Pair const&, Pair const&))() 
#3 0x00000000004011b3 in void std::sort<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, bool (*)(Pair const&, Pair const&)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, bool (*)(Pair const&, Pair const&))() 
#4 0x0000000000400b9e in kSmallestPairs(std::vector<int, std::allocator<int> >&, std::vector<int, std::allocator<int> >&, int)() 
#5 0x0000000000400dbb in main() 

Answer 1

コンパレータが契約を破棄します。 strict weak orderingの関係を満たしています。それは親指の同じaとb

ルールのtrue両方の時間を得たことがないものfalse渡さ同一の要素、およびcmp(a,b)とcmp(b,a)を得なければならない意味

：コンパレータ用<=を使用しないでください。代わりに<を使用してください。