0

In a program for an array-based list, I have a function that calls the following 3 times:

list->remove(1)

My issue is that, when this prints out, it says it's deleting the original first item 3 times, rather than going to the next, new first item.

To be specific, when this code is called in test.cpp:

for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
                cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
                cout << "*** Error deleting from position " << i << " ***" << endl;
        }
}

it returns the following:

Deleting item 1.
Deleted item 1
Deleting item 2.
Deleted item 1
Deleting item 3.
Deleted item 1

Here is the ABList class I created. I think the error is in my remove method, but I cannot figure out where:

#ifndef _ABLIST_H_
#define _ABLIST_H_

#define LIST_MAX 10

#include <iostream>
#include "ABCList.hpp"

using namespace std;

template <class T>
class ABList : public ABCList<T> {

    private:
        T    a[LIST_MAX];
        int  size;

    public:
        ABList ();
        ~ABList ();
        virtual bool isEmpty ();
        virtual int  getLength ();
        virtual void insert (int pos, T item);
        virtual T    remove (int pos);
        virtual T    retrieve (int pos);
};


template <class T>
ABList<T>::ABList () {
    size = 0;
}

template <class T>
bool ABList<T>::isEmpty () {
    if (size == 0)
        return true;
    return false;
}

// returns size, which is updated whenever the list is lengthened or shortened
template <class T>
int ABList<T>::getLength() {
    return size;
}

template <class T>
void ABList<T>::insert(int pos, T item) {

    try {
        // if list is at maximum size
        if (size >= LIST_MAX)
            throw "Size is greater than or equal to LIST_MAX\n";
        // if "pos" is a negative number
        if (pos < 0)
            throw "Pos must be greater than 0\n";
        // if "pos" is outside the bounds of the existing list
        if (pos > size + 1)
            throw "Pos must be less than or equal to list size\n";

        //shift all items at indices > pos one index up
        for (int i = size; i >= pos; --i) {
            a[i] = a[i-1];
        }
        //insert new item
        a[pos-1] = item;
        //increment size
        size++;

    } catch (char* message) {
        cout << "Error: " << message;
        throw 1; // any int will do, to catch exception flag in test.cpp
    }
}

template <class T>
T ABList<T>::remove(int pos) {

    try {
        if (pos < 1)
            throw "Pos cannot be less than 1";
        if (pos > size)
            throw "Pos cannot be greater than size";
        //find T to be removed, to return later
        T temp = retrieve(pos);
        //shift all items greater than pos down one index
        for (int i = pos + 1; i <= size; i++)
            a[i] = a[i+1];
        // decrement size
        size--;
        return temp;
    } catch (char* message) {
        cout << "Error: " << message;
        throw 1;
    }
}

template <class T>
T ABList<T>::retrieve(int pos) {
    try {
        //check that pos is valid
        if (pos < 1 || pos > size)
            throw "Position is outside bounds of ABList\n";

        return a[pos-1];

    } catch (char* message) {
        cout << "Error: " << message;
    }
}


#endif

Here is the main program. (For the sake of this problem, I have to assume it is immutable):

int main () {
    // Testing the List implmenetations; first, get a list:
    ABCList<string> * list = getList();

    // Test "insert"
    cout << "Let's populate the list with a few items." << endl;
    for (int i = 1; i <= TEST_SIZE; i++) {
        int pos = getPos(i); // Randomise "i" to test
        string input;

        cout << "Enter a word to place into the list at position " << pos << ": ";
        cin >> input;

        try {
            list->insert(pos, input);
            cout << "Successfully inserted at position " << pos << "." << endl;
        }
        catch (int e) {
            cout << "*** Error inserting at position " << pos << " ***" << endl;
        }
}


    // Test "retrieve" & "getLength"
    cout << "List is as follows: \n\t";
    for (int i = 1; i <= list->getLength(); i++) {
        cout << list->retrieve(i) << " ";
    }
    cout << endl;


    // Test "delete" and "isEmpty"
    for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
            cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
            cout << "*** Error deleting from position " << i << " ***" << endl;
        }
    }

    // Done. Let the destructor handle the rest.
    delete list;

    return 0;
}
9
  • Check for off-by-one errors Commented Dec 24, 2012 at 19:32
  • You know that array indexes start at zero in c++ right? And instead of this: list->remove(1) did you mean this: list->remove(i) Commented Dec 24, 2012 at 19:34
  • @K-ballo Thanks, but that's not the issue. The issue is that remove() is returning the original item repeatedly, rather than going to the next item. Commented Dec 24, 2012 at 19:36
  • @SteveWellens - Yes, I know that array-based indices start at 0. The point of calling this, with a "1" is that it repeatedly deletes the first item in the list. That's what makes this problem tricky. Calling it with "i" does what I "want", but is not the right answer. Commented Dec 24, 2012 at 19:38
  • A non sequitur, but what you've implemented is not actually a list. Lists allow internal insertions. Commented Dec 24, 2012 at 19:56

2 Answers 2

2

During removal you do this after getting the item at (1) (which is really the item at a[0]:

for (int i = pos + 1; i <= size; i++)
    a[i] = a[i+1];

Now what is pos when this is entered? it's (1), so you're walking the list from (2) to size, shifting everything from 3..(size+1) to 2...(size). The item at "position" 1 (which again, is actually in slot 0 in the array, is never overwritten, thus it is always the reported returned item.

Not only is this incorrect, it is also UB (undefined behavior) when the array is fully populated you'll be access data one slot past the last viable location.

You want to throw out the item at pos, which is 1-based (your design; not mine). Its underlying element was at location a[pos-1] in the array. so try this:

for (int i = pos; i < size; ++i)
    a[i-1] = a[i];

This should be safe if you check to ensure pos is always 1 or greater (and it appears you do, in fact, do this). Personally I'd stick with a zero-based indexing system, but you have your design reasons, I'm sure.

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

2 Comments

Thanks @whoz. I completely missed this when I was debugging, The deign specification comes from a book I picked up to try to learn some c++. I know Java, and wanted to learn this. Agreed that the spec is quirky, but that's what made it tough.
@Adam_G programming for so long in C/C++, it's just odd seeing a 1-based anything.
1

In the remove method you are shifting down one index wrongly. It should be like this:

for (int i = pos + 1; i <= size; i++)
    a[i-1] = a[i]; // instead of a[i] = a[i+1];

The other way could be

for (int i = pos; i <= size; i++)
    a[i] = a[i+1];

Please check if it works.

1 Comment

The final iteration in both versions still accesses a[size] which is off the end. In the second version it also accesses a[size+1] which is even worse.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.