Copy Constructor

[stoneJax]

I am trying to modify a copy constructor from a previous program so that it can work with a templated class. The last line of the function uses strpy(). Now, with a template I can see that I need to be able to copy any data type (ItemType), but I am not sure what kind of code I should use to replace this. Is there something from a library, or should coding something?

const int MAX_STACK = 5;

template<class ItemType>
class ArrayStack : public StackInterface<ItemType>
{
private:
	static const int DEFAULT_CAPACITY = 1;
	ItemType items[DEFAULT_CAPACITY]; // Array of stack items
	int top;                     // Index to top of stack
	int capacity;
	ItemType* ptr;

public:
	ArrayStack(); 	
	ArrayStack(const ArrayStack<ItemType>& right);
	~ArrayStack();
	ArrayStack operator = (const ArrayStack<ItemType>& right);

	bool isEmpty() const;
	bool push(const ItemType& newEntry);
	bool pop();
	ItemType peek() const;
}; 



template<class ItemType>
ArrayStack<ItemType>::ArrayStack(const ArrayStack<ItemType>& right)
{
	capacity = right.capacity;
	ptr = new ItemType[DEFAULT_CAPACITY];
	strcpy(ptr, right.ptr);
}  

[stoneJax]

I tried the modification below, but when I try to create an object in the client such as ArrayStack stack; I get an error with a red squiggly line that says, "argument list for class template "ArrayStack" is missing."

template<class ItemType>
ArrayStack<ItemType>::ArrayStack(const ArrayStack<ItemType>& right)
{
	capacity = right.capacity;
	ptr = new ItemType[DEFAULT_CAPACITY];
	for (int i = 0; i < MAX_STACK; i++)
	{
		ptr[i] = items[i];
	}
}  

[lastchance]

You declared a constructor for ArrayStack with no arguments on line 14.
ArrayStack();
This is just a prototype. Did you ever define it?

[coder777]

I tried the modification below

Your modification does not have anything to do with the error, does it?

I try to create an object in the client such as ArrayStack stack;

Yes, with template you need to tell the compiler what type you want, i.e.: ArrayStack<char> stack;

[stoneJax]

Hi guys, the default constructor is given to me so yes it is defined. In fact all the functions are given already defined and my job is to create the big 3 so the program can use dynamic memory.

Totally makes sense to have to plug in a template data type such as ArrayStack<char> stack; . I can create an object fine now.

I am still stuck on the copy constructor. Not sure how I should be using ptr pointer inside the copy constructor.

[stoneJax]

I think I got it.

capacity = right.capacity;
	ptr = new ItemType[right.DEFAULT_CAPACITY];
	for(int count = 0; count < right.capacity; count++)
		ptr[count] = right.ptr[count];

[coder777]

I think I got it.

No, this way you can store exactly 1 element not more. Line 7/8 doesn't make sense, just remove them.

capacity = right.capacity;
	ptr = new ItemType[capacity]; // Note
	for(int count = 0; count < right.capacity; count++)
		ptr[count] = right.ptr[count];

[dhayden]

You need to set top in your copy constructor.

[keskiverto]

Hi guys, the default constructor is given to me so yes it is defined.

What class invariants does it set?
What can we trust about a default constructed ArrayStack?
What can we trust about every ArrayStack?

Was all of this given to you?

private:
	static const int DEFAULT_CAPACITY = 1;
	ItemType items[DEFAULT_CAPACITY]; // Array of stack items
	int top;                     // Index to top of stack
	int capacity;
	ItemType* ptr;

What is the purpose of, for example the 'items'?

[stoneJax]

Not sure about the invariants, but the default constructor is given with its job to set top to -1. I was instructed that I would need a capacity variable, but was not told how or where; I put it in the default constructor and initialized it to 1. ItemType* ptr; I created because I am modeling the instructor's approach in creating the big 3.

I'll list the default constructor too.

I added the if statement to delete any old contents in the array.

template<class ItemType>
ArrayStack<ItemType>::ArrayStack() : top(-1), capacity(1)
{
}  




template<class ItemType>
ArrayStack<ItemType>::ArrayStack(const ArrayStack<ItemType>& right)
{
	capacity = right.capacity;

	if (ptr != nullptr)
		delete[] ptr;

	ptr = new ItemType[right.capacity];
	for(int count = 0; count < right.capacity; count++)
		ptr[count] = right.ptr[count];
}  

[coder777]

As @dhayden said: In the copy constructor top needs to be set.

What is top good for? Isn't the first element always the top?

I put it in the default constructor and initialized it to 1

Why 1? Would't be capacity=0 and ptr=nullptr more usefull? Of you use DEFAULT_CAPACITY:

template<class ItemType>
ArrayStack<ItemType>::ArrayStack() : top(-1), capacity(DEFAULT_CAPACITY)
{
  ptr = ItemType[DEFAULT_CAPACITY];
}

[dhayden]

What is top good for? Isn't the first element always the top?

Definitely not. If you made the first item the top then pushing and popping would require moving all items in the stack. Instead, you make the top of the stack at the end of the array so that pushing and popping doesn't move the other items, unless you have to reallocate.

StoneJax, I think the problem here is that your prof hasn't really explained how the array is supposed to grow and shrink. I'll try to do that here.

Of course one way to store the data is to an array that is always exactly the right size for the number of items in the stack. But since the number of items changes each time you push or pop, you'd have to allocate a new array each time you pushed or popped. Performance would be terrible.

To avoid this, you instead allocate extra space in the array. When you push enough items to fill that array, you allocate a new array with more space.

But now there's a problem: suppose you have space in the array for 10 items and the stack has 4 items in it. You need to keep track of both values. By convention, we call the total number of items that the array can hold the capacity. We call the number of items that are currently in use in the array, the size.

