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

  • From: Bob Pendleton <bob@xxxxxxxxxxxxx>
  • To: gameprogrammer@xxxxxxxxxxxxx
  • Date: Fri, 13 Jul 2007 10:08:10 -0500

On Fri, 2007-07-13 at 08:49 -0400, Roger D Vargas 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?

Average look up time for a list and a vector is proportional to N/2 when
N is the number of items to search. Average look up time for a map is
proportional to Log2(N). 

N       N/2     Log2(N)
5       2.5     2.3
10      5       3.3
15      7.5     3.9
20      10      4.3

If all else is equal, then maps are faster. OTOH, the real question is
how often do you do the look and which is going to take the least amount
of time to implement. Also, will the size of these lists ever going to
grow?

Since you are using STL the development time is the same so I would just
always use maps.

                Bob Pendleton

> 
-- 
+--------------------------------------+
+ Bob Pendleton: writer and programmer +
+ email: Bob@xxxxxxxxxxxxx             +
+ web: www.GameProgrammer.com          +
+ www.Wise2Food.com                    +
+ nutrient info on 7,000+ common foods +
+--------------------------------------+



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

Other related posts:

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