DBSCAN in C++ for general and Android use I've implemented a templated DBSCAN for general use. At the moment, it's going to be used on Android through the JNI. I used Wikipedia's pseudocode and a little bit of the DBSCAN paper for reference. It's pretty naive, so I'm wondering how I can speed it up, and what I can do to make it perform reasonably well on a phone. How can I improve my code?

template &lt;typename T&gt;
    struct node {
        T val;
        bool visited;
        bool clustered;
        node() : visited(false), clustered(false) {}
    };

    template &lt;typename T&gt;
    using cluster = std::vector&lt;T&gt;;

    template &lt;typename T&gt;
    using adj_list = std::list&lt;node&lt;T&gt;*&gt;;

    template &lt;typename T&gt;
    using graph = std::map&lt;node&lt;T&gt;*, adj_list&lt;T&gt;&gt;;

    template &lt;typename T&gt;
    std::vector&lt;cluster&lt;T&gt;&gt; DBSCAN(T* const&amp; dataset, size_t const&amp; dataset_size, double const&amp; eps, size_t const&amp; min_pts, double(*distance_function)(T const&amp; lhs, T const&amp; rhs)) {

        std::vector&lt;node&lt;T&gt;&gt; node_list(dataset_size);
        for (auto i = 0; i &lt; dataset_size; ++i) {
            node_list[i].val = dataset[i];
        }

        graph&lt;T&gt; g;
        for (auto i = 0; i &lt; node_list.size(); ++i) {
            for (auto j = 0; j &lt; i; ++j) {
                if (distance_function(node_list[i].val, node_list[j].val) &lt; eps) {
                    g[&amp;node_list[i]].push_back(&amp;node_list[j]);
                    g[&amp;node_list[j]].push_back(&amp;node_list[i]);
                }
            }
        }

        std::vector&lt;cluster&lt;T&gt;&gt; clusters;
        cluster&lt;T&gt; C;
        for (node&lt;T&gt;&amp; n : node_list) {
            if (n.visited) continue;
            n.visited = true;
            adj_list&lt;T&gt; neighbour_pts = g[&amp;n];
            if (neighbour_pts.size() &gt;= min_pts) {
                expandCluster(n, neighbour_pts, C, g, min_pts);
                clusters.push_back(C);
                C = cluster&lt;T&gt;();
            }
        }

        return clusters;
    }

    template &lt;typename T&gt;
    void expandCluster(node&lt;T&gt;&amp; point, adj_list&lt;T&gt;&amp; neighbourhood, cluster&lt;T&gt;&amp; C, graph&lt;T&gt;&amp; g, unsigned const&amp; min_pts) {
        C.push_back(point.val);
        point.clustered = true;
        for (node&lt;T&gt;*&amp; n : neighbourhood) {
            if (!n-&gt;visited) {
                n-&gt;visited = true;
                adj_list&lt;T&gt; next_neighbourhood = g[n];
                if (next_neighbourhood.size() &gt;= min_pts) neighbourhood.splice(neighbourhood.end(), next_neighbourhood);
            }
            if (!n-&gt;clustered) {
                C.push_back(n-&gt;val);
                n-&gt;clustered = true;
            }
        }
    }
Naming things

Why you have all caps function name?

Why you have variable with capital letter in expandCluster()?
At first I thought it is template parameter i miss.

Use auto more often:

// looks ugly
for (node&lt;T&gt;*&amp; n : neighbourhood) {
}

// looks better
for (auto &amp; n : neighbourhood) {
     // adjust for * here
}

// or you can do with using
using mynode = node&lt;T&gt;;

// still looks better
for (mynode* &amp; n : neighbourhood) {
}


DBSCAN()

Make this a type:

template&lt;class T&gt;
using something = std::vector&lt;cluster&lt;T&gt;&gt;


Why you pass dataset_size by reference?

size_t is as big as the pointer, but there will be additional hidden dereference that will slow down the execution.
keep the const, remove &amp;

size_t const dataset_size


Do the same for all non class parameters.

dataset

probably I am wrong, but if you type this:

T* const&amp; dataset


like this:

const T* dataset


will be same, but more readable? Not sure what T is. If T is a container or array, why not just:

const CONTAINER dataset


Why you pass C like function pointers?

Do it with functor class. Or with std::function.

I am not very experienced with this, so I will do it with functor, but will add it into template parameters.

expandCluster()

more or less similar comments.