A bunch of the code deals with managing the size and capacity and adjusting them when needed.

Now let's look at that capacity and answer some questions.

Q1: How big should the capacity be initially?
A1: The DEFAULT_CAPACITY

Q2: When you have to expand the capacity, by how much should you do it?
A2: I think you said in another thread that it should double.

Now be careful in the copy constructor. You want to copy right.size items, not right.capacity.

Hope this helps.

[keskiverto]

Let me see, the

template<class ItemType>
ArrayStack<ItemType>::ArrayStack() : top(-1), capacity(1)
{
}

* Is not the default constructor given to you, because you said that you did add the 'capacity'.
* You have to modify the (default) constructor(s); creating "big 3" is not sufficient.

Was the original ArrayStack using plain array?
As in:

template<class ItemType>
class ArrayStack : public StackInterface<ItemType>
{
private:
  static const int DEFAULT_CAPACITY {1};
  ItemType items[DEFAULT_CAPACITY]; // array
  int top;
public:
  // interface
};

The 'items' is then clearly the array that holds all the items of the stack.

In order to convert the stack to use dynamic array, one does not add. One has to replace:

template<class ItemType>
class ArrayStack : public StackInterface<ItemType>
{
private:
  static const int DEFAULT_CAPACITY {1};
  ItemType* items; // array
  int capacity; // size of the array
  int top;
public:
  // interface
};

The static array's size is known but the size of dynamic array has to be stored.
The static array is allocated automatically but the dynamic array has to be allocated (copied and deallocated) explicitly.

template<class ItemType>
ArrayStack<ItemType>::ArrayStack()
: items(new ItemType[DEFAULT_CAPACITY]), capacity(DEFAULT_CAPACITY), top(-1)
{
}

// "big 3" 

An optional addition is a reallocation procedure that allows the stack to grow, if needed.
Without that the dynamic array won't resize.

[stoneJax]

dhayden, your right the the top is always at the end. With the end meaning the last element that contains a value, and not the end as in capacity. The nature of a stack is first in last out, so popping values off the top will eventually go back to the first element.

Your also right that my professor hasn't explained how the array is supposed to grow and shrink; just says it has to be converted so it's dynamic, and to double its size whenever it becomes full.

I took note of how you mention:
Now be careful in the copy constructor. You want to copy right.size items, not right.capacity.

That makes sense. Why iterate past any element that doesn't contain a value. I thought that since top is to represent the last "element number" that contains a value (it's initialized to -1 in the default constructor, but it is incremented in the push() function whenever a value is added to the stack), that I can use this for the size variable that you speak of.

I have a question about that though. What is the difference between doing for(int count = 0; count < right.top; count++)
or for(int count = 0; count < top; count++) ? I tried them both and they both seem to work fine.





keskiverto, thanks for pointing out that items is the array to focus on, and putting it in the default constructor. I did get rid the ptr variable, but I was actually initializing items as ItemType* items = new ItemType[DEFAULT_CAPACITY]; in the header instead of the default constructor though. After you pointed that out, it makes sense to put it in the default constructor.




Here is my updated code:

template<class ItemType>
ArrayStack<ItemType>::ArrayStack() : items(new ItemType[DEFAULT_CAPACITY]), top(-1), capacity(DEFAULT_CAPACITY)
{
}  





template<class ItemType>
ArrayStack<ItemType>::ArrayStack(const ArrayStack<ItemType>& right)
{
	capacity = right.capacity;

	if (items != nullptr)
		delete[] items;

	items = new ItemType[right.capacity];
	for(int count = 0; count < right.top; count++)
		items[count] = right.items[count];
}  

[keskiverto]

Copy constructor is a constructor. It constructs a new object.
Therefore, line 15-16 makes no sense. Where was 'items' used before this point?

Member initializer list syntax:

template<class ItemType>
ArrayStack<ItemType>::ArrayStack(const ArrayStack<ItemType>& right)
 : items(new ItemType[right.capacity]), top(???), capacity(right.capacity)
{
	for ( int count = 0; count < ???; ++count )
		items[count] = right.items[count];
}

The ??? are for you to figure out. Pay attention to definitions of "top" and "size".
Aren't they:
top -- index of the last "on top of stack" element
size -- number of elements currently in stack

[stoneJax]

Regarding lines 15-16, my thought for an initial object created wouldn't need this since there would be nothing to delete at this point; however, when creating a second object wouldn't I need to delete the items so there will be a clean copy for the new object?

With the question marks, it looks like your saying if top is initialized to -1, 0 is not less than -1, therefore the loop will not execute. This should be ok when there is an empty stack right, as there would be nothing to copy. However, if the stack has been pushed once, then top would increment to zero, so I guess the for loop should be

for ( int count = 0; count <= top; ++count )

that way if count = 0 and top = 0, it will assign the value. Also, if there is a size of 10, then the for loop will count from 0-9 as 10 items.


I don't understand why you put : items(new ItemType[right.capacity]), top(???), capacity(right.capacity) in the copy constructor. Why is it not sufficient to just have it in the default constructor?

[keskiverto]

Look at integers:

int x = 42;
int y;
// What is the value of y now? 

The answer is that we do not know. The fact that we did set some value to the x has no effect on the value of y.

struct MyInt {
  int val;
  MyInt( int v ) : val(v) {}
};

MyInt z( 42 );
MyInt w;
// Should integer z.val affect integer w.val even if x does not affect y? 

The answer in no: z.val and w.val are separate and unrelated integers.

You construct what does not yet exist.

Every constructor does member initialization before it runs the code in its body. If you want to initialize members differently than what would happen by default, then you have to write initializers.

[stoneJax]

Thank you for pointing out the things to get rid of, and making sure the copy constructor has an initializer list. I see what you mean now.