Template with comparator function with custom parameter

Question

I am working on a data structure and I want it to have comparison function, that can be passed to the constructor, the same way as stl data structures (set, queue, etc.) work. I also want a default function provided in the constructor.

The problem is, that the query to the structure is a function template, that takes custom type as a parameter. But I don't know how to provide the default comparison function if I don't know what type the query will be. Is there a way to do this?

This works if the Query is the same as the NodeType (Query is useless in this example):

template<class NodeType, class Query = NodeType>
inline float eucDistance(const Query * p1, const NodeType * p2) {
    ...
}


template<class NodeType, typename Comp = decltype(eucDistance<NodeType>)>
class KDTree {

    Comp* distance;

public:

    KDTree(Comp comaprator = &eucDistance<NodeType>) : distance(comaprator) {

    }

    template<class Query = NodeType>
    NodeType * nearestNeighbor(const Query *query) {
        ...
        float tmp = distance(query, sth); 
        //I want something like distance<NodeType, Query>(query, sth); 
        ...
   }
}

But I would like to do something like this:

class Point; //some type that the tree contains

KDTree<Point> tree;
Point p1;
Point *p = tree.nearestNeighbor(&p1); //this works with the given example
...
vec3 vec = ...; //some different type as a query
p = tree.nearestNeighbor<vec3>(vec); // <-- this is what I would like to do

If each call to query can have a different type as argument that affects the comparator called, then instead of passing the comparator to the class, shouldn't the comparator be passed to the function? — legends2k, Mar 28 '14 at 02:58
No, the comparator will be the same for different queries. It will be different only for different instances of the class. The comparator will call only `operator[]` on the query, so it can easily accept different types. — Jaa-c, Mar 28 '14 at 03:04
In the above example, since `KDTree` has `Point` as `NodeType` type the `nearestNeighbour(&p1)` works since the types match; this means that when the `NodeType` passed to the queried function is different from the one passed to the class' constructor, then it won't work `nearestNeighbour(vec)`. Is that correct? — legends2k, Mar 28 '14 at 03:09
Yes, that is correct. I want to know if it is a way how to make the comparator work with different types. Obviously it can't be passed to the constructor the way I do it now, that's what I haven't figured out... — Jaa-c, Mar 28 '14 at 03:15

score 1 · Answer 1 · edited May 23 '17 at 12:28

template<typename Query, typename NodeType = Query>
inline float eucDistance(const Query * p1, const NodeType * p2) {
    ...
}

class KDTree {
public:
    template<typename Query = NodeType, typename Comparator>
    NodeType * nearestNeighbor(const Query *query, Comparator comp) {
        ...
        float tmp = comp(query, sth);
        ...
   }
}

This code takes in the comparator at the member function level due to which it can take on different type of nodes. Also the template type deduction will work; so instead of calling function like thus comp<T>(a, b); just comp(a, b) should work.

The main difference between your code and C++ standard library functions (algorithms) taking a comparator argument is that they don't enforce them to be pointers or rather C-style pointer to functions. Instead they use functors.

Take std::for_each which calls a functor for the elements passed; it takes a functor thus

template <typename InputIter, typename UnaryFunc>
UnaryFunc std::for_each(InputIter first, InputIter last, UnaryFunc func)
{
    for (; first != last; ++first)
        func(*first);
    return func;
}

If you notice, there're no pointers. It calls func with the operator (); the beauty of this is that it works for both C-style function pointers and also C++ style functors i.e. a struct with an operator() defined. Also notice that the template type used for the functor is agnostic of what type the functor accepts.

I now this is a possibility, but it's really not practical... if you make the queries on multiple places in your code, you need to have the comparator available everywhere, which adds additional code and complexity... — Jaa-c, Mar 28 '14 at 03:38
Usually utility functions and standalone algorithms, like the Euclidean distance function, are in a common header which can be called/referred to from anywhere. — legends2k, Mar 28 '14 at 03:59

score 0 · Answer 2 · answered Mar 28 '14 at 07:54

0

You should use polymorphic functor instead of plain function, for example

struct eucDistance
{
    float operator()(Point, Point) const;
    float operator()(vec3, Point) const;
    ...
};

BTW, you really should take a look at Boost.Geometry and it's R-tree design.

answered Mar 28 '14 at 07:54

Jamboree

5,139
2
16
36

This still makes me declare all acceptable types in advance, I'm looking for a generic solution if possible. Thanks for the link, I'll look at it. – Jaa-c Mar 28 '14 at 12:17

Template with comparator function with custom parameter

2 Answers2