
Boost : 
From: Jason House (jhouse_at_[hidden])
Date: 20031202 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 runtime input (such as the number of nodes in a
network to simulate). Even if it wasn't runtime 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 ;)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk