Завершить итератор с помощью nullptr

Question

Я пытаюсь улучшить свои знания о C++, внедряя различные общие структуры данных. Я начал со связанного списка. Я бы хотел использовать диапазон, основанный на цикле. Я прочитал this question, а затем основал свою реализацию с this sample code.

Моя проблема в том, что я в настоящее время завершаю свой связанный список с помощью nullptr; в окончательном ListNode указан его член данных next_, установленный на nullptr. Таким образом, я передал в nullptr аргумент в конструкторе итератора в функции LinkedList<T>::end(), который, как я полагаю, должен правильно прекратить функцию. И он работает так, как ожидалось; когда я перегружаю <<, он правильно записывает содержимое в поток.

К сожалению, это происходит с некоторыми ошибками памяти (при использовании DrMemory). Это связано с тем, что существует строка, которая неправильно пытается извлечь элемент данных из nullptr (код и пояснения ниже). Однако, добавив сравнение для nullptr, чтобы избежать этого (см. Ниже). Наконец, поскольку перегрузка операторов равенства (in) требует, чтобы они взяли ссылку, в конечном элементе списка передается ссылка на nullptr. Согласно this answer, это большой нон. Как я мог либо исправить мою текущую реализацию, либо переработать мою реализацию, чтобы избежать nullptr?

Я компиляции с использованием mingw32-г ++ компилятор, версия 4.8.1, следующим

$ mingw32-g++ -g -Wall -Werror -Wextra -pedantic -std=gnu++11 -c <cpp file> 
$ mingw32-g++ -o main <object files> 

А потом запустить его в DrMemory с помощью

$ drmemory -- main 

Запуск его в DrMemory получает меня выход

UNINITIALIZED READ: reading register edx 
# 0 ConstListIterator<>::operator!=    [structures/listiterator.hpp:167] 
# 1 _fu0___ZSt4cout       [C:\Users\dannn_000\documents\github\datastructures/main.cpp:10] 
# 2 __mingw_CRTStartup 
# 3 mainCRTStartup 
# 4 ntdll.dll!RtlInitializeExceptionChain +0x8e  (0x77e6b5af <ntdll.dll+0x5b5af>) 
# 5 ntdll.dll!RtlInitializeExceptionChain +0x59  (0x77e6b57a <ntdll.dll+0x5b57a>) 
Note: @0:00:00.738 in thread 9500 
Note: instruction: cmp %edx %eax 

Основываясь на выходе DrMemory, проблема заключается в перегруженном операторе != реализация в ConstListIterator, и, глядя на что мы можем ясно видеть проблему линии:

return current_ != rhs.current_; 

, который будет выполнять неинициализированное чтение, когда последний узел (nullptr) достигается. Я подумал про себя: «О, легко исправить» и изменил его

if (rhs == nullptr) 
    return current_ != nullptr; 
return current_ != rhs.current_; 

, который при компиляции выдает ошибку

mingw32-make : In file included from structures/list.hpp:16:0, 
At line:1 char:1 
+ mingw32-make main 2> t.txt 
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~ 
    + CategoryInfo   : NotSpecified: (In file include.../list.hpp:16:0,:String) [], RemoteException 
    + FullyQualifiedErrorId : NativeCommandError 

       from structures/linkedlist.hpp:16, 
       from main.cpp:1: 
structures/listiterator.hpp: In instantiation of 'bool ConstListIterator<T>::operator!=(const ConstListIterator<T>&) [with T = 
int]': 
main.cpp:10:16: required from here 
structures/listiterator.hpp:167:10: error: no match for 'operator==' (operand types are 'const ConstListIterator<int>' and 
'std::nullptr_t') 
    if (rhs == nullptr) 
     ^

structures/listiterator.hpp:167:10: note: candidate is: 

structures/listiterator.hpp:153:6: note: bool ConstListIterator<T>::operator==(const ConstListIterator<T>&) [with T = int] <near 
match> 
bool ConstListIterator<T>::operator==(const ConstListIterator<T>& rhs) 
    ^

structures/listiterator.hpp:153:6: note: no known conversion for implicit 'this' parameter from 'const 
ConstListIterator<int>*' to 'ConstListIterator<int>*' 

