🔒 Locked

STL sorted container

Started by RunningInt Dec 20, 2005 at 1:38 PM 8 replies 2.1k views

Original Post

Dec 20, 2005 at 1:38 PM

Hi, I am trying to optimise my C++ A* algorithm but cannot find what I am after in the standard template library, but that might just indicate my lack of search skills. I need a container in which I can easily get the smallest element. The most efficient way to do this in my mind would be to use a sorted container. If I wasn't bothered about the speed I would just use an stl vector and use sort() each time I inserted an element. But I suspect it would be much more efficient to actually insert the element in the correct place. So vector is out of the question. I came across this STL compliant "sorted_vector": http://www.codeproject.com/vcpp/stl/sorted_vector.asp But it points out the fact that insertions are rather slow being that it is a vector and all. What would seem the best solution to me is a sorted linked list. This allows insertion in O(n) and obtaining the smallest element in O(1). But I am not aware of an STL implementation of a sorted linked list. Could write my own but there is always that luxury of knowing a container is properly optimised when it is official.

Trap

Dec 20, 2005 at 1:42 PM

What you are looking for is std::priority_queue or (for advanced users) make_heap, push_heap and pop_heap.

Or for expert users (write it yourself): general d-heaps, fibonacci heaps, radix heaps or multilevel buckets

taby

Dec 20, 2005 at 2:06 PM

10 out of 10 times, if being able to define sort order through overloading the class' operator<, the std::set works beautifully.

If you need to allow for duplicate objects, std::multi_set.

It is an extremely efficient container designed for your type of need.

However, it should be noted that the other containers mentioned by Trap are as equally important to experiment with as well!

It all depends on how you insert/look up/delete elements in the container.

Since the time complexity of each of these containers' main operations is set in the standard, once you find a perfect combination for a particular type of data storage/access, similar situations are guaranteed to perform the same way using the same container.

Iftah

Dec 20, 2005 at 2:20 PM

a quick review of imoprtant containers:

unsorted:
- vector: random access
- list: iterating access, O(1) insert/remove

sorted:
- priority_queue (heap) O(1) to pop the smallest, O(log(n)) to insert
- set (sorted tree) O(log(n)) to pop any node, O(log(n)) to insert

heap is most efficient for popping the minimum node.

if you are unfamiliar with complexity what it means is:

O(1) - constant number of oprations
O(log(n)) - for a container with n items, this operation takes at most M*log(n) (M is a constant). for example a inserting to "set" with 10000 nodes will take about M*5 and inserting to "set" with 100000000 nodes will take M*9
O(n) - container with n items, this operation takes at most M*n for example finding the maximum of an unsorted list.
O(n^2) - at most M*n^2, for example finding the maximum in an unsorted matrix
O(n*log(n)) - for example the most efficient sorting of arrays.

Iftah.

Trap

Dec 20, 2005 at 2:32 PM

For an efficient implementation of A*/Dijkstra one needs these operations to be fast:
a) insert
b) removeMinimum
c) decreaseValueOfSomethingInQueue

c) is often ignored, but is important too. Inserting a new entry for every improvement you find guarantees bad perfomance on complete graphs (on grids/roadmaps/maps it is not that bad).

std::priority_queue doesn't allow c) but is very easy to use that's why recommended it.

[Edited by - Trap on December 20, 2005 2:32:11 PM]

markr

Dec 20, 2005 at 3:12 PM

I did this - I used a multi_set with the key the node cost - that worked a treat.

Technically it's a priority queue. multi_set behaves in the same way.

Mark

snk_kid

Dec 20, 2005 at 3:19 PM

Quote:
Original post by Anonymous Poster
Great, a game development forum software can't parse inline code..

i think that is only the case for anonymous posters, if you where registered member you could have used < tt > < / tt > or [ code ] [ / code ] for inline or small snippets of code.

Agony

Dec 20, 2005 at 3:29 PM

While the other suggestions are probably better, it isn't too hard to use a basic linked list in a sorted fashion. Just make sure than every time you need to insert an item, just use std::lower_bound() (found in ) to figure out where to insert it. Maybe something like this:

#include <list>#include <algorithm>template <class T>std::list<T>::iterator list_insert_sorted(std::list<T>& lst, const T& x = T()){  return lst.insert(std::lower_bound(lst.begin(), lst.end(), x), x);}template <class T, class Pred>std::list<T>::iterator list_insert_sorted(std::list<T>& lst, const T& x = T(), Pred pr){  return lst.insert(std::lower_bound(lst.begin(), lst.end(), x, pr), x);}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.