c++ - QSort 排序不正确，除非之后再多排序一次

Question

我正在尝试通过重载“+”运算符将两个优先级队列相互添加。

// Overloading add operator (+)
template <class T> PrioQueue<T> operator + (PrioQueue<T> &a, PrioQueue<T> &b) {
    // Create a new queue that's big enough to hold our 2 queues
    PrioQueue<T> newPrioQueue(a.num_items + b.num_items);

    // Push all items to the new queue
    // all items will be sorted on pushtime (get it? Instead of runtime? Haha... Ha...)
    for (T * element = a.bottom_; element < a.bottom_ + a.num_items; element++) {
        newPrioQueue.push(*element);
        std::cout << newPrioQueue;
    }

    // Push all items to the new queue
    // all items will be sorted on pushtime
    for (T * element = b.bottom_; element < b.bottom_ + b.num_items; element++) {
        newPrioQueue.push(*element);
        std::cout << newPrioQueue;
    }

    // This one is needed - why?
    newPrioQueue.sort();

    std::cout << newPrioQueue;

    // New queue is done, return it.
    return newPrioQueue;
}

这是我的 PrioQueue 的 push 函数:

void push(T t) {
    if (!full()) {
        *top_ = t;
        top_++;
        num_items++;

        // Sort items using qsort
        qsort(bottom_, num_items, sizeof(T), compareFunction);
    } else {
        std::cout << "Queue is full" << endl;
    }

};

如您所见，PrioQueue 将在每次push 后进行排序。但是，在合并两个数组后还需要最后一种排序!检查此输出:

Queue has 1 item(s): 429
Queue has 2 item(s): 429|123
Queue has 3 item(s): 429|123|24
Queue has 4 item(s): 429|123|24|24
Queue has 5 item(s): 429|123|24|24|3
Queue has 6 item(s): 429|123|24|24|3|2
Queue has 7 item(s): 24|123|24|429|3|2|1
Queue has 7 item(s): 429|123|24|24|3|2|1

倒数第二行是错误。它突然打乱了所有数据!

为什么会这样？

编辑:这是我的 CompareFunction:

static int compareFunction (const void * a, const void * b) {
    // Relies on overloading of the "<" operator with non-std objects
    return (*(T*)a < *(T*)b);
}

这是输入:

intQueue1.push(24);
intQueue1.push(429);
intQueue1.push(123);

intQueue2.push(1);
intQueue2.push(2);
intQueue2.push(3);
intQueue2.push(24);

intQueue3 = intQueue1 + intQueue2;

Answer 1

我可能是错的，但是你的compareFunction:

static int compareFunction (const void * a, const void * b) {
    // Relies on overloading of the "<" operator with non-std objects
    return (*(T*)a < *(T*)b);
}

应该返回 1、0 或 -1，它返回 true 或 false...