Vectors

As Abstract Data Type

Static vectors operations:

• create (at the fixed size); destroy
• size, isEmpty
• iterate (random access)
• get/set value at index

Dynamic vectors, additional operations:

• insert at position (by index or by iterator)
• remove at position (by index or by iterator)

C++ vector

Below is an approximation of the definition of vector in c++

template<typename T>
class vector {
    vector();
    ~vector();
    vector(vector const& src);
    vector& operator=(vector const& src);
    
    bool empty() const;
    size_t size() const;
    void clear();

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end();
    T& operator[](size_t index);
    T const& operator[](size_t index) const;

    iterator insert(iterator pos, T const& val);
    void erase(iterator pos);
};

Java ArrayList

Main functions in java arrays are:

class ArrayList
{
    ArrayList();
    ArrayList(Collection src);
    Object clone();

    boolean isEmpty();
    int size();
    void clear();
    
    Iterator iterator();
    ListIterator listIterator();
    ListIterator listIterator(int index);
    E get(int index);
    E set(int index, E element);
    
    void add(int index, E element);
}

Some functions are performed directly through iterators

class ListIterator {
    boolean hasNext();
    boolean hasPrevious();
    E next();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E element); // changes the last element returned by next() or previous()
    void add(E element); // adds at current position
    void remove(); // removes the last element returned by next() or previous()
}

Memory management

For dynamic vectors, the actual array of elements is allocated separately from the vector variable. The vector is defined as:

template<typename T>
class vector {
  T* m_data; // pointer to the array
  size_t m_size; // number of actually used elements in the array
  size_t m_allocated; // number of allocated elements in the array
};

template<typename T>
class vector {
  T* m_data; // pointer to the array
  T* m_end_data; // pointer after the last used element
  T* m_end_allocated; // pointer after the last allocated element
};

The constructors, destructor and assignment operators must take care of the actual array of elements.

vector::~vector()
{
	delete[] m_data;
}

vector& vector::vector(vector const& src)
	:m_data(new T[src.size()],
	m_size(src.size()),
	m_allocated(src.size())
{
	for(size_t i=0 ; i<m_size ; ++i) {
		m_data[i] = src[i];
	}
}

Reallocation strategy

When adding an element exceeds the allocated capacity, the data array must be reallocated and the existing elements must be copied.

Question: what should be the new allocated size?

It is tempting to allocate the current size plus a fixed number. However, a better strategy is to allocate the current size times a fixed coefficient. The first strategy requires a number of element copies of O(n²), while the second one requires O(n).

Below we give the cumulated number of element copies after adding n elements to an initially empty vector. Strategy 1 starts with a capacity of 0 and reallocates at a capacity 16 plus the old capacity each time the capacity is exceeded. Strategy 2 starts with a capacity of 1 and doubles the capacity each time it is exceeded.

Iterators

There are several ways to represent an iterator:

• the index only - not quite an iterator, since it does not allow access to an element without the user also having the vector;
• pointer to the current element - use pointer arithmetic for next/previous; simple and fast; downside: reallocating data array leads to invalidating all iterators.
• index plus pointer to the vector - does not get invalidated; however, it is larger and slower.