1

I'm testing a very basic implementation of a heap by adding and deleting a lot (50k) random elements to it. However I never get to remove elements, as a SIGABRT occurs.

I've tried to initialize an array of integers with zeroes, but that didn't help.

int Heap::pop() {
if (size == 0) {
    std::cerr << "The heap is empty.\n";
    return 0;
}
if(size == 1){
    int key = heap[0];
    heap = new int[0];
    size = 0;
    return key;
}
else {
    int key = heap[0];

    int *temp;
    temp = heap;
    temp[0] = temp[size - 1];
    heap = new int[size - 1]; //GDB marks this line
    for (int i = 0; i < size - 1; i++)
        heap[i] = temp[i];

    heapifyDown(0);

    size--;
    return key;
}
}

It seems it fails when it's about to initialize an array of size 49992.

Shumatsu
  • 150
  • 9
  • 3
    You might best avoid that using just `std::vector` instead of fiddling with `new` and `delete` manually. – πάντα ῥεῖ Apr 02 '19 at 16:26
  • 3
    This is only a code excerpt. Please change it to a complete, minimal, reproducible piece of code which invokes the error. – Inon Peled Apr 02 '19 at 16:27
  • My money is on "If `size` ever becomes 0 then your code will do bad nasty things". Edit: See, the minimal example helps us eliminate that cause :) – Max Langhof Apr 02 '19 at 16:28
  • 1
    @InonPeled Pro tip: If you type `[mcve]` in a comment it will be rendered with the full wording and appropriate link like this: _[mcve]_ – πάντα ῥεῖ Apr 02 '19 at 16:34
  • _@Shumatsu_ You should note that this ^^^^^^^^^^^^^ is required when asking here about problems with code. – πάντα ῥεῖ Apr 02 '19 at 16:37
  • @πάνταῥεῖ Thanks, I was looking for that `[mcve]` [mcve] – Inon Peled Apr 02 '19 at 16:38
  • In modern c++ you will rarely need and want to use `new`, and `delete` (or even `malloc`, `free` or `realloc`). You only need them if you have to interact with libraries that requires their usage. When ever possible you want that c++ takes care of the lifetime and ownership. – t.niese Apr 02 '19 at 16:40
  • 1
    Also, there are already heap functions available such as [std::make_heap](https://en.cppreference.com/w/cpp/algorithm/make_heap) and [std::pop_heap](https://en.cppreference.com/w/cpp/algorithm/pop_heap) that do this work. – PaulMcKenzie Apr 02 '19 at 17:01
  • @InonPeled more secret codes here: https://stackoverflow.com/editing-help#comment-formatting . Remember that they are secret, so don't do anything silly like posting a link to them online. – user4581301 Apr 02 '19 at 17:08
  • 1
    @user4581301 as electronic secrets can be easily exposed (see, e.g., WikiLeaks), I shall make a hard copy of these and lock it in a drawer. – Inon Peled Apr 02 '19 at 17:13

1 Answers1

2

You never deallocate the memory that you allocate with new. You will therefore eventually run out of heap space if your code runs long enough, at which point further allocations will fail (as GDB shows).

In the snippet you have shown, all that is missing is a delete[] temp; after the loop that copies the data. But these errors are easily avoided by using the standard library containers (such as std::vector) which do all of this for you.

Max Langhof
  • 23,383
  • 5
  • 39
  • 72
  • 8
    @Shumatsu - "I knew it was some stupid mistake" - and the mistake was "using manual memory management", *not* forgetting the `delete[]` call. Btw; you should accept the answer if it solved your problem. – Jesper Juhl Apr 02 '19 at 16:37
  • 1
    @Shumatsu Handy reading: https://stackoverflow.com/questions/6500313/why-should-c-programmers-minimize-use-of-new – user4581301 Apr 02 '19 at 17:09