Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 13 of 13

Thread: Have a C++ project due soon and am not sure if I'm using pointers right.

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Have a C++ project due soon and am not sure if I'm using pointers right.

    I have a spot where I'm worried that, since a silly IDE glitch won't let it run properly, perhaps as I don't have a makefile or put it in wrong package or something (new IDE/compiler).

    Out: 10th September 2011 Due: 19th September 2011 at 11:59pm
    In this assignment you will write a class two versions of an adjusting array. The first version will work similar to the ArrayList class in Java (or vector class in C++), while the second one will make deletion more efficient.
    Part 1: Adjusting Array
    Write a class AdjustArray that represents an array of integers. Initially it has a size of 1. At any time, it can be partially full, so it keeps track of its current occupied size, as well as its true size. Add the following to this class:
    1. A default constructor. It initializes the array to have all 0’s.
    2. An overloaded [] operator as follows: int& operator [](unsigned int i). This returns a reference to the number at index ‘i’. Returning a reference is no different than returning the value at that position, C++ takes care of actually returning a reference to it. If ‘i’ is beyond the size of the array, so be it (the program will likely crash if this case is encountered at run-time).
    3. A function “push_back(int m)” that will add ‘m’ to the end of the occupied part of the array. If the array is already full, it must first double the size of the array before adding this number. Double the array by creating a new array that is twice as big, copying all the elements of this array to the new one, and the making the new array as the “current” one. Be sure to free up any memory as necessary!
    4. A function “erase(unsigned int i)”. This function deletes the number at position ‘i’ by shifting everything to its right by one position to the left. Note: the size of the occupied part of the array reduces by 1. If the array’s occupancy reduces to less than 50%, make the array half as big similar to how you expanded it.
    Write a main function that tests this class in all possible ways (i.e. adding elements, deleting from the middle and either ends, allowing the array to expand and contract, etc.). The main function is worth points!
    Part 2: Adjusting Array with Faster Deletion
    The above array does not delete an element efficiently (because of all the shifting). Make it more efficient as follows (write a separate class, do not modify the above class).
    1. Add an array “deletion” of booleans that maintains whether each position in the array of number is currently occupied, i.e. “deletion[i]= true” if number at index ‘i’ has been deleted, false otherwise.
    2. Modify erase so that it simply changes the above array, but does not shift anything.
    3. Add a variable that stores the smallest index that has been deleted.
    4. Modify the [] operator above as follows:
    a. If the index ‘i’ to be accessed is before the first deleted position, return reference directly.
    b. Otherwise, remove all “empty” positions to the left of this index ‘i’ by shifting elements to the left. This will move the “true” number to this position and the smallest index that has been deleted will be greater than ‘i’. Now return the reference. (If the occupancy falls below 50%, contract as before)
    Your main function does not change at all, and it should work as before.
    Extra Credit (5 points): Do step 4(b) in Part 2 without using an extra array. Hint: During shifting, keep track of the position which must shift, and the position it must shift to.

    I have these:

    AdjustArray.h:

    #ifndef _ADJUSTARRAY_H_
    #define _ADJUSTARRAY_H_
     
    class AdjustArray
    {
     
    public:
           AdjustArray();
           ~AdjustArray();
           void push_back(int m);
           void erase(unsigned int i);
           int& operator[](unsigned int i);
           void setSize(unsigned int size);
           unsigned int getSize() const;
           void setFilledSize(unsigned int filledSize);
           unsigned int getFilledSize() const;
           bool isFull() const;
     
     
           private: 
                    unsigned int size;
                    unsigned int filledSize;
                     int *array;
                    };
     
           #endif

    AdjjustArray.cpp (I misspelled Adjust but it's too late now to fix.):
    #include <iostream>
     
    using namespace std;
    #include "AdjustArray.h"
     
     
    AdjustArray::AdjustArray()
    {
                              array = new int[1];
                              setSize(1);
                              setFilledSize(0);
    int i;
    for (i =0; i < getSize(); i++)
    {
        array[i] = 0;
    }
     
    }
     
    AdjustArray::~AdjustArray()
    {
     
    }
     
     int& AdjustArray::operator[](unsigned int i)
    {
     
    if (i >= getSize())
    {
    cout <<"Invalid!";
    exit(1);
     
    }
     
    return array[i];
     
    }
     
    void AdjustArray::push_back(int m)
    {
     
    if(isFull() == true)
    {
                int newArray[getSize() * 2];
                int k;
                for (k = 0; k < getSize(); k++)
                {
                    newArray[k] = array[k];
     
                    }
     
                    newArray[getSize()] = m;
                    array = newArray;
                    setSize(getSize() *2);
                  //  setFilledSize(getFilledSize() + 1);
     
     
                }
     
                // this should set index getFilledSize() to m
                else
                {
                    array[getFilledSize()] = m;
     
                    }
     
     
    setFilledSize(getFilledSize() + 1);
     
     
    }
     
    void AdjustArray::erase(unsigned int i)
    {
     
    if (i >= getFilledSize())
    {
          cout <<"Cannot delete out of bounds!";
         return;
          }
     
     
               int x;
              for (x = i; x < getFilledSize(); x++)
              {
                  int temp = array[x+1];
                  array[x] = temp;
     
                  }
     
     
                  setFilledSize(getFilledSize() -1);
     
     
     
     
    }
     
    void AdjustArray::setSize(unsigned int size)
    {
    this -> size = size;
    }
     
    unsigned int AdjustArray::getSize() const
    {
    return size;
    }
     
    void AdjustArray::setFilledSize(unsigned int filledSize)
    {
    this -> filledSize = filledSize;
    }
     
    unsigned int AdjustArray::getFilledSize() const
    {
    return filledSize;
    }
     
    bool AdjustArray::isFull()const
    {
            if (getFilledSize() == getSize())
            return true;
            return false;
     
            }
     
     
    int main()
    {
        return 0;
    }

    BetterAdjustArray.h:
    #ifndef _BETTERADJUSTARRAY_H_
    #define _BETTERADJUSTARRAY_H_
     
    class BetterAdjustArray
    {
    public:
    BetterAdjustArray();
    ~BetterAdjustArray();
    int& operator[] (unsigned int i);
    unsigned int getSmallestIndexDeleted() const;
    void setSmallestIndexDeleted(unsigned int index);
    void erase (unsigned int i);
     
    private:
    *bool boolArray;
    unsigned int index;
    // more stuff 
     
     
    };
     
     
    #endif

    BetterAdjustArray.cpp:
     
    #include "BetterAdjustArray.h"
    #include <iostream>
    using namespace std;
     
     
    BetterAdjustArray()::BetterAdjustArray()
    {
     
     
    }
     
    BetterAdjustArray::~BetterAdjustArray()
    {
     
    }
     
    void BetterAdjustArray::setSmallestIndexDeleted(unsigned int index)
    {
    this -> index = index;
    }
     
    unsigned int BetterAdjustArray::getSmallestIndexDeleted() const
    {
    return index;
    }
     
    int& BetterAdjustArray:: operator[] (unsigned int i)
    {
     
    }
     
    void BetterAdjustArray::erase(unsigned int i)
    {
     
     
    }
     
    int main()
    {
    return 0;
    }

    When I was trying to double the size of the array, was I setting the pointer to a temporary variable that will be lost when the method or whatever ends, this making array point to nothing or am I worried about nothing?

    Also, how could you change erase to modify the array without shifting?
    Last edited by javapenguin; September 17th, 2011 at 09:29 PM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    C++ does not allow for dynamically sized arrays on the stack, you must allocate the array on the heap (a.k.a. using "new"), then you will need to delete it when you're done. Even assuming that you could have dynamically sized arrays you would still need to allocate the array on the heap because as soon as push_back() returned the stack will be reclaimed, along with the array and the pointer in your class will point to an invalid memory location.

    You can't erase an element from the array without shifting.

  3. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    I thought I did use "new" in the constructor for AdjustArray.

    Are you referring to when I set it to point to that larger array? If so, how would I do it then?

  4. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    How'd you get four coffee cups?

    The most I've ever seen is three before.

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    Yes, in push_back:

    int newArray[getSize() * 2];

    If this was legal (it isn't because C++ doesn't allow dynamic sized arrays on the stack), the actual array would go out of scope and be reclaimed after push_back returned.

    You're constructor has the correct syntax for using the new operator.

    One thing is that you will need to manually delete the old referenced array in push_back, as well as in the destructor when the whole object is being reclaimed. Note: you only need to delete items allocated on the heap. Items allocated on the stack are automatically reclaimed when they go out of scope.

    delete[] array; // frees the memory pointed to by array

  6. The Following User Says Thank You to helloworld922 For This Useful Post:

    javapenguin (September 18th, 2011)

  7. #6
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    What's the difference between heap and stack?

    int* newArray;
    newArray = new int[getSize() * 2];

    Is that right?
    Last edited by javapenguin; September 17th, 2011 at 11:03 PM.

  8. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    For the creation of the array, yes. You still need to manage memory cleanup or you'll be left with memory leaks.

    memory management - What and where are the stack and heap - Stack Overflow

  9. #8
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    When I call delete[] in push_back, do I want to delete

    array or newArray?

    I know in the destructor it would be a good idea to delete array.

  10. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    Which chunk of memory do you want to keep, the one pointed to by array, or the one pointed to by newArray (note: this is before they both point to the same array)?

  11. #10
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    He said to make the new array as the "current" one. I'm assuming array will point to newArray, but how do I get rid of the old space that array used to point to?

    When do I type:

    delete[] array;

    ?

    or do I delete newArray instead?

    I know both need to be deleted before the program ends.

  12. #11
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    void AdjustArray::push_back(int m)
    {
     
    if(isFull() == true)
    {
      int* newArray;
                newArray = new int[getSize() * 2];
                int k;
                for (k = 0; k < getSize(); k++)
                {
                    newArray[k] = array[k];
     
                    }
     
                    newArray[getSize()] = m;
                    array = newArray;
                    setSize(getSize() *2);
                  //  setFilledSize(getFilledSize() + 1);
     
     
                }
     
                // this should set index getFilledSize() to m
                else
                {
                    array[getFilledSize()] = m;
     
                    }
     
     
    setFilledSize(getFilledSize() + 1);
     
     
    }

    I believe the old array that the dynamic variable array USED to point to needs to have its memory deallocated but how do I do that?

    delete[] array;

    or

    delete[] newArray;

    ?

  13. #12
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Unhappy Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    What do I delete?

    delete[] newArray is causing weird things to happen.

    Where should I put delete[] array or whatever I need?

    Ok, delete[] array isn't working either.

    What's the problem?

    void AdjustArray::push_back(int m)
    {
     
    if(isFull() == true)
    {
      int* newArray;
                newArray = new int[getSize() * 2];
                int k;
                for (k = 0; k < getSize(); k++)
                {
                    newArray[k] = array[k];
     
                    }
     
                    newArray[getSize()] = m;
                    delete[] array;
                    array = newArray;
     
                    setSize(getSize() *2);
                  //  setFilledSize(getFilledSize() + 1);
     
     
                }
     
                // this should set index getFilledSize() to m
                else
                {
                    array[getFilledSize()] = m;
     
                    }
     
     
    setFilledSize(getFilledSize() + 1);
     
     
    }
     
    void AdjustArray::erase(unsigned int i)
    {
     
    if (i >= getFilledSize())
    {
          cout <<"Cannot delete out of bounds!";
         return;
          }
     
     
               int x;
              for (x = i; x < getFilledSize(); x++)
              {
                  int temp = array[x+1];
                  array[x] = temp;
     
                  }
     
     
                  setFilledSize(getFilledSize() -1);
     
    	      if (getFilledSize() < static_cast<int>(getSize()/2))
    		{
     
    		  int *newArray;
                      newArray = new int[static_cast<int>(getSize()/2)];
                      int v;
                      setFilledSize(static_cast<int>(getSize() /2));
    		  for (v= 0; v < getFilledSize(); v++)
    		    {
    		      newArray[v] = array[v];
    		    }
    delete[] array;
    		  array = newArray;
     
    		  setSize(getFilledSize());
     
    		}
     
     
     
    }

    ------Edit--------
    I edited it above. I think this is what they wanted.

    Now I need help on Part 2.
    Last edited by javapenguin; September 18th, 2011 at 08:53 PM. Reason: I think I fixed the problems with Part 1.

  14. #13
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Have a C++ project due soon and am not sure if I'm using pointers right.

    I've almost got it now, but I can't figure out some segmentation error that I'm thinking is being created, likely by an indexing error I can't see for some reason, inside the overloaded [] operator method, though there's a very small chance the error could be elsewhere.

    Ignore the part about AdjustArray. That can be removed for testing.

    BetterAdjustArray.cpp:

    #include "BetterAdjustArray.h"
    #include "AdjustArray.h"
    #include <iostream>
    using namespace std;
     
     
    BetterAdjustArray::BetterAdjustArray()
    {
      array = new int[1];
      int x;
      for ( x = 0; x < 1; x++)
        {
          array[x] = 0;
        }
      setFilledSize(0);
      setSize(1);
      boolArray = new bool[1];
     
      int y;
      for (y = 0; y < 1; y++)
        {
          boolArray[x] = true;
        }
     
    }
     
    BetterAdjustArray::~BetterAdjustArray()
    {
     delete[] boolArray;
     delete[] array;
     cout <<"BetterAdjustArray destructor called.\n";
    }
     
    void BetterAdjustArray::setSmallestIndexDeleted(unsigned int index)
    {
    this -> index = index;
    }
     
    unsigned int BetterAdjustArray::getSmallestIndexDeleted() const
    {
    return index;
    }
     
    int& BetterAdjustArray:: operator[] (unsigned int i)
    {
     
      if (i < getSmallestIndexDeleted())
        {
          return array[i];
        }
     
      else
        {
    while (getSmallestIndexDeleted() < i)
    {
     
    for (int x = getSmallestIndexDeleted(); x < (getFilledSize() -1); x++)
    {
    int temp = array[x+1];
    array[x] = temp;
     
    }
      setFilledSize(getFilledSize() -1);
     boolArray[getSmallestIndexDeleted()] = false;
    for (int v = getSmallestIndexDeleted()+1; v < getFilledSize(); v++)
    {
    if (boolArray[v] == true)
    {
    setSmallestIndexDeleted(v);
     cout<<"Smallest index deleted now is:" <<v <<"\n";
    break;
     
    }
     
    }
     
     
     
    }
     
     if (getFilledSize() < static_cast<int>(getSize()/2))
    		{
     
    		  int *newArray;
                      bool *newBoolArray;
                      newArray = new int[static_cast<int>(getSize()/2)];
                      newBoolArray = new bool[static_cast<int>(getSize()/2)];
                      int p;
    		  // setFilledSize(static_cast<int>(getSize() /2));
    		  for (p= 0; p < getFilledSize(); p++)
    		    {
    		      newArray[p] = array[p];
                          newBoolArray[p] = boolArray[p];
     
    		    }
     
    			 for (int w = getFilledSize(); w < static_cast<int>(getSize()/2); w++)
    			   {
                                 newArray[w] = 0;
                                 newBoolArray[w] = true;
    			   }
                      delete[] array;
    		  array = newArray;
                     delete[] boolArray;
                     boolArray = newBoolArray;
     
    		       setSize(static_cast<int>(getSize()/2));
     
    		}
    return array[i];
     
     
        }
     
     
    }
     
    void BetterAdjustArray::erase(unsigned int i)
    {
      if (i >= getFilledSize())
        {
          cout<<"No can do. \n";
          return;
        }
     
     
     
      boolArray[i] = true;
      if (i < getSmallestIndexDeleted())
        setSmallestIndexDeleted(i);
     
     
     
    }
     
     
    void BetterAdjustArray::setSize(unsigned int size)
    {
      this->size = size;
    }
     
    unsigned int BetterAdjustArray::getSize() const
    {
      return size;
    }
     
    void BetterAdjustArray::setFilledSize(unsigned int filledSize)
    {
      this->filledSize = filledSize;
    }
     
    unsigned int BetterAdjustArray::getFilledSize() const
    {
      return filledSize;
    }
     
    void BetterAdjustArray::push_back(int m)
    {
     
      if (isFull() == true)
        {
          int *newArray;
          bool *newBoolArray;
     
         //had forgotten to instantiate those two
         newArray = new int[getSize() * 2];
         newBoolArray = new bool[getSize() * 2];
             int k;
                for (k = 0; k < getSize(); k++)
                {
                    newArray[k] = array[k];
                    newBoolArray[k] = boolArray[k];
     
                    }
     
    	    for (int v = getSize(); v < (getSize() * 2); v++)
    	      {
     
    		newArray[v] = 0;
    		newBoolArray[v] = true;
    	      }
                    newArray[getSize()] = m;
                    newBoolArray[getSize()] = false;
                    delete[] array;
                    delete[] boolArray;
                    array = newArray;
                    boolArray = newBoolArray;
    		setSize(getSize() * 2);
     
        }
     
      else
        {
      array[getFilledSize()] = m;
      boolArray[getFilledSize()] = false;
        }
     
     
      setFilledSize(getFilledSize() + 1);
     
     
    }
     
    bool BetterAdjustArray::isFull() const
    {
      if (getFilledSize() == getSize())
        return true;
      return false;
    }
     
    void BetterAdjustArray::printArray() const
    {
     cout <<"[";
      for (int m =0; m < (getFilledSize()-1) ; m++)
        {
          cout << array[m] << ",";
        }
     
      cout <<array[getFilledSize() -1];
      cout <<"] \n";
     
     
    }
    int main()
    {
      AdjustArray arr;
      arr.push_back(222);
      arr.erase(0);
      cout <<arr[0];
      arr.push_back(11);
      cout <<arr[0] << "\n";
      arr.push_back(45);
      cout<< arr[0] << "," << arr[1] << "\n";
      arr.push_back(15);
      arr.push_back(99);
      arr.push_back(1111);
      arr.erase(2);
      arr.printArray();
     
      BetterAdjustArray barr;
      barr.push_back(91);
      barr.push_back(33);
      barr.push_back(45);
      barr.push_back(999);
      barr.push_back(15);
      barr.push_back(121);
      barr.push_back(555);
      barr.push_back(777);
      barr.push_back(888);
      barr.push_back(10000);
      barr.erase(2);
      barr.erase(5);
      barr.erase(7);
      cout <<barr[8] << "\n";
      barr.printArray();
      barr.push_back(19);
      barr.printArray();
     
    }

    It's saying

    "Segmentation error after printing out all the AdjustArray stuff, so no problems with AdjustArray.

    The problem could also be in push_back, though I'm thinking it's maybe my break statement in the overloaded [] method or an indexing error.

    Please help. This is almost done and due in about exactly 2 hours! It's nearly done but I need help or I might not be able to finish it all the way in time!

    Another thought would be because maybe I was supposed to set SmallestIndexDeleted() to 0 right away, but I don't think so.


    Thanks.

    -----Edit----
    Found part of error, but still getting message.
    Had forgotten to initialize some stuff. But it's still giving me the error, just in a different place.

    Now it's printing:
     

    [91,33,45,999,15,121,555,777,888,10000]
    Smallest index deleted now is:5
    Smallest index deleted now is:7
    Segmentation fault




    I was trying to set smallestIndexDeleted to be bigger than i.

    Maybe I should have not tried that in the for loop. Let me see if changing that makes a difference....

    Better but still not working quite as expected:

    [91,33,45,999,15,121,555,777,888,10000]
    Smallest index deleted now is:5
    Smallest index deleted now is:7

    Why isn't it adding 19 to the end and instead ending the program?
    Last edited by javapenguin; September 19th, 2011 at 10:26 PM.

Similar Threads

  1. Null pointers
    By Jared in forum What's Wrong With My Code?
    Replies: 13
    Last Post: October 7th, 2010, 06:40 PM
  2. Project
    By Mac in forum What's Wrong With My Code?
    Replies: 15
    Last Post: June 4th, 2010, 04:39 AM
  3. help with project
    By pairenoid in forum Object Oriented Programming
    Replies: 1
    Last Post: May 7th, 2010, 08:55 AM
  4. Need Help With Project
    By jstew132 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: November 11th, 2009, 06:15 PM
  5. [SOLVED] Problem in generating Fibonacci sequence in java
    By big_c in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 24th, 2009, 08:52 AM