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

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

"Jason House" <jhouse_at_[hidden]> wrote in message
news:3FCBFDCD.4000808_at_mitre.org...
> 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?

Dave

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