STL's slist vs singly linked list 
Author Message
 STL's slist vs singly linked list

Hi,

Where is the difference in performance when using an slist instead of
a raw singly linked list?

I think it is in the iterators that the 2 differ the most in
performance.

Thanks in advance,
Gabriel



Tue, 18 May 2004 21:06:20 GMT  
 STL's slist vs singly linked list
What's a "raw list"? Is slist cooked or what?
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat, and
wrong." H.L. Mencken


Quote:
> Hi,

> Where is the difference in performance when using an slist instead of
> a raw singly linked list?

> I think it is in the iterators that the 2 differ the most in
> performance.

> Thanks in advance,
> Gabriel



Sat, 22 May 2004 04:38:14 GMT  
 STL's slist vs singly linked list

Quote:

> What's a "raw list"? Is slist cooked or what?
> --
> With best wishes,
>     Igor Tandetnik

> "For every complex problem, there is a solution that is simple, neat, and
> wrong." H.L. Mencken



> > Hi,

> > Where is the difference in performance when using an slist instead of
> > a raw singly linked list?

> > I think it is in the iterators that the 2 differ the most in
> > performance.

> > Thanks in advance,
> > Gabriel

I'm sorry, I meant a classical single linked list implementation (my
english is not very good isn't it?), like this:

typedef struct linkedlistnode {
  int data;
  struct linkedlistnode* next;

Quote:
} LINKED_LIST, *PLINKED_LIST;

PLINKED_LIST aList = NULL;

against the STL one:

std::slist<int> aList;

Regards,
Gabriel



Sat, 22 May 2004 20:14:54 GMT  
 STL's slist vs singly linked list

Quote:
> I'm sorry, I meant a classical single linked list implementation (my
> english is not very good isn't it?), like this:

> typedef struct linkedlistnode {
>   int data;
>   struct linkedlistnode* next;
> } LINKED_LIST, *PLINKED_LIST;
> PLINKED_LIST aList = NULL;

> against the STL one:

> std::slist<int> aList;

slist _is_ a singly linked list, which I would expect to be implemented
internally exactly the way you show (maybe as a circular list). It just
hides implementation details behind a convenient interface consistent with
the rest of the STL. I don't see where that would incur a performance hit or
boost. It sure provides a boost to programmer productivity.
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat, and
wrong." H.L. Mencken



Sat, 22 May 2004 23:02:14 GMT  
 STL's slist vs singly linked list

Quote:

>I'm sorry, I meant a classical single linked list implementation (my
>english is not very good isn't it?), like this:

>typedef struct linkedlistnode {
>  int data;
>  struct linkedlistnode* next;
>} LINKED_LIST, *PLINKED_LIST;
>PLINKED_LIST aList = NULL;

>against the STL one:

>std::slist<int> aList;

slist isn't part of the current standard, but it probably will be part
of a future standard. That said, the big difference in performance
would seem to be the amount of copying that is done to get data into
the container. STL containers are all non-intrusive, which means the
data types users store in them don't contain the link field or any
other container housekeeping information. Thus, to get an object into
the container, you use a function like push_back(x), which takes the
existing object x and copies it into the container. So you create x
and then copy it.

On the other hand, you can create an object of your LINKED_LIST node
type and store that object directly in your container without making
any copies, because it has the necessary link field. This is called an
intrusive container, and if copying is expensive, it can be more
efficient. Using smart pointers can mitigate the copying expense for
the non-instrusive STL containers, which tend to be much more
convenient to use than intrusive containers.

--
Doug Harrison [VC++ MVP]
Eluent Software, LLC
http://www.eluent.com
Tools for Visual C++ and Windows



Sun, 23 May 2004 05:34:11 GMT  
 STL's slist vs singly linked list

Quote:

> >I'm sorry, I meant a classical single linked list implementation (my
> >english is not very good isn't it?), like this:

> >typedef struct linkedlistnode {
> >  int data;
> >  struct linkedlistnode* next;
> >} LINKED_LIST, *PLINKED_LIST;
> >PLINKED_LIST aList = NULL;

> >against the STL one:

> >std::slist<int> aList;

