[boost] combining maps and vectors - creating interchangeable versions?

From: Jason House (jhouse_at_[hidden])
Date: 2003-12-01 21:49:49

I'm trying to see if such a thing exists already or if there is a need 
to code one...

Consider the differences between
   std::map<int,foo> m
and
   std::vector<foo>  v

v can be superior to m in some cases, which I try to describe below. In 
order to get v to act like m, some kind of default value for a 
non-existent element must be used.  When switching between the two 
forms, use of at least m.count, v.size, and v.resize must be recoded. 
Accessors might also need to get modified slightly (such as m[i] verse 
v[i - min_i])

The performance can vary depending on which one you use
(table assumes N useful elements over a numerical range of width X)

map         vector
  O(log(N))    O(1)       Random Element Access
  O(log(N))    O(1)       Insertions/Deletions (0<=key<X)
  O(1)         O(X/N)     Sequential Element Access (per element)
  O(1)         O(X/N)     Memory Consumption        (per element)

   The decision for which to use can be influenced by either the type of 
element access, the ration of X/N, and/or memory consumption.  Knowing 
the usage at the beginning and making a design decision at the start of 
coding can make the use of either form rather trivial, but a decision to 
switch later can be quite non-trivial.
   My initial idea of what I want would have only 2 data structures, but 
allow the same code to operate on either.  I imagine that it might be 
interesting to see if a set of policies could be created or not.  For 
instance, sequential element access for the vector based alternative 
could be sped up to O(1) if insertions/deletions are made O(X/N).
   My current work keeps having me come back to this issue and I do not 
know which is better to use since the dominance of random or sequential 
access can change based on program input.  Memory consumption could also 
force the use of a map, even if random element access dominates.
   I am uneasy about any design decision I make because I may become 
unable to switch down the road.  I am imagining some kind of library 
that is a sort of merger of the two data structures that can perform 
either compile-time (or maybe run-time) switching of what underlying 
methods it uses.  I am assuming that compile-time solution would yield 
faster runtimes as well as greater capability (if done correctly).

I have a couple of questions:

Does anything like this exist already?
Are there any design suggestions or extensions of the concept?