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
> 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
>> 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
>> 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 ;)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk