libkdtree++ 0.2.1 review
Downloadlibkdtree++ is a C++ template container implementation of k-dimensional space sorting, using a kd-tree. Usage: A simple example
|
|
libkdtree++ is a C++ template container implementation of k-dimensional space sorting, using a kd-tree.
Usage:
A simple example program is provided in the ./examples directory
(/usr/share/doc/libkdtree++-dev/examples on Debian).
The library supports pkg-config. Thus, to compile with the library,
include < kdtree++/kdtree.hpp >
and append the output of `pkg-config libkdtree++ --cflags` to your $CPPFLAGS.
Each call to erase() and insert() unbalances the tree. It is possible that nodes will not be found while the tree is unbalanced.
You rebalance the tree by calling optimize(), and you should call it before you need to search the tree (this includes erase(value) calls, which search the tree).
It is ok to call insert(value) many times and optimize() at the end, but every erase() call should be followed with optimize().
Here are some key features of "libkdtreeplusplus":
sports an unlimited number of dimensions (in theory)
can store any data structure, provided the data structure provides operator[0 - k-1] to access the individual dimensional components (arrays, std::vector already do) and a std::less implementation for the type of dimensional components
has support for custom allocators
implements iterators
provides standard find as well as range queries
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.
provides a means to rebalance and thus optimise the tree.
exists in its own namespace
uses STL coding style, basing a lot of the code on stl_tree.h
libkdtree++ 0.2.1 search tags