//...
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;
}
/...
Speed of STL Lists?
Author
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:
If not, what are some other available options (STL's vector, ect..)?
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.
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.
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).
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]
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]
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.
Author
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.
I'm just looking for other alternatives that provide O(1) insertion/removal/lookup.
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.
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...).
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...).
Author
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!
I'm having other problems with SAP ATM, but nothing related to this.
Thanks for your guys help!
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
