数组实现线性表带迭代器

阳光穿透心脏的1/2处 2023-07-12 09:16 41阅读 0赞

### 数组实现线性表带迭代器 ###

*   *   *  源代码
         *  输出

### 源代码 ###

#include<bits/stdc++.h>
    using namespace std;
    
    /** * @brief 非法参数异常类 */
    class illegalParameterValue { 
       public:
          illegalParameterValue(string theMessage = "Illegal parameter value")
                { message = theMessage;}
          void outputMessage() { cout << message << endl;}
       private:
          string message;
    };
    
    class illegalIndex 
    { 
       public:
          illegalIndex(string theMessage = "Illegal index")
                { message = theMessage;}
          void outputMessage() { cout << message << endl;}
       private:
          string message;
    };//非法索引异常类
    
    template<class T>
    class Array{ 
        public:
        Array(int init=10){ 
            if(init<1)throw illegalParameterValue(); 
            element = new T[init];
            maxLength = init;
            length = 0;
        }
        Array(const Array<T>& theArray){ //深复制
            maxLength = theArray.maxLength;
            length = theArray.length;
            element = new T[maxLength];
            for(int i=0;i<length;++i)element[i]=theArray.element[i];
        }
        ~Array(){ delete [] element;}
        /** * @brief 获取元素 * @return 返回索引为index的元素 */
        T& get(int index)const{ 
            check(index);
            return element[index];
        }//通过索引返回元素
        int indexOf(const T& theElement)const { 
            for(int i=0;i<length;++i)if(element[i]==theElement)return i;
            return -1;
        }//查找元素在数组的索引，没有返回-1
        void erase(int index){ 
            check(index);
            for(int i=index;i<length-1;++i)element[i]=element[i+1];
            element[--length].~T();
        }//删除索引为index的元素
        void insert(int index,const T& theElement){ 
            if(index<0||index>length)throw illegalIndex();
            if(length==maxLength){ 
                maxLength*=2;
                T* newElement = new T[maxLength];
                for(int i=0;i<length;++i)newElement[i]=element[i];
                delete []element;
                element = newElement; 
            }
    
            for(int i=length;i>index;--i)element[i]=element[i-1];
            element[index]=theElement;
            length++;
        }//在索引为index的位置上插入一个元素
        int capacity()const { return maxLength;}
        bool empty()const { return length==0;}
        int size()const { return length;}
        class iterator;
        iterator begin(){ return iterator(element);}
        iterator end(){ return iterator(element+length);}
    
        class iterator{ 
            public:
                typedef bidirectional_iterator_tag iterator_category;
                typedef T value_type;
                typedef ptrdiff_t difference_type;
                typedef T* pointer;
                typedef T& reference;
                iterator(T* thePosition=0){ position=thePosition;}
                T& operator*() const { return *position;}
                T* operator->()const { return &*position;}
                iterator& operator++(){ 
                    ++position;
                    return *this;
                }//前置增加
                iterator operator++(int){ 
                    iterator old = *this;
                    ++position;
                    return old;
                } 
                iterator& operator--(){ 
                    --position;
                    return *this;
                }//前置--
                iterator operator--(int){ 
                    iterator old =*this;
                    --position;
                    return old;
                }
                bool operator!=(const iterator right)const{ 
                    return position !=right.position;
                }
                bool operator==(const iterator right)const{ 
                    return position == right.position;
                }
            protected:
                T* position;//指针位置
        };
    
        private:
        void check(int index) const{ 
            if(index<0||index>=length) throw illegalIndex();
        }//判断数组索引是否越界
        T* element;//线性表
        int maxLength;//数组开辟长度
        int length;//元素大小
    };
    
    
    template<class T>
    ostream& operator<<(ostream& out ,const Array<T>& x){ 
        for(int i=0;i<x.size();++i){ 
            out<<x.get(i)<<" ";
        }
        return out;
    }
    
    int main(){ 
       Array<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 (Array<int>::iterator i = y.begin();
            i != y.end(); i++)
          cout << *i << " ";
       cout << endl;
       for (Array<int>::iterator i = y.begin();
            i != y.end(); ++i)
          cout << *i << " ";
       cout << endl;
    
       cout << "Ouput using backward iterators pre and post --" << endl;
       for (Array<int>::iterator i = y.end();
            i != y.begin(); cout << *(--i) << " ");
       cout << endl;
       for (Array<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;
    }

### 输出 ###

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