CODEWITHSUNDEEP
c++c++11linked-listunique-ptr
Hubert
Hubert

Reputation: 152

Implement iterator for std::uniqe_ptr Linked list

This is my code so far, it obviously does not work. I want this iterator to work on both range and increment based for loops. How can I do it?

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

Upvotes: 0

Views: 53

Answers (1)

Remy Lebeau
Remy Lebeau

Reputation: 595971

T* is not suitable as a linked-list iterator, as it has no way to get to the next node in the list when incremented. Also because &_head.get()->data is not valid when the list is empty.

And Node* will not work for either iterator or const_iterator, either, since it can't have a valid operator++ to iterator the list, or anoperator* to access the data. See the requirements for a ForwardIterator.

You are better off defining a separate type to act as a (const_)iterator and let it hold a Node* internally for iterating and dereferencing, eg:

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

    ...
};

Upvotes: 1

Related Questions