[boost] Re: combining maps and vectors - creating interchangeableversions?

From: Jason House (jhouse_at_[hidden])
Date: 2003-12-02 09:28:38

David B. Held wrote:

> "Jason House" <jhouse_at_[hidden]> wrote in message
> news:3FCBFDCD.4000808_at_mitre.org...
> 
> Just like an associative vector can be superior to a map.  But
> that's not what you're talking about.  You're talking about a sparse
> vector, I think.

I think that you're right, but what is an associative vector and where 
would I find one?  You also mention a hash map below and I'd also be 
interested in where to find that one too.

>>[...]
>>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)
> 
> 
> Since X is a constant that is always larger than N in a way that
> doesn't depend on N, I'm pretty sure that the vector complexity
> is O(1) (though the average computational cost is proportional
> to X/N).

In my scenario X is a run-time input (such as the number of nodes in a 
network to simulate).  Even if it wasn't run-time input, the code would 
then have to get recompiled all the time since the value changes for 
each use of the program.  The X/N is mostly due to the sparse nature. 
Multiple increments of an iterator are required in order to find the 
next element.

> 
> 
>>  O(1)         O(X/N)     Memory Consumption        (per element)
> 
> 
> The amortized memory consumption for the vector is proportional
> to X/N, but the space cost for each is really O(1).

The idea is that a sparse vector is less memory efficient.  I can 
imagine practical usage of some structures where X = O(N^3).

> Have you considered a hash map?

I didn't even know such a thing existed.

I made sure to check http://www.boost.org/libs/libraries.htm#Containers 
before my post, but did not see anything that would fit the bill. 
(property map prompted investigation but has a completely different purpose)

I have now also taken a look at http://groups.yahoo.com/group/boost/files/

I did not see anything that looked like an associative vector or a hash 
map.  I did examine tree.zip and indexed_set, but both appear to offer 
O(log(N)) random access. Of course, I've been known to be blind before ;)