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

runtime error

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

Your comparison is broken. It needs to adhere to strict weak ordering standards. This means if (x < y) is true, then (y < x) must be false. — Retired Ninja
– Retired Ninja, Commented Dec 12, 2012 at 1:02
Not sure why you did the sort comparison the way you did. Please see: cplusplus.com/reference/algorithm/sort — RonaldBarzell
– RonaldBarzell, Commented Dec 12, 2012 at 1:04
So, for testing replace the comparison with return u1 < u2; [which is a valid sort] and see if you still crash — Zero
– Zero, Commented Dec 12, 2012 at 1:05
Well, if you don't post your real code you can't expect a real answer. Either way, if you are seeing that assertion fail then your comparison is still broken. — Retired Ninja
– Retired Ninja, Commented Dec 12, 2012 at 1:07
Still not a strict weak ordering, replace with return price2 < price1 — Zero
– Zero, Commented Dec 12, 2012 at 1:11

Praetorian · Accepted Answer · 2012-12-12 01:10:11Z

7

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.

answered Dec 12, 2012 at 1:10

Praetorian

110k20 gold badges248 silver badges340 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

thiagoh Over a year ago

another question, why the parameters of the operator() must be const?

Praetorian Over a year ago

@thiagoh Because the comparator should not mutate the objects being compared

David G · Accepted Answer · 2012-12-12 01:18:14Z

5

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).

edited Dec 12, 2012 at 1:18

David G

97.6k41 gold badges173 silver badges258 bronze badges

answered Dec 12, 2012 at 1:07

Nemanja Boric

22.2k6 gold badges72 silver badges93 bronze badges

2 Comments

thiagoh Over a year ago

another question, why the parameters of the operator() must be const?

Daniel Castro Over a year ago

Because you should not try to modify the object data to determine if it's 'less than' other

Collectives™ on Stack Overflow

c++ sort vector of pointers error

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related