
//
// To jest przykładowy kod z podrozdziału 20.8 „Dostosowanie wektora do biblioteki STL” książki
// "Programowanie. Teoria i praktyka z wykorzystaniem C++" Bjarne'a Stroustrupa.
//

//------------------------------------------------------------------------------

template<class T> class allocator {
public:
    // ...
    T* allocate(int n);            // Alokacja przestrzeni dla n obiektów typu T.
    void deallocate(T* p, int n);  // Dealokacja n obiektów typu T, zaczynając od p.

    void construct(T* p, const T& v); // Tworzy obiekt typu T z wartością v w p.
    void destroy(T* p);            // Usuwa ten obiekt T z p.
};

//------------------------------------------------------------------------------

template<class T, class A = allocator<T> > class vector {
    int sz;     // rozmiar
    T*  elem;   // wskaźnik na elementy
    int space;  // liczba elementów plus liczba wolnych miejsc w pamięci
    A   alloc;  // obsługa pamięci dla elementów za pomocą alloc
public:
    typedef unsigned long size_type;
    typedef T             value_type;
    typedef T*            iterator;    // Elem* jest najprostszym możliwym iteratorem.
    typedef const T*      const_iterator;

    iterator       begin();
    const_iterator begin() const;
    iterator       end();
    const_iterator end() const;

    size_type size();
    int capacity() const { return space; }

    // ... cała reszta z rozdziału 19 i podrozdziału 20.5 ...

    T&       back();
    iterator insert(iterator p, const T& val);
    iterator erase(iterator p);    
};

//------------------------------------------------------------------------------

template<class T, class A> 
typename vector<T,A>::iterator vector<T,A>::erase(iterator p)
{
    if (p==end()) return p;
    for (iterator pos = p+1; pos!=end(); ++pos)
        *(pos-1) = *pos; // Kopiuje element o „jedną pozycję w lewo”.
    alloc.destroy(&*p);  // Usuwa nadmiarową kopię ostatniego elementu.
    --sz;
    return p;
}

//------------------------------------------------------------------------------

template<class T, class A>
typename vector<T,A>::iterator vector<T,A>::insert(iterator p, const T& val)
{
    int index = p-begin();
    if (size()==capacity()) reserve(2*size());    // Zapewniamy miejsce.

    // Skopiowanie najpierw elementu w niezainicjowaną przestrzeń:
    alloc.construct(elem+sz,*back());
    ++sz;
    iterator pp = begin()+index; // Miejsce, w którym zostanie wstawiona wartość val.
    for (iterator pos = end()-1; pos!=pp; --pos)
        *pos = *(pos-1);         // Kopiuje elementy o jedno miejsce w prawo.
    *(begin()+index) = val;      // „wstawia” val
    return pp;
}

//------------------------------------------------------------------------------
