C++STL vector 의 시 뮬 레이 션 실현

15286 단어 C++STLvector
1.vector 의 소개 와 사용
  • vector 는 가 변 크기 배열 을 나타 내 는 시퀀스 용기 입 니 다
  • 4.567917.배열 처럼 vector 도 연속 저장 공간 으로 요 소 를 저장 합 니 다.즉,아래 표 시 를 통 해 vector 의 요 소 를 방문 할 수 있 고 배열 과 마찬가지 로 효율 적 이라는 것 을 의미한다.그러나 배열 과 달리 크기 는 동적 으로 바 뀔 수 있 고 크기 는 용기 에 의 해 자동 으로 처 리 됩 니 다4.567917.본질 적 으로 vector 는 동적 분배 배열 을 사용 하여 요 소 를 저장 합 니 다.새 요소 가 삽입 되 었 을 때 이 배열 은 저장 공간 을 늘 리 기 위해 크기 를 재배 치 해 야 합 니 다.새로운 배열 을 할당 한 다음 모든 요 소 를 이 배열 로 옮 기 는 것 이다.시간 적 으로 이것 은 상대 적 으로 대가 가 높 은 작업 입 니 다.새로운 요소 가 용기 에 들 어 갈 때마다 vector 는 매번 크기 를 재분배 하지 않 기 때 문 입 니 다4.567917.vector 분배 공간 전략:vector 는 가능 한 성장 에 적응 하기 위해 추가 공간 을 분배 합 니 다.저장 공간 이 실제 필요 한 저장 공간 보다 더 크기 때 문 입 니 다.서로 다른 라 이브 러 리 는 서로 다른 전략 으로 공간의 사용 과 재 분 배 를 저울질 한다.그러나 어쨌든 재 분 배 는 대수 적 으로 증가 하 는 간격 크기 로 말미 에 하나의 요 소 를 삽입 할 때 상수 시간의 복잡 도 에서 이 루어 져 야 한다4.567917.따라서 vector 는 더 많은 저장 공간 을 차지 하고 저장 공간 을 관리 하 는 능력 을 얻 기 위해 효과 적 인 방식 으로 동태 적 으로 성장 했다
  • 다른 동적 시퀀스 용기 에 비해(deques,lists and forwardlists),vector 는 요 소 를 방문 할 때 더욱 효율 적 이 고 끝 에 요 소 를 추가 하고 삭제 하 는 것 이 상대 적 으로 효율 적 입 니 다.마지막 에 없 는 다른 삭제 와 삽입 작업 에 대해 서 는 효율 이 더 낮 습 니 다.lists 와 forward 보다lists 통 일 된 교체 기와 인용 이 더 좋 습 니 다
  • 더 자세 한 것 은vector 문서 소개
    2.vector 의 시 뮬 레이 션 실현
    vector 의 내장 형 정의
    
    typedef _Ty         value_type;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t      size_type;
    
    vector 의 구성원 변수
    
    private:
            iterator _start;
            iterator _last;
            iterator _end;
    2.1 vector 구조 함수 와 복사 구조 함수
    
    vector():_start(nullptr),_last(nullptr),_end(nullptr)
    {}
    vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
    {
         insert(n,value);
    }
    vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
    {
         insert(f,l);
    }   
    vector(const vector<int>& iv)
    {
            reserve(iv.capacity());
            iterator it = begin();
            iterator vit = iv.end();
            while (vit != iv.begin())
            {
                  *it++ = *vit--;     
            }
    }
    2.2 insert 함수 와 eraser 함수
    
    iterator insert(iterator pos,const _Ty& value)
    {
        //1. size()==capacity() ,  vector  ,            
        if(size()== capacity())
        {
            size_type oldpos = pos - begin();
            //          : vector     ,  capacity 0,          2      ,
            //  2*0 = 0,          
            size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
    
            reserve(newcapacity);
    
            //         ,pos      ,       pos    
            //reserve   vector       
            pos = begin() + oldpos;
        }
        //2. size() < capacity() ,  vector  ,     pos       
        //          pos         ,          ,
        // pos               ,        ,           
        iterator tail = _last;
        while(tail > pos)
        {
            *tail = *(tail-1);
            --tail;
        }
        //            ,     pos      ,  pos           ,
        //  pos             ,         ,            
        *pos = value;
    
        //     ,    _last  +1,             
        ++_last;
    
        return pos;
    }
    
    void insert(size_type n,const _Ty& value)
    {
        for(int i = 0;i < n; ++i)
        {
            insert(end(),value);
        }
    }
    void insert(iterator f,iterator l)
    {
        while(f!=l)
        {
            insert(end(),*f);
            ++f;
        }
    }
    
    
    iterator erase(iterator pos)
    {
        assert(pos >= _start || pos < _last);
        //1.  pos     ,   [pos,end()]            
        iterator it = pos + 1;
        while(it != _last)
        {
            *(it-1) = *(it);
            ++it;
        }
    
        --_last;
        return pos;
    }
    2.3 reserve 함수 와 resize 함수
    
    void reserve(size_type n)
    {
        //  n     vector   ,     
        //  n       ,        
        if(n > capacity())
        {
            //1.       
            size_type oldSize = size();
            _Ty* newVector = new _Ty[n];
            //2.             
            if(_start)
            {
                //  :      memcpy,  memcpy      。
                //memcpy(newVector,_start,sizeof(_Ty)*size());
                for(size_type i = 0; i < oldSize; ++i)
                {
                    newVector[i] = _start[i];
                }
            }
            //3.         
            //               ,    reserve()              
            _start = newVector;
            _last = _start + oldSize;
            _end = _start + n;
        }
    }
    
    void resize(size_type n,const _Ty& value = _Ty())
    {
        //1.  n      size()   ,     _last         
        if(n <= size())
        {
            _last = _start + n;
            return;
        }
        //2.  n    capacity()   ,    reserve()  ,        
        if(n > capacity())
        {
            reserve(n);
        }
        //  n    size()   capacity()   ,   _last        
    
        iterator it = _last;
        _last = _start + n;
    
        while(it != _last)
        {
            *it = value;
            ++it;
        }
        //resize()                
    }
    2.4 push_back 함수 와 popback 함수
    
    void push_back(const _Ty& value)
    {
        insert(end(),value);
    }
    void pop_back()
    {
        erase(end()-1);
    }
    
    2.5 begin 함수 와 end 함수
    
    iterator begin()const
    {
        return _start;
    }
    iterator end() const
    {
        return _last;
    }
     
    
    2.6 size 함수,capacity 함수
    
    size_type size()
    {
        return end()-begin();
    }
    size_type capacity()const
    {
        return _end-begin();
    }
     
    
    2.7 empty 함수 와 operator[]재 부팅
    
    bool empty()const
    {
        return end() == begin();
    }
    
    reference operator[](size_type n)
    {
        return *(begin() + n);
    }
     
    
    
    2.8 전체 코드 와 해당 하 는 테스트
    
    #include <iostream>
    #include <assert.h>
    
    using namespace std;
    
    
    namespace mytest{
        template<class _Ty>
        class vector
        {
            public:
                typedef _Ty         value_type;
                typedef value_type* iterator;
                typedef value_type& reference;
                typedef size_t      size_type;
            public:
                iterator begin()const
                {
                    return _start;
                }
                iterator end() const
                {
                    return _last;
                }
                size_type size()
                {
                    return end()-begin();
                }
                size_type capacity()const
                {
                    return _end-begin();
                }
                bool empty()const
                {
                    return end() == begin();
                }
                reference operator[](size_type n)
                {
                   return *(begin() + n); 
                }
    
            public:
                vector():_start(nullptr),_last(nullptr),_end(nullptr)
                {}
                vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
                {
                    insert(n,value);
                }
                vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
                {
                    insert(f,l);
                }   
                vector(const vector<int>& iv)
                {
                    reserve(iv.capacity());
                    iterator it = begin();
                    iterator vit = iv.end();
                    while (vit != iv.begin())
                    {
                        *it++ = *vit--;     
                    }
                }
            public:
                void reserve(size_type n)
                {
                    //  n     vector   ,     
                    //  n       ,        
                    if(n > capacity())
                    {
                        //1.       
                        size_type oldSize = size();
                        _Ty* newVector = new _Ty[n];
                        //2.             
                        if(_start)
                        {
                            //  :      memcpy,  memcpy      。
                            //memcpy(newVector,_start,sizeof(_Ty)*size());
                            for(size_type i = 0; i < oldSize; ++i)
                            {
                                newVector[i] = _start[i];
                            }
                        }
                        //3.         
                        //               ,    reserve()              
                        _start = newVector;
                        _last = _start + oldSize;
                        _end = _start + n;
                    }
                }
    
                void resize(size_type n,const _Ty& value = _Ty())
                {
                    //1.  n      size()   ,     _last         
                    if(n <= size())
                    {
                        _last = _start + n;
                        return;
                    }
                    //2.  n    capacity()   ,    reserve()  ,        
                    if(n > capacity())
                    {
                        reserve(n);
                    }
                    //  n    size()   capacity()   ,   _last        
                    
                    iterator it = _last;
                    _last = _start + n;
    
                    while(it != _last)
                    {
                        *it = value;
                        ++it;
                    }
                    //resize()                
                }
    
                void push_back(const _Ty& value)
                {
                    insert(end(),value);
                }
                void pop_back()
                {
                    erase(end()-1);
                }
    
                
    
                iterator insert(iterator pos,const _Ty& value)
                {
                    //1. size()==capacity() ,  vector  ,            
                    if(size()== capacity())
                    {
                        size_type oldpos = pos - begin();
                        //          : vector     ,  capacity 0,
                        //          2      ,  2*0 = 0,          
                        size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
    
                        reserve(newcapacity);
    
                        //         ,pos      ,       pos    
                        //reserve   vector       
                        pos = begin() + oldpos;
                    }
                    //2. size() < capacity() ,  vector  ,     pos       
                    //          pos         ,          ,
                    // pos               ,        ,           
                    iterator tail = _last;
                    while(tail > pos)
                    {
                        *tail = *(tail-1);
                        --tail;
                    }
                    //            ,     pos      ,  pos           ,
                    //  pos             ,         ,            
                   *pos = value;
    
                   //     ,    _last  +1,             
                   ++_last;
    
                   return pos;
                }
    
                void insert(size_type n,const _Ty& value)
                {
                    for(int i = 0;i < n; ++i)
                    {
                        insert(end(),value);
                    }
                }
                void insert(iterator f,iterator l)
                {
                    while(f!=l)
                    {
                        insert(end(),*f);
                        ++f;
                    }
                }
    
    
                iterator erase(iterator pos)
                {
                    assert(pos >= _start || pos < _last);
                    //1.  pos     ,   [pos,end()]            
                    iterator it = pos + 1;
                    while(it != _last)
                    {
                        *(it-1) = *(it);
                        ++it;
                    }
    
                    --_last;
                    return pos;
    
                }
    
     
    
                
    
            private:
                iterator _start;
                iterator _last;
                iterator _end;
        };
    
    };
    
    void Test1()
    {
        mytest::vector<int> iv;
    
        cout << "iv.size() = " << iv.size() << endl;
        cout << "iv.capacity() = " << iv.capacity() << endl;
        iv.push_back(1);
        iv.push_back(2);
        iv.push_back(3);
        iv.push_back(4);
        cout << "iv.size() = " << iv.size() << endl;
        cout << "iv.capacity() = " << iv.capacity() << endl;
    
        mytest::vector<int>::iterator it = iv.begin();
    
        while(it != iv.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        iv.pop_back();
        iv.pop_back();
        it = iv.begin();
        while(it != iv.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    
    
    }
    
    void Test2()
    {
        mytest::vector<int> iv(10,2); 
        mytest::vector<int>::iterator it = iv.begin();
        while(it != iv.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    
    void Test3()
    {
        int ar[] = {1,2,3,3,4,5};
        mytest::vector<int> iv(ar,ar+6);
        mytest::vector<int>::iterator it = iv.begin();
        while(it != iv.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    
    }
    int main()
    {
    //    Test1();
    //    Test2();
        Test3();
        return 0;
    }
    
    
    C++STL vector 의 모 의 실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++STL vector 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!

    좋은 웹페이지 즐겨찾기