Access violating when pushing into priority queue

Question

I have the following code:

bool custom(pair<int, int>& a, pair<int, int>& b)
{
    return (double)a.first / (double)a.second > (double)b.first / (double)b.second;
}

int reviews(vector<pair<int,int>>& ratings, int t) {

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&custom)> q;
    int numProducts = ratings.size();
    double rating = 0;
    int numRevs = 0;

    // fill up queue and compute initial rating
    for (int i = 0; i < ratings.size(); i++)
    {
        rating += ((double)ratings[i].first / (double)ratings[i].second) / numProducts;
        q.push(ratings[i]);
    }
// other stuff, crashes before this point

    return numRevs;
}

int main()
{
    vector<pair<int, int>> ratings = { {4,4}, {1,2}, {3,6} };
    int t = 80;
    cout << reviews(ratings , t) << endl;
        

}

Which gives the following error the second time q.push() is run: Exception thrown at 0x00000000 in ConsoleApplication1.exe: 0xC0000005: Access violation executing location 0x00000000.

Does anyone know why this is? Thanks

Warning -- using floating point math to determine ordering may produce different results if you change compiler options or compiler. — PaulMcKenzie, Oct 16 '20 at 19:09
@PaulMcKenzie interesting, wasn't able to get that warning with `-Wall -Wextra` flags in GCC. Can you please share the flag you passed? I would be very keen to include it in my answer, if you have no objection ofc. :) — gsamaras, Oct 16 '20 at 19:10
Don't know about warnings. Just in general -- if you're using FP math to determine ordering, just be very careful. — PaulMcKenzie, Oct 16 '20 at 19:14
The dupe in fact shows exactly the same behavior. The answer there is correct, but you can pass the comparator directly, instead of passing its address. — cigien, Oct 16 '20 at 19:18
Would you agree with my answer too @cigien? Nice dupe finding, couldn't find one when searching for it.. Indeed the dupe is not an exact match, but still good IMHO. — gsamaras, Oct 16 '20 at 19:20
@gsamaras Your solution is definitely correct. I prefer it in fact, though you don't explain *why* the crash occurs. If you update your answer, then the dupe could be reversed. There's almost no views on that one anyway. — cigien, Oct 16 '20 at 19:22

score 3 · Answer 1 · edited Oct 16 '20 at 20:34

3

Pass custom method as q's parameter. So, change this:

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&custom)> q;

to this:

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&custom)> q(custom);

Run it Online

The reason for that is that in std::priority_queue, the third template parameter is:

Compare - A Compare type providing a strict weak ordering.

That means that in your code you had only specified the type of the comparator only (decltype(&custom)), a function pointer. As a result the function object will be default-constructed. Using a default constructed function pointer will invoke undefined behavior. So you need to pass the actual function object, in order for it to be correctly usable.

PS: You might want to take a look in this relevant lambda-using example.

edited Oct 16 '20 at 20:34

cigien

57,834
11
73
112

answered Oct 16 '20 at 19:06

gsamaras

71,951
46
188
305

Hmm, this *seems* ok, and the current dupe target says the same thing (i.e. the comparator is default-initialized), but all the [overloads](https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue) seem to value-initialize the comparator, so I think I must be misunderstanding something. If I can't figure it out, there *may* be a language-lawyer question lurking here I could ask :) But either way, until then, I think the dupe target should be left as is. – cigien Oct 16 '20 at 19:32
I think overload #3: `explicit priority_queue( const Compare& compare = Compare(), const Container& cont = Container());`, which might explain why the compare method should be passed as the first parameter, I think. Relevant [question](https://stackoverflow.com/questions/39884827/custom-arguments-to-stdset-comparison-function) with another STL container. @cigien yes ok about the approximate dupe, and please make sure to link any related question you might ask, here please. – gsamaras Oct 16 '20 at 19:35
Yes, exactly. So shouldn't `Compare()` do the right thing, i.e. value-intitialization? And yes, I'll definitely link to this question if I do ask another one. – cigien Oct 16 '20 at 19:39
We have passed `decltype(&custom)` as the template's 3rd parameter, which might be related @cigien. – gsamaras Oct 16 '20 at 19:42
1

Aah yes, I think that's it :) The type of the comparator is not a function object at all, but a function pointer. – cigien Oct 16 '20 at 19:48
Ok, I think the answer is clear now :) The dupe can be reversed, but only if/when the OP accepts this answer. – cigien Oct 16 '20 at 20:37
1

@cigien it's fine, what matters is that we improved the answer to this question, thank you! – gsamaras Oct 16 '20 at 22:22

Access violating when pushing into priority queue

1 Answers1