vector的基本实现（c++）

1.描述

vector的基本操作实现（包括迭代器）

 

2.基本操作

 

3.代码

 

#ifndef DS_EXCEPTIONS_H
#define DS_EXCEPTIONS_H

class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };

#endif

 

 

#ifndef VECTOR_H
#define VECTOR_H
#include <cstdio>
#include "dsexceptions.h"

template <typename Object>
class Vector
{
  public:
    explicit Vector( int initSize = 0 )
      : theSize( initSize ), theCapacity( initSize + SPARE_CAPACITY ), currentIndex(0)
      { objects = new Object[ theCapacity ]; }
    Vector( const Vector & rhs ) : objects( NULL )
      { operator=( rhs ); }
    ~Vector( )
      { delete [ ] objects; }

    bool empty( ) const
      { return size( ) == 0; }
    int size( ) const
      { return theSize; }
    int capacity( ) const
      { return theCapacity; }

		//操作符[]重载
    Object & operator[]( int index )
    {
                                                     #ifndef NO_CHECK
        if( index < 0 || index >= size( ) )
            throw ArrayIndexOutOfBoundsException( );
                                                     #endif
        return objects[ index ];
    }
		//const操作符[]重载
    const Object & operator[]( int index ) const
    {
                                                     #ifndef NO_CHECK
        if( index < 0 || index >= size( ) )
            throw ArrayIndexOutOfBoundsException( );
                                                     #endif
        return objects[ index ];
    }
		//操作符=重载，实现对象复制
    const Vector & operator= ( const Vector & rhs )
    {
        if( this != &rhs )
        {
            delete [ ] objects;
            theSize = rhs.size( );
            theCapacity = rhs.theCapacity;

            objects = new Object[ capacity( ) ];
            for( int k = 0; k < size( ); k++ )
                objects[ k ] = rhs.objects[ k ];
        }
        return *this;
    }
		//重新设置vector尺寸（两倍）
    void resize( int newSize )
    {
        if( newSize > theCapacity )
            reserve( newSize * 2 );
        theSize = newSize;
    }
		//设置vector尺寸（修改大小，并拷贝所有元素到新的数组，并销毁原来的数组）
    void reserve( int newCapacity )
    {
        Object *oldArray = objects;
    		//1.重设size,capacity
        int numToCopy = newCapacity < theSize ? newCapacity : theSize;
        //capacity是在size的基础上加一个常数
        newCapacity += SPARE_CAPACITY;
    		//2.建立新的数组，并拷贝元素到新数组
        objects = new Object[ newCapacity ];
        for( int k = 0; k < numToCopy; k++ )
            objects[ k ] = oldArray[ k ];
    
        theSize = numToCopy;
        theCapacity = newCapacity;
    		//删除原来的数组
        delete [ ] oldArray;
    }

      // Stacky stuff
    //放置元素，一旦容量达到最大就重置大小
    void push_back( const Object & x )
    {
        if( theSize == theCapacity )
            reserve( 2 * theCapacity + 1 );
        objects[ theSize++ ] = x;
    }
		//删除最后元素
    void pop_back( )
    {
        if( empty( ) )
            throw UnderflowException( );
        theSize--;
    }
		//最后元素
    const Object & back ( ) const
    {
        if( empty( ) )
            throw UnderflowException( );
        return objects[ theSize - 1 ];
    }
    


		//为了遍历vector中的元素，实现一个iterator迭代器(迭代器其实就是指向数组的指针,并对指针操作进行了封装)
      // Iterator stuff: not bounds checked
    typedef Object * iterator;
    typedef const Object * const_iterator;

    iterator begin( ){
    	currentIndex = 0;
    	return &objects[ currentIndex ]; 
    }
    const_iterator begin( ) const{
    	currentIndex = 0;
    	return &objects[ currentIndex ]; 
    }
    iterator end( ){ 
    	return &objects[size( )]; 
    }
    const_iterator end( ) const{
    	return &objects[size( )]; 
    }
    iterator next(){
    	currentIndex++;
      if( currentIndex < 0 || currentIndex > size( ) )
          throw ArrayIndexOutOfBoundsException( );
    	return &objects[currentIndex];
    }
    //插入操作
    void insert(int position,  const Object & x ){
    	//从这里我们也可以看出，插入操作会导致迭代器失效的原因所在（从新分配了空间，原迭代器变成了悬垂指针）
    	if( theSize == theCapacity )
            reserve( 2 * theCapacity + 1 );
      if(position > theSize || position < 0){
      		throw ArrayIndexOutOfBoundsException( );
      }else{
	      for(int i=theSize-1; i>=position; i--){
	      	objects[i+1] = objects[i];
	      }
	      objects[ position ] = x;
        theSize++;
	    }
    }
    //插入（利用迭代器）
    iterator insert(iterator position, const Object& x ){
    	if( theSize == theCapacity )
            reserve( 2 * theCapacity + 1 );
      if(position<begin() || position>end())
    		throw ArrayIndexOutOfBoundsException( );
    	iterator ite = end();
    	while(ite != position){
    		*ite = *(ite-1);
    		ite--;
    	}
    	*position = x;
    	theSize++;
    	return begin();
    }
    
