vendredi 27 février 2015

Terminate an iterator with a nullptr

I'm trying to improve my knowledge of C++ by implementing various common data structures. I've started with a linkedlist. I'd like to be able to use a range based for loop with it. I read this question and then based my implementation off of this sample code.


My problem is that I'm currently terminating my linkedlist with a nullptr; the final ListNode has its data member next_ set to nullptr. Thus, I passed in nullptr as the argument in the iterator's constructor within the LinkedList<T>::end() function, which I believe should correctly terminate the function. And it works as expected; when I overload << it correctly writes the contents to stream.


Unfortunately it does so with some memory errors (seen while using DrMemory). This is because there is a line that improperly tries to extract a data member from a nullptr (code and explanation is below). However, adding a comparison for nullptr to avoid that fails (see below). Lastly, because overloading the (in)equality operators requires that they take a reference, at the final element of the list a reference to a nullptr is passed. According to this answer that is a big nono. How could I either fix my current implementation, or rework my implementation to avoid the nullptr?


I'm compiling using the mingw32-g++ compiler, version 4.8.1, as follows



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


And then I run it in DrMemory using



$ drmemory -- main


Running it in DrMemory gets me the output



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


Based on the output from DrMemory the problem is in the overloaded operator != implementation in ConstListIterator, and looking at that we can clearly see the problem line:



return current_ != rhs.current_;


which will perform an uninitialized read when the last node (the nullptr) is reached. I thought to myself "oh, easy fix" and changed it to



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


which when compiled gives the error



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


So then I go ahead and add a member function that would compare a ConstListIterator to a std::nullptr_t, but once that was added I got a new error



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


Here is a (simplified) version of my code. I've removed a number of member functions I don't believe are relevant to this code, and I've done my best to remove their usage within the code itself.


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


I have another file, "list.hpp", that contains an abstract base class for my LinkedList class, all member functions are pure virtual functions. Excluded for brevity. This file also has the appropriate member functions for dealing with a non-const iterator, however those are more or less the same and aren't the ones being used here and are being excluded for that reason.


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


Lastly, the implementation of my iterator. Again, I've excluded the non-const version of these (for the same reason as above).


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


And the file I'm using to run this all


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;
}

Aucun commentaire:

Enregistrer un commentaire