A key-value datastructure with fast (on average) member move and nearest neighbors search? I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N neighbors in a range surrounding a given key) as fast as possible in terms of search algorithmic complexity (on average). Also I need a fast (on average) remove-insert or key update mechanism in that datastructure. I wonder what is such structure?
An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.