which will be more efficient Stdlib MAP or Array /w sequential search for may be 50-1000 times?

[g35rider]

Hi was contemplating the use of either MAP or Hashtable for keeping a
cache of objects with name as the key to object. I would be searching
the MAP/Array/Hashtable often now for such a small number, which would
be quicker and how exactly does MAP search?

Thanks
Ankur

 

[g35rider]

To be clearer, the data size could be anywhere from 50-1000 objects and
access could be around 1-10 times a sec.

Thanks
Ankur

 

[Mark P]

Hi was contemplating the use of either MAP or Hashtable for keeping a
cache of objects with name as the key to object. I would be searching
the MAP/Array/Hashtable often now for such a small number, which would
be quicker and how exactly does MAP search?

Thanks
Ankur

First of all the standard library provides "map" not "MAP".

To answer your last question, it's implementation dependent but
typically it's a binary search on a red-black tree.

As to your original question, there's not enough information here to
provide a useful answer. How many objects? How many searches? Will
the contents of the container change between searches (insertions or
deletions?)? If you can better define the parameters we may be able to
take an educated guess but the best idea is to try each and see which is
faster (if you can observe any difference at all... 1000 searches is
really very little on modern hardware).

Mark

 

[Jerry Coffin]

To be clearer, the data size could be anywhere from 50-1000 objects and
access could be around 1-10 times a sec.

With only a few objects like this, it's unlikely to make any
difference at all. A hash table or a sorted vector should be at least
as fast to search as an std::map. Even in that worst case, searching
1000 items should take on the order of microseconds or so (unless
comparing two items is _incredibly_ slow).

 

[Jerry Coffin]

With only a few objects like this, it's unlikely to make any
difference at all. A hash table or a sorted vector should be at least
as fast to search as an std::map. Even in that worst case, searching
1000 items should take on the order of microseconds or so (unless
comparing two items is _incredibly_ slow).

Thinking about it, it seemed relevant to add one more detail here:
the "microseconds or so" is based on an assumption that the computer
is busy doing other things between the queries, so most (if not all)
of the data will usually have to be read in from main memory. If the
computer is sitting idle between queries so the data stays in cache,
then a query is more likely to finish in somewhere on the order of
nanoseconds.