БЛОГ НА HUSL


Реализация итераторов для собственного контейнера

Автор вопроса: Sunny Stealth

Пытаюсь первый раз реализовать итераторы для своего контейнера, вроде бы все работает хорошо, но вот std::rbegin(test), std::rend(test) не выводят первый элемент (последний с конца). Не могу понять в чем у меня заключается проблема, если не сложно подскажите как решить данную проблему.

main.cpp для тестов

#include <iostream>
#include <algorithm>
#include <vector>
#include "deque.h"

int main()
{
    Deque<int> test;
    test.push_back(123);
    test.push_back(77);
    test.push_back(1);
    test.push_back(777);
    test.push_back(321);
    test.push_back(111);
    test.push_back(12);
    test.push_back(1000);

    auto [min_it2, max_it2] = std::minmax_element(std::rbegin(test),
    std::rend(test));
    std::cout << *min_it2 << " - " << *max_it2 << '\n';

    Deque<int>::reverse_iterator rvIter;
    std::cout << "The deque reversed is: ( ";
    for ( rvIter = test.rbegin() ; rvIter != test.rend(); ++rvIter)
    {
        std::cout << *rvIter << " ";
    }
    std::cout << ")." << std::endl;

    return 0;
}

Deque.h (Реализация)

#ifndef _DEQUE_H_
#define _DEQUE_H_

#include <cstddef>
#include <utility>
#include <stdexcept>
#include <iterator>

//-------------------------------------------------------------------------------------------------
template <typename Type>
class Node
{
public:
    Type element;
    Node<Type>* prev;
    Node<Type>* next;
public:
    Node() : element{}, prev(nullptr), next(nullptr) {};
    Node(const Node & node) : Node(node.element, node.prev, node.next) {};
};
//-------------------------------------------------------------------------------------------------
template <typename Type>
class Iterator
{
public:
    using difference_type = std::ptrdiff_t;
    using value_type = std::remove_cv_t<Type>;
    using pointer = Type*;
    using reference = Type&;
    using iterator_category = std::random_access_iterator_tag;
    using iterator_concept = std::contiguous_iterator_tag;
public:
    explicit Iterator(Node<Type>* ptr = nullptr);
    Iterator(const Iterator& iterator);

    ~Iterator() = default;

    bool operator==(const Iterator& lhs) const;
    bool operator!=(const Iterator& lhs) const;

    Iterator operator++();
//    Iterator operator++(int post);
    Iterator operator--();
//    Iterator operator--(int post);

