Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #5810

Re: STL list or map?

Followups directed to: comp.lang.c++

Show all headers | View raw

Mike Copeland wrote:

>    I have the following structure defined, and I'm trying to decide the
> best container to use for accessing specific elements: "best" meaning
> the fastest way.  I will be searching on the "sBibNo" field, and it will
> likely contain values in a high range (20000-50000).  The elements
> stored will not be contiguous.  I can't allocate an array of elements
> because doing so would waste a lot of memory space...so I can't use a
> direct index to find the elements.
>    I'm thinking I could use either an STL list or map for this
> application, but I fear the list processing would be prohibitively slow
> and the map might be quite wasteful in other ways. 

Memory: A list node contains the data and typically two pointers. Very 
likely, the underlying allocator is also putting in a hidder pointer. That 
is three pointers in addition to your data. A map node typically contains 
three pointers and the hidden pointer in addition to the data. Taking into 
account that the allocator is likely to round sizes to multiples of 16 or 32 
bytes, you are somewhat unlikely to see a difference.

Cost of iteration: incremening / decrementing an iterator is constant time 
for a list and ammortized constant time for a map.

> The actual number of
> elements used in this application probably won't exceed 3000.
>    Please advise.  TIA
[...]

Elsethread, the suggestion was made to hide this decision as an 
implementation detail of some class. That is a good idea.

If you choose a list representation, then a lot will depend on which pattern 
of searches predominates in your application. E.g., if there is a 
comparatively small set of keys that you will search for very often, then a 
"self organizing file" might be a good idea: you always search from front to 
tail and when you dfind a key, you move the entry to the head of the list. 
This way, frequently searched entries gather near the front and will be 
found quickly.

If your searches are more or less evenly distributed among the keys, a 
better data structure would probably improve performance of searching. The 
tradeoff is usually a slightly greater complexity for inserting an entry. 
Whether changing the data structures pays off, therefore, also depends on 
whether your application will search way more often than it will modify the 
underlying data.

As the influencing factors are hard to predict, you should write your 
program so that it will be easy to change the data structure. Then, 
implement one that you can easily prove correct. Create unit tests. When you 
change the data structure, those tests will catch bugs. Once the other data 
structure is up and running, you can compare performance.


Best,

Kai-Uwe Bux

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

STL list or map? mrc2323@cox.net (Mike Copeland) - 2011-05-29 11:58 -0700
  Re: STL list or map? Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-29 21:37 +0200
    Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 03:52 -0500
      Re: STL list or map? Ian Collins <ian-news@hotmail.com> - 2011-06-06 21:07 +1200
        Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 05:36 -0500
          Re: STL list or map? Ian Collins <ian-news@hotmail.com> - 2011-06-07 09:53 +1200
            Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 17:38 -0500
  Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-05-29 23:32 -0700
    Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 03:55 -0500
      Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-06-06 02:08 -0700
        Re: STL list or map? Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-06-06 12:23 +0200
          Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 05:44 -0500
            Re: STL list or map? Rune Allnor <allnor@tele.ntnu.no> - 2011-06-06 04:23 -0700
              Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 09:06 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-06 08:29 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 11:10 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-06 14:37 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 17:22 -0500
                Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-06 15:33 -0700
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-07 01:28 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 07:00 -0500
                Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-07 14:50 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 06:56 -0500
                Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-06-07 00:58 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-07 06:52 -0500
                Re: STL list or map? "io_x" <a@b.c.invalid> - 2011-06-06 18:20 +0200
                Re: STL list or map? "io_x" <a@b.c.invalid> - 2011-06-07 18:10 +0200
                Re: STL list or map? Keith H Duggar <duggar@alum.mit.edu> - 2011-06-06 09:29 -0700
                Re: STL list or map? "MikeP" <mp011011@some.org> - 2011-06-06 12:42 -0500
  Re: STL list or map? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-30 00:19 -0700
  Re: STL list or map? Michael Doubez <michael.doubez@free.fr> - 2011-05-30 01:02 -0700
  Re: STL list or map? Juha Nieminen <nospam@thanks.invalid> - 2011-05-30 11:43 +0000
    Re: STL list or map? mrc2323@cox.net (Mike Copeland) - 2011-05-30 14:07 -0700
      Re: STL list or map? Jeff Flinn <TriumphSprint2000@hotmail.com> - 2011-05-31 08:37 -0400
  Re: STL list or map? "K. Frank" <kfrank29.c@gmail.com> - 2011-06-06 17:58 -0700

csiph-web