Thread: C++ templates

  1. #1
    Registered User
    Join Date
    Sep 2009
    Location
    US
    Posts
    6

    C++ templates

    Hi, I'm fairly new to C++. I'm trying to make a priority queue with a binary search tree. My BST class is
    Code:
    template <class T>
    class BST
    {
    private:
    	class Node
    	{
    	public:
    		T Value;
    		Node* Left;
    		Node* Right;
    
    		Node(const T& value)
    		{
    			Value = value;
    			Left = NULL;
    			Right = NULL;
    		}
    	};
    
    	Node* Root;
    
    public:
    	BST()
    	{
    		Root = NULL;
    	}
    
    	~BST()
    	{
    	}
    
    
    	void Add(const T& value)
    	{
    		Node* node = new Node(value);
    		...
    	}
    Code:
    #include "BST.h"
    
    template <class T, class K>
    class PriorityQueue
    {
    private:
    	class PriorityNode
    	{
    	public:
    		T Value;
    		K Priority;
    
    		PriorityNode(T value, K priority)
    		{
    			Value = value;
    			Priority = priority;
    		}
    
    		inline bool operator<(const PriorityNode& node) const
    		{
    			...
    		}
    
    		inline bool operator==(const PriorityNode& node) const
    		{
    			...
    		}
    	};
    
    	BST<PriorityNode> Bst;
    
    public:
    	void Add(T value, K priority)
    	{
    		PriorityNode* node = new PriorityNode(value, priority);
    		Bst.Add(*node);
    		...
    	}
    };
    My problem is here:
    PriorityNode* node = new PriorityNode(value, priority);
    Bst.Add(*node);

    When I try to add to the Bst, it expects type T instead of PriorityNode.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Sorry, but I cannot reproduce your problem, though I did get a compile error having to do with the fact that PriorityNode does not have a default constructor (you should be using the constructor initialiser list in various places instead of what you are doing now).

    I suggest that you post the smallest and simplest program that you think should compile but which demonstrates the error. Also, post the error messages.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This is so muddled up!
    A "Binary Search Tree" is something completely different from a "Priority Queue". A "Priority Queue" strongly implies a heap data structure. A heap should not be implemented as a binary tree at all. It is actually much harder to implement a heap using as a binary tree and it a lot less efficient.

    Choose which of these things it is supposed to be. Once you've done that we can work out which bits of this code can be salvaged.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Sep 2009
    Location
    US
    Posts
    6
    Hi,
    This is about as simple as I can make it (you can remove operator overloads I guess). My error is error C2512: 'PriorityQueue<T,K>::PriorityNode' : no appropriate default constructor available BST.h 19 1
    I'm compiling with VS 2012 if that helps.

    Also, this is an assignment, so I am required to use a BST to implement a priority queue. My plan was to have a BST that is of type PriorityNode, and the PriorityNode overloads <, >, and ==, and does that comparison based on the priority. The value of the PriorityNode will probably be a vector of whatever values have that priority.

  5. #5
    Registered User antred's Avatar
    Join Date
    Apr 2012
    Location
    Germany
    Posts
    257
    Stab in the dark ...

    Code:
    template <class T>
    class BST
    {
    private:
        class Node
        {
        public:
            T Value;
            Node* Left;
            Node* Right;
     
            Node(const T& value)
            {
                Value = value;
                Left = NULL;
                Right = NULL;
            }
        };
    This code requires T to be default-constructible. My guess is, whatever type you specialize this template for just doesn't have a parameterless default constructor. To fix that, you could do what laserlight suggested and INITIALIZE rather than assign.

    Code:
    Node(const T& value) : Value( value ), Left( NULL ), Right( NULL )
    {
    }

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I am required to use a BST to implement a priority queue.
    O_o

    Are you sure the requirement were "binary search tree" and not just "binary tree"?

    A heap built from a simple binary tree is easier than messing about building a balanced search tree.

    My guess is, whatever type you specialize this template for just doesn't have a parameterless default constructor.
    That should probably be "instantiate" instead of "specialize".

    Soma

  7. #7
    Registered User antred's Avatar
    Join Date
    Apr 2012
    Location
    Germany
    Posts
    257
    Uh ... yeah, sorry. Language barrier problem.

  8. #8
    Registered User
    Join Date
    Sep 2009
    Location
    US
    Posts
    6
    Thanks, that worked. I will look up constructor initializers.
    edit: yes, it has too be a BST

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Templates
    By axydias in forum C++ Programming
    Replies: 4
    Last Post: 04-30-2006, 01:43 PM
  2. Templates
    By arjunajay in forum C++ Programming
    Replies: 4
    Last Post: 11-16-2005, 11:17 AM
  3. Templates
    By f0r3nsic in forum C++ Programming
    Replies: 5
    Last Post: 10-02-2005, 09:26 AM
  4. templates using Dev-c++
    By Good0m3n in forum C++ Programming
    Replies: 3
    Last Post: 06-26-2004, 08:38 AM
  5. Templates
    By Trauts in forum C++ Programming
    Replies: 3
    Last Post: 05-16-2003, 03:58 PM