structures/listiterator.hpp:168:19: error: no match for 'operator!=' (operand types are 'ListNode<int>*' and 'const 
ConstListIterator<int>') 
    return current_ != rhs; 
       ^

mingw32-make: *** [main.o] Error 1 

Итак я иду вперед и добавить функцию-член, которая будет сравнивать ConstListIterator с std::nullptr_t, но как только что был добавлен я получил новую ошибку

mingw32-make : In file included from structures/list.hpp:16:0, 
At line:1 char:1 
+ mingw32-make main 2> t.txt 
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~ 
    + CategoryInfo   : NotSpecified: (In file include.../list.hpp:16:0,:String) [], RemoteException 
    + FullyQualifiedErrorId : NativeCommandError 

       from structures/linkedlist.hpp:16, 
       from main.cpp:1: 
structures/listiterator.hpp: In instantiation of 'bool ConstListIterator<T>::operator!=(const ConstListIterator<T>&) [with T = 
int]': 
main.cpp:10:16: required from here 
structures/listiterator.hpp:182:10: error: no match for 'operator==' (operand types are 'const ConstListIterator<int>' and 
'std::nullptr_t') 
    if (rhs == nullptr) 
     ^

structures/listiterator.hpp:182:10: note: candidates are: 

structures/listiterator.hpp:156:6: note: bool ConstListIterator<T>::operator==(const ConstListIterator<T>&) [with T = int] <near 
match> 
bool ConstListIterator<T>::operator==(const ConstListIterator<T>& rhs) 
    ^

structures/listiterator.hpp:156:6: note: no known conversion for implicit 'this' parameter from 'const 
ConstListIterator<int>*' to 'ConstListIterator<int>*' 

structures/listiterator.hpp:162:6: note: bool ConstListIterator<T>::operator==(std::nullptr_t&) [with T = int; 
std::nullptr_t = std::nullptr_t] 
bool ConstListIterator<T>::operator==(std::nullptr_t& rhs) 
    ^

structures/listiterator.hpp:162:6: note: no known conversion for argument 1 from 'std::nullptr_t' to 
'std::nullptr_t&' 