    Type& operator*();
protected:
    Node<Type>* date;
};
//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type>::Iterator(Node<Type>* ptr) : date(ptr)
{

}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type>::Iterator(const Iterator& iter) : Iterator(iter.date)
{

}
//-------------------------------------------------------------------------------------------------
template <typename Type>
bool Iterator<Type>::operator==(const Iterator& lhs) const
{
    return (date == lhs.date);
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
bool Iterator<Type>::operator!=(const Iterator& lhs) const
{
    return (date != lhs.date);
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type> Iterator<Type>::operator++()
{
    date = date->next;
    return *this;
}
//-------------------------------------------------------------------------------------------------
//template <typename Type>
//Iterator<Type> Iterator<Type>::operator++(int post)
//{
//    Iterator<Type> temp(date);
//    date = date->next;
//    return temp;
//}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type> Iterator<Type>::operator--()
{
    date = date->prev;
    return *this;
}
//-------------------------------------------------------------------------------------------------
//template <typename Type>
//Iterator<Type> Iterator<Type>::operator--(int post)
//{
//    Iterator<Type> temp(date);
//    date = date->prev;
//    return temp;
//}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Type& Iterator<Type>::operator*()
{
    return date->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
class Deque
{
public:
    //Using
    using iterator = Iterator<Type>;
    using const_iterator = Iterator<const Type>;
    using reverse_iterator = std::reverse_iterator<Iterator<Type>>;
    using const_reverse_iterator = std::reverse_iterator<Iterator<const Type>>;
private:
    //Member
    size_t count {};
    Node<Type>* head;
    Node<Type>* tail;
public:
    //Member functions
    Deque();
    Deque(const Deque & deq);
    Deque(Deque && deq) noexcept;
    Deque & operator = (const Deque & deq);
    Deque & operator = (Deque && deq);
    ~Deque();

    //Element access
    //const Type & at(Deque pos) const; Not implemented
    //template <typename Type>
    //const Type & operator[](size_type pos) const; Not implemented
    const Type & front() const;
    const Type & back() const;

    //Iterators
    iterator begin() { return iterator(head); }
    iterator end() { return iterator(tail->next); }

    iterator begin() const { return iterator(head); }
    iterator end() const { return iterator(tail->next); }

    const_iterator cbegin() const { return head; }
    const_iterator cend() const { return tail->next; }

    reverse_iterator rbegin() { return std::make_reverse_iterator(tail); }
    reverse_iterator rend() { return std::make_reverse_iterator(head); }
//
//    reverse_iterator rbegin() const { return std::make_reverse_iterator(rbegin()); }
//    reverse_iterator rend() const  { return std::make_reverse_iterator(rend()); }
//
//    const_reverse_iterator crbegin() const { return rend(); }
//    const_reverse_iterator crend() const { return rbegin(); }

    //Capacity
    bool empty() const;
    size_t size() const;
    //size_t max_size() const noexcept; Not implemented

    //Modifiers
    void push_front(const Type & tp);
    void push_back(const Type & tp);

    //void emplace_front(); Not implemented
    //void emplace_back(); Not implemented

    void pop_front();
    void pop_back();

    void clear() noexcept;
    void swap(Deque & deq) noexcept;
};
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque() : count(0), head(nullptr), tail(nullptr)
{
    //Body of the constructor class
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(const Deque & deq) : count(deq.count), head(nullptr), tail(nullptr)
{
    for (const Node<Type>* n_ptr = deq.head; n_ptr != nullptr; n_ptr = n_ptr->next)
    {
        auto* n_ptr_new = new Node<Type>;
        n_ptr_new->element = n_ptr->element;
        if (head == nullptr && tail == nullptr)
        {
            head = n_ptr_new;
            tail = head;
        }
        else
        {
            tail->next = n_ptr_new;
            n_ptr_new->prev = tail;
            n_ptr_new->next = nullptr;
            tail = n_ptr_new;
        }
    }
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(Deque && deq) noexcept : count(deq.count), head(deq.head), tail(deq.tail)
{
    deq.count = 0;
    deq.head = nullptr;
    deq.tail = nullptr;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (const Deque & deq)
{
    if (this == &deq)
    {
        return *this;
    }
    Deque tmp(deq);
    std::swap(count, tmp.count);
    std::swap(head, tmp.head);
    std::swap(tail, tmp.tail);
    return *this;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (Deque && deq)
{
    if (this == &deq)
    {
        return *this;
    }
    std::swap(count, deq.count);
    std::swap(head, deq.head);
    std::swap(tail, deq.tail);
    return *this;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Deque<Type>::~Deque()
{
    while (head)
    {
        Node<Type>* n_ptr_del = head;
        head = head->next;
        delete n_ptr_del;
    }
    count = 0;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_front(const Type & tp)
{
    auto* n_ptr_new = new Node<Type>;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        n_ptr_new->next = head;
        n_ptr_new->prev = nullptr;
        head->prev = n_ptr_new;
        head = n_ptr_new;
    }
    ++count;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_back(const Type & tp)
{
    auto* n_ptr_new = new Node<Type>;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        tail->next = n_ptr_new;
        n_ptr_new->prev = tail;
        n_ptr_new->next = nullptr;
        tail = n_ptr_new;
    }
    ++count;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_front()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node<Type>* n_ptr_del = head;
    head = head->next;
    head->prev = nullptr;
    --count;
    delete n_ptr_del;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_back()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node<Type>* n_ptr_del = tail;
    tail = tail->prev;
    tail->next = nullptr;
    --count;
    delete n_ptr_del;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
bool Deque<Type>::empty() const
{
    return head == nullptr;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::front() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return head->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::back() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return tail->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
size_t Deque<Type>::size() const
{
    return count;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::clear() noexcept
{
    while (count)
    {
        pop_back();
    }
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::swap(Deque & deq) noexcept
{
    Deque temp(deq);
    deq = std::move(*this);
    *this = std::move(temp);
}
//-------------------------------------------------------------------------------------------------
#endif // _DEQUE_H_

Если оставить как сейчас

    reverse_iterator rbegin() { return std::make_reverse_iterator(tail); }
    reverse_iterator rend() { return std::make_reverse_iterator(head); }

То в выводе я получаю The deque reversed is: ( 12 111 321 777 1 77 123 ). А если я делаю

    reverse_iterator rend() { return std::make_reverse_iterator(head->prev); }

То все падает.


Источник

Ответы (1 шт):

Автор решения: Andrej Levkovitch

Вроде простенький, но, однако, интересный случай! Итак, начнем с того, что я вас поругаю:

  1. ваш код не соответствует критериям минимальности! У вас куча методов, который не используются в примере и без них легче понять в чем проблема
  2. вместо того, чтобы фиксить проблемы, на которые вам указывают опытные участники (@ARHovsepyan) вы пытаетесь сделать что-то невразумительное! Ваш пример выдает что-то похожее на результат только благодаря своей простоте! Ноды ложаться в куче по-порядку - вот он и работает, но стоит что-либо удалить, добавить переменную в куче в другом месте или т.п., как вы обратитесь нетуда

Итак, как я уже говорил, основная проблема в том, что вы неверно берете реверс итератор (на что вам уже указали в комментах). Таким образом верный код функций будет выглядеть так:

  reverse_iterator rbegin() { return std::make_reverse_iterator(this->end()); }
  reverse_iterator rend() { return std::make_reverse_iterator(this->begin()); }

Но, как вы заметили, пример крашится. А теперь, вместо того, чтобы делать непонятно что, разберемся - почему? Так как для меня проблема очевидна, сделаем такую проверку:

  Deque<int> test;
  test.push_back(123);

  auto iter = test.end();
  --iter;

И мы увидем краш. Все дело в том, как вы создаете итератор на конец:

    iterator end() { return iterator(tail->next); }

Это равносильно:

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

Как из nullptr получить предыдущий элемент? Никак! Что делать? Ответ и очевиден и не очевиден. Вам нужно добавить end-элемент, который не будет в контейнере, но из него можно будет получить последний элемент. Как это сделать? Есть разные способы как это сделать, например так, как это сделал я:

#ifndef _DEQUE_H_
#define _DEQUE_H_

#include <cstddef>
#include <iterator>
#include <stdexcept>
#include <utility>

//-------------------------------------------------------------------------------------------------
template <typename Type> class Node {
public:
  Type element;
  Node<Type> *prev;
  Node<Type> *next;

public:
  Node() : element{}, prev(nullptr), next(nullptr){};
  Node(const Node &node) : Node(node.element, node.prev, node.next){};
};
//-------------------------------------------------------------------------------------------------
template <typename Type> class Iterator {
public:
  using difference_type = std::ptrdiff_t;
  using value_type = std::remove_cv_t<Type>;
  using pointer = Type *;
  using reference = Type &;
  using iterator_category = std::random_access_iterator_tag;

public:
  explicit Iterator(Node<Type> *ptr = nullptr);
  Iterator(const Iterator &iterator);

  ~Iterator() = default;

  bool operator==(const Iterator &lhs) const;
  bool operator!=(const Iterator &lhs) const;

  Iterator operator++();
  //    Iterator operator++(int post);
  Iterator operator--();
  //    Iterator operator--(int post);

  Type &operator*();

protected:
  Node<Type> *date;
};

namespace std {
template <typename Type> struct iterator_traits<Iterator<Type>> {
  using difference_type = std::ptrdiff_t;
  using value_type = std::remove_cv_t<Type>;
  using pointer = Type *;
  using reference = Type &;
  using iterator_category = std::random_access_iterator_tag;
};
} // namespace std

//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type>::Iterator(Node<Type> *ptr) : date(ptr) {}
//-------------------------------------------------------------------------------------------------
template <typename Type>
Iterator<Type>::Iterator(const Iterator &iter) : Iterator(iter.date) {}
//-------------------------------------------------------------------------------------------------
template <typename Type>
bool Iterator<Type>::operator==(const Iterator &lhs) const {
  return (date == lhs.date);
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
bool Iterator<Type>::operator!=(const Iterator &lhs) const {
  return (date != lhs.date);
}
//-------------------------------------------------------------------------------------------------
template <typename Type> Iterator<Type> Iterator<Type>::operator++() {
  date = date->next;
  return *this;
}
//-------------------------------------------------------------------------------------------------
// template <typename Type>
// Iterator<Type> Iterator<Type>::operator++(int post)
//{
//    Iterator<Type> temp(date);
//    date = date->next;
//    return temp;
//}
//-------------------------------------------------------------------------------------------------
template <typename Type> Iterator<Type> Iterator<Type>::operator--() {
  date = date->prev;
  return *this;
}
//-------------------------------------------------------------------------------------------------
// template <typename Type>
// Iterator<Type> Iterator<Type>::operator--(int post)
//{
//    Iterator<Type> temp(date);
//    date = date->prev;
//    return temp;
//}
//-------------------------------------------------------------------------------------------------
template <typename Type> Type &Iterator<Type>::operator*() {
  return date->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type> class Deque {
public:
  // Using
  using iterator = Iterator<Type>;
  using const_iterator = Iterator<const Type>;
  using reverse_iterator = std::reverse_iterator<Iterator<Type>>;
  using const_reverse_iterator = std::reverse_iterator<Iterator<const Type>>;

private:
  // Member
  size_t count{};
  Node<Type> *root;

public:
  // Member functions
  Deque();
  ~Deque();

  // Iterators
  iterator begin() { return iterator(root->next); }
  iterator end() { return iterator(root); }

  reverse_iterator rbegin() { return std::make_reverse_iterator(this->end()); }
  reverse_iterator rend() { return std::make_reverse_iterator(this->begin()); }

  void push_back(const Type &tp);
};

template <typename Type> Deque<Type>::Deque() : count(0) {
  root = new Node<Type>;
  root->prev = root;
}

template <typename Type> Deque<Type>::~Deque() {
  Node<Type> *ptr = root->next;

  while (ptr && ptr != root) {
    Node<Type> *next = ptr->next;
    delete ptr;
    ptr = next;
  }

  delete root;
  count = 0;
}

template <typename Type> void Deque<Type>::push_back(const Type &tp) {
  auto *n_ptr_new = new Node<Type>;
  n_ptr_new->element = tp;

  n_ptr_new->next = root;
  n_ptr_new->prev = root->prev;

  root->prev->next = n_ptr_new;

  root->prev = n_ptr_new;

  ++count;
}

#endif // _DEQUE_H_

Если коротко: в контейнере я оставил только одну ноду - root, next - это первый элемент, prev - это последний элемент. Сам же root можно использовать как end. Это, конечно, не верх мысли - сдесь есть проблемы, вроде: нельзя создать контейнер для класса без дефолтного конструктора; по итогу получился закольцованный список, что тоже не очень. Решение они имеют, но это займет дополнительное время.

PS также прошу заметить насколько упроситилась логика добавления элемента - никаких if-ов

→ Ссылка

licensed under cc by-sa 3.0 with attribution.