linked list problem

[viliml]

Hi, I am trying to make my own double-linked list class, and make it compatible with al the STL algorithms, but I get an error when I run it(it compiles fine). Here's the mylist.hpp:

#ifndef MYLIST_HPP
#define MYLIST_HPP

namespace std
{
template<typename _Tp, typename _Ref, typename _Ptr>
    struct mylist_it
    {
      typedef mylist_it<_Tp, _Tp&, _Tp*>             iterator;
      typedef mylist_it<_Tp, const _Tp&, const _Tp*> const_iterator;

      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                        value_type;
      typedef _Ptr                       pointer;
      typedef _Ref                       reference;
      typedef size_t                     size_type;
      typedef ptrdiff_t                  difference_type;
      typedef _Tp**                      _Map_pointer;
      typedef mylist_it               _Self;

      _Tp* _M_cur;
      _Tp* _M_first;
      _Tp* _M_last;
      _Map_pointer _M_node;

      mylist_it() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}

      mylist_it(const iterator& __x)
      : _M_cur(__x._M_cur), _M_first(__x._M_first),
        _M_last(__x._M_last), _M_node(__x._M_node) {}
        
      mylist_it(_Ref a):_M_cur(&a), _M_first(&a)
      {
                        _Tp temp=*_M_cur;
                        _M_last=&temp;
                        for (int i=0; i<a.size; i++)
                        {
                            _M_last=_M_last->next;
                            }
                        _M_first=&a;
                        _M_cur=_M_first;
                        _M_node=&_M_first;
                        }
      mylist_it(_Ptr a):_M_cur(a), _M_first(a), _M_node(&a)
      {
                        _Tp temp=*_M_cur;
                        _M_last=&temp;
                        for (int i=0; i<a->size; i++)
                        {
                            _M_last=_M_last->next;
                            }
                        _M_first=a;
                        _M_cur=_M_first;
                        _M_node=&_M_first;
                        }

      _Ref
      operator*() const
      { return *_M_cur; }

      pointer
      operator->() const
      { return _M_cur; }

      _Self&
      operator++()
      {
	_M_cur=_M_cur->next;
	return *this;
      }

      _Self
      operator++(int)
      {
	_Self __tmp = *this;
	++*this;
	return __tmp;
      }

      _Self&
      operator--()
      {
	_M_cur=_M_cur->prev;
	return *this;
      }

      _Self
      operator--(int)
      {
	_Self __tmp = *this;
	--*this;
	return __tmp;
      }

      _Self&
      operator+=(difference_type __n)
      {
	for (int i=0; i<__n; i++)
	{
        (*this)++;
        }
	return *this;
      }

      _Self 
      operator+(difference_type __n) const
      {
       _Self __tmp=*this;
	return __tmp += __n;
      }

      _Self&
      operator-=(difference_type __n)
      { return *this += -__n; }

      _Self
      operator-(difference_type __n) const
      {
	_Self __tmp = *this;
	return __tmp -= __n;
      }
      difference_type
      operator-(_Self a)
      {
           _Self temp=*this;
           int i;
           for (i=0; temp!=a; i++, temp++);
           return i;
           }
      reference
      operator[](difference_type __n) const
      { return *(*this + __n); }

      void
      _M_set_node(_Map_pointer __new_node)
      {
	_M_node = __new_node;
	_M_first = *__new_node;
	_M_last = _M_first + _M_first->size;
      }
    };

template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator==(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
      return a._M_cur==b._M_cur;
      }
      
template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator!=(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
      return !(a==b);
      }
      
template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator<(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
      int i, j;
      for (i=0; a._M_cur!=a._M_first; i++) a._M_cur=a._M_cur->prev;
      for (j=0; b._M_cur!=b._M_first; i++) b._M_cur=b._M_cur->prev;
      return i<j;
      }
      
template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator>(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
      return b<a;
      }
      
template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator<=(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
       return !(a>b);
       }
      
template<typename _Tp, typename _Ref, typename _Ptr>
inline bool operator>=(mylist_it<_Tp, _Ref, _Ptr> a, mylist_it<_Tp, _Ref, _Ptr> b)
{
      return !(a<b);
      }

template<typename T>
struct mylist
{
      typedef mylist_it<mylist<T>, mylist<T>&, mylist<T>*> iterator;
      typedef T value_type;
      T data;
      mylist<T>* next;
      mylist<T>* prev;
      int size;
      mylist()
      {
              data=T();
              next=NULL;
              prev=NULL;
              size=0;
              }
      mylist(int n, T a=T())
      {
                 mylist<T>* temp=this;
                 for (int i=0; i<n; i++)
                 {
                     temp->data=a;
                     temp->next=new mylist<T>;
                     temp->next->prev=temp;
                     temp=temp->next;
                     }
                 temp->next=NULL;
                 this->prev=NULL;
                 size=n;
                 }
      void add(T a)
      {
           mylist<T>* temp=this;
           if (!size)
           {
               size++;
               data=a;
               return;
               }
           while (temp->next!=NULL)
           {
                 temp->next->prev=temp;
                 temp=temp->next;
                 }
           temp->next=new mylist<T>;
           temp->next->data=a;
           temp->next->next=NULL;
           temp->next->prev=temp;
           this->prev=NULL;
           size++;
           }
      iterator begin()
      {
               return *this;
               }
      iterator end()
      {
               return begin()+size;
               }
      };
template<typename T>
inline bool operator<(mylist<T> a, mylist<T> b)
{
       return a.data<b.data;
       }
       
template<typename T>
inline bool operator>(mylist<T> a, mylist<T> b)
{
       return a.data>b.data;
       }
       
template<typename T>
inline bool operator<=(mylist<T> a, mylist<T> b)
{
       return a.data<=b.data;
       }
       
