• Advertisement
Sign in to follow this  

std:slist in VC6

This topic is 4181 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm using a linked list in a performance sensative environment and I only ever iterate forwards, so I thought it would make sense to use a singly linked list. I assume it will be faster since you don't have to manipulate the next item's pointer to previous item. I can #include <list>, but not <slist> - file doesn't exist. Where can I get it? This list is also allocating and deallocating lots of very small objects (pointers) very often - is boost::pool_allocator the way to go? Thanks

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by AshleysBrain
I can #include <list>, but not <slist> - file doesn't exist. Where can I get it?


slist isn't a standard C++ container. Try STLPort. Switching to a vector is also a possibility: you need to profile and see if the list iteration/access overhead overweighs the vector's insertion/deletion overhead. It all depends on the number of elements and your usage pattern.

Quote:
This list is also allocating and deallocating lots of very small objects (pointers) very often - is boost::pool_allocator the way to go?


It's well worth a try. Or (again) see if STLPort has some custom allocators. I know that libstdc++ does (and does have slist, too), but if you're stuck with VC6 it won't help you much.

Share this post


Link to post
Share on other sites
Please give more context - type(s) of objects being stored (by value or by pointer? If by pointer, why?), operations performed other than forward iteration, requirements on the sequence (e.g., maintained sorted), etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by AshleysBrain
I'm using a linked list in a performance sensative environment...
Then stay the hell away from VC6's STL implementation. Seriously. The STL implementation isn't very well optimised, and VC6 isn't as good at optimising as other, more recent compilers.

If at all possible, try to use VC2005 Express, it's free to Download. If not, I'd recomment STLPort as an alternative STL implementation.

Share this post


Link to post
Share on other sites
OK, the situation is this (I hope its not too abstract):

I have a list of classes. There are probably going to be a few hundred of these classes. I need to generate a list of the classes which match certain user-defined requirements. I start with an empty list, and if the class matches, I add a pointer to the class to the list. Once done, an action is applied to all the matching classes by iterating the list.

It's possible to have multiple conditions, in which case the list of pointers is iterated again, and if the class does NOT match, it is erased from the list.

So the only operations really are push_back, forwards iteration and erasure of the current element during iteration. Order does not matter so sorting isn't an issue.

Is slist the way to go? If not STL, is there another method you'd recommend?

I have tried VC2005 Express, and I can't use it - I'm using MFC and it also seems to lack a resource editor. I will get the full version at some point for the more sophisticated optimisations but for now I'm stuck with VC6.

Share this post


Link to post
Share on other sites
Quote:
Original post by AshleysBrain
OK, the situation is this (I hope its not too abstract):

I have a list of classes. There are probably going to be a few hundred of these classes. I need to generate a list of the classes which match certain user-defined requirements. I start with an empty list, and if the class matches, I add a pointer to the class to the list. Once done, an action is applied to all the matching classes by iterating the list.

It's possible to have multiple conditions, in which case the list of pointers is iterated again, and if the class does NOT match, it is erased from the list.

So the only operations really are push_back, forwards iteration and erasure of the current element during iteration. Order does not matter so sorting isn't an issue.

Is slist the way to go? If not STL, is there another method you'd recommend?

I have tried VC2005 Express, and I can't use it - I'm using MFC and it also seems to lack a resource editor. I will get the full version at some point for the more sophisticated optimisations but for now I'm stuck with VC6.


None of this sounds "performance sensitive", have you actually profiled your app using std::list, or are you just pulling wild guesses out of thin air?

Also I doubt switching to a single linked list rather than double will help you much. Iteration speed will be pretty much the same, allocation for the nodes might be slightly faster but thats about it. If you're genuinely worried about iteration speed you want a vector as they're much more cache friendly than jumping all around memory in an unpredictable way.

Share this post


Link to post
Share on other sites
Erasing near the beginning of a vector with a few hundred elements is pretty inefficient isnt it? Wont that impact the performance more? What I need is a kind of list container which allocates in contiguous blocks of memory, is this what the pool allocator does?

I have profiled and in some cases up to 40% of the execution time is spent in this area, and I've optimised the other areas as far as I can manage. It's difficult to explain without the specifics, but performance IS important here.

Share this post


Link to post
Share on other sites
Try a std::deque.

Erasing/Inserting is fast at the beginning and end of the container.

Share this post


Link to post
Share on other sites
Quote:
Original post by AshleysBrain
Erasing near the beginning of a vector with a few hundred elements is pretty inefficient isnt it? Wont that impact the performance more? What I need is a kind of list container which allocates in contiguous blocks of memory, is this what the pool allocator does?

If order doesn't matter, then when you are iterating and you need to erase the current item, then the easy thing to do when using a vector is to copy the last item over the current item, and do a .pop_back(). This completely removes the need to shift all items after the location of the erased item.

Since your only insertion is a .push_back(), and order does not matter, std::vector sounds like exactly what you want.

Share this post


Link to post
Share on other sites
Also, if you intend to remove several things at once, the standard library algorithms std::remove and std::remove_if are highly recommended. This actually sounds ideal from your description since you seem to be implementing some sort of rules engine/filtering stuff. If the speed is REALLY critical, you may consider one of the 'unstable_remove_if' implementations floating around these forums.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement