linked list with unique pointers being used as type

349 views Asked by At

I'm having a problem getting my linked list (it's actually a square list) passing tests that have been given by my professor, and I'm not sure what I'm supposed to do.

Here's my code:

/** LinkedList class declaration. */
template <typename T>
class LinkedList;

template <class TNode>
class Iterator
{
    /* Helper class to provide pointer like facilities around a node */
    friend class LinkedList<typename TNode::value_type>;
    TNode* pNode; //The node oriented with this instance of iterator.

    //Iterator(TNode* _pNode) : pNode(_pNode) {}
public:
    Iterator(TNode* _pNode) : pNode(_pNode) {}
    using value_type = typename TNode::value_type;
    //using size_type = std::size_type;
    using pointer = TNode*;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using iterator = Iterator<TNode>;
    using iterator_category = std::bidirectional_iterator_tag;

    .............removed unneeded code...............       

    value_type get() {
        return pNode->_data;
    }

    typename TNode::value_type &operator*(){ return pNode->_data; }
};

template <typename T>
class Node
{
    friend class LinkedList<T>;
    friend class Iterator<Node<T> >;
    Node() : _next(0), _prev(0), _head(0), _nextHead(0), _prevHead(0) {}
    Node(T data) : _data(data), _next(0), _head(0), _nextHead(0), _prevHead(0) {}
    Node(T data, Node<T>* next, Node<T>* prev, Node<T>* head, Node<T> nextHead, Node<T> prevHead) :
        _data(data), _next(next), _prev(prev), _head(head), _nextHead(nextHead), _prevHead(prevHead){}

    T _data;
    Node<T>* _next;
    Node<T>* _prev;
    Node<T>* _head;
    Node<T>* _nextHead;
    Node<T>* _prevHead;

public:
    typedef T value_type;
};

template <typename T>
class LinkedList
{

public:
    using size_type = std::size_t;

private:
    Node<T>* first;
    Node<T>* last;
    Node<T>* lastHead;
    size_type _count = 0;
    double columnNumbers = 0;

public:

    typedef T value_type;
    using pointer = std::unique_ptr<Node<T>>;
    using iterator = Iterator<Node<T>>;
    using difference_type = std::ptrdiff_t;
    using reference = T&;
    using const_reference = T const&;
    using const_pointer = T const*;
    using const_iterator = iterator const;
    using reverse_iterator = std::reverse_iterator < iterator >;
    using const_reverse_iterator = reverse_iterator const;

    LinkedList() : first(0), last(0), lastHead(0) { }
    ~LinkedList()
    {
    .............removed unneeded code...............
    }

    iterator                begin(){ return iterator(first); }
    iterator                end(){ return iterator(last); }
    const_iterator          begin() const { return const_iterator(first); }
    const_iterator          end() const { return const_iterator(last); }
    const_iterator          cbegin() const { return const_iterator(first); }
    const_iterator          cend() const { return const_iterator(last); }
    reverse_iterator        rbegin() { return reverse_iterator(last); }
    reverse_iterator        rend() { return reverse_iterator(first); }
    const_reverse_iterator  rbegin() const { return const_reverse_iterator(last); }
    const_reverse_iterator  rend() const { return const_reverse_iterator(first); }
    const_reverse_iterator  crbegin() const { return const_reverse_iterator(last); }
    const_reverse_iterator  crend() const { return const_reverse_iterator(first); }

    .............removed unneeded code...............

    void insert(T data)
    {
    .............removed unneeded code...............
    }

    void reorder() { // this reorders the head pointers so they are all in the correct spot for the square list
    .............removed unneeded code...............
    }

    bool erase(iterator& _iNode) //True for success, vice versa
    {
    .............removed unneeded code...............
    }

    void clear()
    {
    .............removed unneeded code...............
    }
};

template <typename T>
bool operator==(Iterator<Node<T>> const& lhs, Iterator<Node<T>> const& rhs){ 
    return lhs.compare(rhs);
}

Here's the test I am supposed to run

BOOST_AUTO_TEST_CASE(ut_Rvalue_insert_scrambled_int) {
    typedef std::unique_ptr<int> UP;
    std::vector<int> data{ 9, 10, 7, 8, 5, 6, 3, 4, 1, 2 };
    LinkedList<UP> sqi;
    for (auto datum : data) {
        sqi.insert(UP(new int(datum)));
    }

    std::sort(data.begin(), data.end());
    std::vector<int> dup;
    for (auto iter = sqi.begin(); iter != sqi.end(); ++iter) {
        dup.push_back(*iter->get());
    }

    std::sort(data.begin(), data.end());
    std::sort(dup.begin(), dup.end());
    BOOST_CHECK(dup.size() == data.size());
    BOOST_CHECK_EQUAL_COLLECTIONS(dup.begin(), dup.end(), data.begin(), data.end());
}

When compiling, I get these errors:

Error   1   error C2819: type 'Iterator<Node<T>>' does not have an overloaded member 'operator ->'   ut_square_list_10_insert_rvalue.cpp    33

and

Error   2   error C2232: '->Iterator<Node<T>>::get' : left operand has 'class' type, use '.'    ut_square_list_10_insert_rvalue.cpp 33  1

So, I know this is an issue relating to pointers, but I don't know how, or what I should be doing here.

In particular, it's this line...

dup.push_back(*iter->get());

Is there a better way to set this up, or is he requiring me to overload the -> operator?

I tried changing it to this (even though my prof will not want it this way -- he rips the current ut files out and puts fresh copies in, so he wants it to work the above way, and not this way)

dup.push_back(*iter.get());

It no longer gives me the overloaded errors, but is it giving me this now:

Error   1   error C2280: 'std::unique_ptr<int,std::default_delete<_Ty>>::unique_ptr(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)' : attempting to reference a deleted function
2

There are 2 answers

0
adprocas On BEST ANSWER

Now that this project has been submitted and marked, I thought I would give the answer.

value_type *operator->() const {
    TNode* node = pNode;
    value_type* nodeData = &node->_data;
    return nodeData;
}

Essentially, from what I understand, and the way I created my linked list, I needed to overload the -> operator and pass out a pointer to the data reference.

If someone could explain this a bit more I would really appreciate it. It's tough to wrap my head around why I would need to do this, but this is the only way I could figure out how to achieve this, and was the accepted answer by the prof (I didn't lose any marks on the project).

1
Maryan Pritsak On

Ok, lets look at the types here.

You have a LinkedList<UP> and std::vector<int>. So when you're trying to push an element to vector using list's iterator, you have to get a UP value from iterator using iter.get(), and then dereference it using operator *.

So the final line should look like this: dup.push_back(*iter.get());