From: Jason House (jhouse_at_[hidden])
Date: 2003-12-01 21:49:49
I'm trying to see if such a thing exists already or if there is a need
to code one...
Consider the differences between
v can be superior to m in some cases, which I try to describe below. In
order to get v to act like m, some kind of default value for a
non-existent element must be used. When switching between the two
forms, use of at least m.count, v.size, and v.resize must be recoded.
Accessors might also need to get modified slightly (such as m[i] verse
v[i - min_i])
The performance can vary depending on which one you use
(table assumes N useful elements over a numerical range of width X)
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)
O(1) O(X/N) Memory Consumption (per element)
The decision for which to use can be influenced by either the type of
element access, the ration of X/N, and/or memory consumption. Knowing
the usage at the beginning and making a design decision at the start of
coding can make the use of either form rather trivial, but a decision to
switch later can be quite non-trivial.
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. For
instance, sequential element access for the vector based alternative
could be sped up to O(1) if insertions/deletions are made O(X/N).
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. Memory consumption could also
force the use of a map, even if random element access dominates.
I am uneasy about any design decision I make because I may become
unable to switch down the road. I am imagining some kind of library
that is a sort of merger of the two data structures that can perform
either compile-time (or maybe run-time) switching of what underlying
methods it uses. I am assuming that compile-time solution would yield
faster runtimes as well as greater capability (if done correctly).
I have a couple of questions:
Does anything like this exist already?
Are there any design suggestions or extensions of the concept?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk