++ Operator Overloading

[c++noobie]

I am trying to overload operator++ for a type I have defined. Here' s a little explanation beforehand.
I am working on a link_list class that can be used to create dynamic arrays of any type. I created a basic_link template to hold each element of the array. Each basic_link contains<T> contains a pointer to the next link, the previous link, and a variable to hold a T value. It looks something like this

template <typename T>
struct basic_link
{
T value;
basic_link<T> *previous, *next;
// Definitions of constructors and operators and such
}

I then have a basic_list template that contains two basic_list pointers to the first and last (head and tail) elements of the array and a size variable. I have two typedefs in the class. It looks a little like this

template <typename T>
class basic_list
{
typedef basic_link<T> link;
typedef link* iterator;

iterator head, tail;
size_t size;
// Further class  definition
}

I am trying to make it so that iterator++ causes the iterator to become iterator->next. This is what I tried

friend const iterator& operator++ ( iterator& _iter )
{
_iter= _iter->next;
return _iter;
}

Any help you may can offer would be greatly appreciated.

[ArkM]

As usually, a container iterator is not typedef only, it's a class.
It seems your solution have at least two defects (apart from incorrect syntax):
1. Your list container users want LIST abstraction, not LIST NODE one.
2. It's a class declares some classes or ordinar functions as friends, a function can't proclaim herself as a friend.
Look at some C++ iterator tutorials:
http://sourcemaking.com/design_patterns/iterator/c++/1
http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=1
then try again ;)

[c++noobie]

Thanks a lot for your help, this clears things up quite a bit. I've started working on a basic_link iterator, I am trying to implement some operators, and I am not sure of an effective way to implement the -> operator or comparison operators (>, <, >=, <=).

[c++noobie]

Another quick question. I have a begin() function that returns the head of the list, but I cannot reference it when I try to call it from another list that came into the current list as an argument e.g.

iterator begin()
{
	return head;
}
list& append( const list &_list )
{
	for( iterator position = _list.head; !position.null(); position++ )
		this->append(*position.element);
	return *this;
}

The above append function works fine using _list.head, but I cannot use a call to _list.begin(). I'm thinking it's because I'm accepting it as a const list and then trying to call something from it. I was trying to use const list& to avoid the overhead of creating another copy of the list. What would be the best course of action here? Leave it as it is or try to change it up somehow?

[ArkM]

Post the code, it's impossible to answer without class List definition. You define list node only in the original post. No a list and a list iterator complete definitions till now.

[skatamatic]

I don't think the -> operator (or the . or & operator) can be overloaded =(

[c++noobie]

Ok, I'm sorry this is so long, but you did ask for my code.
BTW, I'm running this with the default gcc compiler that comes with the binary release of the codeblocks IDE.

#ifndef _LIST
#define _LIST

#ifndef _LINK
#include "link.h"
#endif

#ifndef _GLIBCXX_IOSTREAM
#include <iostream>
#endif

#ifndef __EXCEPTION__
#include <exception>
#endif

class iteratorexception: public std::exception
{
	virtual const char* what() const throw()
	{
		return "Bad iterator reference (iterator was NULL)";
	}
} nulliterator;

class indexexception: public std::exception
{
	virtual const char* what() const throw()
	{
		return "Error, the index was out of range";
    }
} badindex;

template <typename T>
class basic_list
{
	typedef basic_link<T> link;
	typedef basic_list<T> list;
    typedef link* plink;

    plink head, tail;
    size_t size;

public:
    class iterator;
    const static size_t npos= -1;

	basic_list()
		: head(NULL), tail(NULL), size(0)
	{}

	basic_list( const T &_value )
		: head(new link(_value)), tail(head), size(1)
	{}

	basic_list( const link &_link )
		: head(new link(_link.value)), tail(head), size(1)
	{}

	basic_list( const list &_list )
		: head(NULL), tail(NULL), size(0)
	{
		for( iterator position = _list.head; !position.null(); position++ )
			this->append(*position);
	}

	~basic_list()
	{
		iterator position (head);
		while( !position.null() )
		{
			delete position++.element;
		}
	}

// Data methods
	iterator begin()
	{
		iterator iter(head);
		return iter;
	}
	iterator end()
	{
		iterator iter(tail);
		return iter;
	}

