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

Groups > comp.lang.c++ > #5806 > unrolled thread

STL list or map?

Back to article view | Back to comp.lang.c++

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#6347

Michael Doubez wrote:
> On 7 juin, 00:33, Joshua Maurice <joshuamaur...@gmail.com> wrote:
>> On Jun 6, 3:22 pm, "MikeP" <mp011...@some.org> wrote:
>>
>>> Michael Doubez wrote:
>>>> I strongly disagree. The concern of a container is to provide a
>>>> storage with complexity guarantees related to access/insertion/
>>>> suppression of data
>>
>>> There you go with the Big O stuff again. The concept of "queue" is
>>> orthogonal to the language lawyer stuff.
>>
>> If that's what you really think, you should not be a programmer. You
>> need to go back to school. "Big O" talk is /not/ language lawyering.
>>
>> The defining characteristics of a container are its methods and
>> contracts (if any) of insert, removal, finding, and iteration, and
>> the time and space complexity to do those operations.
>>
>> You don't need to use any of the containers except for a singly
>> linked list and linear search. There is a reason why that isn't done
>> in practice, and the answer is precisely Big O.
>
> Re-reading the thread, I think I understand the misunderstanding. At
> one point, we have lost the context of the OP which question directly
> related to performances.
>
> AFAIS, MikeP's comment was just to choose the right abstraction
> related to the problem and not a specific implementation (MikeP,
> correct me if I have misread your answer).

I made the mistake of getting sucked into this "discussion". I should 
have just made one post and then shut up.

> And thus, this "go back to
> the basic"; with the corollary of not basing a decision on the
> complexity guarantees.
>
> This is generally good advice but, from an engineering point of view,
> this is  debatable :)
>
> Still, the list vs queue doesn't make sense IMNSHO.

Where did you (not) learn the material from? What is keeping your mind 
from extracting the simple concepts from your paradigmic thought. Ah! 
That's it: it's your PARADIGM! 

[toc] | [prev] | [next] | [standalone]

#6383

On Jun 7, 1:28 am, Michael Doubez <michael.dou...@free.fr> wrote:
> On 7 juin, 00:33, Joshua Maurice <joshuamaur...@gmail.com> wrote:
>
> > On Jun 6, 3:22 pm, "MikeP" <mp011...@some.org> wrote:
>
> > > Michael Doubez wrote:
> > > > I strongly disagree. The concern of a container is to provide a
> > > > storage with complexity guarantees related to access/insertion/
> > > > suppression of data
>
> > > There you go with the Big O stuff again. The concept of "queue" is
> > > orthogonal to the language lawyer stuff.
>
> > If that's what you really think, you should not be a programmer. You
> > need to go back to school. "Big O" talk is /not/ language lawyering.
>
> > The defining characteristics of a container are its methods and
> > contracts (if any) of insert, removal, finding, and iteration, and the
> > time and space complexity to do those operations.
>
> > You don't need to use any of the containers except for a singly linked
> > list and linear search. There is a reason why that isn't done in
> > practice, and the answer is precisely Big O.
>
> Re-reading the thread, I think I understand the misunderstanding. At
> one point, we have lost the context of the OP which question directly
> related to performances.

But it's always about performance. Only toy projects generally can
ignore performance. In the real world, there are always performance
requirements. Perhaps they're trivial to meet, but they're still
there.

> AFAIS, MikeP's comment was just to choose the right abstraction
> related to the problem and not a specific implementation (MikeP,
> correct me if I have misread your answer). And thus, this "go back to
> the basic"; with the corollary of not basing a decision on the
> complexity guarantees.

Not basing a decision on complexity guarantees means ignoring
performance in its entirety. This is no way to write software. There's
early optimization by picking the proper data structures and
algorithms, and then there's premature optimization. They are not the
same.

My original point in this thread was perhaps a more pedantic one -
that it is absurd to say "Big O" is language lawyering. If you think
that, then you really haven't seen language lawyering. My recent
discussion of why null pointer deferences are undefined behavior (or
not), now that's language lawyering. Google groups archive link:
http://groups.google.com/group/comp.lang.c++/msg/72899ddeaa2e13b9

