Re: random access container: reference and resize if necessary
ijs@iitis.gliwice.pl wrote:
You could use a std::map<int, whatever> instead. Its
operator[] will create an element if there is none. Not
enough information to base advise on.
I was thinking of using std::map too, but the access time of a
map is logarithmic while the access time of a vector is
constant. For this reason I want to use only a vector or a
deque.
There's always tr1::unordered_map, or its non-standard
precursers hash_map or hashmap.
The real question, I think, is whether the vector should be
sparce or not. If you have only accessed three elements, and
they are -10000, 1 and 10000000, you almost surely don't want
vector or deque -- std::map or one of the unordered maps would
be preferable. If, on the other hand, the vector is dense ; if
there are only three elements accessed, they will be 1, 2 and 3,
for example, then a vector which automatically grows is an
obvious solution (and is very easy to implement using
std::vector).
BTW: don't get hung up over the logrithmic access times for
std::map. Until the map gets really big, the constant factors
will probably predomindate. std::vector is still considerably
faster, but that's because it has a very low constant factor as
well. My benchmarks show that for anything less than around a
thousand elements, std::map is actually faster than a hash
table, at least when using strings as an index.
--
James Kanze GABI Software
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]