> slist isn't part of the current standard, but it probably will be part
> of a future standard. That said, the big difference in performance
> would seem to be the amount of copying that is done to get data into
> the container. STL containers are all non-intrusive, which means the
> data types users store in them don't contain the link field or any
> other container housekeeping information. Thus, to get an object into
> the container, you use a function like push_back(x), which takes the
> existing object x and copies it into the container. So you create x
> and then copy it.

> On the other hand, you can create an object of your LINKED_LIST node
> type and store that object directly in your container without making
> any copies, because it has the necessary link field. This is called an
> intrusive container, and if copying is expensive, it can be more
> efficient. Using smart pointers can mitigate the copying expense for
> the non-instrusive STL containers, which tend to be much more
> convenient to use than intrusive containers.

What about iterators?
slists create a new iterator to traverse the list. On a linked list I
must create only a pointer.
Which one is more efficient?

Regards,
Gabriel



Fri, 28 May 2004 21:31:11 GMT  
 STL's slist vs singly linked list

Quote:
> What about iterators?
> slists create a new iterator to traverse the list. On a linked list I
> must create only a pointer.
> Which one is more efficient?

I would expect an implementation to define an slist::iterator as a very
lightweight class with all members inlined. I don't think it is less
efficient than a pointer.
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat,
and wrong." H.L. Mencken



Fri, 28 May 2004 23:02:30 GMT  
 STL's slist vs singly linked list

Quote:

>What about iterators?
>slists create a new iterator to traverse the list. On a linked list I
>must create only a pointer.
>Which one is more efficient?

That's going to depend entirely on the implementation, the library
together with the compiler. In principle, there's no reason the STL
version shouldn't be as efficient as the hand-written list, and I
wouldn't think achieving that would be particularly hard. As ever,
when using iterators, the main thing to avoid when possible is postfix
increment and decrement, which are required to return a copy of the
iterator's original value. The compiler may be able to optimize the
copy away, but using the prefix operators eliminates the question.
That's typically not a concern when you're chasing pointers by hand.
Ultimately, if you're worried about such things, you'll need to
profile to determine if your STL implementation is acceptable.

--
Doug Harrison [VC++ MVP]
Eluent Software, LLC
http://www.eluent.com
Tools for Visual C++ and Windows



Sat, 29 May 2004 03:42:30 GMT  
 STL's slist vs singly linked list

Quote:

> >What about iterators?
> >slists create a new iterator to traverse the list. On a linked list I
> >must create only a pointer.
> >Which one is more efficient?

> That's going to depend entirely on the implementation, the library
> together with the compiler. In principle, there's no reason the STL
> version shouldn't be as efficient as the hand-written list, and I
> wouldn't think achieving that would be particularly hard. As ever,
> when using iterators, the main thing to avoid when possible is postfix
> increment and decrement, which are required to return a copy of the
> iterator's original value. The compiler may be able to optimize the
> copy away, but using the prefix operators eliminates the question.
> That's typically not a concern when you're chasing pointers by hand.
> Ultimately, if you're worried about such things, you'll need to
> profile to determine if your STL implementation is acceptable.

Why is that ++iterator is more efficient that iterator++?

Regards,
Gabriel



Mon, 31 May 2004 02:12:39 GMT  
 STL's slist vs singly linked list

Quote:
> Why is that ++iterator is more efficient that iterator++?

Postincrement needs to return a copy of the iterator as it was before
the increment operation. More often the not, it is implemented this way:

iterator iterator::operator++(int)
{
    iterator temp = *this;
    ++*this; // delegate to preincrement
    return temp;

Quote:
}

Extra copy (or several) needs to be made.
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat,
and wrong." H.L. Mencken



Mon, 07 Jun 2004 06:08:21 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. basic sort for singly linked list...

2. Singly linked List

3. singly linked list code

4. singly linked list

5. problems with singly linked list,

6. Singly Linked Lists

7. Singly Linked List Help

8. Help on printing out singly linked list!

9. Reversing a singly linked list

10. Help with singly linked list

11. New Singly Linked List Question?

12. Help With Singly Linked List

 

 
Powered by phpBB® Forum Software