[toc] | [prev] | [next] | [standalone]

#6346

Joshua Maurice wrote:
> On Jun 6, 3:22 pm, "MikeP" <mp011...@some.org> wrote:
>> Michael Doubez wrote:
>>> I strongly disagree. The concern of a container is to provide a
>>> storage with complexity guarantees related to access/insertion/
>>> suppression of data
>>
>> There you go with the Big O stuff again. The concept of "queue" is
>> orthogonal to the language lawyer stuff.
>
> If that's what you really think, you should not be a programmer. You
> need to go back to school. "Big O" talk is /not/ language lawyering.
>
> The defining characteristics of a container are its methods and
> contracts (if any) of insert, removal, finding, and iteration, and the
> time and space complexity to do those operations.
>
> You don't need to use any of the containers except for a singly linked
> list and linear search. There is a reason why that isn't done in
> practice, and the answer is precisely Big O.

The question becomes: Why can't a "language lawyer" understand the simple
concept of "queue"? And also: How many "language lawyers" (or wannabes)
does it take to install a lightbulb?".

(hehehe) 

[toc] | [prev] | [next] | [standalone]

#6336

On 7 juin, 00:22, "MikeP" <mp011...@some.org> wrote:
> Michael Doubez wrote:
> > On 6 juin, 18:10, "MikeP" <mp011...@some.org> wrote:
> >> Michael Doubez wrote:
> >>> On 6 juin, 16:06, "MikeP" <mp011...@some.org> wrote:
> >>>> Rune Allnor wrote:
> >>>>> On Jun 6, 12:44 pm, "MikeP" <mp011...@some.org> wrote:
> >>>>>> Alain Ketterlin wrote:
> >>>>>>> Rune Allnor <all...@tele.ntnu.no> writes:
>
> >>>>>>> [...]
> >>>>>>>>> The other responder noted that a "priority list" (for lack of
> >>>>>>>>> a better designation in my mind right now) may be in order,
> >>>>>>>>> which may or may not be. A list that moves recently accessed
> >>>>>>>>> elements to the front may be just what the application
> >>>>>>>>> requires. Do not reject a list out of only the above
> >>>>>>>>> characteristic of a simple list. Let the application
> >>>>>>>>> semantics govern.
>
> >>>>>>>> Is that a list? I have seen descriptions of such functionality
> >>>>>>>> in Cormen & al. The description seemed like some sort of tree
> >>>>>>>> structure, that was updated after each access, to me.
>
> >>>>>>> It's called a priority queue, and usually uses a tree to
> >>>>>>> guarantee O(log(N)) insertion and extraction of the highest
> >>>>>>> priority element. It is included in th STL (priority_queue).
>
> >>>>>> No. A list is a list. A queue is a queue. (Notwithstanding, a
> >>>>>> queue can be made from a list). I didn't mean to confuse by using
> >>>>>> "priority list" (and parentheically tried to preclude potential
> >>>>>> confusion and also attempted to avoid by putting it in quotes)
> >>>>>> but apparently I did. I was trying to conjure up a name for a
> >>>>>> list that relinks last-accessed elements to the front of the
> >>>>>> list for I don't know if there is a formal name for such a beast
> >>>>>> while there indeed is a name for the different animal called
> >>>>>> "priority queue".- Hide quoted text -
>
> >>>>>> - Show quoted text -
>
> >>>>> OK, then why not try and untangle the confusion:
>
> >>>>> 1) How is the list you describe functionally and semantically
> >>>>> different from a priority queue?
>
> >>>>> 2) What would the advantages be, if any, with this list compared
> >>>>> to a priority queue?
>
> >>>> Think about what a queue is and what a list is and how their
> >>>> behavior is different and think of some examples where each is
> >>>> appropriately applied from an application point of view.
>
> >>> I don't understand your point.
>
> >> My point is that discussion about fundamentals of ADTs is noise in a
> >> NG about C++. As such, I gave suggestion for further investigation
> >> to the poster.
>
> > Given that one of the main advantage of generic programming is the
> > abstraction of the algorithm relatively to the data structure and
> > given that the standard provides containers with guaranteed
> > complexity, it seems very relevant to me.
>
> As it relates to C++ specifically, yes, but in general, probably not.

