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

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

Re: STL list or map?

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.
>>   Is the container initialized once at the start of the program and then
>> never modified again (fast reading being the only operation done to it
>> for the rest of the program)?
> 
>    Yes.  Furthermore, the (many) searches will attempt to find virtually 
> all of the elements in the container - which is why I'm most interested 
> in speed of searching.
>  
>>   If the answer is yes, then the most efficient way is to put the elements
>> in a vector, sort it, and then use binary searching when you need to read
>> an element. The binary searching can be done with a std::lower_bound() call.
> 
>    That seems to be most worth exploring.  Thanks for the thorough 
> answer.
>>   If the container needs to be updated (elements added or removed) during
>> the execution of the program, and this updating must be as fast as possible,
>> then this solution won't work. (In that case you need to either use std::set
>> or std::unordered_set.)
> 
>    This has no bearing on my application.  Data is stored once (at the 
> program's start) and there will be many accesses of all elements (as I 
> say above). 
>    Thanks to all who responded!

Sounds like a sorted vector and using upper/lower_bound would be the 
best bet.

Jeff

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