Thread: Linked-list custom iterator

Hello All, Season's Greetings.


I'm trying to write a custom iterator for a double linked-list, the code raises hope by compiling and then crashes spectacularly. The debug message is below:

Code:

#0 0x45e99d	std::__shared_ptr<test::Link<std::string>, (__gnu_cxx::_Lock_policy)2>::operator=(this=0x8) (C:/Program Files 
(x86)/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/shared_ptr_base.h:860)
#1 0x45d8ad	std::shared_ptr<test::Link<std::string> >::operator=(this=0x8) 
(C:/Program Files (x86)/CodeBlocks/MinGW/lib/gcc/mingw32/4.9.2/include/c++/bits/shared_ptr.h:93)
#2 0x42e30d	test::List<std::string>::List(this=0x28fea8)

And the program is here: Private Paste - Pastie
I'd be very grateful if someone could offer me some guidance. Many thanks

Please paste the code as the link you have shared is not working

http://pastie.org/10986185

Please paste your code into a post your link location seems to be broken.

Jim

Have you run the program with your debugger? Your debugger should be able to tell you exactly where it detects the problem. For example this is what my compiler reports for the call stack after the crash:

Code:

#0 0x45392d	std::__shared_ptr<test::Link<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, (__gnu_cxx::_Lock_policy)2>::operator=(this=0x10) (/opt/gcc/6.1.0/include/c++/6.1.0/bits/shared_ptr_base.h:870)
#1 0x453975	std::shared_ptr<test::Link<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::operator=(this=0x10) (/opt/gcc/6.1.0/include/c++/6.1.0/bits/shared_ptr.h:93)
#2 0x453a38	test::List<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::List(this=0x7fffffffdf40) (main.cpp:66)
#3 0x453598	main() (main.cpp:168)

So with this call stack you would pretty much ignore the first two locations because they are part of the STL and are most likely not the real problem. So then that moves you to the third message, which happens to be on line 66 in your code:

Code:

        List() { _size = 0; _first = nullptr; _last = nullptr; _first -> _next = _last ;}

And this line is definitely the problem. You're trying to access a value though a nullptr so the program crashes.

By the way this line is also malformed.

Code:

        const size_t getSize() { return _size; }

The const qualifier is probably in the wrong place. It probably should be more like:

Code:

        size_t getSize() const { return _size; }

Which tells the compiler that this function won't change any of the class member variables.

Also this line:

Code:

            using difference_type = ptrdiff_t;

Since you're not using the using namespace std; clause you need to properly scope the ptrdiff_t type.

Jim

I wouldn't advise using shared_ptr in this context.

I have heard that using shared pointers in this kind of context does nothing but create memory leaks (because of the circular references) but regardless, smart pointers are used in C++ to represent ownership over a region of memory. In this instance, the code you're writing is trying to say that each node partially "owns" its neighbors. Keep in mind, a linked list is basically just a graph so that's why I say "neighbors".

So now I have to ask, who actually "owns" the memory in a linked list?

I'd almost just suggest raw pointers. :P

It seems like smart pointers do not favor graph-based data structures.

Please post your current code.


Jim

Here's the latest that only prints the first node and aborts, thanks

Code:

#include <iostream>
#include <initializer_list>
#include <memory>
#include <string>


namespace test
{
    template <typename Elem>
    struct Link
    {
        std::shared_ptr<Link<Elem>> _prev;
        std::shared_ptr<Link<Elem>> _next;
        Elem _val;
        Link(){}
        ~Link () {}
        Link(Elem val) : _val(val){}
    };
    template <typename Elem>
    struct List
    {
        std::shared_ptr<Link<Elem>> _first;
        std::shared_ptr<Link<Elem>> _last;
        size_t _size;


        template <typename T>
        struct Iter
        {
            using iterator_category = std::bidirectional_iterator_tag;
            using value_type = T;
            using pointer = std::shared_ptr<T>;
            using reference = T&;
            using size_type = size_t;
            using difference_type = std::ptrdiff_t;


            std::shared_ptr<T> _p;


