You say you only allocate memory once, but you also say you're clearing an std::set each time, which implies to me that you're also filling it each time, yes? Adding elements to an std::set is going to cause an allocation as it creates a new node to store the element in.

I came across this yesterday, which could perhaps be of use: Pooled Allocators for The STL.

Quote:Original post by intrest86
Ya know, you are exactly right. For some reason it didn't occur to me that it wouldn't work like its .Net counterpart and reserve memory for that. I guess I need to research how to right an allocator that will manage a memory pool for my set.

Just to clarify something as it was only hinted all standard library containers are parameterized by allocator type, generally the last template type parameter and defaults to using std::allocator that generally uses global operators new/delete via explicit invocation & placement new operator (de/allocation & construction/destruction is separated for efficency).

This means you can write or use custom allocator types that uses different memory models/schemes and as mentioned already the boost library has some packaged STL compliant allocator types, example usage:

typedef boost::fast_pool_allocator<foo> foo_alloc;typedef std::set< foo, std::less<foo>, foo_alloc > foo_set;

Note that in general allocators are not really allocators of T (most of the time), they are generally *rebound* (at compile-time) into an allocator of something else internally because generally containers allocate nodes not just T so you can assume that internally a container will do something like as follows:

template < typename Tp >struct foo_node {   //.......   Tp value;};template < typename Tp, typename Alloc = std::allocator<Tp> >class foo_container {   typedef typename Alloc::template rebind< foo_node<Tp> >::other node_allocator;   struct foo_impl : node_allocator { //empty base optimization (EBO)         //....   };   foo_impl imp;   //....   };

Quote:Original post by Extrarius
Doesn't Boost include such allocators?
I just checked and found boost::pool_allocator and a few variations.

So far they are only 2, pool_allocator & fast_pool_allocator. Don't let the names fool you [smile] generally pool_allocator is slightly better for containers that allocate large contiguous chunks of memory as is the case with std::vector.

fast_pool_allocator is slightly better with containers that allocate smaller non contiguous chunks. I found i got superb performance/efficiency with a combination of std::deque & boost::fast_pool_allocator.

Quote:Original post by intrest86
If anyone is still reading this post, am I an idiot for using a set for an A* open list? I'm doing a ton of inserts and erases on it, and those are the most expensive operations I am doing right now.

I use an std::deque, with the default STLPort allocator. Getting the next node is just a front/pop_front, and I just use a linear search to find where to insert new nodes. I have no performance problems yet, and if I do I'll try a binary search there instead.

If you write your A* algorithm in a fairly generic way and don't refer to the data types at all in the main function, you should be able to swap the implementation containers around quite easily and see what works best for you.