[gameprogrammer] Re: faster lookup, lists, vectors, maps?

  • From: Robbert de Groot <zekaric@xxxxxxxx>
  • To: gameprogrammer@xxxxxxxxxxxxx
  • Date: Fri, 13 Jul 2007 11:54:02 -0400 (EDT)

--- Roger D Vargas <luo_hei@xxxxxxxx> wrote:

> I would like to know what STL container provides faster access time
> in 
> short lists of elements. In my game, entities have some properties:
> 
> basic stats, attributes and skills, which I plan to unify under a
> single 
> data structure. Such lists of properties are accessed by scripts
> and 
> currently Im using lists. Does vectors or maps provides faster
> access 
> when number of elements is less than 10-20?

I can depend.  

Is the vector going to be in a sorted order?  If so, you could use a
binary search on a vector and the speed may be a hair better in
lookup times than a map.  Why?  If I'm correct, most STL maps are
organized in some sort of binary tree (not a hash table although
there STL implementations that offer a hash table map.)  Hopefully
they use some sort of balancing binary tree instead of the brain dead
simple binary tree.  But even the balancing binary tress can be a bit
lob sided so it'll give you roughly O(logN) in search but not quite. 


If the vector is unsorted and you have to do a linear search on the
data then the vector method will lose if the vector grows to contain
more than 4 to 6 elements over a hash table or balanced binary tree
implementation.  

Hash table will be fastest.  It borders on almost O(1) if you set the
hash table to be a proper size to your intended use.

Robbert de Groot


      Be smarter than spam. See how smart SpamGuard is at giving junk email the 
boot with the All-new Yahoo! Mail at http://mrd.mail.yahoo.com/try_beta?.intl=ca


---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts:

  1. Home
  2. gameprogrammer
  3. Archive
  4. 07-2007