C ++ Вложенный класс итератора (в классе связанного списка) Функция Insert_After

Question

У меня есть класс итератора, вложенный в класс 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;

Я понимаю ошибки, но не уверен, какобойти их.

Answer 1

Я думаю, что краткий ответ на ваши ошибки компилятора состоит в том, что вы, скорее всего, должны передать Node или Node* в качестве второго аргумента, а не итератор. previous также является итератором, и поэтому не имеет вызова next.

Длинный ответ ниже об общем исправлении рассматриваемой функции:
Там много [не] происходит в этой функции, что заставляет меня задуматься об остальной части класса связанного списка. Я только посмотрел на эту функцию, так как вы утверждаете, что она доставляет вам неприятности.

СУБЪЕКТИВНАЯ МЫСЛЬ Я вообще ненавижу работать с итераторами в моих функциях класса. Работайте с Узлами напрямую, насколько это возможно. Шаблон итератора существует для универсального обхода контейнеров, независимо от того, как они расположены, и с этой абстракцией становится больно иметь дело внутри вашего класса. находится где угодно, но не последний элемент, вы сломаете свой список и потеряете память. Это потому, что вы никогда не проверяете, что после 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);
    }    

Двухсвязный список на первый взгляд никогда не кажется привлекательным для студента, но он делает некоторые операции, такие как удаление из середины списка, намного проще. Да, у вас есть один дополнительный указатель для работы, но это также затрудняет потерю узлов. Наряду с двунаправленной итерацией.