C++ 中的模板类

Question

您好，我收到错误消息错误：预期的初始化程序在“<”之前每次我在下面的代码中声明一个函数时，都会使用 token 。我对 C++ 中的模板不太熟悉，所以这个错误真的让我很困惑。我已经尝试使用 typename 关键字，但它不起作用。任何帮助都会很棒。

BinarySearchTree.h

        #ifndef BINARY_SEARCH_TREE_H_
        #define BINARY_SEARCH_TREE_H_

        #include "dsexceptions.h"
        #include <iostream.h>       // For NULL

          // Binary node and forward declaration because g++ does
          // not understand nested classes.
        template <class Comparable>
        class BinarySearchTree;

        template <class Comparable>
        class BinaryNode
        {
            Comparable element;
            BinaryNode *left;
            BinaryNode *right;

            BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
              : element( theElement ), left( lt ), right( rt ) { }
            friend class BinarySearchTree<Comparable>;
        };


        // BinarySearchTree class
        //
        // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item
        // Comparable findMax( )  --> Return largest item
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order

        template <class Comparable>
        class BinarySearchTree
        {
          public:
            explicit BinarySearchTree( const Comparable & notFound );
            BinarySearchTree( const BinarySearchTree & rhs );
            ~BinarySearchTree( );

            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x ) const;
            bool isEmpty( ) const;
            void printTree( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );

            const BinarySearchTree & operator=( const BinarySearchTree & rhs );

          private:
            BinaryNode<Comparable> *root;
            const Comparable ITEM_NOT_FOUND;

            const Comparable & elementAt( BinaryNode<Comparable> *t ) const;

            void insert( const Comparable & x, BinaryNode<Comparable> * & t ) const;
            void remove( const Comparable & x, BinaryNode<Comparable> * & t ) const;
            BinaryNode<Comparable> * findMin( BinaryNode<Comparable> *t ) const;
            BinaryNode<Comparable> * findMax( BinaryNode<Comparable> *t ) const;
            BinaryNode<Comparable> * find( const Comparable & x, BinaryNode<Comparable> *t ) const;
            void makeEmpty( BinaryNode<Comparable> * & t ) const;
            void printTree( BinaryNode<Comparable> *t ) const;
            BinaryNode<Comparable> * clone( BinaryNode<Comparable> *t ) const;
        };

        #include "BinarySearchTree.cpp"
        #endif

BinarySearchTree.cpp

        #include "BinarySearchTree.h"
        #include <iostream.h>

        /**
         * Implements an unbalanced binary search tree.
         * Note that all "matching" is based on the < method.
         */

        /**
         * Construct the tree.
         */
        template <class Comparable>
        BinarySearchTree<Comparable>::BinarySearchTree( const Comparable & notFound ) :
          root( NULL ), ITEM_NOT_FOUND( notFound )
        {
        }


        /**
         * Copy constructor.
         */
        template <class Comparable>
        BinarySearchTree<Comparable>::
        BinarySearchTree( const BinarySearchTree<Comparable> & rhs ) :
          root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
        { 
            *this = rhs;
        }

        /**
         * Destructor for the tree.
         */
        template <class Comparable>
        BinarySearchTree<Comparable>::~BinarySearchTree( )
        {
            makeEmpty( );
        }

        /**
         * Insert x into the tree; duplicates are ignored.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**
         * Remove x from the tree. Nothing is done if x is not found.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::remove( const Comparable & x )
        {
            remove( x, root );
        }


        /**
         * Find the smallest item in the tree.
         * Return smallest item or ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & BinarySearchTree<Comparable>::findMin( ) const
        {
            return elementAt( findMin( root ) );
        }

        /**
         * Find the largest item in the tree.
         * Return the largest item of ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & BinarySearchTree<Comparable>::findMax( ) const
        {
            return elementAt( findMax( root ) );
        }

        /**
         * Find item x in the tree.
         * Return the matching item or ITEM_NOT_FOUND if not found.
         */
        template <class Comparable>
        const Comparable & BinarySearchTree<Comparable>::
                                 find( const Comparable & x ) const
        {
            return elementAt( find( x, root ) );
        }

        /**
         * Make the tree logically empty.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::makeEmpty( )
        {
            makeEmpty( root );
        }

        /**
         * Test if the tree is logically empty.
         * Return true if empty, false otherwise.
         */
        template <class Comparable>
        bool BinarySearchTree<Comparable>::isEmpty( ) const
        {
            return root == NULL;
        }

        /**
         * Print the tree contents in sorted order.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::printTree( ) const
        {
            if( isEmpty( ) )
                cout << "Empty tree" << endl;
            else
                printTree( root );
        }

        /**
         * Deep copy.
         */
        template <class Comparable>
        const BinarySearchTree<Comparable> &
        BinarySearchTree<Comparable>::
        operator=( const BinarySearchTree<Comparable> & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }

        /**
         * Internal method to get element field in node t.
         * Return the element field or ITEM_NOT_FOUND if t is NULL.
         */
        template <class Comparable>
        const Comparable & BinarySearchTree<Comparable>::
        elementAt( BinaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return ITEM_NOT_FOUND;
            else
                return t->element;
        }

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::
        insert( const Comparable & x, BinaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                t = new BinaryNode<Comparable>( x, NULL, NULL );
            else if( x < t->element )
                insert( x, t->left );
            else if( t->element < x )
                insert( x, t->right );
            else
                ;  // Duplicate; do nothing
        }

        /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::
        remove( const Comparable & x, BinaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != NULL && t->right != NULL ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                BinaryNode<Comparable> *oldNode = t;
                t = ( t->left != NULL ) ? t->left : t->right;
                delete oldNode;
            }
        }

        /**
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        template <class Comparable>
        BinaryNode<Comparable> *
        BinarySearchTree<Comparable>::findMin( BinaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            if( t->left == NULL )
                return t;
            return findMin( t->left );
        }

        /**
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        template <class Comparable>
        BinaryNode<Comparable> *
        BinarySearchTree<Comparable>::findMax( BinaryNode<Comparable> *t ) const
        {
            if( t != NULL )
                while( t->right != NULL )
                    t = t->right;
            return t;
        }

        /**
         * Internal method to find an item in a subtree.
         * x is item to search for.
         * t is the node that roots the tree.
         * Return node containing the matched item.
         */
        template <class Comparable>
        BinaryNode<Comparable> *
        BinarySearchTree<Comparable>::
        find( const Comparable & x, BinaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            else if( x < t->element )
                return find( x, t->left );
            else if( t->element < x )
                return find( x, t->right );
            else
                return t;    // Match
        }
