Templated List errors with Insert

This is a discussion on Templated List errors with Insert within the C++ Programming forums, part of the General Programming Boards category; I'm writing a List Class for use in a school project (it's not due in a week or two, not ...

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    Templated List errors with Insert

    I'm writing a List Class for use in a school project (it's not due in a week or two, not monday) and when I use it to insert an item, the program crashes. I have an idea of what is wrong, but I'm not sure what to do; I just can't see how to fix it.

    I believe the problem is with the constructor and/or the insert function. The problem is that it is trying to insert an item at an invalid point in the list. I will post the few functions, if you need to see the whole project, I will post it.

    Code:
    template <class T>
    bool List<T>::isEmpty()
    {
    	return numItems == -1;
    }
    
    template <class T>
    bool List<T>::isFull()
    {
    	return numItems == MAXSIZE;
    }
    
    template <class T>
    bool List<T>::isValidPos(int n)
    {
    	if ((n >= 0) && (n < numItems))
    		return true;
    	//if ((n > numItems) || (n < 1))
    	//	return false;
    	return false;
    }
    
    template <class T>
    List<T>::List(int n):MAXSIZE(n)
    {
    	data = new T[MAXSIZE];
    	numItems = 0;
    	curpos = 0;
    }
    
    template <class T>
    bool List<T>::insert(const T &r)
    {
    	if (isFull())
    		return false;
    	if (isValidPos())
    	{
    		for (int i=numItems; i>=curpos; i--)
    			data[i+1] = data[i];
    		data[curpos] = r;
    		numItems++;
    		return true;
    	}
    	return false;
    }
    Those are in the header file; this is how I use it in the driver.cpp file.

    Code:
    int main()
    {
    	List<int> a(10);
    	a.insert(1);
    	a.insert(2);
    	int tmp;
    	a.getData(tmp);
    	cout << tmp << endl;
    	a.next();
    	a.getData(tmp);
    	cout << tmp << endl;
    	return 0;
    }
    Thanks for help, but please don't post code.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    First off, make sure list container has space for a new item.

    Second, modify your code.

    // numItems is already the next index

    for (int i = numItems; i >= curpos; --i)
    data[i] = data[i];

    Kuphryn

  3. #3
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Quote Originally Posted by kuphryn
    First off, make sure list container has space for a new item.

    Second, modify your code.

    // numItems is already the next index

    for (int i = numItems; i >= curpos; --i)
    data[i] = data[i];

    Kuphryn
    By check for space do you mean check if the list is full, because I have the function isFull() checked, and I also check if the position is valid. What am I supposed to be modifying in that code? Do you mean to check if there's space?


    I forgot to tell main elements in the class.
    Code:
    template <class T>
    class List
    {
    	private:
    		T *data;
    		int numItems, curpos;
    		const int MAXSIZE;
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  4. #4
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    You need to decide if data[numItems] is the last item, or one past the end. I suggest one past the end, this is the convention used by the stl, that quite frankly you should learn about before new and delete, but that's another battle. In any event I expect your bug is that you attempt to read data[i] where i is -1. For one past the end semantics the inital value of numItems is zero, the isEmpty needs to be changed to reflect this. The current position on an empty list is also zero. to insert a new element you start at numItems (provided it is strictly less than MaxItems) and copy i-1 to i decrementing while strictly greater than current position. On an empty list with both equal to zero this does nothing.

    If you want numItems to be equal to the last valid element (leading to the annoying and confusing fact that the actual number of items is numItems+1) you must insure that current element is zero becuse the curent element must now be greater than numItems on an empty list.

  5. #5
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Alright, I've changed the code so that numItems is one past the last as suggested. I still get the same problems. I'm not seeing why this won't work.

    Code:
    template <class T>
    List<T>::List(int n):MAXSIZE(n)
    {
    	data = new T[MAXSIZE];
    	numItems = 0;
    	curpos = 1;
    }
    
    template <class T>
    bool List<T>::isEmpty()
    {
    	return numItems == 0;
    }
    
    template <class T>
    bool List<T>::isFull()
    {
    	return numItems == MAXSIZE;
    }
    
    template <class T>
    bool List<T>::isValidPos(int n)
    {
    	return ((n >= 0) && (n < numItems));
    }
    template <class T>
    bool List<T>::insert(const T &r)
    {
    	if (isFull())
    		return false;
    	for (int i=numItems; i>curpos; i--)
    		data[i] = data[i-1];
    	data[curpos] = r;
    	numItems++;
    	return true;
    }
    
    template <class T>
    bool List<T>::remove()
    {
    	if (isEmpty())
    		return false;
    	for (int i=curpos; i<numItems; i++)
    		data[i] = data[i+1];
    	numItems--;
    	return true;
    }
    
    template <class T>
    bool List<T>::getData(T &r)
    {
    	if (!isValidPos() && !isEmpty())
    	{
    		r = data[curpos];
    		return true;
    	}
    	return false;
    }
    
    template <class T>
    bool List<T>::next()
    {
    	if (curpos == (numItems-1))
    		return false;
    	curpos++;
    	return true;
    }
    I did as you suggested, and even have code from a list and corrected a few numbers, but the same thing still happens. Am I initializing it ok? argh.

    Here's how I use it in main:
    Code:
    int main()
    {
    	List<int> a(10);
    	a.insert(1);
    	a.insert(2);
    	int tmp;
    	a.getData(tmp);
    	cout << tmp << endl;
    	a.next();
    	a.getData(tmp);
    	cout << tmp << endl;
    	return 0;
    }
    Sorry for all the long code. If someone is willing to look at the whole thing (in case the problem is not in what I've posted, but I'm pretty sure it's there) I can email it to them or post it here. Thanks for the help too.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Here's what I think is happening--as comments.
    If I'm corrrect, how to fix it I'll leave up to you:

    List<int> a(10);
    //a is 10 element array, indexes are 0-9
    //MAXSIZE == 10
    //curpos == 1 by constructor
    //numItems == 0 by constructor

    a.insert(1);
    //numItems != MAXSIZE
    //numItems ! > curpos
    //therefore no data shift
    //value of 1 inserted at a[1]
    //numItems increases to 1
    //curpos remains 1

    a.insert(2);
    //numItems != MAXSIZE
    //numItems !> curpos
    //therefore no data shift
    //value of 2 inserted at a[1] overwriting previous value
    //numItems increases to 2
    //curpos remains 1

    int tmp;
    a.getData(tmp);
    cout << tmp << endl;
    //output to screen == 2

    a.next();
    //curpos == numItems - 1 therefore return call before call to increase curpos
    //therefore curpos remains 1

    a.getData(tmp);
    cout << tmp << endl;
    //output still == 2----------ooops

  7. #7
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    OMFG. OMFG. Error was in a completely different place. Go figure. Thank you so much elad. It got me thinking a bit more. Decided to test the getData(), 'cause the data getting printed was some sort of address; orriginally I thought to be because insert failed. Turns out my getData() was bailing out because I had !isValidPos(). damn damn damn.
    :::smacks palm on forehead <-- programmer's high five:::
    Wow, I really appreciate the help, and going through the trouble of not using code. Thanks alot guys.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 06:29 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21