CODEWITHSUNDEEP
c++referencevectorconstantspriority-queue
cyrux
cyrux

Reputation: 243

Segmentation fault while using priority queues

I have a priority queue with elements of a class named A I need elements from this queue which may be lower down the queue (lesses priority). So , I am trying to pop a few elements until i get the element of my choice. Once i get the element of my choice i am planning to push all the elements i stored temporary in an array. I have a loop, and for every iteration i go further down the queue to check if the element i popped is of my choice . This way I have more data in the temporary array . The problems arises when I try to push data from this temp array back into the priority queue. The underlying container of priority is a vector and debugging shows that the problem is in stl_queue.h with line std::push_heap(c.begin(), c.end(), comp); (c is the vector)

I know this might be the wrong way to do it and i should probably use constructor instead of malloc and have a std:list instead of priority queue, but can some one let me know whats going on here ?

while(count < length_of_queue) // Iterate over all elements of queue
{

  A* temp_array = (A *)malloc(count * sizeof(A));;
  for (int i = 0;i<count;i++) // remove count number of elements from queue
  {
      temp_array[i] = priority queue.top();
      priority queue.pop(); // free_list is the priority queue
  }

  A check_element = free_list.top(); // Check if (count+1)th elements satisfies our         
                                     // criteria   
  if (criteria_satisfied)
  {
    priority_queue.pop();
    //freeing the temp_array and pushing back all the elements from temp_array into 
    // priority_queue like done in the else condition
    return check_element;
   }
  else
  {

    for (int i = 0;i<count;i++) // Push back all the elements popped until now
    {
      priority_queue.push(temp_array[i]); // Offending line
    }
    free (temp_array);
  }
  count++
}

Upvotes: 0

Views: 1967

Answers (2)

Mark B
Mark B

Reputation: 96311

If A is non-POD, then using malloc could cause all sorts of problems. Use a vector instead:

std::vector<A> temp_array(count);

The free would then go away completely.

Upvotes: 1

Michael Kristofik
Michael Kristofik

Reputation: 35218

Your malloc line allocates an array large enough to hold count objects of type A, but doesn't actually create any objects. Undefined behavior happens (e.g., a segfault) when you try to use objects that don't exist.

Try replacing your malloc with std::vector<A> temp_array(count). That'll give you (effectively) an array of count default-constructed A objects. More importantly, it'll free itself when it goes out of scope.

Upvotes: 1

Related Questions