使用 nullptr 终止迭代器

Question

我正在尝试通过实现各种常见的数据结构来提高我对 C++ 的了解。我从一个链表开始。我希望能够使用基于范围的 for 循环。我读 this question and then based my implementation off of this sample code。

我的问题是我目前正在用 nullptr 终止我的链表；最后的 ListNode 将其数据成员 next_ 设置为 nullptr。因此，我在 LinkedList<T>::end() 函数中将 nullptr 作为迭代器构造函数的参数传入，我认为它应该正确地终止该函数。它按预期工作；当我重载 << 时，它会正确地将内容写入流。

不幸的是，它会出现一些内存错误（在使用 DrMemory 时看到）。这是因为有一行不正确地尝试从 nullptr 中提取数据成员（代码和解释如下）。但是，为 nullptr 添加比较以避免失败（见下文）。最后，因为重载 (in)equality 运算符需要它们获取引用，所以在列表的最后一个元素处传递了对 nullptr 的引用。根据 this answer 的说法，这是一个很大的诺诺。我怎样才能修复我当前的实现，或者修改我的实现以避免 nullptr?

我是用mingw32-g++编译器编译的，版本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）时，它将执行未初始化的读取。我心想 "oh, easy fix" 改成

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 class 的抽象基础 class，所有成员函数都是纯虚函数。为简洁起见排除在外。该文件还具有用于处理非常量迭代器的适当成员函数，但是这些函数或多或少是相同的，并且不是此处使用的函数，因此被排除在外。

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;

后缀增量也不正确：

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

至于你的问题：operator != 与它无关，因为你正在比较底层对象的指针（所以它们是否为 nullptr 并不重要）。

根据 DrMemory 的输出判断（我从未使用过它，但我假设 #5-#0 是调用堆栈）有 2 种可能性：

你的 << 运算符有问题
DrMemory 有问题（因为它抱怨 << 内的寄存器比较）。或者它可能是正确的，问题是增量不正确的副作用。

使用 nullptr 终止迭代器

Terminate an iterator with a nullptr

c++

iterator

reference

linked-list

c++11