This particular A* implementation I am starting on will be operating on a 3D grid of a large size, where every node represents a cube in that 3D grid. What is the best data structure for storing refrences to the nodes that have already been traversed in this case? This data structure would ideally be able to work well for both very small and very large search spaces.

The idea I came up with would be a dynamically growing octree, that would begin with just the one start node and would grow over time and add additional layers of parent nodes as the search space increases. Performance is critical, so I need to know if there's a better way to do this.

Thanks for any help!

Hmm..I haven't known Octree a quite well. Have you tried the Priority Queue or even simple vector?