The Node Container

Each node in the orthtree has a spatial index and data. For a static tree, one can store the nodes in an array, sorted by the spatial indices. One can then find a node in logarithmic time with a binary search. For a dynamic tree, storing the nodes in an array may not efficient because inserting or deleting a node has linear complexity in the size of the array. One can mitigate this by caching the insertions and deletions. Another drawback to storing the nodes in an array is that insertions and deletions invalidate pointers. If one were storing iterators to adjacent neighbors, this information would need to be recomputed following an insertion or deletion. A different approach (and the one that we have taken) is to store the nodes in a paired associative container. We use std::map . The node is a std::pair with first being a const spatial index and second being the data. A node can still be found in logarithmic time. Inserting new nodes does not invalidate any iterators. Deleting a node only invalidates iterators to the deleted node. Finally, when iterating through the nodes, they are ordered according to the spatial index.