Random Access List

This is a discussion on Random Access List within the C++ Programming forums, part of the General Programming Boards category; I am working on a C++ project that requires us to make a class that makes a list able to ...

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    38

    Exclamation 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

  2. #2
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    920
    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;
    }
    Last edited by CodeMonkey; 01-21-2007 at 08:57 PM.
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  3. #3
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    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?
    Last edited by avalanche333; 01-21-2007 at 09:30 PM.

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    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,

  5. #5
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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
    Last edited by ChaosEngine; 01-21-2007 at 09:40 PM.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  6. #6
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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
    Last edited by ChaosEngine; 01-21-2007 at 09:54 PM.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    Quote 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,

  8. #8
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    Quote 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

  9. #9
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote 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
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  10. #10
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    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

  11. #11
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  12. #12
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    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,

  13. #13
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    [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?
    Last edited by avalanche333; 01-22-2007 at 09:59 AM.

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    Prefix with the word "typename". I believe it should be
    Code:
    typedef typename Container::iterator iterator;

  15. #15
    Registered User
    Join Date
    Jan 2007
    Posts
    38
    Quote 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

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-28-2008, 12:24 AM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 02:27 PM
  5. link list
    By Unregistered in forum C++ Programming
    Replies: 4
    Last Post: 12-13-2001, 05:41 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21