Stack Exchange
C++ : operator<< fails to compile
I'm coding a B-tree in C++, but when I'm overloading operator<<, it fails to compile.
My code:
#include <cassert>
#include <cstddef>
#include <iostream>
#include <memory>
#include <vector>
#include <utility>

template <typename T, std::size_t t>
class BTree;

template <typename T, std::size_t t>
std::ostream& operator<<(std::ostream&, const BTree<T, t>&);

template <typename T, std::size_t t>
std::ostream& operator<<(std::ostream& os, const typename BTree<T, t>::Node& node);

template <typename T, std::size_t t>
class BTree {
    static_assert(t >= 2);
    class Node {
        std::size_t n = 0;
    public:
        bool leaf = true;
        std::vector<T> key;
        std::vector<std::unique_ptr<Node>> child;
        void setN(std::size_t N) {
            n = N;
            key.resize(n);
            if (!leaf) {
                child.resize(n + 1);
            }
        }

        [[nodiscard]] std::size_t getN() const {
            return n;
        }

        [[nodiscard]] bool isFull() const {
            return n == 2 * t - 1;
        }

        friend std::ostream& operator<< <T, t>(std::ostream& os, const BTree<T, t>::Node& node);
    };

    std::unique_ptr<Node> root;

    std::pair<const Node*, std::size_t> Search(const Node* x, const T& k) const {
        std::size_t i = 0;
        while (i < x->getN() && k > x->key[i]) {
            i++;
        }
        if (i < x->getN() && k == x->key[i]) {
            return {x, i};
        } else if (x->leaf) {
            return {nullptr, 0};
        } else {
            return Search(x->child[i].get(), k);
        }
    }

    void SplitChild(Node* x, std::size_t i) {
        if (!x) {
            return;
        }
        auto y = x->child[i].get();
        if (!y) {
            return;
        }
        assert(!x->isFull() && y->isFull());
        auto z = std::make_unique<Node>();
        z->leaf = y->leaf;
        z->setN(t - 1);
        for (std::size_t j = 0; j < t - 1; j++) {
            z->key[j] = y->key[j + t];
        }
        if (!y->leaf) {
            for (std::size_t j = 0; j < t; j++) {
                z->child[j] = std::move(y->child[j + t]);
            }
        }
        x->setN(x->getN() + 1);
        for (std::size_t j = x->getN() + 1; j >= i + 1; j--) {
            x->child[j + 1] = std::move(x->child[j]);
        }
        x->child[i + 1] = std::move(z);
        for (std::size_t j = x->getN() + 1; j >= i + 1; j--) {
            x->key[j] = x->key[j - 1];
        }
        x->key[i] = y->key[t];
        y->setN(t - 1);
    }

    void InsertNonFull(Node* x, const T& k) {
        std::size_t i = x->getN();
        if (x->leaf) {
            x->setN(i + 1);
            while (i < x->getN() && k < x->key[i]) {
                x->key[i + 1] = x->key[i];
                i--;
            }
            x->key[i + 1] = k;
        } else {
            while (i < x->getN() && k < x->key[i]) {
                i--;
            }
            i++;
            if (x->child[i]->isFull()) {
                SplitChild(x, i);
                if (k > x->key[i]) {
                    i++;
                }
            }
            InsertNonFull(x->child[i].get(), k);
        }

    }

public:
    BTree() {
        root = std::make_unique<Node>();
    }

    [[nodiscard]] std::pair<const Node*, std::size_t> Search(const T& k) const {
        return Search(root.get(), k);
    }

    void Insert(const T& k) {
        if (root->isFull()) {
            auto s = std::make_unique<Node>();
            s->leaf = false;
            s->setN(0);
            s->child[0] = std::move(root);
            root = std::move(s);
            SplitChild(root.get(), 0);
            InsertNonFull(root.get(), k);
        } else {
            InsertNonFull(root.get(), k);
        }
    }


    friend std::ostream& operator<<<> (std::ostream&, const BTree<T, t>&);

};

