我最近从在线法官那里写了解决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 ()

最佳答案

您的比较者违反了契约(Contract)。应该符合strict weak ordering关系。

这意味着当传递相同的元素时,它应该产生false,对于相同的cmp(a,b)cmp(b,a)truea绝不会两次产生b
经验法则:不要将<=用于比较器;请改用<

关于c++ - 使用std::sort时的核心转储,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/39933036/

10-13 07:05