Boost logo

Boost :

From: David B. Held (dheld_at_[hidden])
Date: 2003-12-01 22:36:54

"Jason House" <jhouse_at_[hidden]> wrote in message
> 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

I assume in this case that you expect the map key to act like the
vector index?

> v can be superior to m in some cases, which I try to describe
> below.

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.

> [...]
> 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).

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

> [...]
> 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.

Oh, I'm certain that you could create a policy-based sparse
vector. In fact, I've been toying with the idea of creating a
universal policy-based map that can front for both a tree
implementation and an associative vector implementation (or
any other implementation that provides a suitable interface,
such as a hash table, perhaps?). But that requires time that I
don't have at the moment.

> [...]
> 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.
> [...]

Have you considered a hash map?


Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (
Version: 6.0.544 / Virus Database: 338 - Release Date: 11/25/2003

Boost list run by bdawes at, gregod at, cpdaniel at, john at