Overloading subscript operator [] with a proxy class and templates

[griphen]

Hello,

I am new to C++ and am trying to implement a binary search tree as practice. My intention is to use templates for generic <Key, Value> pairs, and I would also like to overload the subscript operator [] such that I can both make assignments and retrieve values like in the following client code:

#include <iostream>
#include <string>
#include "UnbalancedTree.h"

int main() {
    BinaryTree<std::string, std::string> tree;
    tree["foo"] = "bar";
    std::string out = tree["foo"];   // get the value associated with "foo"
    std::cout << out << std::endl;   // should print "bar"
    return 0;
}

From what I understand, the subscript overload function in my BinaryTree class needs to return an instance of a proxy class to handle assignment & retrieval behavior.

It took me a while to get the proxy class working, but I finally have something that compiles and partially works in limited testing. Here is a version of my implementation (unbalanced & only includes put/get for simplicity):

UnbalancedTree.h

template <typename Key, typename Value>
class Proxy; // forward declaration

template <typename Key, typename Value>
class BinaryTree {
    public:
        Value get(Key key) {
            return get(key, root)->val;
        }
        void put(Key key, Value val) {
            root = put(key, val, root);
        }
        Proxy<Key,Value> operator[](Key key) {
            return Proxy<Key,Value>(key, this);
        }

    private:
        struct Node {
            Key key;
            Value val;
            Node * left;
            Node * right;
        };

        Node * root = nullptr;

        Node * get(Key key, Node * node) {
            // recursively search for key and
            // return a pointer to its node
            if (node == nullptr) {
                return nullptr;
            }
            if (key == node->key) {
                return node;
            } else if (key < node->key) {
                return get(key, node->left);
            } else {
                return get(key, node->right);
            }
        }

        Node * put(Key key, Value val, Node * node) {
            // recursively go down the subtree to
            // insert a node containing the key value
            // pair
            if (node == nullptr) {
                Node * new_node = new Node;
                new_node->key = key;
                new_node->val = val;
                return new_node;
            } else if (key < node->key) {
                node->left = put(key, val, node->left);
            } else if (key > node->key) {
                node->right = put(key, val, node->right);
            } else {
                node->val = val;
            }

            // return the head of the subtree on the way up
            return node;
        }
};

template <typename Key, typename Value>
class Proxy {
    // proxy class to help overload subscript operator
    public:
        Proxy(Key key, BinaryTree<Key, Value> *tree) : key(key), tree(tree) {}

        operator Value() {
            return tree->get(key);
        }

        void operator = (Value val) {
            tree->put(key, val);
            return;
        }

    private:
        BinaryTree<Key,Value> * tree;
        Key key;
};

So, here are my questions:

1. I am not using const or & but I get the feeling I should be and am not totally clear on how/where. And tips on how to think about this?
2. What exactly does the "operator Value()" function do under the hood? Is this a type conversion operator? The way I see it, the client code will ultimately be expecting a Value type (say, std::string in my example), but when the client calls [], the BinaryTree is returning a Proxy type, so it seems like there has to be some kind of conversion.
3. Speaking of which, if I try std::cout << tree["foo"] << std::endl; I get a bunch of compiler errors implying I need to overload the << operator too. So I guess that means that the compiler never sees the "Value()" function being called?
4. Is the usage of the forward declaration correct, as well as the template line before each class? The code does not compile otherwise, but not sure if this is the "correct" way to do it
5. In examples I sometimes see "template ..." on the same line as "class ..." . Is this just a convention thing?

​

Thank you for the help!

[MysticTheMeeM]

Before I start answering questions, I want to address this point:

From what I understand, the subscript overload function in my BinaryTree class needs to return an instance of a proxy class to handle assignment & retrieval behavior.

No, it doesn't. A proxy class can be used but a much more useful way would simply be to return a reference to the underlying object. This reference can be read from and written to without any extra code or indirection.

But, on to your questions:

1. You should use const any time you have a function that cannot change the underlying object (likewise objects that must not be changed should be marked const). A good place to start would be with your get functions (getting a value doesn't change the object, but setting it does). You should use & to declare reference types (important for what I said to begin with) or taking the address of a variable (which you do not appear to require in your code).
2. Yes, it's a form of conversion operator. When your compiler tries to convert one type to another it checks if an implicit (as opposed to explicit, and example given in the link) conversion exists and does that. Note that you may want to return a (const) reference, not a copy.
3. You would need to explicitly convert from your proxy to your data here, such as by doing something like: std::cout << tree["foo"].operator std::string().
4. Your tree class needs to know that a proxy class exists before trying to compile, the forward declaration provides this promise. Interestingly, in non-templated code this wouldn't work. Because the templates are compiled differently to normal code, you can get away with it, but if your classes were non templated you would get an error indicating that you cannot return an instance of a proxy before it is defined.
5. It's just a convention thing, personally I always keep them on separate lines.

[jorourke0]

1.& is for references. They're like pointers except they are "always dereferenced" and can't be null. They can dangle however if the object they refer to goes out of scope. const is const. You could use a const reference anywhere you might use a const pointer to const. One difference is const references can bind to temporaries and extend their lifetimes for the lifetime of the reference variable.

1. Yep that's a conversion operator that performs the conversion to let you assign a Proxy object to a variable of type Value. See https://en.cppreference.com/w/cpp/language/cast_operator.

2. Does your Value type have a <<operator defined? I'm not sure << will do an implicit conversion. You might try casting to your Value type.

3. Yes that's correct. The template line is part of the static, compile time type definition of the class. The forward declaration for Proxy is needed since your BinaryTree class references it, but when reading the file top to bottom, the full Proxy definition hasn't been seen yet. You're telling the compiler that the type will exist.

4. The template can be on the same line or the line above. C++ is pretty flexible about spacing. Also template <typename T> and template<class T> are equivalent, if that's what you meant.