            Iter(std::shared_ptr<T> p) : _p(p) {}
            Iter(T* p) { std::shared_ptr<T> smrt_p = std::shared_ptr<T>(p); _p = smrt_p;}
            ~Iter (){_p = nullptr;}
            Iter(const Iter& rhs) : _p (rhs._p) {}
            Iter& operator = (Iter rhs) { std::swap(_p, rhs._p); return *this; }
            Iter& operator ++ () { _p = _p->_next; return *this; }
            Iter operator ++ (int) { Iter it(*this); _p = _p->next; return it; }
            Iter& operator -- () { _p = _p->prev; return *this;}
            Iter operator -- (int) { Iter it(*this); _p = _p->prev; return it;}
            bool operator == (const Iter& rhs) { return _p == rhs._p; }
            bool operator != (const Iter& rhs) { return _p != rhs._p; }
            Elem& operator *() const { return _p->_val; }
            Iter<T> operator + (int i)
            {
                Iter<T> iter = *this;
                while (i-- > 0 && iter._p)
                {
                    ++iter;
                }
                return iter;
            }
        };
        using iterator = Iter<Link<Elem>>;
        using const_iterator = Iter<const Link<Elem>>;


        List() { _size = 0; _first.reset (new Link<Elem>); _last.reset (new Link<Elem>);  _first -> _next = _last;}
         void add(const Elem &value)
        {
            std::shared_ptr<Link<Elem>> newNode  (new Link<Elem>(value));
            newNode->_next = _first->_next;
            _first->_next = newNode;
            _size++;
        }
        List(const List& rhs)
        {
           _size = 0; _first.reset (new Link<Elem>); _last.reset (new Link<Elem>);  _first -> _next = _last;
            for(const_iterator i = rhs.cbegin(); i!= rhs.cend(); ++i)
            {
                add(*i);
            }
        }
        List(List&& rhs)
        {
           _size = 0; _first.reset (new Link<Elem>); _last.reset (new Link<Elem>);  _first -> _next = _last;
            _size = rhs._size;
            _first = rhs._first;
            _last = rhs._last;
            rhs._size = 0;
            rhs._first = nullptr;
            rhs._last = nullptr;
        };
        List& operator = (List rhs)
        {
            swap(*this, rhs);
            return *this;
        }
        List& operator = (List&& rhs)
        {
            assert(this != &rhs);
            while (_first->_next != _last)
            remove(begin());
            _first = rhs._first;
            _last = rhs._last;
            _size = rhs._size;
            rhs._size = 0;
            rhs._first = nullptr;
            rhs._last = nullptr;


            return *this;
        }
        ~List()
        {
            while (_first->_next != _last)
            remove(begin());
        }
        friend void swap(List& lhs, List& rhs)
        {
            std::swap(lhs._size, rhs._size);
            std::swap(lhs._first, rhs._first);
            std::swap(lhs._last, rhs._last);
        }


        void remove(iterator removeIter)
        {
            std::shared_ptr<Link<Elem>> final = _first;
            iterator i = begin();


            while (i != removeIter)
            {
                final = i._p;
                ++i;
            }


            if (i != end())
            {
                final->_next = i._p->_next;
                _size--;
            }
        }
        size_t getSize() const { return _size; }


        iterator begin()
        {
            return iterator(_first->_next);
        }
        const_iterator cbegin() const
        {
            return iterator(_first->next);
        }
        iterator end()
        {
            return iterator(_last.get());
        }
        const_iterator cend() const
        {
            return iterator(_last.get());
        }
    };
}
int main()
{
    std::initializer_list <std::string> myInitList {"Cambridge", "Oxford", "Imperial", "LSE"};
    test::List<std::string> myList;
    for (auto& e : myInitList)
    {
        myList.add(e);
    }
    for (test::List<std::string>::iterator iter = myList.begin(); iter != myList.end(); ++iter)
    {
        std::cout << *(iter) << ' ';
    }
}
/*http://codereview.stackexchange.com/questions/55834/linked-list-with-iterators
http://stackoverflow.com/questions/30857668/assignment-operator-in-linked-list-c
Above are reference links used for this program */

Your remove method for your list also looks like it's O(n). Maybe I'm wrong but I was under the impression that node removal from a list should be on the order of O(1). This should be a single operation that requires no iteration on your part.