9 Replies - 476 Views - Last Post: 28 September 2016 - 05:44 PM Rate Topic: -----

#1 Balthazar  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 152
  • Joined: 16-November 15

Vector Code

Posted 27 September 2016 - 04:30 PM

I am working on a homework assignment where we need to modify the code given to us in our book that is supposed to emulate a vector. I have all of that code down and the instructor also wants us to add push_back() and pop_back() functionality to the class. Is there a way I can access C++'s inner code to get the functions from the normal vector? If not, what's the best way of going about recreating it? I haven't written any code yet, because I've been looking for the functions. However, if I do need to try and create them I'm not sure exactly how to do the push_back. I am assuming I will create a function that will simply expand the "vector type" array, but how do I pass it the object that I want to add to it? We briefly touched on generics and the examples I copied from the book are generic (ie "SimpleVector<T>::push_back()" but I'm not sure what object type need to go in the ()... would it just be "T"? so like:
SimpleVector<T>::push_back(const SimpleVector &obj, T objToAdd)
{
	code here
}


Is This A Good Question/Topic? 0
  • +

Replies To: Vector Code

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Re: Vector Code

Posted 27 September 2016 - 05:26 PM

Some links for you to read:
http://www.cplusplus.../vector/vector/
http://www.dreaminco...ector-tutorial/
http://www.dreaminco...-using-vectors/
Was This Post Helpful? 0
  • +
  • -

#3 Balthazar  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 152
  • Joined: 16-November 15

Re: Vector Code

Posted 27 September 2016 - 07:20 PM

Thanks for the reply. Your third link (the link to your post) seems to be very close to what I need. I borrowed the "push_back" code and am trying to make it work with my vector class (and of course trying to learn how it all works in the process), but when I test my program it crashes when it tries to add my "item" to the array.

My vector class is called SimpleVector. I have created a SimpleVector of another class ProductionWorker by using SimpleVector<ProductionWorker> test2108 making the vector name "test2108" (2108 is my A113). I then created a ProductionWorker object and populated it's info. Then I try to add the object to my SimpleVector. It gets to the line of the code where it tries to actually add the object to the array. I am assuming the issue is with pointers, which I really suck at. But seeing as you don't have any pointers in your example, I'm a bit confused. I have tried adding * where I thought they should go, but that just produced more errors. Here's my code, any hints?

My driver:
int main()
{
	cout << "Creating vector.\n";
	SimpleVector<ProductionWorker> test2108;
	cout << "Vector Created\n";

	cout << "Creating Production Worker Object\n";
	ProductionWorker a;
	cout << "Object Created\n";
	cout << "Populating Object\n";
	a.setName("Bruce Wayne");
	a.setDate("02/01/2008");
	a.setNumber(1623);
	a.setPay(20.00);
	a.setShift(1);
	cout << "Object Populated\n";
	cout << "Adding Object to vector\n";
	test2108.push_back(a);
	cout << "Object added to vector\n";

	cout << "The size of the array is: " << test2108.size() << endl;



	cout << "\n\n";
	system("pause");
	return 0;

}


Here is the Push_Back function from my SimpleVector class. If need be I can post the entire thing:
//*******************************************
// My attempt at push_back. *
//*******************************************

template <class T>
void SimpleVector<T>::push_back(T &obj) {
	if (arraySize < maxsize) {
		cout << "Adding object to element " << arraySize << endl;
		aptr[arraySize] = obj; // <- This seems to be what's crashing the program.
		arraySize++;

	}
	else {
		cout << "Expanding Array\n";
		T *newarray;
		newarray = new T[maxsize * 2];
		memcpy(newarray, aptr, maxsize*sizeof(T));
		delete[] aptr;
		aptr = newarray;
		maxsize *= 2;
		aptr[arraySize] = obj;
		arraySize++;
	}
}

Was This Post Helpful? 0
  • +
  • -

#4 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 439
  • View blog
  • Posts: 1,147
  • Joined: 31-May 11

Re: Vector Code

Posted 27 September 2016 - 07:42 PM

You may have to post a smallest possible compilable sample for this one.

Just a note on the side though, you want your push_back to take const T &obj as an argument. You're going to copy it anyway, so no point in limiting yourself to non-const version. ;)
Was This Post Helpful? 0
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Re: Vector Code

Posted 28 September 2016 - 12:49 AM

Look at my constructor:
	arrayClass() : maxsize(2) {
		myArray = new int[maxsize]; // Start out with an array of 2 uninitialized elements
		mysize = 0; // We haven't initialized either element
	}


It initializes the vector as a dynamic array with 2 elements. How many does yours start with? I'm guessing none.

Quote

...you want your push_back to take const T &obj as an argument...

For anyone tempted to build their own vector class, note that my class is just an example intended to show how vectors came to be. I didn't worry about optimizing the code because I wasn't planning on using it for anything important. There's no need to since the actual vector class has been well tested so it is likely to be more efficient than anything I'd come up with in a few hours of coding.

That said, I think anyone looking to better understand vectors should build their own vector class. You'll get a good sense of the power and elegance of the actual vector class.
Was This Post Helpful? 0
  • +
  • -