	const char* type() { return typeid(T).name(); }
	bool empty() { return ( this->size == 0 ); }
	size_t length()	{ return this->size; }

// Modifier methods
	list& clear()
	{
		iterator position (head);
		while( !position.null() )
		{
			delete position++.element;
		}

		head= tail= NULL;
		size= 0;

		return *this;
	}

	void swap( list &_list )
	{
		list temp(_list);
		_list.assign(*this);
		this->assign(temp);
	}

	// Assignment methods
	list& assign( list _list )
	{
		this->clear();
		this->append(_list);
		return *this;
	}
	list& assign( list _list, size_t _pos, size_t _n= npos )
	{
		this->clear();
		try
		{
			this->append(_list.sublist( _pos, _n ));
		}
		catch( std::exception &e )
		{
			throw e;
		}
		return *this;
	}
	list& assign( size_t _n, const T &_value )
	{
		this->clear();
		for( size_t i = 0; i < _n; i++ )
			this->append(_value);
		return *this;
	}
	list& assign( size_t _n, const link &_link )
	{
		this->clear();
		for( size_t i = 0; i < _n; i++ )
			this->append(_link.value);
		return *this;
	}
	list& assign( iterator _first, iterator _last )
	{
		this->clear();
		iterator current= _first, end= _last+1; // _last+1 to include the _last
		while( !current.null() && current != end )
			this->append(*current++);
		return*this;
	}

	// Insertion methods
	list& insert( size_t _pos, const T &_value )
	{
		if( _pos >= size )
			throw badindex;
		plink position= &this->at(_pos);
		plink new_link= new link( _value, position->previous, position );
		if( position == head )
			head= position->previous= new_link;
		else
			position->previous= position->previous->next= new_link;
		return *this;
	}
	list& insert( size_t _pos, const link &_link )
	{
		if( _pos >= size )
			throw badindex;
		plink position= &this->at(_pos);
		plink new_link= new link( _link.value, position->previous, position );
		if( position == head )
			head= position->previous= new_link;
		else
			position->previous= position->previous->next= new_link;
		return *this;
	}
	list& insert( size_t _pos, size_t _n, const T &_value )
	{
		if( _pos >= size )
			throw badindex;
		for( size_t i = 0; i < _n; i++ )
			this->append( _pos, _value );
		return *this;
	}
	list& insert( size_t _pos, size_t _n, const link &_link )
	{
		if( _pos >= size )
			throw badindex;
		T _value= _link.value;
		for( size_t i = 0; i < _n; i++ )
			this->append( _pos, _value );
		return *this;
	}
	list& insert( size_t _pos, const list &_list )
	{
		if( _pos >= size )
			throw badindex;
		for( iterator position = _list.head; !position.null(); position++, _pos++ )
			this->insert( _pos, *position );
		return *this;
	}
	list& insert( size_t _pos1, list _list, size_t _pos2, size_t _n= npos )
	{
		if( _pos1 >= size )
			throw badindex;
		try
		{
			this->insert( _pos1, _list.sublist( _pos2, _n ) );
		}
		catch( std::exception &e )
		{
			throw e;
		}
		return *this;
	}