structures/listiterator.hpp:183:19: error: no match for 'operator!=' (operand types are 'ListNode<int>*' and 'const 
ConstListIterator<int>') 
    return current_ != rhs; 
       ^

mingw32-make: *** [main.o] Error 1 

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

listnode.hpp

#ifndef LISTNODE_HPP 
#define LISTNODE_HPP 1 

template <typename T> 
struct ListNode { 
public: 

    ListNode() = delete; 
    ListNode(T value); 
    ListNode<T>* getNext(); 
    void setNext(ListNode<T>* node); 
    T& getValue(); 
    const T& getCValue() const; 
    void setValue(T value); 

private: 
    T value_; 
    ListNode<T>* next_; 
}; 

// Standard implementations of all member functions. 

#endif 

У меня есть еще один файл, «list.hpp», который содержит абстрактный базовый класс для моего LinkedList класса, все функции-члены являются чисто виртуальные функции. Исключено для краткости.Этот файл также имеет соответствующие функции-члены для работы с неконстантным итератором, однако они более или менее одинаковы, а не те, которые используются здесь, и исключаются по этой причине.

linkedlist.hpp

#ifndef LINKEDLIST_HPP 
#define LINKEDLIST_HPP 1 

#include <cstddef> 

#include "listnode.hpp" 
#include "list.hpp" 
#include "listiterator.hpp" 
#include "../exceptions.hpp" 

template <typename T> 
class LinkedList : public List<T> 
{ 
public: 

    LinkedList(); 
    LinkedList(T* arr, std::size_t length); 
    ~LinkedList(); 
    ConstListIterator<T> begin() const; 
    ConstListIterator<T> end() const; 

private: 
    std::size_t numElements_; 
    ListNode<T>* head_; 
    ListNode<T>* tail_; 
}; 


template <typename T> inline LinkedList<T>::LinkedList() : 
    numElements_(0), head_(nullptr), tail_(nullptr) { 
} 

template <typename T> inline LinkedList<T>::LinkedList(
    T* arr, std::size_t length) : 
     numElements_(length), head_(nullptr), tail_(nullptr) { 
    head_ = new ListNode<T>(arr[0]); 
    ListNode<T>* current = nullptr; 
    ListNode<T>* next = nullptr; 
    current = head_; 

    for (std::size_t i = 1; i < length; ++i) { 
     next = new ListNode<T>(arr[i]); 
     current->setNext(next); 
     current = next; 
    } 
    tail_ = current; 
} 

template <typename T> inline LinkedList<T>::~LinkedList() 
{ 
    ListNode<T>* current = head_; 
    ListNode<T>* next = nullptr; 

    for (std::size_t i = 0; i < numElements_; ++i) { 
     next = current->getNext(); 
     delete current; 
     current = next; 
    } 
} 

template <typename T> inline 
ConstListIterator<T> LinkedList<T>::begin() const 
{ 
    return ConstListIterator<T>(head_); 
} 

template <typename T> inline 
ConstListIterator<T> LinkedList<T>::end() const 
{ 
    return ConstListIterator<T>(nullptr); 
} 
#endif 

Наконец, реализация моего итератора. Опять же, я исключил неконстантную версию этих (по той же причине, что и выше).

listiterator.hpp

#ifndef LISTITERATOR_HPP 
#define LISTITERATOR_HPP 1 

#include <iterator> 

#include "listnode.hpp" 

template <typename T> 
class ConstListIterator 
{ 
public: 
    typedef std::forward_iterator_tag iterator_category; 
    ConstListIterator() = delete; 
    ConstListIterator(ListNode<T>* node); 
    ConstListIterator operator++(); 
    ConstListIterator operator++(int); 
    const ListNode<T>& operator*(); 
    const ListNode<T>* operator->(); 
    bool operator==(const ConstListIterator<T>& rhs); 
    bool operator==(std::nullptr_t& rhs); 
    bool operator!=(const ConstListIterator<T>& rhs); 

private: 
    ListNode<T>* current_; 
}; 

template <typename T> inline 
ConstListIterator<T>::ConstListIterator(ListNode<T>* node) : 
    current_(node) { 
} 

template <typename T> inline 
ConstListIterator<T> ConstListIterator<T>::operator++() 
{ 
    current_ = current_->getNext(); 
    return *this; 
} 

template <typename T> inline 
ConstListIterator<T> ConstListIterator<T>::operator++(int) 
{ 
    current_ = current_->getNext(); 
    return *this; 
} 

template <typename T> inline 
const ListNode<T>& ConstListIterator<T>::operator*() 
{ 
    return *current_; 
} 

template <typename T> inline 
const ListNode<T>* ConstListIterator<T>::operator->() 
{ 
    return current_; 
} 

template <typename T> inline 
bool ConstListIterator<T>::operator==(const ConstListIterator<T>& rhs) 
{ 
    return current_ == rhs.current_; 
} 

template <typename T> inline 
bool ConstListIterator<T>::operator!=(const ConstListIterator<T>& rhs) 
{ 
    return current_ != rhs.current_; 
} 

#endif 

И файл я использую для запуска этого все

main.cpp

#include "structures/linkedlist.hpp" 
#include <iostream> 

int main() 
{ 
    LinkedList<int> list; 
    list.append(1); 

    for (auto i : list) 
     std::cout << i << std::endl; 

    return 0; 
} 

Answer 1

Прежде всего, так как вы намереваетесь использовать алгоритмы STL Это было бы хорошей идеей вывести из std :: iterator.

Некоторые заявления итераторов ошибаетесь, вот фикс:

ConstListIterator() : current_(nullptr) {} // basically end() iterator 
ConstListIterator(ListNode<T>* node); 
ConstListIterator& operator++(); 
ConstListIterator operator++(int); 
const ListNode<T>& operator*() const; 
const ListNode<T>* operator->() const; 
bool operator==(const ConstListIterator<T>& rhs) const; 
bool operator!=(const ConstListIterator<T>& rhs) const; 

приращение Postfix также неправильно:

template <typename T> inline 
ConstListIterator<T> ConstListIterator<T>::operator++(int) 
{ 
    auto old = current_; 
    current = current_->getNext() 
    return ConstListIterator<T>(old); 
} 

Что касается вашей проблемы: оператор = не имеет ничего общего с ним, так как вы сравниваете указатели на базовые объекты (поэтому не имеет значения, являются ли они nullptr).

Судя по выходе DrMemory в (я никогда не работал с ним, но я предполагаю, что # 5 # 0 CallStack) есть 2 возможности:

1. есть что-то не так с вашим < < оператор
2. что-то не так с DrMemory (поскольку он жалуется на сравнение регистров внутри < <). Или это может быть правильно, и проблема является побочным эффектом неправильных приращений.