C ++嵌套迭代器类（在链接列表类中）Insert_After函数

2024-05-19 • 问答

我在LinkedList类中嵌套了一个迭代器类。我的问题是如何使用迭代器制作insert_after函数。其余的代码仅供参考，但我试图使用的功能在最后。

Insert_After占据位置并在其后插入一个值。

template <typename T>
class LinkedList : public LinkedListInterface<T> {
private:
    struct Node {

    T data; // data can be any type
    Node* next; // points to the next Node in the list

    Node(const T& d,Node* n) : data(d),next(n) {}
};
Node* head; // Is a pointer

class Iterator
{
private:
    Node* iNode;
public:
    Iterator(Node* head) : iNode(head){ }
    ~Iterator() {}
    bool operator!=(const Iterator& rhs) const { return iNode != rhs.iNode; }
    Iterator& operator++() { iNode = iNode->next; return *this; }
    T& operator*() const { return iNode->data; }
};

/** Return iterator pointing to the first value in linked list */
Iterator begin(void) {
    return LinkedList<T>::Iterator(head); 
}

/** Return iterator pointing to something not in linked list */
Iterator end(void) {
    return LinkedList<T>::Iterator(NULL); 
}

/** Return iterator pointing found value in linked list */
Iterator find(Iterator first,Iterator last,const T& value) {
    Iterator current = first;
    bool found = false;
    while (current != last) {
        if (*current == value) {
            return current;
        }

        ++current;
    }

    return last;
}

Iterator insert_after(Iterator position,const T& value)
{
    // Need help here
}

到目前为止我尝试过的结果导致了一些错误。

Iterator insert_after(Iterator position,const T& value)
{
    // Need to insert after position
    Iterator previous = position;
    ++position;
    Node* newNode = new Node(value,position);
    previous->next = newNode;

}

我得到的错误是错误C2664'函数'：无法将行的参数n从'type1'转换为'type2'

Node* newNode = new Node(value,position);

编译器错误C2819类型'type'没有用于行的重载成员'operator->'

previous->next = newNode;

我了解这些错误，但不确定如何解决。

我认为对您的编译器错误的简短回答是，您很可能应该将Node或Node*作为第二个参数而不是迭代器。 previous也是一个迭代器，因此没有next调用。

以下关于一般修复相关功能的完整答案：
该函数中有很多[未]进行的事情，这也让我对链接列表类的其余部分感到疑惑。我只研究了此功能，因为它是您声称给您带来麻烦的功能。

主观思想我通常讨厌在类函数中使用迭代器。尽可能直接与节点打交道。无论容器的布局如何，都存在用于遍历容器的迭代器模式，而这种抽象使在类内部处理变得很痛苦。

Iterator insert_after(Iterator position,const T& value)
{
    // Need to insert after position
    Iterator previous = position;
    ++position;
    Node* newNode = new Node(value,position);
    previous->next = newNode;

}

按目前的状态，如果position除了最后一个元素之外的任何地方，您将中断列表并泄漏内存。这是因为您永远不会检查position之后的内容。第一个错误导致第二个错误。 newNode->next从未设置。也许默认将其构造为nullptr，就可以了。但是，如果要插入列表的中间，则需要将newNode连接到最初在position之后的所有内容。

您需要考虑的另一个问题是“如果在空列表上调用该怎么办？”您的begin()函数可以处理吗？应该扔吗？

Iterator insert_after(Iterator position,const T& value)
{
    Node* pos = position.iNode;

    if (!pos) {  // assumes an empty list if this is true
        // Correctly build first Node of your list and get everything assigned
        // that you can
        // return the new iterator;

        // or just throw
    }

    if (!pos->next) {  // position at end of list if true
        pos->next = new Node(value,position);  // Is that second argument
                                                // supposed to be an iterator?
        return Iterator(pos->next);
    } else {
        // Some of this is probably redundant depending on how you are actually
        // building Nodes,but the gist is it's important to ensure the list is
        // not broken; connecting tmp before changing existing nodes helps the
        // list stay intact for as long as possible
        Node* tmp = new Node(value,position);
        tmp->next = pos->next;
        pos->next = tmp;

        return Iterator(tmp);
    }

双向链接的列表乍一看似乎对学生没有吸引力，但是它使某些操作（例如从列表中间擦除）变得非常容易。是的，您还有一个额外的指针要处理，但是这也使得丢失节点也变得更加困难。以及双向迭代。

C ++嵌套迭代器类（在链接列表类中）Insert_After函数

sam_xiaosa 回答：C ++嵌套迭代器类（在链接列表类中）Insert_After函数

大家都在问