We are in a C++ NG. So we seem to agree it is not noise.

> >>> A list is a data structure while a
> >>> queue is a way to organize/prioritize data (the FIFO abstraction).
>
> >> The are both ADTs.
>
> > I strongly disagree. The concern of a container is to provide a
> > storage with complexity guarantees related to access/insertion/
> > suppression of data
>
> There you go with the Big O stuff again. The concept of "queue" is
> orthogonal to the language lawyer stuff.

The language and especially the STL is based on the mathematical and
algorithmic abstractions. IMO this comment is disregarding the
contribution of Alexander Stephanov to the language. IMHO the models
defined by the language are pretty good matches.

Apart from that the Container and Queue (let call it FIFO)
abstractions are two different beasts with different concerns. Let
take the definition of wikipedia (which are not too bad):

http://en.wikipedia.org/wiki/Container_%28data_structure%29
"In computer science, a container is a class, a data structure, or an
abstract data type (ADT) whose instances are collections of other
objects."

http://en.wikipedia.org/wiki/Queue_%28data_structure%29
"A queue (pronounced /ˈkjuː/ kew) is a particular kind of collection
in which the entities in the collection are kept in order and the
principal (or only) operations on the collection are the addition of
entities to the rear terminal position and removal of entities from
the front terminal position."

> > while a FIFO/LIFO/whatever is a restriction on the
> > storage to enforce an access policy.
>
> Listen to yourself, seesh! ;) Stop making is so hard!

Could you provide an alternative (softer :) ) definition.

> > Those are two separated concerns and that is reflected in the STL
>
> STL is but one implementation, not THE implementation.

I am talking about the concepts defined by the STL, not the
implementation.

See:
http://www.sgi.com/tech/stl/queue.html

> > : by
> > example std::queue can be built from whatever container supporting
> > back insertion and front deletion, which can then be std::vector<>,
> > std::list<>, std::deque (and std::slist IIRC).
>
> One can build a queue many ways. If you want to break the concepts down
> to minutiae and work from there, that is fine too. In the end you still
> end up with an queue. A queue is a queue is a queue and that is all it
> can be or else you'd have to rename the resultant thing. But to suggest
> that a particular implementation redefines the abstraction that it
> defines what a queue is, is incorrect. When in doubt, go back to first
> principles.

I fail to see how that follow what I said.