template <typename T, std::size_t t>
std::ostream& operator<<(std::ostream& os, const typename BTree<T, t>::Node& node) {
    if (node->leaf) {
        for (std::size_t i = 0; i < node->getN() - 1; i++) {
            os << node->key[i] << ' ';
        }
        os << node->key[node->getN() - 1];
    } else {
        for (std::size_t i = 0; i < node->getN(); i++) {
            os << *node->child[i] << ' ' << node->key[i] << ' ';
        }
        os << *node->child[node->getN()];
    }
    return os;
}

template <typename T, std::size_t t>
std::ostream& operator<<(std::ostream& os, const BTree<T, t>& bt) {
    os << *(bt.root) << '\n';
    return os;
}

int main() {
    BTree<int, 2> tree;
    tree.Insert(1);
    std::cout << tree;

}

This is the first line of the complaint from my compiler (I won't post the full error output because it has 200+ lines):
/mnt/c/Users/kim/CLionProjects/PPP/main.cpp: In instantiation of ��std::ostream& operator<<(std::ostream&, const BTree<T, t>&) [with T = int; long unsigned int t = 2; std::ostream = std::basic_ostream<char>]��:
/mnt/c/Users/kim/CLionProjects/PPP/main.cpp:171:18:   required from here
/mnt/c/Users/kim/CLionProjects/PPP/main.cpp:164:8: error: no match for ��operator<<�� (operand types are ��std::ostream�� {aka ��std::basic_ostream<char>��} and ��BTree<int, 2>::Node��)
  164 |     os << *(bt.root) << '\n';
      |     ~~~^~~~~~~~~~~~~

bt is BTree<T, t>, bt.root is std::unique_ptr<BTree<T, t>::Node>, so I think the dereferencing operator should match with operator<<(std::ostream& os, const typename BTree<T, t>::Node& node), but my compiler still isn't happy.
How can I fix this? Thanks in advance.

I believe T and t in typename BTree<T, t>::Node can't be inferred

I prefer providing a public member function void print(std::ostream&) const; that the std::ostream& operator<<(std::ostream&, typename BTree<T, t>::Node const&) can then just call the node.print(out); and return out; and the heavily lifting is done in the print method.  I don't like my C++ to have any friends.  Lonely, lonely C++.

@Eljay But the senior programmer in my team told me that it is bad practice to use print instead of operator<< because the purpose of operator overloading is to achieve zero-overhead generic programming, rather than a function call, isn't it true?

You can inline the operator<<, and then you'll have zero overhead.

operator<< for the inner class Node is defined as template, but the template parameters can't be deduced because of non-deduced context.

In the following cases, the types, templates, and non-type values that are used to compose P do not participate in template argument deduction, but instead use the template arguments that were either deduced elsewhere or explicitly specified. If a template parameter is used only in non-deduced contexts and is not explicitly specified, template argument deduction fails.

The nested-name-specifier (everything to the left of the scope resolution operator ::) of a type that was specified using a qualified-id:


You can define it as non-template, and define it in the class definition. E.g.
template <typename T, std::size_t t>
class BTree {
    ...
    class Node {
        ...
        friend std::ostream& operator<< (std::ostream& os, const Node& node) {
            if (node->leaf) {
                for (std::size_t i = 0; i < node->getN() - 1; i++) {
                    os << node->key[i] << ' ';
                }
                os << node->key[node->getN() - 1];
            } else {
                for (std::size_t i = 0; i < node->getN(); i++) {
                    os << *node->child[i] << ' ' << node->key[i] << ' ';
                }
                os << *node->child[node->getN()];
            }
            return os;
        }
        ...
    };
    ...
};


Wow, C++ templates are so obscure and dumb.
Working code:
#include <cassert>
#include <cstddef>
#include <iostream>
#include <memory>
#include <vector>
#include <utility>

template <typename T, std::size_t t>
class BTree {
    static_assert(t >= 2);
    class Node {
        std::size_t n = 0;
    public:
        bool leaf = true;
        std::vector<T> key;
        std::vector<std::unique_ptr<Node>> child;
        void setN(std::size_t N) {
            n = N;
            key.resize(n);
            if (!leaf) {
                child.resize(n + 1);
            }
        }

        [[nodiscard]] std::size_t getN() const {
            return n;
        }

        [[nodiscard]] bool isFull() const {
            return n == 2 * t - 1;
        }

        friend std::ostream& operator<<(std::ostream& os, const BTree<T, t>::Node& node) {
            if (node.leaf) {
                for (std::size_t i = 0; i < node.getN() - 1; i++) {
                    os << node.key[i] << ' ';
                }
                os << node.key[node.getN() - 1];
            } else {
                for (std::size_t i = 0; i < node.getN(); i++) {
                    os << *node.child[i] << ' ' << node.key[i] << ' ';
                }
                os << *node.child[node.getN()];
            }
            return os;
        }
    };

    std::unique_ptr<Node> root;

    std::pair<const Node*, std::size_t> Search(const Node* x, const T& k) const {
        std::size_t i = 0;
        while (i < x->getN() && k > x->key[i]) {
            i++;
        }
        if (i < x->getN() && k == x->key[i]) {
            return {x, i};
        } else if (x->leaf) {
            return {nullptr, 0};
        } else {
            return Search(x->child[i].get(), k);
        }
    }

    void SplitChild(Node* x, std::size_t i) {
        if (!x) {
            return;
        }
        auto y = x->child[i].get();
        if (!y) {
            return;
        }
        assert(!x->isFull() && y->isFull());
        auto z = std::make_unique<Node>();
        z->leaf = y->leaf;
        z->setN(t - 1);
        for (std::size_t j = 0; j < t - 1; j++) {
            z->key[j] = y->key[j + t];
        }
        if (!y->leaf) {
            for (std::size_t j = 0; j < t; j++) {
                z->child[j] = std::move(y->child[j + t]);
            }
        }
        x->setN(x->getN() + 1);
        for (std::size_t j = x->getN(); j >= i && j < x->getN(); j--) {
            x->child[j + 1] = std::move(x->child[j]);
        }
        x->child[i + 1] = std::move(z);
        for (std::size_t j = x->getN(); j >= i && j < x->getN(); j--) {
            x->key[j] = x->key[j - 1];
        }
        x->key[i] = y->key[t - 1];
        y->setN(t - 1);
    }

    void InsertNonFull(Node* x, const T& k) {
        std::size_t i = x->getN();
        if (x->leaf) {
            x->setN(i + 1);
            while (i - 1 < x->getN() && k < x->key[i - 1]) {
                x->key[i] = x->key[i - 1];
                i--;
            }
            x->key[i] = k;
        } else {
            while (i - 1 < x->getN() && k < x->key[i - 1]) {
                i--;
            }
            if (x->child[i]->isFull()) {
                SplitChild(x, i);
                if (k > x->key[i]) {
                    i++;
                }
            }
            InsertNonFull(x->child[i].get(), k);
        }

    }

public:
    BTree() {
        root = std::make_unique<Node>();
    }

    [[nodiscard]] std::pair<const Node*, std::size_t> Search(const T& k) const {
        return Search(root.get(), k);
    }

    void Insert(const T& k) {
        if (root->isFull()) {
            auto s = std::make_unique<Node>();
            s->leaf = false;
            s->setN(0);
            s->child[0] = std::move(root);
            root = std::move(s);
            SplitChild(root.get(), 0);
            InsertNonFull(root.get(), k);
        } else {
            InsertNonFull(root.get(), k);
        }
    }

    friend std::ostream& operator<< (std::ostream& os, const BTree<T, t>& bt) {
        return os << *(bt.root) << '\n';
    }

};

int main() {
    BTree<int, 2> tree;
    tree.Insert(1);
    tree.Insert(2);
    tree.Insert(3);
    tree.Insert(4);
    tree.Insert(5);
    tree.Insert(6);
    tree.Insert(7);
    tree.Insert(8);
    tree.Insert(9);
    tree.Insert(10);

    std::cout << tree;

}


This works because each instantiation of Node creates its own friend function (which is not a template) to go with it. The compiler can easily look at all the friend functions and see which one fits; it doesn't have to guess any template parameters.
