パクリSTL実現のvector

まずはvectorの定義

        template <typename T>
        class vector
        {
        };

まずvectorの別名を見てみましょう

        public:
            typedef T         value_type;
            typedef T*        pointer;
            typedef T&        reference;
            typedef const T&  const_reference;
            typedef size_t    size_type;
            typedef ptrdiff_t difference_type;
            typedef const T* const_iterator;
            typedef reverse_iterator<const_iterator, value_type, size_type, difference_type> const_reverse_iterator;
            typedef T* iterator;
            typedef reverse_iterator<iterator, value_type, size_type, difference_type> reverse_iterator;

以上から,下一篇で述べたようにvectorの反復器は原生のポインタによって実現される.次に、内部のメンバー変数を示します.

        protected:
            typedef vector<T>    self;
            typedef allocator<T> Alloc;

            iterator start;
            iterator finish;
            iterator end_of_element;

start:vectorへの開始アドレスfinish:最後の要素の後の要素へのアドレスend_of_element:申請メモリブロックの終了位置(finishは常にend_of_element以下)を指し、STLでbeginからendまで常に前閉後開の形で表され、[begin,end]のようにコードをより簡潔に書くことができる利点がある.

    template <typename Iterator, typename T>
    Iterator find(Iterator first, Iterator last, const T& value)
    {
        while(first != last && *first != value) ++first;
        return first;
    }

次にvectorで最も基本的な構造関数と構造関数を見てみましょう

            vector() : start(0), finish(0), end_of_element(0)
            {
            }

            ~vector()
            {
                destruct(start, end_of_element);
                if (start != 0) Alloc::deallocate(start, end_of_element - start);
            }

ここでは、3つのメンバー変数を0に入力します.下一篇で述べたように、STLではメモリ割り当てがオブジェクト初期化から分離され、同様にオブジェクトプロファイルとメモリ解放も分離される.次に、最初の要素と最後の要素の後の要素の反復器を取得するためのbeginメソッドとendメソッドです.

            inline iterator begin()
            {
                return start;
            }

            inline const_iterator begin()const
            {
                return start;
            }

            inline iterator end()
            {
                return finish;
            }

            inline const_iterator end()const
            {
                return finish;
            }

frontとbackはそれぞれ最初の要素と最後の要素を取得するために使用されます

            inline reference front()
            {
                return *begin();
            }

            inline const_reference front()const
            {
                return *begin();
            }

            inline reference back()
            {
                return *(end() - 1);
            }

            inline const_reference back()const
            {
                return *(end() - 1);
            }

Empty,size,capacityはそれぞれ容器が空であるか否か,容器内の元素の個数,容器の大きさを判別するために用いられる.

            inline bool empty()const
            {
                return begin() == end();
            }

            inline const size_type size()const
            {
                return size_type(end() - begin());
            }

            inline const size_type capacity()const
            {
                return size_type(end_of_element - begin());
            }

vectorのヘッダにエレメントを挿入すると、すべてのエレメントが後方に移動するため、テールからのみデータを挿入または削除できるように設計されています.

            void push_back(const T& x)
            {
                if (end_of_element != finish)
                {
                    construct(&*finish, x);
                    ++finish;
                }
                else
                {
                    insert_aux(end(), x);
                }
            }

            inline void pop_back()
            {
                --finish;
                destruct<T>(finish, has_destruct(*finish));
            }

もちろんヘッダからデータを除去することもできないわけではありませんが、eraseメソッドを使用してヘッダのデータを除去することもできます.eraseメソッドは後述します.まずinsert_を見てみましょうauxという方法は,要素を挿入する際にほとんどこの方法を用いた.

            void insert_aux(const iterator position, const T& x)
            {
                if(finish != end_of_element)
                {
                    construct(&*finish, *(finish - 1));
                    T x_copy = x;
                    copy_backward(position, finish - 1, finish);
                    *position = x_copy;
                    ++finish;
                }
                else
                {
                    const size_type old_size = size();
                    const size_type new_size = old_size == 0 ? 2 : old_size * 2;
                    iterator tmp = Alloc::allocate(new_size);
                    uninitialized_copy(begin(), position, tmp);
                    iterator new_position = tmp + (position - begin());
                    construct(&*new_position, x);
                    uninitialized_copy(position, end(), new_position + 1);
                    destruct(begin(), end());
                    Alloc::deallocate(begin(), old_size);
                    end_of_element = tmp + new_size;
                    finish = tmp + old_size + 1;
                    start = tmp;
                }
            }

コンテナに十分なスペースがある場合は、まずposition位置からfinish位置までの要素全体を1つ後ろに移動し、最後に挿入する要素を元のpositionの位置に書き込むと同時にfinishポインタの値を変更します.スペースが不足している場合は、まず元のスペースの大きさの倍に応じてメモリを申請し、元の位置のbeginからpositionまで要素を新しい申請のメモリにコピーし、次に新しい申請のメモリの指定位置に挿入する要素値を挿入し、最後に残りの部分もコピーします.その後、既存の要素を分析してメモリを解放します.なぜreallocateを使用しないのですか?reallocateの本意は、元のメモリの位置でメモリを増やしたり減らしたりすることではありません.reallocateは、まず元のメモリの位置でメモリを増やしたり減らしたりしようとします.失敗すると、新しいメモリを再申請したり、元のデータをコピーしたりします.この操作の本質は、reallocateではなく、メモリを再申請することです.次にinsertとeraseの方法を見てみましょう

            inline iterator insert(iterator position, const T& x)
            {
                const size_type pos = position - begin();
                if(finish != end_of_element && position == end())
                {
                    construct(&*finish, x);
                    ++finish;
                }
                else insert_aux(position, x);
                return begin() + pos;
            }

            iterator erase(iterator position)
            {
                destruct(position, has_destruct(*position));
                if (position + 1 != end())
                {
                    copy(position + 1, end(), position);
                }
                --finish;
                return position;
            }

最後にエレメントを挿入し、コンテナの残りのスペースが十分であれば、エレメントをfinishの位置に直接挿入し、finishポインタを1つ後ろに移動すればいいです.コンテナスペースが足りないか、最後の場所に挿入されていない場合はinsert_を呼び出します.auxはメモリを再割り当てまたは挿入します.削除時にまず元の要素を解析し、削除された要素が最後の要素でない場合は、後ろのすべての要素をコピーし、finishポインタを前に移動します.最後に、リロードされた演算子を見てみましょう.

            self& operator=(const self& x)
            {
                if(&x == this) return *this;
                size_type const other_size = x.size();
                if(other_size > capacity())
                {
                    destruct(start, finish);
                    Alloc::deallocate(start, capacity());
                    start = Alloc::allocate(other_size);
                    finish = uninitialized_copy(x.begin(), x.end(), start);
                    end_of_element = start + other_size;
                }
                else
                {
                    finish = uninitialized_copy(x.begin(), x.end(), start);
                }
                return *this;
            }

            inline reference operator[](size_type n)
            {
                return *(begin() + n);
            }

            inline value_type at(size_type n)
            {
                return *(begin() + n);
            }

vector内部ではオリジナルのポインタが使用されているため、これらの演算子の使用方法はオリジナルのポインタと変わらない.割り当て操作を行うと、メモリの再割り当てとコピー操作が発生することに注意してください.これでvectorの説明は完了しました.完全なコードはhttp://qlanguage.codeplex.comにダウンロードしてください.