k-nearest neighbors using MATLAB with MEX

I have implemented kNN (k-nearest neighbors) as follows, but it is very slow. I want to get an exact k-nearest-neighbor, not the approximate ones, so I didn't use the FLANN or ANN libraries.

mexFindNN.cpp

#include 
using namespace std;

#include "mex.h"
#include 
#include 
#include 
#include 
#include 
#include 

struct Pair{
    int id;
    double value;
    Pair(int id, double value){
        this->id=id;
        this->value=value;
    }
};

struct PairCompare {
    bool operator()(Pair const &left, Pair const &right) {
        return left.value 
void FindNN(T *X, T *Y, int N, int d, int type, int inner_k, int outer_k, mxArray *innerM, mxArray *outerM){

    if(!type)//just inner_k
    {
        vector ir;
        vector jc;jc.push_back(0);
        vector pr;
        size_t num_ele=0;

        for(int i=0;i inner;
            for(int j=0;j ir,ir2;
        vector jc,jc2;jc.push_back(0);jc2.push_back(0);
        vector pr,pr2;
        size_t num_ele=0;
        size_t num_ele2=0;

        for(int i=0;i inner, outer;
        for(int j=0;j(X,Y,N,d,type,inner_k,outer_k,plhs[0],plhs[1]);
        }
        else
        {
            FindNN(X,Y,N,d,type,inner_k,outer_k,plhs[0],NULL);
        }
    }else if(clsID==mxDOUBLE_CLASS){
        int N=dims[0];
        int d=dims[1];
        double *X=(double *)mxGetPr(prhs[0]);
        double *Y=(double *)mxGetPr(prhs[1]);
        plhs[0]=mxCreateSparse(N,N,N*inner_k,mxREAL);
        if(type)
        {
            plhs[1]=mxCreateSparse(N,N,N*outer_k,mxREAL);
            FindNN(X,Y,N,d,type,inner_k,outer_k,plhs[0],plhs[1]);
        }
        else
        {
            FindNN(X,Y,N,d,type,inner_k,outer_k,plhs[0],NULL);
        }
    }
}

ConstructNNGraph2.m

```
function [innerG,outerG]=ConstructNNGraph2(X,Y,inner_k,outer_k)
[N,d]=size(X);
if isempty(Y)
Y=ones(N,1);
end
type=0;
if outer_k>0
type=1;
end
if(type)
[innerG,outerG]=mexFindNN(X,Y,1,inner_k,outer_k);
innerG = max(innerG, innerG');
outerG = ma

Your code appears to be very C-like with some C++. I'll just give some feedback in regards to that:

-
Try not to use using namespace std.

-
` is a C library; use with C++.

-
In C++, prefer std::size_t over size_t from C.

-
For testing algorithms such as these, it's good to provide your main() to show how you're doing your testing. Although the code there may already work, you cannot always determine how well an algorithm works if there is no test code.

-
Instead of creating a new Pair structure, consider using std::pair from the STL. It is more idiomatic C++, and it already comes with a few functions and operator overloads.

Moreover, Pair is not a very descriptive name in relation to this program. All that's known is that it holds an int and a double.

Here's how you can change this with std::pair`:

// this creates an alias for a new std::pair type
// this is just a generic type name for demonstration
typedef std::pair SomePair;

// create a new std::pair
SomePair newPair;

// pass it to a function
void someFunc(SomePair pair /* ... */) {}

-
For better readability, keep operators and operands separated by whitespace:

for (int i = 0; i < 10; ++i) {}

-
In this function:

void FindNN(T *X, T *Y, int N, int d, int k)

It's not clear what these variables are for as they're single-character. An exception to this is loop counters, which can be single-character.

StackExchange Code Review Q#33269, answer score: 10