libkdtree++ is a C++ template container implementation of k-dimensional space sorting, using a kd-tree. It sports a theoretically unlimited number of dimensions, and can store any data structure. Provided the data structure, it provides operator- k-1 to access the individual dimensional components (arrays, std::vector already do) and a std::less implementation for the type of dimensional components. It has support for custom allocators, implements iterators, and provides standard find as well as range queries. It has amortised O(lg n) time (O(n lg n) worst case) on most operations (insert/erase/find optimised) and worst-case O(n) space, and also provides a means to rebalance and thus optimise the tree.
