Using templates to specify member variable

user_13076642 0
Viewed 61

Here I have a binary search tree class with a class template:

template <class T>
class Tree {
    T* root_ptr;
public:
    void Insert(T* ptr_to_value);
};

template <typename T>
void Tree<T>::Insert(T* ptr_to_value) {
    T** temp = &root_ptr;
    while (*temp) {
        if (ptr_to_value->name <= (*temp)->name)
            temp = &(*temp)->left_ptr;
        else
            temp = &(*temp)->right_ptr;
    }
    (*temp) = ptr_to_value;
}

But it refers to name variable of T class, and I may want comparison to be made with other member variable. I want something like template </*some type*/ data> so that I could initialize tree like Tree<Node, name>, or Tree<Node, Node.name>.

templates class c++
2 Answers

Template parameters don't have to be types; they can be certain non-types too, as long as they're compile-constants. Pointers-to-members qualify!

template <class T, auto Ptr>
class Tree {
    T* root_ptr;
public:
    void Insert(T* ptr_to_value);
};

template <typename T>
void Tree<T>::Insert(T* ptr_to_value)
{
    T** temp = &root_ptr;
    while (*temp) {
        if (ptr_to_value->*Ptr <= (*temp)->*Ptr)
            temp = &(*temp)->left_ptr;
        else
            temp = &(*temp)->right_ptr;
    }
    (*temp) = ptr_to_value;
}

// Tree<Foo, &Foo::name> t;
// t.insert(&val);

If you can't use auto template parameters, because your C++ is too old, you'll need to spell it out:

template <class T, class T2, T2 Tree<T>::*Ptr>
class Tree {

Then:

// Tree<Foo, std::string, &Foo::name> t;
// t.insert(&val);

Note, though, that Visual Studio 16.6.1 has bugs with passing pointers-to-members as template arguments, only accepting the auto Ptr variety at present.

Also, come to think of it, this variant might not work as I've spelt Tree<T> before it's known.

It's more conventional to pass a comparator as template argument, so someone can define the whole <= bit rather than being limited to naming a single data member. I suggest you look into how standard map and set work.

user_43862780

Instead of doing the comparison directly in your Insert method, you could have your Tree hold a comparison function. This is the approach that the standard containers take.

For example:

template <typename T, typename Comp = std::less<T>>
class Tree {
    T* root_ptr;
    Comp comp;
public:
    Tree(Comp comp = Comp{})
      : root_ptr{nullptr},
        comp{comp}
    {
    }
    void Insert(T* ptr_to_value);
};

template <typename T, typename Comp>
void Tree<T, Comp>::Insert(T* ptr_to_value) {
    T** temp = &root_ptr;
    while (*temp) {
        if (comp(*ptr_to_value, **temp))
            temp = &(*temp)->left_ptr;
        else
            temp = &(*temp)->right_ptr;
    }
    (*temp) = ptr_to_value;
}

struct Foo {
    int foo;
    Foo* left_ptr;
    Foo* right_ptr;
};

bool operator<(const Foo& left, const Foo& right) {
    return left.foo < right.foo;
}

struct CompareFoosGreater {
    bool operator()(const Foo& left, const Foo& right) {
        return left.foo > right.foo;
    }
};

int main() {
    // Defaults to using std::less, which compares
    // objects using the < operator
    Tree<Foo> foo_tree_less;
    // Use a custom comparator
    Tree<Foo, CompareFoosGreater> foo_tree_greater;
}

This has a couple of advantages over using a pointer to member:

  1. You can compare multiple attributes
  2. You can change the order elements are stored in
  3. The functionality can be encoded entirely in your type
user_41515990
Related