	// Appending methods
	list& append( const T &_value )
	{
		plink new_link= new link(_value, tail);
		if( size == 0 )
			tail= head= new_link;
		else
			tail= tail->next= new_link;
		size++;
		return *this;
	}
	list& append( const link &_link )
	{
		plink new_link= new link(_link.value, tail);
		if( size == 0 )
			tail= head= new_link;
		else
			tail= tail->next= new_link;
		size++;
		return *this;
	}
	list& append( const list &_list )
	{
		iterator position= _list.head;
		size_t count= _list.size;
		for( size_t i = 0; i < count; i++ )
			this->append(*position++);
		return *this;
	}
	list& operator+= ( const T &_value )
	{
		plink new_link= new link(_value, tail);
		if( size == 0 )
			tail= head= new_link;
		else
			tail= tail->next= new_link;
		size++;
		return *this;
	}
	list& operator+= ( const link &_link )
	{
		plink new_link= new link(_link.value, tail);
		if( size == 0 )
			tail= head= new_link;
		else
			tail= tail->next= new_link;
		size++;
		return *this;
	}
	list& operator+= ( const list _list )
	{
		for( iterator position = _list.head; !position.null(); position++ )
			this->append(*position);
		return *this;
	}

// Access Methods
	link& at( size_t _pos )
	{
		if( _pos >= size )
			throw badindex;
		iterator position(head);
		return *(position+_pos);
	}
	link& operator[] ( size_t _pos )
	{
		if( _pos >= size )
			throw badindex;
		iterator position(head);
		return *(position+_pos);
	}

// Operation methods
	size_t find( const T &_value, size_t _pos )
	{
		if( _pos >= size )
			throw badindex;
		iterator position(&this->at(_pos));
		while( !position.null() && _value != *position++ )
			if( *position == _value )
				return _pos;
			else
				_pos++;
		return npos;
	}
	size_t find( const link &_link, size_t _pos )
	{
		if( _pos >= size )
			throw badindex;
		iterator position(&this->at(_pos));
		while( !position.null() && _link.value != *position++ )
			if( *position == _link.value )
				return _pos;
			else
				_pos++;
		return npos;
	}

	list sublist( size_t _pos, size_t _n= npos )
	{
		if( _pos >= size )
			throw badindex;
		list temp;
		iterator position(&this->at(_pos));
		for( size_t i = 0; i < npos && !position.null(); i++, position++ )
			temp.append(*position);
		return temp;
	}

// Output method
    template <typename CharT>
    friend std::basic_ostream<CharT>& operator<< ( std::basic_ostream<CharT> &out, const list &_list )
    {
    	if( _list.size > 0 )
    	{
    		out << "{ ";
    		iterator start(_list.head), end(_list.tail);
    		for( iterator position= start; !position.null(); position++ )
    		{
    			if( typeid(T) == typeid(char) )
					out << '\'' << *position << '\'';
				else if( typeid(T) == typeid(char*) || typeid(T) == typeid(std::string) )
					out << '\"' << *position << '\"';
				else
					out << *position;
				out << ( position != end ? ", " : " }" );
    		}
    	}
        return out;
    }
};

template <typename T>
struct basic_list<T>::iterator
{
	plink element;

	// Constructors
	iterator()
		: element(NULL)
	{}

	iterator( plink _link )
		: element(_link)
	{}

	iterator( const iterator &_iter )
		: element(_iter.element)
	{}

	bool null() { return ( this->element == NULL ); }

	// Operators

	link& operator* ()
	{
		if( element == NULL )
			throw nulliterator;
		return *element;
	}
	// Problem, find out how to declare operator->
	// operator-> ()

	link& operator[] ( size_t _offset )
	{
		if( element == NULL )
			throw nulliterator;
		iterator temp(*this);
		for( size_t i = 0; i < _offset; i++ )
		{
			if( temp.element == NULL )
				throw nulliterator;
			temp.element= temp.element->next;
		}
		return *temp.element;
	}

	bool operator== ( const iterator &_iter ) { return ( this->element == _iter.element ); }
	bool operator!= ( const iterator &_iter ) { return ( this->element != _iter.element ); }
	bool operator== ( const plink _link ) { return ( this->element == _link ); }
	bool operator!= ( const plink _link ) { return ( this->element != _link ); }

	iterator operator+ ( const size_t &_n )
	{
		iterator temp(*this);
		for( size_t i = 0; i < _n; i++ )
		{
			if( temp.element == NULL )
				throw nulliterator;
			temp.element= temp.element->next;
		}
		return temp;
	}
	iterator operator- ( const size_t &_n )
	{
		iterator temp(*this);
		for( size_t i = 0; i < _n; i++ )
		{
			if( temp.element == NULL )
				throw nulliterator;
			temp.element= temp.element->previous;
		}
		return temp;
	}

	iterator& operator+= ( const size_t &_n )
	{
		for( size_t i = 0; i < _n; i++ )
		{
			if( this->element == NULL )
				throw nulliterator;
			this->element= this->element->next;
		}
		return *this;
	}
	iterator& operator-= ( const size_t &_n )
	{
		for( size_t i = 0; i < _n; i++ )
		{
			if( this->element == NULL )
				throw nulliterator;
			this->element= this->element->previous;
		}
		return *this;
	}

