std:slist in VC6
Author
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
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.
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.
Quote:Original post by AshleysBrainThen 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.
I'm using a linked list in a performance sensative environment...
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.
Author
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.
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.
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.
Author
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
