Optimal Time and Space Vector

From: Thomas Holenstein (tholenst_at_[hidden])
Date: 2000-05-04 04:41:36

Hello,

I've written an alternative implementation of the std::vector class.  
It provides all fundamental operations (push_back, pop_back,
operator[]) in _worst_case_ O(1).  Furthermore, the wasted space is
always O(sqrt(n)), which can be shown to be optimal.

The implementation is from the paper 'Resizable Arrays in Optimal Time
and Space', see http://daisy.uwaterloo.ca/~eddemain/papers/WADS99a/

It is designed to work instead of vector.  So if your code has an
vector<int>, it should also work with an optvect<int>, but need less
memory.

Anyhow, because the class does not allocate storage in one piece,
i.e. &(v[0]) + n != &(v[n]), the class is not conformant to the
standard.

Below, I summarize the advantages and disadvantages of optvect:

 + Worst Case O(1) push_back, pop_back, operator[]
 + Always O(sqrt(n)) wasted space
 + Elements are not copied in memory if you don't move it

 - Element access is slower
 - Elements are not stored in one chunk

I submitted the class into the vault, folder optvect, after all, it
has already > 1000 lines.  I hope some of take a look at it.

There is also a TODO list, for it to become a real substitute for 
vector:

  - Make it faster
  - remove bugs
  - Writing optvect<bool> specialisation
  - Writing optvect<T*> specialisation
  - Make integer log2 faster (this is needed for operator[])
  - maybe implement methods for optvect and vector work together
  - currently, (--(optvect.begin())) > optvect.begin().  While 
    this is standard conformant, its not great.

I hope for much discussion and please take a look at the vault.

Thomas