Sign in to follow this  
bronxbomber92

Speed of STL Lists?

Recommended Posts

bronxbomber92    275
Hi, I was wondering if the the STL's list container provides O(1) insertion, O(1) removal and O(1) finding? The insertion is only appended onto the end of the list, the removal is from any place in the list, and the finding I wrote this:
//...
Pair temp(ID0, ID1);
	
std::list<Pair>::iterator begin = pars.begin();
std::list<Pair>::iterator end = pars.end();
for( begin; begin != end; being++ )
{
	if( temp == *it ) return it;
}
/...
If not, what are some other available options (STL's vector, ect..)?

Share this post


Link to post
Share on other sites
rip-off    10976
O(1) on all operations? The holy grail of data structures [smile].

Your loop could be replaced with std::find(begin,end,temp), from the <algorithm> header.

Finding, by nature, is O(n) on an unsorted list. If finding needs to be faster and insertions/removals are allowed to be slower you could use a sorted container.

Share this post


Link to post
Share on other sites
Washu    7829
Quote:
Original post by rip-off
O(1) on all operations? The holy grail of data structures [smile].

Your loop could be replaced with std::find(begin,end,temp), from the <algorithm> header.

Finding, by nature, is O(n) on an unsorted list. If finding needs to be faster and insertions/removals are allowed to be slower you could use a sorted container.


Or a hashed container, which provides a better optimal lookup than most sorted containers, typically amortized O(1) in the case of TR1.

Also note that he could use a sorted vector and the bound functions (lower_bound, upper_bound, equal_range).

Share this post


Link to post
Share on other sites
Jan-Lieuwe    206
If you have to look up values, std::list and std::vector are not suitable [Edit: when unsorted - SiCrane point taken :)] - they're great when you have to iterate through all elements at once. If you have to look up values, look into: std::map or some hashing method. Exception: a small amount of elements.

When you have to iterate through all elements, the choice between std::list and std::vector depends on things like:

* do you often erase elements and does the order of elements matter? (yes = std::list, no = std::vector, replace erased element with last element and remove last element)
* do you often insert elements and you don't want to add them at the tail? (yes = std::list, no = std::vector)

Iterating through a std::vector is faster and std::vector is more cache friendly as well, so only go for the std::list when you answer 'yes' to one of the questions mentioned.

Edit: also note that std::list is a double-linked list. If you only need a forward-linked list (they exist in STL extensions), you might gain some extra performance and memory benefits by using those instead.

[Edited by - Jan-Lieuwe on November 21, 2007 4:37:36 PM]

Share this post


Link to post
Share on other sites
SiCrane    11839
Quote:
Original post by Jan-Lieuwe
If you have to look up values, std::list and std::vector are not suitable

That's not really true. If the number of look-ups significantly outnumbers the number of insertions and removals or the look-ups and modifications occur in batches (which is a remarkably common usage pattern), a sorted std::vector can often outperform a std::map or std::set.

Share this post


Link to post
Share on other sites
bronxbomber92    275
To put some context to my usage: I'm writing an AABB sweep and prune broadphase collision detection routine, and I'm using writing the "Pair Manager" which keeps tracking of the overlapping AABBs. The PairManager is based off of the Erin Catto's Box2D PairManager, but his seems overly complicated (It looks like it uses a hash table, but I don't exactly understand how it works).

I'm just looking for other alternatives that provide O(1) insertion/removal/lookup.

Share this post


Link to post
Share on other sites
swiftcoder    18426
Quote:
Original post by bronxbomber92
I'm just looking for other alternatives that provide O(1) insertion/removal/lookup.


There is absolutely no container that can provide O(1) for all of insertion, deletion, and lookup.

A linked list (eg. std::list) can provide O(1) insertion, and even deletion (provided you already hold the position, i.e. you have already performed a lookup).

A binary search (eg. std::map) provides O(log n) lookup, at the cost of longer insertion and deletion times.

A hash map (eg. std::ext::hash_map) can provide at best O(1) lookup, insertion, and deletion - but it may perform much worse.

Share this post


Link to post
Share on other sites
Vorpy    869
Er, am I missing something, or does a hash table actually provide the requested O(1) lookup, insertion, and deletion, as swiftcoder just said? Used correctly, a hash table does have O(1) or amortized O(1) complexity for all those operations.

The thing that would make the structure imposssible would be if you also wanted the elements sorted. As long as no sort is required, insertion, deletion, and lookup are all O(1) in a hash table.

What part of the sweep and prune are you trying to implement? A hash table is definitely usable for keeping track of overlaping pairs. The best alternative I can think of would be a comparison based map, which is log(n) for all three operations. It might also be possible to distribute the overlap data to data structures maintained by each entity, for example when two entities overlap have the one with the lower id number track that overlap using a list or map (hmm...might require a little care if you remove the entity with the higher id from the world, if you want to reuse ids...).

Share this post


Link to post
Share on other sites
bronxbomber92    275
I've written (more like graciously copied) an implementation based on Box2D's PairManager (which in-turn is based on Pierre Terdiman's PairManager). It has O(1) insertion, removal and finding! So, I'm all good :-)

I'm having other problems with SAP ATM, but nothing related to this.

Thanks for your guys help!

Share this post


Link to post
Share on other sites
Sc4Freak    643
Quote:
Original post by bronxbomber92
I've written (more like graciously copied) an implementation based on Box2D's PairManager (which in-turn is based on Pierre Terdiman's PairManager). It has O(1) insertion, removal and finding! So, I'm all good :-)

I'm having other problems with SAP ATM, but nothing related to this.

Thanks for your guys help!

Care to share it with us? I'm sure that many people here would be extremely interested in a container which has O(1) insertion, deletion and lookup.

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Care to share it with us? I'm sure that many people here would be extremely interested in a container which has O(1) insertion, deletion and lookup.


Container that holds only numbers between 0..n or elements that can be mapped to those.

Insertion: set element[i] to value (offset calculation is one)
Deletion: clear element[i], again, only offset calculation
Lookup: is element[i]

A better wording would probably be no generic or no general purpose container.

In general, memory will be a consideration as well. Some operations can be improved at expense of memory use.

Share this post


Link to post
Share on other sites
>Care to share it with us? I'm sure that many people here would be extremely
>interested in a container which has O(1) insertion, deletion and lookup.

He's talking about this:
http://www.codercorner.com/PairManager.rar

- Pierre

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