Random Access List

I am working on a C++ project that requires us to make a class that makes a list able to use random access.

I have made a class RAList<Temp> (Random Access list) that inherits from list<Temp>.

I have random access working correcty with the [] operator, but i am stuck on the next part. Here are the instructions given:

"list<ELEM>::iterator +, allows an iterator to it = it + 5 which will increment the iterator to point to the fifth element from the current position "

I have somewhat of a solution but it does not meet those requirments, right now I am implementing the + operator in the RAList class and I iterate n number of time until I get to the iterator that is "n" away from its current iterator, problem with this is when I use the code it looks something like this:

RAList<int> intList;

// populate intList....

RAList<int>::iterator itInt;
itInt = intList + 5;

and this does not follow the it = it + 5 format, is acually it = RAList<int> + 5.

Anyone know how I would be able to implement this solution?

Thanks in advanced,

Matt

Doesn't std::list<>::iterator do that already?

Are iterator::operator ++ () and operator -- () already defined?

Code:

RAList<T>::iterator & RAList<T>::iterator::operator + (int inc)
{
   RAList<T>::iterator temp(*this);
   if(inc > 0)
   {
      do { temp++; } while(--inc);
   }
   else if(inc < 0)
   {
      do { temp--; } while(++inc);
   }
   return temp;
}

Code:

//Hey -- I don't know how to distinguish between post increment function and pre-increment function
//Post:
RAList<T>::iterator & RAList<T>::iterator::operator ++ ()
{
   RAList<T>::iterator old(*this);
   if(this->ptr->next != NULL)
       this->ptr = this->ptr->next;
   else {}//exception? undefined behavior?
   return old;
}

I am only concered with getting the increment working.

operator ++ and operator -- are already defined (in base class list)

But it = it + 5 does not exist, that would make lists random access already, which they are not. And this is what i am trying to accomplish with RAList<temp>.

since lists do not have this, the following code does not compile as you are trying to access a + operator in RAList (which inherits from list) and list does not have a + operator:

Code:

RAList<T>::iterator & RAList<T>::iterator::operator + (int inc)

Thanks though!

Any other suggestions?

In case anyone was wonder the current operator + i have implemented looks like this:

Code:

iterator operator + (size_type const& iNum )

Altough this is incorrect (as stated above) as it means I need to call it like this:

Code:

itInt = intList + 1;

intList being an instance of RAList<int>

And I need to be able to use an iterator of RAList there instead.

Thanks,

First don't publicly inherit from std containers. They don't have virtual destructors.

you should use containment instead and add inline forwarding methods

i.e.

Code:

template <typename T>
class RAList
{
private:
    typedef std::list<T> Container;

public:
    typedef Container::iterator iterator;

    // forward std::list methods
    iterator begin(void) { return m_list.begin(); }
    inline size_t size(void) const { return m_list.size(); }
    
private:
    Container m_list;
};

the easiest way to implement the subscript operator is to use the std::advance algorithm.



also FYI the way to distinguish between pre and post increment operators is by adding an unused int parameter to the operator usually implemented like this

Code:

// pre-increment
 MyClass& MyClass::operator++ ()
 {
   ++m_number;
   return *this;
 }
 
// post-increment
 MyClass MyClass::operator++ (int)
 {
   MyClass ans = *this;
   ++(*this); 
   return ans;
 }

see the C++ FAQ

for operator + you need to make a non-member function

Code:

template <typename T>
RAList<T>::iterator operator+(RAList<T>::iterator iter, size_t inc)
{
    std::advance(iter, inc);
    return iter;
}

// and another for RAList + int
template <typename T>
RAList<T>::iterator operator+(RAList<T>& coll, size_t inc)
{
    return coll.begin() + inc;
}

note: you'll also need overloads for const_iterator

Originally Posted by ChaosEngine

First don't publicly inherit from std containers. They don't have virtual destructors.

you should use containment instead and add inline forwarding methods

i.e.

Code:

template <typename T>
class RAList
{
private:
    typedef std::list<T> Container;

public:
    typedef Container::iterator iterator;

    // forward std::list methods
    iterator begin(void) { return m_list.begin(); }
    inline size_t size(void) const { return m_list.size(); }
    
private:
    Container m_list;
};

the easiest way to implement the subscript operator is to use the std::advance algorithm.



also FYI the way to distinguish between pre and post increment operators is by adding an unused int parameter to the operator usually implemented like this

Code:

// pre-increment
 MyClass& MyClass::operator++ ()
 {
   ++m_number;
   return *this;
 }
 
// post-increment
 MyClass MyClass::operator++ (int)
 {
   MyClass ans = *this;
   ++(*this); 
   return ans;
 }

see the C++ FAQ

Thanks for that tip, I'll change code over so it does not inherit from List.... but the problem of the + operator still remains. I am not looking to use ++, i need + to implement random access.

Thanks,

Originally Posted by ChaosEngine

for operator + you need to make a non-member function

Code:

template <typename T>
RAList<T>::iterator operator+(RAList<T>::iterator iter, size_t inc)
{
    std::advance(iter, inc);
    return iter;
}

note: you'll also need overloads for const_iterator

I have tried this... and now tired again and I get compile error, operator + has too many paramaters

Originally Posted by avalanche333

I have tried this... and now tired again and I get compile error, operator + has too many paramaters

