Boost logo

Boost :

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
>>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
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

I did not see anything that looked like an associative vector or a hash
map. I did examine 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, gregod at, cpdaniel at, john at