2

Пытаюсь первый раз реализовать итераторы для своего контейнера, вроде бы все работает хорошо, но вот 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); }

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

7
  • 2
    Приведите минимальный воспроизводимый пример, сейчас много не относящегося к проблеме кода
    – dIm0n
    9 сен 2020 в 11:33
  • 1
    чтобы создать reverse_iterator std::make_reverse_iterator должен получать итераторный тип, а именно Iterator<Type>, а не Node<Type>*. В вашем случаи нужно было просто определить: using iterator = Node<Type>*, или подойти к вопросу иначе. Смотрите другие примеры итераторов. 9 сен 2020 в 12:04
  • Попробуйте так: reverse_iterator rbegin() { return std::reverse_iterator(end()); } reverse_iterator rend() { return std::reverse_iterator(begin()); } 9 сен 2020 в 12:07
  • Уже пытался, увы все падает. Но если передавать именно tail и head то вывод получаю The deque reversed is: ( 12 111 321 777 1 77 123 ), когда begin и end отрабатывают нормально The deque is: ( 123 77 1 777 321 111 12 1000 ). 9 сен 2020 в 12:13
  • 2
    Код всё ещё можно значительно сократить. Создавая минимальный воспроизводимый пример, вы локализуете проблему. Часто на этом этапе можно понять, в чём дело, и задавать вопрос уже не надо
    – dIm0n
    9 сен 2020 в 12:19

1 ответ 1

6

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

  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-ов

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.