vector - 효율성과 편의성이 높은 array

벡터의 구현

 

vector는 array인데, size, clear, push_back 등을 지원해주는 효율적이며 편의성이 높은 container이다.

 

1.vector는 array의 기본성질을 유지한다. (maintain the primitive array)

    a pointer variable to the block of allocated memory,

    capacity,

   현재 저장된 item 수

2. deep-copy 제공, operator= 제공

    destructor 제공

3. resize 제공,

    capacity를 바꿔주는 routine을 가진다. (reserve routine~)

4. operator[]

5. size, empty, clear

    back, pop_back, push_back

6. nested type을 지원한다. iterator, const_iterator, begin, end

 

 

/*
< STL - vector >
studied on Jun 23rd, 2019

 */

#include <algorithm>

template <typename Object>
class Vector
{
private:
    int theSize;
    int theCapacity;
    Object * objects;
public:
    explicit Vector(int initSize = 0) : theSize { initSize },
        theCapacity{ initSize + SPARE_CAPACITY }
        { objects = new Object[theCapacity]}
    
    Vector(const Vector & rhs) : theSize{rhs.theSize},
        theCapacity{rhs.theCapacity}, objects{nullptr}
        {
            objects = new Object[theCapacity];
            for (int k=0; k<theSize; ++k)
                objects[k] = rhs.objects[k];
        }
    
    Vector & operator= ( const Vector & rhs )
    {
        Vector copy = rhs;
        std::swap( *this, copy );
        return *this;
    }

    ~Vector()
    { delete[] objects; }

    Vector(Vector && rhs) : theSize{rhs.theSize},
        theCapacity{rhs.theCapacity}, objects{rhs.objects}
    {
        rhs.objects = nullptr;
        rhs.theSize = 0;
        rhs.theCapacity = 0;
    }

    Vector & operator= (Vector && rhs)
    {
        std::swap(theSize, rhs.theSize);
        std::swap(theCapacity, rhs.theCapacity);
        std::swap(objects, rhs.objects);
        return *this;
    }

    void resize(int newSize)
    {
        if (newSize > theCapacity)
            reserve(newSize*2); // It is a optimal way to multiply by 2
        theSize = newSize;
    }

    void reserve(int newCapacity)
    {
        if (newCapacity < theSize) return;

        Object *newArray = new Object[newCapacity];
        for (int k=0; k<theSize; ++k)
            newArray[k] = std::move(objects[k]);
        theCapacity = newCapacity;
        std::swap(objects, newArray);
        delete[] newArray;
    }

    Object & operator[] (int index)
        { return objects[index]; }
    const Object & operator[] (int index) const
        { return objects[index]; }
    
    bool empty() const
        { return size()==0; }
    int size() const
        { return theSize; }
    int capacity() const
        { return theCapacity; }
    
    void push_back(const Object & x)
    {
        if (theSize==theCapacity)
            reserve(2*theCapacity+1);
        objects[theSize++] = std::move(x);
    }
    
    void pop_back()
    {
        --theSize;
    }

    const Object & back () const
    {
        return objects[theSize - 1];
    }

    typedef Object * iterator;
    typedef const Object * const_iterator;

    iterator begin()
        { return &objects[0]; }
    const_iterator begin() const
        { return &objects[0]; }
    
    iterator end()
        { return &objects[size()]; }
    const_iterator end() const
        { return &objects[size()]; }
    
    static const int SPARE_CAPACITY = 16;
}