# Cover Trees

A cover tree is a tree data structure used for the partitiong of metric spaces to speed up operations like nearest neighbor, $k$-nearest neighbor, or range searches. In this blog post, I introduce cover trees, their uses, their properties, and I measure the effect of the dimension of the metric space on the run-time in an experiment with synthetic data.

# Implicit Type Conversions Gone Wrong, C++ Edition

Consider the following setup:

#include <cstddef>
using namespace std;
// ...
size_t n = 100;
size_t* array = new size_t[n];

The goal is to set every element of the array to the fixed value x.

In C++, an idiomatic way to solve this problem are the functions std::fill (link to documentation) and std::fill_n (link to documentation) from the STL header algorithm. In addition to the fixed value x, std::fill requires a pair of output iterators specifying a half-open range as its arguments whereas the additional argument to std::fill_n is an output iterator pointing to the first element and the length of the container. That is, we could assign to the elements of the array above as follows:

#include <cstddef>
#include <algorithm>
using namespace std;
// ...
size_t n = 100;
size_t* array = new size_t[n];

fill(array, array+n, x);
fill_n(array, n, x);

What made me write this blog post is the following line of code:

fill_n(array, array+n, x);

Here, I accidentally used std::fill_n in place of std::fill but the code still compiles because of the automatic, implicit type conversion (type coercion) from std::size_t* to std::size_t. With warnings enabled (-Wextra -Wall -std=c++11 -pedantic) neither g++ 4.8.5 nor clang++ 3.5 warn about this line and yet this piece of code causes a segmentation fault on my computer whenever it is executed.