0

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++
}
Improve this question
8
  • The best way to get help is to provide a free standing compilable piece of code that shows the problem. Since this code does not meet those requirements what you ask is made harder and might be imposable because the problem may not even be in the code you provided. Commented Jul 29, 2010 at 1:44
  • 1
    Replace the line with malloc with a vector. The above code leaks very badly. Commented Jul 29, 2010 at 1:47
  • You do not free(local_bd_arr) before returning. Also you do not push back any of the items back before returning. Commented Jul 29, 2010 at 1:56
  • 1
    If you've written that array cleanup code twice, then a better way to make the code more readable would be to move that code into a separate function. Commented Jul 29, 2010 at 2:45
  • 1
    @cyrux: Your simplifications does not help. We need to see the actual class definitions of several objects. What we need is a piece of code that compiles and runs. The code provided will not even compile let alone run. You will find that with programming that the location of the crash is usually a side effect of something completely different. But we can find the completely different part as you have not provided it. Commented Jul 29, 2010 at 16:58

2 Answers 2

Reset to default
1

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.

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

2 Comments

True, the malloc does create an array to hold count number of objects. But later on I also do this temp_array[i] = priority queue.top(); where priority queue has elements of type A. So there I have my first object constructed. The reason I know that it does is while debugging at the particular line priority_queue.push(temp_array[i]); I checked what temp_array[i] is (i = 0 in this case), and it de-referenced to an object of type A, but strangely enough, as i step into the code i get a SIGTERM in stl_vector.h I didn't do vectors initially cause my class A didnt have a default constructor
and the strange this is that , even without the default constructor , my code works now. I have a parametrized constructor in the class which should override the standard default constructor
1

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.

Improve this answer

5 Comments

Why O why would you do that! Use a vector in all situations like this so that you do not manually have to do the memory management. Any time your code looks like it contains business logic and memory management this is a code smell. The code is either business logic or memory management (never mix the two).
@martin , I agree that the code stinks. The reason why i didnt write a vector earlier is I thought if you have a initialization statement like std::vector<A> temp_array(count), its going to call the default constructor of A count number of times. I didnt have a default constructor for class A but only a parameterized one. So thought of using a malloc. Later on when I changed it to vector after taking suggestions , the code worked , which is again confusing because my class A doesnt have a default constructor. I know that problem solved, but I just want to know how the code is being raed
@cyrux Are you sure there's no default constructor for A? If the vector initialization compiles, the compiler thinks it was able to find one.
@Mark , I am pretty much sure there is not default constructor in class A. I just did a debug on the initialization vector statement to see what happens. The control went from init statement > vector():_Base() (stl_vector.h) > allocator.h >new_allocator.h and back to original file. It didnt go into class A at all. Weird
@cyrux: Please read me comment on your question. You need to provide more code. the definition of the class A for example (there are a whole host of problems that can be in the class definition that caused the problem but without the code it will never be solved). It may work now but that does not help you understand why it was broken. So ALWAYS post a compilable and runable version of the problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.