Sign in to follow this  
Rozik

STL List Template

Recommended Posts

I have read in Game Coding Complete that useing the STL List Template with long lists where you have to remove things from the middle is too slow. what i am planing to do is make a priority list of a lot of items when one of the items is used i want to remove it from the list and push it in on top i was going to use a STL list for this and use the folowing line of code to remove items List.remove(item); is this too slow for long lists? and if so whats a better way to do it?

Share this post


Link to post
Share on other sites
Removing an item from a container requires finding the element and then removing it. Removal time does not depend on the position of the removed objects within the list. If you know the position of the element within the list (through an iterator, for instance), then erasing that element can be done in constant time. Removal times for several containers are:

Unsorted array, list: O(n)
Sorted container: O(log n)
Hash table: O(1)

For comparison, erasing times are:

Unsorted array, list, hash table: O(1)
Sorted container: O(log n)

Therefore, if your main concern is removal speed, I'd suggest a hashtable if you have a hashtable library around. If not, use std::set.

However, it is quite probable that your usage of the container will involve other operations, which may require different overall complexities. A good idea would be to tell us more about how data is inserted and accessed in the container. The best idea would be to encapsulate that behavior and profile, to avoid mispredicting what the fastest approach is.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Removing an item from a container requires finding the element and then removing it. Removal time does not depend on the position of the removed objects within the list. If you know the position of the element within the list (through an iterator, for instance), then erasing that element can be done in constant time. Removal times for several containers are:

Unsorted array, list: O(n)
Sorted container: O(log n)
Hash table: O(1)

For comparison, erasing times are:

Unsorted array, list, hash table: O(1)
Sorted container: O(log n)

Therefore, if your main concern is removal speed, I'd suggest a hashtable if you have a hashtable library around. If not, use std::set.

However, it is quite probable that your usage of the container will involve other operations, which may require different overall complexities. A good idea would be to tell us more about how data is inserted and accessed in the container. The best idea would be to encapsulate that behavior and profile, to avoid mispredicting what the fastest approach is.

Hashtables are a sorted container, and he wants an unsorted container. He could probably use a hashmap, with the key being the item's priority, but he'd get a lot of collisions at the #1 spot as items get bumped up there.

A list may well be appropriate, depending on how you're using it. Finding elements in a list is a linear operation. But will you be finding the elements, or will you already know where they are? If so, then you can do your 'promote' operation in constant time. This even has the benefit of not invalidating any iterators. But you also have to consider how often you are adding elements to your list, and what their initial priority is. In fact, do you keep track of a priority, or is that implied by their position within the list? All important information.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Hashtables are a sorted container, and he wants an unsorted container.


Associative, yes, but sorted, no. Neither the items nor the keys being placed in the container do not need to have an ordering defined on them unlike, say, std::set or std::map.

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Hashtables are a sorted container


I don't think I can agree with this. How is a hashtable sorted?

My initial approach to the problem (given the information available here) would be to use a hashtable to associate elements and list iterators, thus combining a list and a hashtable into one single container, with O(1) removal and O(1) insertion/extraction from the front (but, obviously, greater complexities for other operations).

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by Conner McCloud
Hashtables are a sorted container, and he wants an unsorted container.


Associative, yes, but sorted, no. Neither the items nor the keys being placed in the container do not need to have an ordering defined on them unlike, say, std::set or std::map.

I think I meant ordered, I tend to get them confused. A set in this case would also be inappropriate, because you have no control over where things get placed, and he explicitly needs to be able to rearrange them at will.

CM

Share this post


Link to post
Share on other sites
well the basic idea is to have a list of items

when a item is used its erased and inserted at the top of the list

when an item has to be deleted cause there are too many it supposed to be taken from the end of the list which arent used often any ways

thats about it

is a STL list the right container to use?

since i will have a lot of items i am not sure if i should use the list because there will be a lot of removing and inserting at the top

the removing is the part i am concerned about

the application will know what item has to be moved but it doesnt know where in the list it will be

Share this post


Link to post
Share on other sites
Personally, I would start with a list, yes. You will have a linear time search for items when they're used, but by definition frequently used items will be near the top. So typically, you won't be making a long search anyhow. Why make things more complicated than they need to be?

But, like ToohrVyk said, you should hide as many of the annoying little details as possible. That way, should a more complicated solution be neccessary, all you have to change are your wrapper functions.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
I think I meant ordered, I tend to get them confused.

Uh, TR1 refers to hashed containers as unordered associative containers. The word you're looking for might be a sequence container.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this