c++ - 删除基于数组的列表中的项目

Question

在基于数组的列表的程序中，我有一个调用以下 3 次的函数:

list->remove(1)

我的问题是，当它打印出来时，它说它删除了原来的第一项 3 次，而不是转到下一个新的第一项。

具体来说，在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;
        }
}

它返回以下内容:

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

这是我创建的 ABList 类。我认为错误出在我的 remove 方法中，但我不知道在哪里:

#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

这是主程序。 (为了这个问题，我不得不假设它是不可变的):

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;
}

Answer 1

在移除过程中，您在获取位于 (1) 的项目(实际上是位于 a[0] 的项目)之后执行此操作:

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

现在输入这个时 pos 是什么？它是 (1)，因此您正在将列表从 (2) 移动到 size，将所有内容从 3..( size+1) 到 2...(size)。 “位置”1 处的项目(同样，实际上位于数组中的插槽 0 中)永远不会被覆盖，因此它始终是报告的返回项目。

这不仅是不正确的，而且当数组完全填充时，它也是 UB(未定义行为)，您将访问最后一个可行位置后一个插槽的数据。

您想在 pos 处扔掉元素，这是从 1 开始的(您的设计；不是我的)。它的底层元素位于数组中的 a[pos-1] 位置。所以试试这个:

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

如果您检查以确保 pos 始终为 1 或更大，这应该是安全的(看起来您确实如此，事实上，确实如此)这)。就我个人而言，我会坚持使用从零开始的索引系统，但我敢肯定，您有自己的设计原因。