Не понимаю как реализовать iterator для списка

Question

Не понимаю как реализовать iterator для списка

Рейтинг: 0Ответов: 2Опубликовано: 25.02.2025

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

в общем список выглядит так:

template<typename T>
class Forward_list
{
  T data_;
  Forward_list<T>* next_;
};

итератор выглядит так:

class iterator
{
  Forward_list<T>* node_;
};

и проблема заключается в том что я не могу придумать как написать функцию end() которая будет указывать за последний элемент списка, чтобы удобно работать и <algorithm>.

сейчас код выглядит очень плохо, и много чего нехватает, понимаю, буду рад если его поругаете чтобы он стал лучше https://gist.github.com/shycoshy/b39ce63ea19984ee2a3073d0a1c1075e

если пользовться только push_back() в списке и попытаться вывести спомощью, то он "типа рабочий" и просто "съедает" последний элемент который нужно вывести по итератору end(). если указать за последний элемент, то собственно будет указатель на начало.

создать псевдоузел в начале или конце нельзя т.к. это другой вариант С:

c# итераторы

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Надо вводить "что-то" дополнительное, которое ограничивало бы повторы в переборе, при достижении последнего элемента. Вариант с "флагом для первого элемента" - хорошее решение от HolyBlackCat. У меня получилось с хранением указателя на последний элемент. Вот сильно урезанная реализация, только ради демо:

#include <iostream>
#include <algorithm>

template<typename T>
class Forward_list {
    struct Node {
      T data_;
      Node* next_;
      Node(const T& data) : data_(data), next_(nullptr) {}
    };
  public:
    class const_iterator;

    Forward_list() : head_(nullptr), last_(nullptr) {}

    ~Forward_list() {
      clear();
    }

    void push_back(const T& value) {
      Node* new_node = new Node(value);
      if (!head_) {
        head_ = new_node;
        last_ = new_node;
        new_node->next_ = head_; // Указываем на себя
      } else {
        last_->next_ = new_node;
        new_node->next_ = head_;
        last_ = new_node;
      }
    }

    void clear() {
      if (!head_)
        return;
      Node* current = head_;
      Node* next_node;
      do {
        next_node = current->next_;
        delete current;
        current = next_node;
      } while (current != head_);
      head_ = nullptr;
      last_ = nullptr;
    }

    const_iterator begin() const {
      return const_iterator(head_, last_);
    }

    const_iterator end() const {
      return const_iterator(nullptr, last_); // Указываем на nullptr для конца
    }

    class const_iterator {
      public:
        const_iterator(Node* node, Node* last) : current_(node), last_(last) {}

        const T& operator*() const {
          return current_->data_;
        }

        const_iterator& operator++() {
          if (current_ && current_ != last_) {
            current_ = current_->next_;
          } else {
            current_ = nullptr;
          }
          return *this;
        }

        bool operator!=(const const_iterator& other) const {
          return current_ != other.current_;
        }

        bool operator==(const const_iterator& other) const {
          return current_ == other.current_;
        }

      private:
        Node* current_;
        Node* last_; // Храним указатель на последний элемент
    };

  private:

    Node* head_;
    Node* last_;
};

int main() {
  Forward_list<int> list;
  list.push_back(1);
  list.push_back(2);
  list.push_back(3);
  // Используем стандартный алгоритм
  std::for_each(list.begin(), list.end(), [](int value) {
    std::cout << value << " ";
  });
  std::cout << std::endl;
  return 0;
}

Напечатает: 1 2 3

Онлайн тут.

Answer 2

▲ 0

Добавить в итератор флаг, равный true для первого элемента, и сбрасывать его в false на любой инкремент. В == сравнивать этот флаг тоже.

Не понимаю как реализовать iterator для списка

Ответы