> >> In the simplest case, I think of a priority queue as a
> >> queue that allows adding to the front of the queue in addition to
> >> just the back of the queue. That one additional capability can
> >> distinguish a priority queue from a regular queue. Here's a good
> >> "homework" question: Should a queue allow iteration over it's
> >> elements just like a list does? (Good homework or test question in
> >> general. I wasn't assigning you homework!).
>
> > From a theoretical point of view or from a practic
>
> ?

[Oups, missing part.]

From a theoretical point of view, this can be discussed. From a
practical point of view, it would have been convenient for debugging/
logging purpose.

Actually from STL SGI, removing iteration is the raison d'etre of
std::queue<>:
"[...]Queue does not allow iteration through its elements. [2]"
"[2] This restriction is the only reason for queue to exist at all.
Any container that is both a front insertion sequence and a back
insertion sequence can be used as a queue;[snip] The only reason to
use the container adaptor queue instead of the container deque is to
make it clear that you are performing only queue operations, and no
other operations.

>
> >>> Thus, in the C++ standard, a std::list<> is a container while a
> >>> std::queue<> is a container adapter.
>
> >> You seem to be confusing the abstraction with a particular
> >> implementation. Just because you CAN build a queue from a list does
> >> not mean you HAVE to build it that way, nor is it necessarily the
> >> best way.
>
> > Well, I am speaking of the abstraction. std::queue<> implementation
> > can vary.
>
> I was talking about queues in general. Not STL queue.

So we are talking of the same thing.


> >  I have never seen it, but I could specialize it on a
> > vector<T> container to provide an alternative implementation of
> > pop_front() push_back(), or even, in the case of a priority_queue<>, I
> > could use a sorted area and an unsorted one in order to amortize the
> > cost of sorting (or whatever).
>
> > That's quality of implementation, the standard providing the semantic
> > and complexity guarantee (in some case).
>
> All of that is not really relevant to the current place in this thread. I
> tried to keep you from dragging implementation details into this, but no
> avail. Oh well, so much for so much for the ol' college try.

I don't see how speaking about complexity or concepts would be a
implementation detail.

> >>> I would be interest on how you can compare them ?
>
> >> I compare them according to their behavioral capabilities and by
> >> their applicability to a given scenario.
>
> > But, to me, if you compare a container and an access policy, you are
> > basically comparing vegetables and a frying pan. They may be related
> > but don't compare.
>
> You are over-thinking it and making it harder than it is. The fundamental
> concepts are much simpler than that. And it's only those fundamental
> concepts that this thread required, but now it's littered with all the
> extraneous material. I should have just posted this link and been done:http://en.wikipedia.org/wiki/Queue_(data_structure). If you have issues
> with what is there, you can change it (but I'll probably revert the
> changes). Wikipedia is your friend, then, I should have said.

I see no fault with the Wikipedia page.

--
Michael

[toc] | [prev] | [next] | [standalone]

#6345

Michael Doubez wrote:

>> I should have just posted this link and been
>> done:http://en.wikipedia.org/wiki/Queue_(data_structure). If you
>> have issues with what is there, you can change it (but I'll probably
>> revert the
>> changes). Wikipedia is your friend, then, I should have said.
>
> I see no fault with the Wikipedia page.

Good then. See, wasn't that easy? Case closed. 

[toc] | [prev] | [next] | [standalone]

#6297

"Michael Doubez" <michael.doubez@free.fr> ha scritto nel messaggio 
news:8b8488c8-d1cb-4e33-bb88-7c0010c3ec59@f11g2000vbx.googlegroups.com...
>I don't understand your point. A list is a data structure while a
>queue is a way to organize/prioritize data (the FIFO abstraction).
>Thus, in the C++ standard, a std::list<> is a container while a
>std::queue<> is a container adapter.

io> always in the C++ library: queue is not a double list?
io> and list is a simple list?

>I would be interest on how you can compare them ?

[toc] | [prev] | [next] | [standalone]

#6363

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4decfe0c$0$38640$4fafbaef@reader1.news.tin.it...
>
> "Michael Doubez" <michael.doubez@free.fr> ha scritto nel messaggio
> news:8b8488c8-d1cb-4e33-bb88-7c0010c3ec59@f11g2000vbx.googlegroups.com...
>>I don't understand your point. A list is a data structure while a
>>queue is a way to organize/prioritize data (the FIFO abstraction).
>>Thus, in the C++ standard, a std::list<> is a container while a
>>std::queue<> is a container adapter.
>
> io> always in the C++ library: queue is not a double list?
> io> and list is a simple list?

wrong, C++ list is a double list

>>I would be interest on how you can compare them ?
>
>

[toc] | [prev] | [next] | [standalone]

#6299

n Jun 6, 10:06 am, "MikeP" <mp011...@some.org> wrote:
> I recommend Cormen's book as the best on the subject.

It's not appropriate to refer to that book as "Cormen's book".
The first edition had 3 authors who each contributed fully and
substantially to the book. Also, in case you didn't notice the
names are listed /alphabetically/ and otherwise equally. And I
suspect that 99% of students who take a course based on this
book refer to it as "CLR" just as we did at MIT.

KHD

[toc] | [prev] | [next] | [standalone]

#6303

Keith H Duggar wrote:
> n Jun 6, 10:06 am, "MikeP" <mp011...@some.org> wrote:
>> I recommend Cormen's book as the best on the subject.
>
> It's not appropriate to refer to that book as "Cormen's book".
> The first edition had 3 authors who each contributed fully and
> substantially to the book. Also, in case you didn't notice the
> names are listed /alphabetically/ and otherwise equally. And I
> suspect that 99% of students who take a course based on this
> book refer to it as "CLR" just as we did at MIT.
>

My bad. "Introduction to Algorithms" (Third Edition) by Stein, Rivest, 
Leiserson, Cormen. Or as I like to call it, "SRLC", pronounced "sirlk". 
;) 

