Amortized Analysis: The Optimal Dynamic Array

Amortized Analysis

When dealing with dynamic array data type, we are interested in the average time cost on each element for a dynamic array of size .

Potential Method

For a data structure , we use to map it into a numerical quantity . Then the amortized cost for the manipulation is Intuitively, it manifests that the amortized cost is the addition of actual cost and the potential variation. Sum the two sizes up we obtain If one can guarantee that , then

The Contraction and Expansion of Dynamic Array

The upperbound for expansion of an array is pretty easy to find. Assume that we undergo continuous times of array pushback, then then the average cost is . Consider the contraction of array, we then apply the potential method. Define as This guarantees that . Popping out an element, if and no contraction occurs, then If contraction occurs, then Likewise, when , no contraction occurs. When and when Hence, we conclude that both the contraction and expansion manipulation for dynamic array has linear time consumption.

The Basic Manipulations Implemented with Build-in Type

#include <memory>
using namespace std;

template<class T>
class dynamicArray{ // STL vector datatype using build-in type
    T *begin;
    T *end;
    T *ptr;
    int size;
    allocator<T> alloc;

public:
    dynamicArray() { initialize(); }
    T *getBegin() { return begin; }
    T *getEnd() { return end; }
    int getSize() { return size; }
    T *getPtr() { return ptr; }
    void changeSize(int n) { size = n; }
    T& operator[](int);
    inline bool checkUpper();
    inline bool checkLower();
    void arrayExtend();
    void arrayContract();
    void push_back(T);
    void pop_back();
    void initialize();
};

template<class T>
inline bool dynamicArray<T>::checkUpper(){
    double loadedFactor = (double)(ptr - begin + 1) / (double)size;
    return (loadedFactor >= 1.00);
}

template<class T>
inline bool dynamicArray<T>::checkLower(){
    double loadedFactor = (double)(ptr - begin + 1) / (double)size;
    return (loadedFactor <= 0.25);
}

template<class T>
void dynamicArray<T>::initialize(){
    begin = alloc.allocate(1);
    size = 1;
    end = begin + size - 1;
    ptr = begin;
}

template<class T>
void dynamicArray<T>::arrayExtend(){
    if (this->checkUpper()){
        auto originalSize = size;
        size *= 2;
        auto tempPt = alloc.allocate(size);
        auto originalIndex = ptr - begin;
        uninitialized_copy_n(begin, originalSize, tempPt);
        for (int i = 0; i < originalSize; i++){
            alloc.destroy(begin + i);
        }
        alloc.deallocate(begin, originalSize);
        begin = tempPt;
        ptr = begin + originalIndex;
        end = begin + size - 1;
    }
    return;
}

template<class T>
void dynamicArray<T>::arrayContract(){
    if (this->checkLower()){
        auto originalSize = ptr - begin + 1;
        size /= 2;
        auto tempPt = alloc.allocate(size);
        auto originalIndex = ptr - begin;
        uninitialized_copy_n(begin, originalSize, tempPt);
        for (int i = 0; i < originalSize; i++){
            alloc.destroy(begin + i);
        }
        alloc.deallocate(begin, originalSize);
        begin = tempPt;
        ptr = begin + originalIndex;
        end = begin + size - 1; 
    }
    return;
}

template<class T>
T& dynamicArray<T>::operator[](int index){
    return *((*this).begin + index);
}

template<class T>
void dynamicArray<T>::push_back(T element){
    if (size == 1){
        *begin = element;
        arrayExtend();
    }
    else{
        ptr++;
        arrayExtend();
        *ptr = element;
        return;
    }
}

template<class T>
void dynamicArray<T>::pop_back(){
    alloc.destroy(this->ptr);
    ptr--;
    arrayContract();
    return;
}