Реализовать итератор для связанного списка std :: uniqe_ptr - PullRequest
Новая
       81

Реализовать итератор для связанного списка std :: uniqe_ptr

0 голосов
/ 08 апреля 2020

Пока это мой код, он явно не работает. Я хочу, чтобы этот итератор работал как для диапазона, так и для приращения на основе циклов. Как я могу это сделать? 

template<typename T>
class MyList {
  public:
    class Node {
      public:
        Node(const T& data): data(data) {
            this->next = NULL;
        }
        std::unique_ptr<Node> next;
        T data;
    };
    MyList() {
        this->_size = 0;
    }
    int size() const;
    void push_front(const T& data);
    T pop_front();
    T front() const;
    void remove(T data);

    typedef T* iterator;
    typedef const Node* const_iterator;
    iterator begin() {
        return (&_head.get()->data);
    }
    iterator end() {
        return (NULL);
    }

  private:
    int _size;
    std::unique_ptr<MyList<T>::Node> _head;
};

1 Ответ

1 голос
/ 08 апреля 2020

T* не подходит в качестве итератора связанного списка, так как при увеличении он не может добраться до следующего узла в списке. Кроме того, &_head.get()->data недопустимо, когда список пуст.

И Node* также не будут работать ни для iterator, ни для const_iterator, поскольку у него не может быть действительного operator++ итерацию списка или operator* для доступа к data. См. Требования к ForwardIterator .

. Вам лучше определить отдельный тип, который будет действовать как (const_)iterator, и пусть он будет содержать Node* внутри для итераций и разыменования, например: 

template<typename T>
class MyList {
  public:
    class Node {
      public:
        Node(const T& data): data(data) {}
        std::unique_ptr<Node> next;
        T data;
    };

    template<typename D>
    class my_iterator
    {
      public:
        my_iterator(Node* node) : _current(node) {}
        bool operator==(const my_iterator &rhs) const { return _current == rhs._current; }
        D& operator*() { return _current->data; }
        D* operator->() { return &(_current->data); }
        my_iterator& operator++() { _current = _current->next.get(); return *this; }
        my_iterator operator++(int) { my_iterator tmp(_current); ++(*this); return tmp; }
      private:
        Node* _current;
    };

    using iterator = my_iterator<T>;
    using const_iterator = my_iterator<const T>;

    ...

    iterator begin() {
        return iterator(_head.get());
    }

    const_iterator cbegin() const {
        return const_iterator(_head.get());
    }

    iterator end() {
        return iterator(nullptr);
    }

    const_iterator cend() const {
        return const_iterator(nullptr);
    }

    ...
};
...