Vector Iterator Not dereferencable

[coder1]

Hello I was writing a program, it should take an integer (n) and then do the following n times:
1) read an integer k then read k integers.
2) take the max integer and the min integer and add the difference between them to the answer.
3) delete the max and min integer that have been used in step 2.
note: the integers from which we take the max,min are the ones read in step 1.

Here is my code:
my idea was to make two priority queues and when i read an integer i add it to first priority queue and add it to second priority queue as a negative number.
so that when I take the top element of first priority queue that would be the max
and from the second that would be the min.

# include <iostream>
# include <queue>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		priority_queue <int> a;
		priority_queue <int> b;
		long long k;
		long long now;
		cin>>k;
		k++;
			ans+=a.top()+b.top();
			a.pop();
			b.pop();
		
		for (int x=0;x<k;x++)
		{
			if (x==0)
				continue;
			cin>>now;
			a.push(now);
			b.push(-now);
		}
		ans+=a.top()+b.top();
		a.pop();
		b.pop();
		
	}
	cout<<ans<<endl;
}

the problem: when k=0 it stops and shows the following message:

Vector Iterator Not dereferencable

[vlad from moscow]

When these statements are executed the priority queues are empty

		cin>>k;
		k++;
			ans+=a.top()+b.top();
			a.pop();
			b.pop();

So for example operation a.top() has no any sense.

[coder1]

even when I removed the code from line 17->19
the same error occurs even when the queue isnt empty

[vlad from moscow]

If you enter k equal to 0 then the queues also will be empty.

[coder1]

no
try this input:

5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2

[vlad from moscow]

And I do not see any sense to use a priotity queue for this assignment.

[coder1]

why?

[vlad from moscow]

One more if k is entered 0 then the queues will be empty.

[coder1]

not if u try them input i listed above

[vlad from moscow]

I am not interested what you listed. I see your code. If k had initial value equal to 0 then the next loop will have only one iteration that will be terminated by statement continue.

[coder1]

Yes, but the task says that i can assume that there will be atleast 2 integers left

[coder1]

that means that there wont be any case like you are saying

[vlad from moscow]

I am not interested what the task says. I talk about your code. I am repeating the fourth time if the initial value of k is equal to 0 the queues will be empty.

[coder1]

what i mean is that the error isnt because of the queue is empty.
becuase thats happening when it isnt empty
my question is:
why this error is happening (which is clearly not because the priority queue is empty)
and how can it be done without priority queue?

[vlad from moscow]

I am repeating the fifth time you get the error because the queues are empty.

[coder1]

nevermind we are not understanding each other

[Script Coder]

This code seems to be working for me. Try it and let me know if you understand it.

#include <iostream>
#include <limits>

int main() {
	int N, sum=0;
	std::cin>>N;
	
	for(int i=0; i<N; ++i) {
		int k, 
			min=std::numeric_limits<int>::max(), 
			max=std::numeric_limits<int>::min();
			
		std::cin>>k;
		if(!k) continue;
		for(int j=0; j<k; ++j) {
			int t;
			std::cin>>t;
			min= t<min ? t:min;
			max= t>max ? t:max;
		}
		sum+=max-min;
	}
	std::cout<<sum;
	return(0);
}

[JLBorges]

> it should take an integer (n) and then do the following n times
> ...
> 3) delete the max and min integer that have been used in step 2.

Each time, we are removing two integers from the integers to be considered.
So after performing step 3) n/2 times, there will be no integers left.


> how can it be done without priority queue?

By using a sorted std::vector<>

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    // read an integer k
    unsigned int k ;
    std::cout << "k? " ;

    // if we have been able to read k and k is at least 2
    if( std::cin >> k && k > 1 )
    {
        // then read k integers
        std::cout << "enter " << k << " integers\n" ;

        // create a vector to hold these k integers
        std::vector<int> integers ;

        // read k integers one by one into the vector
        int i ;
        while( integers.size() < k && std::cin >> i ) integers.push_back(i) ;

        if( integers.size() == k ) // if we have read k integers
        {
            // 2) take the max integer and the min integer and add the difference
            //    between them to the answer.
            // 3) delete the max and min integer that have been used in step 2.

            int answer = 0 ;

            // rearrange the integers in ascending order
            std::sort( integers.begin(), integers.end() ) ;

            int pos_min = 0 ; // position of min integer
            int pos_max = integers.size() - 1 ; // position of max integer

            while( pos_min < pos_max ) // as long as there are at least two integers left
            {
                // add the difference between them to the answer.
                answer += integers[pos_max] - integers[pos_min] ;

                // delete the max and min integer that have been used in step 2
                ++pos_min ; // the new min integer is the next integer after the old min
                --pos_max ; // the new max integer is the previous integer after the old max
            }

            // print out the answer
            std::cout << "answer: " << answer << '\n' ;
        }
    }
}

> my idea was to make two priority queues and when i read an integer i add it to first priority queue
> and add it to second priority queue as a negative number.
> so that when I take the top element of first priority queue that would be the max
> and from the second that would be the min.

Yes, it is a good (inventive) idea.

Something like this:

#include <iostream>
#include <queue>
#include <functional>

int main()
{
    // read an integer k
    unsigned int k ;
    std::cout << "k? " ;

    // if we have been able to read k and k is at least 2
    if( std::cin >> k && k > 1 )
    {
        // then read k integers
        std::cout << "enter " << k << " integers\n" ;

        // create a pair of priority_queues to hold these k integers
        std::priority_queue<int> pos_q ;
        std::priority_queue<int> neg_q ; // holds negetive of the numbers

        // read k integers one by one into the priority queues
        int i ;
        while( pos_q.size() < k && std::cin >> i )
        {
            pos_q.push(i) ;
            neg_q.push( -i ) ;
        }

        if( pos_q.size() == k ) // if we have read k integers
        {
            // 2) take the max integer and the min integer and add the difference
            //    between them to the answer.
            // 3) delete the max and min integer that have been used in step 2.

            int answer = 0 ;

            // take the half the number of integers from each priority queue
            while( pos_q.size() > k/2 ) // as long as there are integers left
            {
                // add the difference between them to the answer.
                answer += pos_q.top() + neg_q.top() ; // yes, as in your code +

                // delete the max and min integer that have been used in step 2
                pos_q.pop() ;
                neg_q.pop() ;
            }

            // print out the answer
            std::cout << "answer: " << answer << '\n' ;
        }
    }
}

[coder1]

thank you all for your help, and for vlad im sorry i wasnt understanding you my problem was that i should made the priority queues outside the for loop, im so sorry

[vlad from moscow]

I am glad that at last you have understood (?) that the error message was issued because the queues were empty. However if the queues will be placed outside the outer loop you can get this error message if you will enter the first k equal to 0. In this case the queues will be still empty and this statement

ans+=a.top()+b.top();

will generate the error..