[toc] | [prev] | [next] | [standalone]

#5822

On May 29, 11:58 am, mrc2...@cox.net (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.  The actual number of
> elements used in this application probably won't exceed 3000.
>    Please advise.  TIA
>
> struct SHADOWS
> {
>         char sRCode, aRCode;
>         int  sBibNo, aBibNo;
> }

How often do you insert, and how often do you do finds? Specifically
the relative frequencies.

std::list is /usually/ the wrong answer to any performance problem. If
you're doing lookups and you're concerned about memory, it is
definitely the wrong answer. std::map would be better.

std::set, equivalently std::map, is the good default choice.

If the number of finds greatly outweigh the number of inserts, a
std::vector kept in sorted order using binary searches is probably the
best approach for performance.

Alternatively, maybe a B-tree with the right branching factor.
http://en.wikipedia.org/wiki/B-tree
I don't know offhand if this is a good idea. I would implement and
measure.

Specifically, if your problem is that important, I would implement and
measure all reasonable alternatives.

[toc] | [prev] | [next] | [standalone]

#5825

On 29 mai, 20:58, mrc2...@cox.net (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.  The actual number of
> elements used in this application probably won't exceed 3000.
>    Please advise.  TIA
>
> struct SHADOWS
> {
>         char sRCode, aRCode;
>         int  sBibNo, aBibNo;
> };

In addition to what others said, you can also consider unorder_map
(hash_map extension on some compilers) but it depends on the
distribution of sBibNo or if you can find a good hash function.

--
Michael

[toc] | [prev] | [next] | [standalone]

#5827

Mike Copeland <mrc2323@cox.net> 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)?

  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.

  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.)

[toc] | [prev] | [next] | [standalone]

#5849

> >   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!

[toc] | [prev] | [next] | [standalone]

#5898

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

[toc] | [prev] | [next] | [standalone]

#6323

On May 29, 2:58 pm, mrc2...@cox.net (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.  The actual number of
> elements used in this application probably won't exceed 3000.
>    Please advise.  TIA
>
> struct SHADOWS
> {
>         char sRCode, aRCode;
>         int  sBibNo, aBibNo;
> }

Coming back to Mike's original question, why not consider allocating
an array (or std::vector) of SHADOWS, or perhaps pointers to SHADOWS,
indexed by sBibNo?  If element look-up (and insertion, for that
matter)
is an important performance bottleneck for your application, then this
would probably be the fastest way to go.

Assuming sBibNo has an acceptable upper bound (for example, 50,000),
then an array of pointers (assuming four-byte pointers) would take
up 200 kB, and an array of SHADOWS would take less than a megabyte.

Unless your application uses lots of separate containers of SHADOWS
(instead of one or just a few), then devoting a few megabytes to this
data structure for the sake of performance would seem to be quite
reasonable for a desktop or server application.  (For an embedded
application, then the cost in memory might be more of a concern.)

Both look-up and insertion are order-one operations, with a very
small pre-factor.

At least as you've described it, your data structure isn't all that
sparse -- 3,000 elements in a structure allocated for 50,000 elements
is a load factor greater than 10%.

Of course the trade-offs appropriate for your application may lead
you in a different direction -- all I'm saying is that you shouldn't
reject the scheme of indexing into a full array with sBibNo out of
hand.

Good luck.


K. Frank

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web