/****** NONRECURSIVE VERSION*************************
        template <class Comparable>
        BinaryNode<Comparable> *
        BinarySearchTree<Comparable>::
        find( const Comparable & x, BinaryNode<Comparable> *t ) const
        {
            while( t != NULL )
                if( x < t->element )
                    t = t->left;
                else if( t->element < x )
                    t = t->right;
                else
                    return t;    // Match

            return NULL;   // No match
        }
*****************************************************/

        /**
         * Internal method to make subtree empty.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::
        makeEmpty( BinaryNode<Comparable> * & t ) const
        {
            if( t != NULL )
            {
                makeEmpty( t->left );
                makeEmpty( t->right );
                delete t;
            }
            t = NULL;
        }

        /**
         * Internal method to print a subtree rooted at t in sorted order.
         */
        template <class Comparable>
        void BinarySearchTree<Comparable>::printTree( BinaryNode<Comparable> *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                cout << t->element << endl;
                printTree( t->right );
            }
        }

        /**
         * Internal method to clone subtree.
         */
        template <class Comparable>
        BinaryNode<Comparable> *
        BinarySearchTree<Comparable>::clone( BinaryNode<Comparable> * t ) const
        {
            if( t == NULL )
                return NULL;
            else
                return new BinaryNode<Comparable>( t->element, clone( t->left ), clone( t->right ) );
        }

Answer 1

要模板化类，您不必在 .h 文件中定义函数。您也无法在 .cpp 文件中定义它们。我一直以来的做法是像平常一样在 .h 文件中定义模板类。然后将函数定义写入 .hpp 文件中。

.h 文件将这样编写：

#ifndef MYCLASS_H
#define MYCLASS_H

template<typename T> class MyClass
{
 public:
    int MyFunction();
}
#include "MyClass.hpp"
#endif

确保将 .hpp 文件包含在 .h 文件中，而不是相反。

然后您的 .hpp 文件将如下所示：

template<typename T>
int MyClass::MyFunction()
{
    ...
}

确保您确定了该函数的范围，并且不要在 .hpp 中包含 .h 文件。编译器会生你的气。

这本质上与在 .h 文件中定义函数相同，但这允许您保留两个单独的文件。如果你的类很小，功能很少，或者大多数功能都是一个衬垫，即。 getter/setter 函数。可能不值得为此创建一个完整的文件，但在像 BST 和 AVL 这样的情况下，拥有多个文件是非常好的，这样您就不会盯着代码墙。