arrayListWithIterator

添加iterator类和begin()，end()

• 迭代器类型定义迭代器的分类。这些标签都是空类型，分别对应五种迭代器分类中的一种，迭代器类型用于指明实例化迭代器的标签，如:输入迭代器(写)、输出迭代器(读)、随机访问迭代器等，算法可通过不同迭代器种类来实现各版本。
  input_iterator_tag 对应 LegacyInputIterator 。
  output_iterator_tag 对应 LegacyOutputIterator 。
  forward_iterator_tag 对应 LegacyForwardIterator 。
  bidirectional_iterator_tag 对应 LegacyBidirectionalIterator 。
  random_access_iterator_tag 对应 LegacyRandomAccessIterator

emplate<class T>
class arrayList : public linearList<T>
{
   public:
     ...

      // iterators to start and end of list
      class iterator;
      iterator begin() {return iterator(element);}
      iterator end() {return iterator(element + listSize);}

      // iterator for arrayList
      class iterator
      {
         public:
            // typedefs required by C++ for a bidirectional iterator
            typedef bidirectional_iterator_tag iterator_category;
            typedef T value_type;
            typedef ptrdiff_t difference_type;
            typedef T* pointer;
            typedef T& reference;

            // constructor
            iterator(T* thePosition = 0) {position = thePosition;}

            // dereferencing operators
            T& operator*() const {return *position;}
            T* operator->() const {return &*position;}

            // increment
            iterator& operator++()   // preincrement
                      {++position; return *this;}
            iterator operator++(int) // postincrement
                      {iterator old = *this;
                       ++position;
                       return old;
                      }

            // decrement
            iterator& operator--()   // predecrement
                      {--position; return *this;}
            iterator operator--(int) // postdecrement
                      {iterator old = *this;
                       --position;
                       return old;
                      }

            // equality testing
            bool operator!=(const iterator right) const
                  {return position != right.position;}
            bool operator==(const iterator right) const
                  {return position == right.position;}
         protected:
            T* position;
      };  // end of iterator class

   protected:  // additional members of arrayList
      void checkIndex(int theIndex) const;
            // throw illegalIndex if theIndex invalid
      T* element;            // 1D array to hold list elements
      int arrayLength;       // capacity of the 1D array
      int listSize;          // number of elements in list
};

应用实例

// test the iterator for arrayList
#include<iostream>
#include<algorithm>   // has reverse
#include<numeric>     // has accumulate
#include "linearList.h"
#include "arrayListWithIterator.h"

using namespace std;

int main()
{
   // create a linear list
   arrayList<int> y(2);
   y.insert(0, 2);
   y.insert(1, 6);
   y.insert(0, 1);
   y.insert(2, 4);
   y.insert(3, 5);
   y.insert(2, 3);
   cout << "Inserted 6 integers, list y should be 1 2 3 4 5 6" << endl;
   cout << "Size of y = " << y.size() << endl;
   cout << "Capacity of y = " << y.capacity() << endl;

   // test iterator
   cout << "Ouput using forward iterators pre and post ++" << endl;
   for (arrayList<int>::iterator i = y.begin();
        i != y.end(); i++)
      cout << *i << "  ";
   cout << endl;
   for (arrayList<int>::iterator i = y.begin();
        i != y.end(); ++i)
      cout << *i << "  ";
   cout << endl;

   cout << "Ouput using backward iterators pre and post --" << endl;
   for (arrayList<int>::iterator i = y.end();
        i != y.begin(); cout << *(--i) << "  ");
   cout << endl;
   for (arrayList<int>::iterator i = y.end();
        i != y.begin();)
      {i--; cout << *i << "  "; *i += 1;}
   cout << endl;
   cout << "Incremented by 1 list is " << y << endl;

   // try out some STL algorithms
   reverse(y.begin(), y.end());
   cout << "The reversed list is " << y << endl;
   int sum = accumulate(y.begin(), y.end(), 0);
   cout << "The sum of the elements is " << sum << endl;

   return 0;
}

output

lcl@FX50JK:~/Documents/hub/learning-record/datastruct_and_algrithm$ ./arrayListWithIterator
Inserted 6 integers, list y should be 1 2 3 4 5 6
Size of y = 6
Capacity of y = 8
Ouput using forward iterators pre and post ++
1  2  3  4  5  6  
1  2  3  4  5  6  
Ouput using backward iterators pre and post --
6  5  4  3  2  1  
6  5  4  3  2  1  
Incremented by 1 list is 2  3  4  5  6  7  
The reversed list is 7  6  5  4  3  2  
The sum of the elements is 27