	iterator& operator= ( const iterator &_iter )
	{
		this->element= _iter.element;
		return *this;
	}
	iterator& operator= ( link *_link )
	{
		this->element= _link;
		return *this;
	}

	iterator& operator++ ()
	{
		if( element == NULL )
			throw nulliterator;
		element= element->next;
		return *this;
	}
	iterator operator++ ( int )
	{
		if( element == NULL )
			throw nulliterator;
		iterator current (*this);
		element= element->next;
		return current;
	}

	iterator& operator-- ()
	{
		if( element == NULL )
			throw nulliterator;
		element= element->previous;
		return *this;
	}
	iterator operator-- ( int )
	{
		if( element == NULL )
			throw nulliterator;
		iterator current (*this);
		element= element->previous;
		return current;
	}

	/*void* operator new ( size_t size)
	{
		this->element= new link
	}

	void operator delete (void *p)
	{
		free(p);
	}*/
};

typedef basic_list<int> intlist;
typedef basic_list<double> doublelist;
typedef basic_list<char> charlist;
typedef basic_list<bool> boollist;
#ifdef _GLIBCXX_STRING
typedef basic_list<std::string> stringlist;
#define slist stringlist
#define strlist stringlist
#endif
#define ilist intlist
#define dlist doublelist
#define dbllist doublelist
#define clist charlist
#define blist boollist

#endif /* _LINK */

One thing I would like to figure out, but can't quite figure out. I want to overload the -> operator on the iterator class to be able to reference the members of the list (i.e. iterator->next, iterator->previous, and iterator->value). I also still have no idea where to go with the comparison operators.

I don't think the -> operator (or the . or & operator) can be overloaded =(

I'm not 100% sure it can, but I thought it could. I have seen some stuff about overloading the -> operator, I just don't quite understand it.

[ArkM]

Regrettably you forgot to present list.h so I've invented my own complete list_node type to compile your code. The base_list template member functions used class iterator objects so you must insert class iterator definition in the base_list body, incomplete class (why struct? ) declaration is insufficient.

template <typename T>
class basic_list
{ ...
    friend class iterator;
    class iterator
    {
     ...
    };
...
};

Correct base_list destructor: class base_list can't access private element member of basic_node (may be you did that at the true list.h).

No need to declare base_list<T>::iterator as a template.

After that try to debug the code. I think, there are lots of errors in base_list and iterator logics, it's a common case.

Alas, I don't like these classes design very much:
1. C++ Standard:

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) in a uniform manner.
...
All iterators i support the expression *i, resulting in a value of some class, enumeration, or built-in type T, called the value type of the iterator. All iterators i for which the expression (*i).m is well-defined, support the expression i->m with the same semantics as (*i).m. For every iterator type X for which equality is defined, there is a corresponding signed integral type called the difference type of the iterator.
Since iterators are an abstraction of pointers, their semantics is a generalization of most of the semantics of pointers in C + +.

However you "iterator" returns link object (not base_list value type) and does not support operator -> at all.
More info: http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=2
2. Your base_list<T> is not a list of T elements. It's a list of nodes. This C-like approach transmute this "yet another linked list" class into some kind of caricature on C++ container and container iterator concepts. It's a container-exhibitionist, it exposes its own internals (list nodes and other list support structures) outside. It's a rather strange (and incomplete) chimere of std::vector and C-like double linked list.

Of course, that's your affairs, not mine. I'm a potential user of these classes only but I don't want such list containers in my codes. The worst thing is that you can't study simple, clear and useful C++ container/iterator concepts on this base...

Oh, I forgot to answer your last question about begin() member function. The point is that a natural container.begin() must return referencable iterator to the 1st real node (not at list head - internal list structure). Apropos, container.end() must return unreferencable iterator "past-the-end" of list.

[c++noobie]

Thank you for all of your input. I basically started this whole project to try and do a little learning by experience with class relationships, dynamic memory management, and found a new topic to learn about in the process (iterators). I really had no idea where to start so I took a topic that was briefly referenced in a programming class (link lists) and tried to expand on it. Apparently I missed the target and began writing some ineffective and ugly classes. Do you have any suggestions for a better way to try to deepen my understanding for these topics? (BTW thanks again for all of your help thusfar)