c++ sort vector of pointers error

Question

I have a vector vec that I need to sort every time I put an element inside it

so when I put the first Upgrade* inside the vector I have no problems

but when I put the second Upgrade* inside it and the sort routine is called I have a runtime error

this is how I put elements and call sort every time I insert

std::vector<Upgrade*> stack = getStack();

stack.push_back(element);

std::sort(stack.begin(), stack.end(), CostBenefitUpgradeOrder());

and this is my comparator

struct CostBenefitUpgradeOrder {
    bool operator ()(const Upgrade * u1, const Upgrade * u2) const {

        const UpgradeType upgradeType1 = u1->getUpgradeType();
        const UpgradeType upgradeType2 = u2->getUpgradeType();

        int price1 = PriceUtil::getPrice(upgradeType1);
        int price2 = PriceUtil::getPrice(upgradeType2);

        if (price2 < price1)
            return true;
        else
            return false;
    }
}

and this is the error

I have noticed that it only happens when I execute the program in Debug mode!!

Answer 1

Your comparison function is broken. You cannot have a predicate that returns true for both u1 < u2 and u2 < u1.

Replace the return statement with return u1 < u2; if you just need something for a quick test.

Also, are you sure you need to use a vector? Unless you need the pointers to be stored in contiguous memory, you'd be better off using an std::set instead with an appropriate comparator. The set will keep the elements ordered after every insertion / deletion.

Also, since you're using raw pointers, if you're allocating the objects using new make sure you delete before removing elements from the container. Better yet, use an std::set<std::unique_ptr<Upgrade>, CostBenefitUpgradeOrder> instead and not have to worry about deleting the allocated memory.

Answer 2

You need to pass "strict weak ordering" (less than) operator to the std::sort method, and that operator must be "valid".

Valid operator< have the following properties:

• For all , it is not the case that < (irreflexivity). For all ,
• , if < then it is not the case that y < x (asymmetric). For all
• , , and , if < and < then < (transitivity). For all ,
• , and , if is incomparable with , and is incomparable with , then is incomparable with (transitivity of incomparability).

You can see that your operator fails on the first point (CostBenefitUpgradeOrder(x, x) == true, in your case) (and on most other points, as well).