Creating and using array in Heap

Question

as part of my study we are learning about using the "Heap" and were tasked with writing a short maths program with the use of pointers to reference and deference the heap. As a bit of personal learning I've tried to replicate this with an Array, by creating one and using a Binary Search on it. But it simply won't work.

Here's my code:

#include <iostream>
#include <Windows.h>
using namespace std;

int main()
{

//creating pointers
int* ii = new int;
int* top = new int;
int* bottom = new int;
int* uArray = new int[12];
int* uChoice = new int;

//assigning values in location of pointer
*ii = 5;
*top = 11;
*bottom = 0;

cout<<"Please input a value between 1 and 12 to find in the array: \t";
cin >> *uChoice;

for (int x = 0; x<12; x++) //adding values into the array
{
    uArray[x] = x;
    cout<<x;
    Sleep(1000);//checking loop works
}


while (uArray[*ii] != *uChoice)
{
    if (uArray[*ii] > *uChoice)
    {
        *bottom = *ii;
        *ii = (*top + *bottom)/2;
    }

    else 
    {
        *top = *ii;
        *ii = (*top + *bottom) /2;
    }

    if (*uChoice == *ii)
    {
        break;
    }


}

//clearing pointers.
delete ii;
delete top;
delete bottom;
delete uArray;
ii = 0;
top = 0;
bottom = 0;
uArray = 0;

cout<<uChoice<<" Found at position: \t"<< *ii;
Sleep(10000);
return 0;

}

Many thanks in advance.

[Edit:] The error occurs within the while loop. Something is happening that means its not correctly searching the array. Sorry i didn't clarify this.

Even if you are using pointers because you want to learn about them, use them properly. Having ii, top, bottom and uChoice be pointers is pointless, don’t do it. Also, be aware that in real code you wouldn’t use pointers at all in this situation, you’d use a container class. — Konrad Rudolph
– Konrad Rudolph, Commented Oct 12, 2012 at 12:21

Ian Goldby · Accepted Answer · 2012-10-12 11:53:22Z

3

The delete keyword frees the memory pointed to by the pointer. So you should not try to use the pointer again after that.

Also, when the pointer is to an array you must use the delete[] uArray syntax, or the memory won't be freed properly.

Not sure if this is the part that "won't work" as you weren't more specific.

answered Oct 12, 2012 at 11:53

Ian Goldby

6,2351 gold badge50 silver badges91 bronze badges

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

4 Comments

Ian Goldby Over a year ago

@KonradRudolph I was looking at the final cout of *ii after ii is deleted and reset to zero.

Konrad Rudolph Over a year ago

@IanGoldby Oh, true – I didn’t see that.

Konrad Rudolph Over a year ago

@WillzSawyer You’re lucky (or rather, unlucky!) that it works. It could equally well blow up or output a completely wrong result.

WillzSawyer Over a year ago

@KonradRudolph This wasn't the error, :( I put in 5 as my search number...well its the first number it looks at so i worked, the error is in the while loop.

Alok Save · Accepted Answer · 2012-10-12 11:52:01Z

0

Technically, Standard does not define "Heap" but as far implementations do it, new creates elements on Freestore and not Heap. malloc() creates elements on Heap.

Good Read:
GotW #9: Memory Management - Part I

You have an Undefined Behavior lurking when you did:

   int* uArray = new int[12];
   delete uArray;

You need:

delete []uArray;

answered Oct 12, 2012 at 11:52

Alok Save

208k56 gold badges448 silver badges540 bronze badges

2 Comments

Ian Goldby Over a year ago

Freestore is a C++ concept whereas the heap is an OS concept. I'm wondering whether at the OS level, Freestore is on the heap anyway?

Alok Save Over a year ago

@IanGoldby: Yes it is.Given the usage specifications that Freestore demands, it has to be some sort of an Heap :)

Ian Goldby · Accepted Answer · 2012-10-15 14:06:06Z

The reason that the while loop doesn't find the correct element in the array is nothing to do with the use of pointers. I could just give you the answer directly, but it will be more useful to you to find it yourself (before you look at the spoiler below).

I suggest you try running the code in a debugger. If you haven't used the debugger before, I strongly recommend you try it. Set a breakpoint at the start of the while loop. You might find it useful to write down on a piece of paper the contents of the uArray[] array for reference. Then step through the while loop one line at a time, paying careful attention to the if statement - whether it goes into the if clause or the else clause, and as a consequence whether it moves *top or *bottom. See if what happens makes sense given the value of *uChoice compared to uArray[*ii].

It's a trivial mistake and you'll kick yourself once you spot it. But the more useful lesson is in how to debug your code.

(If you don't have a debugger, you can achieve the same effect by inserting a few cout statements in the while loop to print out the values of the key variables.)

Here's the answer (mouse-over to see it):

The greater-than operator should be a less-than in the test comparing uArray[*ii] and *uChoice. If the number you are searching for is less than the value in the array, you know it is in the bottom half, so you want to move the top down, not the bottom up.

Collectives™ on Stack Overflow

Creating and using array in Heap

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related