Re: map vs list performance

From:

Naive Group User <imuaplease@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Wed, 30 Dec 2009 19:50:07 -0800 (PST)

Message-ID:

<47f6bd80-e779-4a95-8237-e3b03e39db89@c3g2000yqd.googlegroups.com>

On Dec 31, 10:44 am, Naive Group User <imuaple...@gmail.com> wrote:

On Dec 31, 6:17 am, "barcaroller" <barcarol...@music.net> wrote:

I have an STL list that contains about 1500 objects. To check if an =

object

exists in my list I iterate over it and check if a "key" matches. A =

key is

just a struct that contains four integers.

    typedef struct
    {
        int a;
        int b;
        int c;
        int d;
    } abcd;

    class C
    {
        abcd key;
        char data[100];
    }

    for i = list.begin(); i != list.end(); i++)
        if ( mya == i->key.a && myb == i->key.b &&
             myc == i->key.c && myd == i->key.d )
            // object has been found; access data[]

To improve performance, I converted the list to an STL map. I used t=

struct as the map's key and I added the operator<() and operator==(=

)

functions to allow the map to sort and find objects. I also replaced=

the

list's for loop with map's find() function.

if (map.find(mykey) != map.end())
// object has been found; access data[]

Everything is working correctly (adding, finding, deleting, etc) but th=

e map

solution is over 100% slower than the list for searches (say 100,000
searches). I understand that a map has some additional overhead but =

I would

have expected this overhead to be negligible for 1500 elements. I ca=

n't

explain why a sequential list search is faster (the found objects are
randomly dispersed and are not at the beginning of the list).

Has anyone else noticed this performance issue? Using gcc on Linux.

Dear Sir,

I have just made a question about speaking skill in sci.math- a very
necessary skill I would like to acquire via your experience Sir.
I have been to an interview as of late for a job of business
consultant and definitely I fail but I am not absolutely in a bad mood
because those interviewers are a little limited in viewpoints and
evaluation process, and admittedly there are things I forget; things I
(sadly) missed during I was at schools but definitely I lack a special
speaking skill that I strongly need to acquire during the next few
weeks or more. Thereby, seeking Sir, The Professor and Bear's advice
as well as experience is a must-do right now. Just a few posts don't
count up the tall pyramids but they are priceless and appriciative
things ever from an online community Sir.

About your question, Sir,
Since built-in functions in those containers are mainly to as
versatile as possible to 'feed' a large number of coders of varied
needs. So, a hefty import of different headers as well as libraries
will be performed during the compiling and linking processes. The
containers inheritted from the base classes i.e iostream reimplemented
several to many virtual functions to expose their (aka) polymorphism
for current and future uses with the templatizing capabilities. Once
the objects are assigned to each placeholder of the list which is more
limited in functionalities performed in terms of first-key-second-
value pairwise implementation in comparison to map container. I think
that is why it is much faster than the map in relation to runtime
speed.- Hide quoted text -

- Show quoted text -

Ohhh I read what i wrote and I don't understand what I wrote too :-D

I am Sorry Sir but
I am have been online too long
I better go now

Next time next better
Remember me, remember you