declare this function outside the class definition (NON-member function!)

Code:

template <typename T>
class RAList
{
   // ...
};

template <typename T>
RAList<T>::iterator operator+(RAList<T>::iterator iter, size_t inc)
{
    std::advance(iter, inc);
    return iter;
}

if that still doesn't work post your whole code

Still No dice... now I get

Warning: RAList<T>::iterator dependent name is not a type
Error: syntax error missing ; before +
Error: missing type specifier - int assumed
Error: unable to recover from previous error

Here is the full code... i taken out my + operator as it is wrong anyways and have your in as a non member function.

P.S I really appriciate your help

Code:

#ifndef _GUARD_RALIST_
#define _GUARD_RALIST_

#include <list>
#include <cassert>

template <typename T>
class RAList : public std::list<T>
{
private:
	list<iterator> _lstInsertHistory;		// Keeps history of each element added using insert()
	list<T> _lstRemoveHistory;			// Keeps history of each element removed using remove()
	iterator _currentIt;				// Keeps the current iterator, used for + operator
public:

	// Default Constructor
	RAList() : std::list<T>(), _lstInsertHistory(), _lstRemoveHistory(), _currentIt( begin() )
	{
		assert( _lstInsertHistory.empty() );
		assert( _lstRemoveHistory.empty() );
		
		assert( empty() );
	}

	// Destructor
	~RAList()
	{
		_lstInsertHistory.clear();
		_lstRemoveHistory.clear();
		clear();
		assert( _lstInsertHistory.empty() );
		assert( _lstRemoveHistory.empty() );
		assert( empty() );
	}

	reference operator [] ( size_type const& iNum )
	{
		iterator it = 0;

		( iNum > static_cast<size_type>( size() / 2) ) ? it = end() : it = begin();

		if ( it == end() )
			for( size_type i = size(); i != iNum; --i)
				--it;
		else
			for( size_type i = 0; i != iNum; ++i)
				++it;

		return *it;
	}

	iterator insert( iterator it, const T& x = T( ) )
	{
		_lstInsertHistory.push_front( list<T>::insert( it, x ) );
		return _lstInsertHistory.front();
	}

	void undo_last_insert()
	{
		if ( _lstInsertHistory.size() <= 0 )
			return;
		
		for ( list<iterator>::iterator it1 = _lstInsertHistory.begin(); it1 != _lstInsertHistory.end(); ++it1)
		{
			iterator it = begin();
			for( size_type i = 0; i <= size(); ++i )
			{
				if ( it == *it1 )
				{				
					erase( it );
					_lstInsertHistory.erase( it1 );
					return;
				}
				else
					++it;
			}			
		}
	}

	void remove( const T& _Val )
	{
		for( iterator it = begin(); it != end(); ++it )
		{
			if ( *it == _Val )
			{
				_lstRemoveHistory.push_back( _Val );
				list<T>::remove( _Val );
				break;
			}
		}
	}

	void undo_last_remove()
	{
		if ( _lstRemoveHistory.size() <= 0 )
			return;
		
		push_back( _lstRemoveHistory.back() );
		_lstRemoveHistory.pop_back();
	}

};

template <typename T>
RAList<T>::iterator operator+ (RAList<T>::iterator iter, size_t inc)
{
    std::advance(iter, inc);
    return iter;
}

#endif

Well, first off there is a very good reason that std::list does NOT have operator[] nor operator+, and unless you've been specifically assigned to make one, you should rethink your design if you need this capability.

Second, why not do just as you did in the [] code, just loop and increment/decrement one step at a time. However you code it, that's how the code will be working anyway.

That is the reason, incidentally, why std::list doesn't have them. It's an O(N) traversal as opposed to O(1) like a true random access container.

Yes this is part of an assignment we are working on in class. The point is to make lists have random access using [] and the + operators... the teacher did tell us this is inefficient, but ultimately the goal of this exercise is to demonstrate the boost test library, where we will be performing various unit tests. And I am sure this is probably not the best design, you can go on and on making it better faster... so on, but at this point I just need to get it working. I will likely go back and optimize or or completely change this class should I need to.

If anyone has tips on how I can make this code better and more efficient please feel free to add, I'm a student trying to learn , but for now lets stick to the task at hand, getting + operator working.

Thanks,

[QUOTE=ChaosEngine]First don't publicly inherit from std containers. They don't have virtual destructors.

you should use containment instead and add inline forwarding methods

i.e.

Code:

template <typename T>
class RAList
{
private:
    typedef std::list<T> Container;

public:
    typedef Container::iterator iterator;

    // forward std::list methods
    iterator begin(void) { return m_list.begin(); }
    inline size_t size(void) const { return m_list.size(); }
    
private:
    Container m_list;
};

I am beginning to implement the solution this way... question is when when I compile with any fuctions returing an iterator I get missing type specifier - int assumed error? I have tired using the return iterator as per typedef... and std::list<T>::iterator and it doesnt seem to be working?

Idea's on this issue?

Prefix with the word "typename". I believe it should be

Code:

typedef typename Container::iterator iterator;

Originally Posted by Daved

Prefix with the word "typename". I believe it should be

Code:

typedef typename Container::iterator iterator;

Thanks, just as checked this i figured this out.

Still looking into the + operator