Thread: 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

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,

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

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

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,

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