Lab 6: Linked List Iterator

Objectives

Implement the list iterators.

Linked List Class

Assignment

iterator class

  1. Write both const iterator& operator--(int); and iterator& operator--(int); functions. The int parameter is simply to specify that this is the post increment function. If the direction of the iterator is forward, you should go to next. Otherwise go to prev. Don't allow incrementing past the head or tail.
  2. Once you have the above forward iterators completed, provide two additional iterator classes:
            class const_reverse_iterator : public const_iterator
    	{
    	...
    	}
            class reverse_iterator : public const_iterator
    	{
    	...
    	}
    	
    These are reverse iterators, meaning that they start at the node just before the end() node, and when incremented, they go backwards...the reverse of the forward iterators.
  3. Provide the following iterator functions:
            iterator               begin();			// first node mutator
            const_iterator         begin() const;           // first node accessor
            iterator               end();			// tail node mutator
            const_iterator         end() const;		// tail node accessor
            
            reverse_iterator       rbegin();                // last node mutator
            const_reverse_iterator rbegin() const;          // last node accessor
            reverse_iterator       rend();                  // head node mutator
            const_reverse_iterator rend() const;            // head node accessor
    
            iterator        insert(iterator, const T&);	// before iterator
            iterator        erase(iterator);		// at iterator
            iterator        erase(iterator, iterator);	// iterator range
    	

list class

  1. Provide the following list_t public member functions:
            int             size() const;			// size of list
            bool            empty() const;			// list empty?
            void            clear();			// nuke all elements
    
            T&              front();                        // front data mutator
            const T&        front() const;                  // front data accessor
            T&              back();                         // back data mutator
            const T&        back() const;                   // back data accessor
            iterator        push_front(const T& o);         // insert at front
            iterator        push_back(const T& o);          // insert at end
            iterator        pop_front();                    // nuke front node
            iterator        pop_back();                     // nuke back node
    	

main.cpp driver

  1. Your program should produce the sample output with the following driver program:
    #include <iostream>
    #include <cstdlib>
    #include <sys/time.h>
    
    #include "list.h"
    #include "pairs.h"
    
    int        main();
    void       insert(list_t<pairs_t>& plist, pairs_t pair);
    
    int main()
    {
            int                             num;
            list_t<int>                     list;
            list_t<int>::iterator           itr;
            list_t<int>::reverse_iterator   ritr;
            list_t<pairs_t>                 plist;
    
            struct timeval                  tp;
    
      // get time of day
      gettimeofday(&tp,NULL);
    
      // use microseconds as the seed
    //srand((unsigned int)tp.tv_usec);
      srand((unsigned int)1337);
    
      // sort while inserting, thus maintaining list as priority queue
      std::cout << "Inserting:" << std::endl;
      for(int i=0;i<10;i++) {
        num = static_cast<int>((float)rand()/(float)RAND_MAX*100.0);
        std::cout << num << " ";
        for(itr = list.begin(); itr != list.end() && num > *itr; ++itr);
        list.insert(itr,num);
      }
      std::cout << std::endl;
    
      std::cout << "list_t (front to back):" << std::endl;
      for(list_t<int>::iterator itr = list.begin(); itr != list.end(); ++itr)
        std::cout << *itr << " ";
      std::cout << std::endl;
    
      std::cout << "list_t (back to front, using operator--):" << std::endl;
      for(list_t<int>::iterator itr = --list.end(); itr != --list.begin(); --itr)
        std::cout << *itr << " ";
      std::cout << std::endl;
    
      std::cout << "list_t (back to front, using reverse_iterator):" << std::endl;
      for(ritr = list.rbegin(); ritr != list.rend(); ++ritr)
        std::cout << *ritr << " ";
      std::cout << std::endl;
    
      ///////////
    
      insert(plist,pairs_t(45.0,'b'));
      insert(plist,pairs_t(37.2,'c'));
      insert(plist,pairs_t(42.6,'a'));
      insert(plist,pairs_t(53.7,'d'));
    
      std::cout << "list_t (front to back):" << std::endl;
      for(list_t<pairs_t>::iterator pitr = plist.begin(); pitr != plist.end(); ++pitr)
        std::cout << *pitr << " ";
      std::cout << std::endl;
    
      std::cout << "list_t (back to front):" << std::endl;
      for(list_t<pairs_t>::reverse_iterator pitr = plist.rbegin(); pitr != plist.rend(); ++pitr)
        std::cout << *pitr << " ";
      std::cout << std::endl;
    }
    
    void insert(list_t<pairs_t>& plist, pairs_t pair)
    {
            list_t<pairs_t>::iterator        pitr;
    
      // sort while inserting, thus maintaining list as priority queue
      std::cout << "Inserting: " << pair << std::endl;
      for(pitr = plist.begin(); pitr != plist.end() && pair > *pitr; ++pitr);
        plist.insert(pitr,pair);
    }
    

sample output

    Inserting:
    1 86 24 21 30 74 89 64 21 68 
    list_t (front to back):
    1 21 21 24 30 64 68 74 86 89 
    list_t (back to front, using operator--):
    89 86 74 68 64 30 24 21 21 1 
    list_t (back to front, using reverse_iterator):
    89 86 74 68 64 30 24 21 21 1 
    Inserting: ('b',45)
    Inserting: ('c',37.2)
    Inserting: ('a',42.6)
    Inserting: ('d',53.7)
    list_t (front to back):
    ('a',42.6) ('b',45) ('c',37.2) ('d',53.7) 
    list_t (back to front):
    ('d',53.7) ('c',37.2) ('b',45) ('a',42.6) 
    

Turn in

Turn in all of your code, in one tar.gz archive of your lab##/ directory, including:
  1. A README file containing
    1. Course id--section no
    2. Name
    3. Lab description
    4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
    5. Lessons learned, identified interesting features of your program
    6. Any special usage instructions
  2. Makefile
  3. source code (.h headers and .cpp source)
  4. object code (do a make clean before tar)

How to hand in

See sendlab notes