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
> std::vector<foo> v
I assume in this case that you expect the map key to act like the
> v can be superior to m in some cases, which I try to describe
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
> 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 (http://www.grisoft.com). Version: 6.0.544 / Virus Database: 338 - Release Date: 11/25/2003
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk