Реализуйте пользовательский Iterator и const_iterator для двусвязного списка в c ++ - PullRequest
Новая
       32

Реализуйте пользовательский Iterator и const_iterator для двусвязного списка в c ++

0 голосов
/ 14 декабря 2018

Вот моя реализация iterator и const_iterator для двусвязного списка.Программа имеет обязательные тесты.Когда я запускаю свою программу, я получаю сообщение об ошибке из тестов:

«Оператор уменьшения перемещает итератор назад, префикс», из-за фатальной ошибки: SIGSEGV - сигнал нарушения сегментации

Что я делаю не так?

test.cpp // вот мой тестовый файл, в котором я получаю сообщение об ошибке // 

TEST_CASE("Decrement operator moves the iterator backward", "[stage2]") {
    list l;
    append_to_list(l, { 5.55, 6.66, 7.77, 8.88 });

    auto it = l.end();
    SECTION("Prefix") {
        REQUIRE(*(--it) == 8.88);
        REQUIRE(*(--it) == 7.77);
        REQUIRE(*(--it) == 6.66);
        REQUIRE(*(--it) == 5.55);
        REQUIRE(it == l.begin());
    }

    SECTION("Postfix") {
        it--;
        REQUIRE(*(it--) == 8.88);
        REQUIRE(*(it--) == 7.77);
        REQUIRE(*(it--) == 6.66);
        REQUIRE(*it == 5.55);
        REQUIRE(it == l.begin());
    }
}

TEST_CASE("Decrement operator moves the (const) iterator backward", "[stage2]") {
    list l;
    append_to_list(l, { 5.55, 6.66, 7.77, 8.88 });

    auto it = l.cend();
    SECTION("Prefix") {
        REQUIRE(*(--it) == 8.88);
        REQUIRE(*(--it) == 7.77);
        REQUIRE(*(--it) == 6.66);
        REQUIRE(*(--it) == 5.55);
        REQUIRE(it == l.cbegin());
    }

    SECTION("Postfix") {
        it--;
        REQUIRE(*(it--) == 8.88);
        REQUIRE(*(it--) == 7.77);
        REQUIRE(*(it--) == 6.66);
        REQUIRE(*it == 5.55);
        REQUIRE(it == l.cbegin());
    }
}

list.hpp 

class list {
private:
    struct node {
        double val = 0;
        node* prev = nullptr;
        node* next = nullptr;
    };

    node* head = nullptr;
    node* tail = nullptr;
    size_t num_elements = 0;

public:

    class const_iterator {
        node* current_ptr = nullptr;
        const list* o_list = nullptr;
    public:
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = const double;
        using reference = const double&;
        using pointer = const double*;

        const_iterator() = default;
        const_iterator(node* ptr, const list* gen);

        const_iterator& operator++();
        const_iterator operator++(int);
        const_iterator& operator--();
        const_iterator operator--(int);

        reference operator*() const;
        pointer operator->() const;

        bool operator==(const const_iterator& rhs) const;
        bool operator!=(const const_iterator& rhs) const;

        friend class list;
    };

    class iterator {
        node* current_ptr = nullptr;
        const list* o_list = nullptr;
    public:
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = double;
        using reference = double&;
        using pointer = double*;

        iterator() = default;
        iterator(node* ptr, const list* gen);

        iterator& operator++();
        iterator operator++(int);
        iterator& operator--();
        iterator operator--(int);

        reference operator*() const;
        pointer operator->() const;

        operator const_iterator() const;

        bool operator==(const iterator& rhs) const;
        bool operator!=(const iterator& rhs) const;

        friend class list;
    };

list.cpp // моя реализация итератора и const_iterator // 

list::iterator list::begin() {
        return list::iterator(head, this);
    }

    list::iterator list::end() {
        return list::iterator(tail->next, this);
    }

    list::const_iterator list::begin() const {
        return list::const_iterator(head, this);
    }

    list::const_iterator list::end() const {
        return list::const_iterator(tail->next, this);
    }

    list::const_iterator list::cbegin() const {
        return list::const_iterator(head, this);
    }

    list::const_iterator list::cend() const {
        return list::const_iterator(tail->next, this);
    }

    list::iterator::iterator(node *ptr, const list *gen) {
        this->current_ptr = ptr;
        this->o_list = gen;
    }

    list::iterator& list::iterator::operator++() {
        current_ptr = this->current_ptr->next;
        return *this;
    }

    list::iterator& list::iterator::operator--() { //here triggers error!!!
        current_ptr = this->current_ptr->prev;
        return *this;
    }

    list::iterator list::iterator::operator++(int)
    {
        iterator old(*this);
        ++(*this);
        return old;
    }

    list::iterator list::iterator::operator--(int)
    {
        iterator left(*this);
        --(*this);
        return left;
    }
    list::const_iterator& list::const_iterator::operator++() {
        current_ptr = current_ptr->next;
        return *this;
    }

    list::const_iterator& list::const_iterator::operator--() { //here triggers error!!!
        current_ptr = current_ptr->prev;
        return *this;
    }

    list::const_iterator list::const_iterator::operator++(int) {
        const_iterator old = *this;
        ++(*this);
        return old;
    }

    list::const_iterator list::const_iterator::operator--(int) {
        const_iterator old = *(this);
        --(*this);
        return old;
    }

1 Ответ

0 голосов
/ 14 декабря 2018

Проблема в том, что вы используете нулевой node * в качестве конца (), который не работает с оператором--;нет способа уменьшить его, чтобы попасть в последний узел списка.

Вам нужно использовать что-то еще в качестве конечного стража, что позволяет вам вернуться к списку - либо поддельный «узел» насписок, который не является элементом реального списка, или добавьте указатель на исходный список к классам итераторов, поэтому при уменьшении итератора end () вы можете восстановить последний узел в списке.

Поскольку у вашего итератора уже есть указатель o_list, проще всего его использовать: 

list::iterator& list::iterator::operator--() {
    current_ptr = current_ptr ? current_ptr->prev : o_list->tail;
    return *this;
}
...