template<typename T>
inline bool operator>=(mylist<T> a, mylist<T> b)
{
       return a.data>=b.data;
       }
       
template<typename T>
inline bool operator==(mylist<T> a, mylist<T> b)
{
       return a.data==b.data;
       }
       
template<typename T>
inline bool operator!=(mylist<T> a, mylist<T> b)
{
       return a.data!=b.data;
       }

template<typename T>
void swap(mylist<T> a, mylist<T> b)
{
     swap(a.data, b.data);
     }
}
#endif

the line in bold it the line where my debugger says the error is, but I don't know what the error is excatly and I don't know how to fix it. I get the error with almost any algorithm.

[guestgulkan]

Come on - give us a clue - what do you mean you don't know exactly what the error is??
It must report something??

Or at least give us the main.cpp file that you are testing with.

[viliml]

By I dont know excatly what the error is, I mean that I dont know why there is a proble there where the program chrashes. I was testing with std::sort, std::binary_search, std::count, std::max_element, std::replace, std::copy, and basicly I am trying any STL algorithm that uses iterators to try and make my class compatible with them, and count, max_element and replace are working but sort, binary_Search and copy(and possibly many more) are not!

[viliml]

the main.cpp:

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include "mylist.hpp"

using namespace std;

int main()
{
    mylist<int> a;
    for (int i=0; i<10; i++)
    {
        a.add(10-i);
        }
    /*the code for the algorithm i'm currently testing*/
    mylist<int>::iterator it;
    for (it=a.begin(); it!=a.end(); it++)
    {
        cout<<it->data<<" ";
        }
    system ("pause");
    return 0;
}

[viliml]

And all the algorithms that don't work, crash at the very same point, the line 68 in mylist.hpp!

[ne555]

but I get an error when I run it(it compiles fine)

I can't make it compile. Please provide an example.

std::mylist<int> l;
std::cout << *std::min_element(l.begin(), l.end()); //no match for ostream << mylilst<int> ¿? 

typedef mylist_it<mylist<T>, mylist<T>&, mylist<T>*> iterator;
template<typename _Tp, typename _Ref, typename _Ptr>
    struct mylist_it;

Dereferencing your iterator returns a list ¿?

If your template arguments are dependent, then you should only take one

typedef T value_type;
typedef T* pointer;
typedef T& reference;

I think that _[A-Z] names are reserved.

[viliml]

I can't make it compile. Please provide an example.

std::mylist<int> l;
std::cout << *std::min_element(l.begin(), l.end()); //no match for ostream << mylilst<int> ¿?  

Did you try this:

std::mylist<int> l;
std::cout << std::min_element(l.begin(), l.end())->data;

?
And, by the way, you are trying to find the max element of an empty list! Put some elements in it with a constructor, or add them with the add function.

And, about the template arguments for the iterator, I just copyed them from std::deque, and made some modifications to make it a list iterator.

And yes, dereferencing the iterator returns a list, like it should be.

[guestgulkan]

This is a really weird way to do a list.

[viliml]

I know, im just doing this for fun and extercise

[ne555]

And, by the way, you are trying to find the max element of an empty list

The min element. I don't care that the list was empty as it wasn't compiling.

And yes, dereferencing the iterator returns a list, like it should be.

¿where did you see that behaviour?
Iterators in the STL don't return the container but the element.

std::list<std::string> list;
std::string crash = *list.end(); //it will compile (but hopefully crash) 

You've got a lot of memory leaks and bad pointer ownership, fix that first.

I just copyed them from std::deque, and made some modifications to make it a list iterator.

It may be better to look at std::list
So, random access...

[ne555]

Your list is a node ¿?

When you create a list with several elements you only update the size of the first node (all the others have size=0)
Now look at this

			mylist_it(_Ref a):_M_cur(&a), _M_first(&a)
			{
				_Tp temp=*_M_cur;
				_M_last=&temp;
				for (int i=0; i<a.size; i++) //never executes if size=0
				{
					_M_last=_M_last->next;
				}
				//_M_last points to local variable.
				_M_first=&a;
				_M_cur=_M_first;
				_M_node=&_M_first;
			}

[viliml]

never executes if size=0

Ummm, that's kinda the point! if size=0, the first, and one after the last are the same, which is impossible, and so is a list of 0 elements.

_M_last points to local variable.

_M_last points to an element of an element of (...) of an element of a local variable, and I don't know if that is a local variable.

[guestgulkan]

Sorry viliml but you are on a loser with this design of list.

[viliml]

@ne555:

Iterators in the STL don't return the container but the element.

I know, but if I do so, I get errors.

It may be better to look at std::list

I know, but Iwanted to do it at least somewhat by myself, and with something like std::deque, I need to fix a LOT of things, which is close to making it from scratch.

[ne555]

_Tp temp=*_M_cur;
_M_last=&temp;

_M_last points to temp, that is a local variable.
So it ends with garbage.

Another thing

iterator end(){
  return begin()+size;
}

The result iterator has _M_cur = NULL so you can't operate with it.

[viliml]

_M_last points to temp, that is a local variable.
So it ends with garbage.

then how would you do it?

The result iterator has _M_cur = NULL so you can't operate with it.

I dont have to OPERATE with it! the only time I use it is to define the end of the list, which is the point where there is no next node, which means that the next node is NULL? So, isn't it supposed to be NULL?

[ne555]

I wouldn't use your approach.
An iterator will have a pointer to the 'current' node. Just that.
Node will have links and a value. (an struct, hidden inside list)
A list will manage the links. To avoid especial cases it has an empty header node and it may be circular.

For your case, _M_last = _M_cur; may be what you want.


--list.end(); perfectly legal, and perhaps useful. It crashes with your code.