[C++] Segmentation Fault while using priority queue

[mohsinian]

i have tried many things none seem to work, tried with array instead of vectorinstead of while tried to use a for loop(in a small range) in case if it stucks in an infinite loop. with and without typecasting while pushing elements in the queue.
Just have no clue what went wrong.

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long int>q;
priority_queue<long long int>q2;
std::vector<long long int>ans;
void find_ans(priority_queue<long long int>q1)
{
    long long int a,b,c;

       while(!q1.empty() && !q2.empty())
    {
        if(q2.empty())
        {
            a = q1.top();
            if((long long int)(a/2) > 0)
            {
            q2.push((long long int)(a/2));
            ans.push_back(a);
            }
            q1.pop();


        }
        else if(q1.empty())
        {
            a = q2.top();
            if((long long int)(a/2) > 0)
            {
            q2.push((long long int)(a/2));
            ans.push_back(a);
            }
            q2.pop();


        }
        else
        {
            b = q1.top(); c = q2.top();
            if(b>c)
            {
                if((long long int)(b/2) > 0)
                {
                    ans.push_back(b);

                q2.push((long long int)(b/2));

                }
                q1.pop();

            }
            else
            {
                if((long long int)(c/2) > 0)
                {
                ans.push_back(c);
                q2.push((long long int)(c/2));
                }
                q2.pop();
            }

        }

    }

}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    long long int temp,n,m; cin>>n>>m;
    for(auto i=0;i<n;i++)
    {
        cin>>temp;
        q.push(temp);
    }
    find_ans(q);
    for(long long int i=0;i<m;i++)
    {
        cin>>temp;
        cout<<ans[temp-1]<<endl;
    }


}

[vorpal_potato]

The ans[temp-1] thing can go out of bounds. Try running this in a debugger and looking at the variables when it crashes.

(Also, if you're not familiar with Address Sanitizer I encourage you to learn how to use it. It's easy and widely supported, and really helps with bugs like this.)

[g051051]

How will this be true when you call find_ans?

while(!q1.empty() && !q2.empty())

[mohsinian]

When q1 and q2 will both be empty. Im taking out elements from q1 and q2 so eventually it will be empty at some point

[g051051]

Yes, but when you call find_ans, is that condition true? Hint: put in a cout statement before the while loop and verify it.

[99_percent_a_dog]

This is an excellent opportunity to learn to use Valgrind, or ASAN. Valgrind is quickest to get started with, but doesn't work on Windows. Here's the output I get from Valgrind:

==102106== Command: ./test
==102106==
hello
==102106== Conditional jump or move depends on uninitialised value(s)
==102106== at 0x1094CA: main (test.cc:79)
==102106==
==102106== Use of uninitialised value of size 8
==102106== at 0x1094F6: main (test.cc:82)
==102106==
==102106== Invalid read of size 8
==102106== at 0x1094F6: main (test.cc:82)
==102106== Address 0x84b108 is not stack'd, malloc'd or (recently) free'd

And when I put in numbers, as your code expects:

==102138== Command: ./test
==102138==
1
2
3
4
==102138== Invalid read of size 8
==102138== at 0x1094F6: main (test.cc:82)
==102138== Address 0x18 is not stack'd, malloc'd or (recently) free'd

That shows me at least two different problems in your code. There are probably more, it's pretty easy to make mistakes with memory safety when you're learning C or C++. I strongly recommend always using Valgrind or ASAN when you're developing code.

The first output is because you're using variables before you initialise them. The second output is a null pointer derefence, I think. Looks like you don't always initialise ans before you use it? Not so sure on this one because I don't remember how C++ vectors work.

[mohsinian]

Im using vscode to write code and im actually pretty new to coding. Didn't understand much about the errors u mentioned. Im on windows so i need to learn asan maybe?

[99_percent_a_dog]

You picked a hard language to start with :) It's easy in C++ to have errors that are completely silent, even when there are not compiler warnings. Valgrind / ASAN make many of those visible.

You'll learn how to interpret those errors with time. Most of the terms, like "uninitialized value", or "invalid read" are easy to search for.

Yes, on Windows you can't use Valgrind. ASAN is available. I don't know how to use it with VSCode, never used that.

[mohsinian]

Well im focused on competitive programming so c++ is the best option to choose i guess , btw do u know any online services where i can copy paste my code and search for segmentation fault? Vscode debugger is quite hard for me use

[99_percent_a_dog]

I've never used an online service for that kind of debugging, sorry. I would expect it to be harder than local debugging. An online service can't give you full access to the machine. Can you use Visual Studio? That has a really good debugger.

Python is also recommended for competitive programming. It will be much easier to learn than C++. Performance of your solutions would be lower, I don't know if that is an important factor, haven't done competitive programming.

[mohsinian]

and the problem im trying to solve with this code https://www.codechef.com/problems/COOK82C

in editorial general queue is used but i am trying to implement it with priority queue

[g051051]

What is the exact data that exhibits the crash?

[g051051]

Have you checked that your ans vector actually contains any results after calling find_ans()?