#6 Balthazar  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 152
  • Joined: 16-November 15

Re: Vector Code

Posted 28 September 2016 - 06:18 AM

Thank you. I got the Push_Back function working. I now need to add a Pop_Back function, which I am assuming works very similarly, just in reverse. So I just copied the push_back code and modified it, but for some reason it crashes when it tries to delete the old array.
I have changed the variables to work with my code:
aptr = myArray
arraySize = mySize

I am not using a MaxSize because I only need the array to be as big as what's being used, due to needing to utilize the Pop_Back function.

template <class T>
void SimpleVector<T>::pop_back() {
	if (arraySize == 0) {
		cout << "Array size is " << arraySize << ". Nothing to pop back\n";
	}
	else {
		cout << "Shrinking Array\n";
		T *newarray;
		cout << "New Array Declared\n";
		newarray = new T[arraySize - 1];
		cout << "New Array Created with a size of " << arraySize - 1 << endl;
		memcpy(newarray, aptr, (arraySize - 1)*sizeof(T));
		cout << "Array copied\n";
		delete[] aptr; // this is what crashes it
		cout << "Old Array deleted\n";
		aptr = newarray;
		cout << "New array renamed\n";
		arraySize--;
		cout << "arraySize decreased to " << arraySize << endl;
	}
}



Thank you for all your help.

This post has been edited by Balthazar: 28 September 2016 - 06:20 AM

Was This Post Helpful? 0
  • +
  • -

#7 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Re: Vector Code

Posted 28 September 2016 - 09:28 AM

Look at my erase method:
	void erase(int n) {
		if(n < mysize && n >= 0) {
			for (int i = n; i < mysize-1; i++) {
				myarray[i] = myarray[i+1];
			}
			mysize--;
		}
	}


Notice that I don't bother to reallocate the array. Why would I? If I have N elements in an array holding a maximum of N elements and I want to add another, I need to allocate a new array and copy the old to it before adding the N+1th element. On the other hand, if I want to remove one element from an array holding a maximum of 2*N elements and I have N+1 do I really want to make the array smaller when I might need to add more elements later?
Was This Post Helpful? 0
  • +
  • -

#8 Balthazar  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 152
  • Joined: 16-November 15

Re: Vector Code

Posted 28 September 2016 - 09:51 AM

Well for this assignment I do need to remove the items. This is what the instructions say:

Quote

Add 3 production workers to the SimpleVector using push_back() and display the contents of the vector after each push_back(). Then remove workers using pop_back() and display the contents of the vector after each pop_back(). Use the SimpleVector's test for emptiness to show that the vector is empty after the pop_back()s are complete.

That's why I figured I would just reallocate the array to one less element.
Was This Post Helpful? 0
  • +
  • -

#9 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 439
  • View blog
  • Posts: 1,147
  • Joined: 31-May 11

Re: Vector Code

Posted 28 September 2016 - 01:24 PM

So I threw a few lines of code together to test some stuff:
Spoiler

where:
    void push_back(const T& obj) {
        if (allocated == size) {
            float ratio = pre_allocation_ratio;
            if (allocated < 100) {
                ratio *= 2.0f;
            } else if (allocated < 200) {
                ratio *= 1.5f;
            }
            size_t new_allocated = allocated * ratio;
            if (new_allocated <= allocated) {
                new_allocated = allocated + 1;
            }
            reallocate(new_allocated); 
        }
        data[size] = obj;
        size += 1;
    }
    
    // slow version, with shrinking available
    T pop_back() {
        if (!auto_shrink) {
            return data[--size];
        } else {
            T tmp = data[size - 1];
            if (1.0f * size/allocated < deallocation_ratio) {
                size_t new_allocated = allocated * deallocation_ratio;
                if (new_allocated >= allocated) {
                    new_allocated = allocated - 1;
                }
                reallocate(new_allocated);
            }
            size -= 1;
            return tmp;
        }
    }
    
    // fast version, without shrinking
    T pop_back2() {
        return data[--size];
    }

This of course points out the obvious - you want to have some strategy of allocating more memory in case of many consecutive push_backs, but regardless of that - from the point of view of the user - if you know that you'll have many consecutive push_backs - it's best to reserve enough memory upfront. If that test did reallocate memory every single push_back and pop_back... Well, let's say that I'd probably still be running it.

Anyway, it's okay for your vector to "pretend" that it shrinks in pop_back, after all - that's what std::vector does too. ; )

This post has been edited by Xupicor: 28 September 2016 - 01:26 PM

Was This Post Helpful? 1
  • +
  • -

#10 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Re: Vector Code

Posted 28 September 2016 - 05:44 PM

View PostXupicor, on 28 September 2016 - 04:24 PM, said:

Anyway, it's okay for your vector to "pretend" that it shrinks in pop_back, after all - that's what std::vector does too. ; )

Yes, I was trying to say that.

I believe that std::vector will usually start with an array of 0 items, then 1, 2, 4, 8, 16, 32, 64, etc. as it reallocates when the array needs to expand.
This depends on the implementation, but that seems to be the most efficient for most situations. If you know you're going to start with a large vector, then use the resize() method.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1