    //擦除从指定位置起数据
    iterator erase(iterator position){
    	if(position<begin() || position>end())
    		throw ArrayIndexOutOfBoundsException( );
    	while(position != end()){
    		theSize--;
    	}
      return begin();
    }
    //擦除从指定范围内的数据
    iterator erase(iterator first, iterator last){ 
    	if((first < begin() || first>end()) || (last < begin() || last>end()) || first>last)
    		throw ArrayIndexOutOfBoundsException( );
    	if(last == end())	erase(first);
    	//1.先将指定范围内的数据覆盖
    	int i=1;
    	while(first != last+1){
    		*first = *(last+i);
    		first++;
    		theSize--;
    		i++;
    	}
    	//2.将覆盖所用数据剩余部分前移（如1,2,3,4,5,6要删除2,3先用4,5覆盖2,3-->1,4,5,4,5,6-->然后6前移到4的位置-->1,4,5,6）
    	i--;
    	while(last <= end()){
    		last++;
    		*last = *(last+i);
    	}
      return begin();
    }

    bool isEnd(){
    	if(currentIndex < 0 || currentIndex >= size( ))
    		return true;
    	return false;
    }
    //操作符++重载(前增量，++a)，注还有后增量的重载差不多，只是Object & operator++(int a)有参数
    Object & operator++()
    {                                         
    		currentIndex++;
        if( currentIndex < 0 || currentIndex > size( ) )
            throw ArrayIndexOutOfBoundsException( );
        return objects[ currentIndex ];
    }
	
    //操作符--重载
    Object & operator--()
    {                                         
    		currentIndex--;
        if( currentIndex < 0 || currentIndex > size( ) )
            throw ArrayIndexOutOfBoundsException( );
        return objects[ currentIndex ];
    }

    enum { SPARE_CAPACITY = 16 };

  private:
    int theSize;
    int theCapacity;
    int currentIndex;//仅用于iterator
    Object * objects;
};

#endif

 

 

#include "vector.h"
#include <iostream>
using namespace std;

int main( )
{
    Vector<int> v;
    

    for( int i = 0; i < 10; i++ )
        v.push_back( i );

    for( int i = 0; i < 10; i++ )
        cout << v[ i ] << " ";
    
  //利用操作符--输出
   Vector<int>::iterator t = v.end()-1;//注意end()返回的是最后元素之后的位置
  	cout<<endl;
  	for(; t >= v.begin(); t--){
  		cout<< *t <<" ";
  	}  

    cout<<endl;
    Vector<int>::iterator k = v.begin();
    while(!v.isEnd()){
    	cout<< *k <<" ";
    	k = v.next();
    }
 
		Vector<int>::iterator m = v.begin()+6;
		//m = v.erase(m);//正确用法
		v.erase(m);	//这样是错误的，会使当前迭代器m失效，必须返回新的迭代器，像上面那样用
    cout<<"\nerase:"<<*m<<endl;
    
  	for(m=v.begin(); m != v.end(); ){
  		cout<< *m <<" ";
  		m = v.next();
  	}


		Vector<int>::iterator mm = v.begin()+2;
		mm = v.insert(mm, 5);
  	cout<<endl;
  	for(; mm != v.end(); ++mm){
  		cout<< *mm <<" ";
  	}
  	

    return 0;
}

 

 

4.从上面的迭代器实现，可以看出，为了方便指针操作，使用了迭代器封装指针操作，这样使得指针操作变得简单

明白两点：a.迭代器的原理，从上面代码可以看出，就是指针操作

b.迭代器自增原理，当size=capacity的时候，长度会增长一倍

c.size和capacity的区别？为什么用capacity？（使用capacity是为了避免空间浪费，譬如size=20，capacity=30,如果没有capacity

那么大小为21的数据就会使用41个空间的长度（当插入最后一个元素的时候从新分配空间），而有了capacity就不用重新分配）