Implementation of BST using templates bu

Implementation of BST using templates but error no default constructor available, help???

Pages: 12

I'm using Visual Studio C++ 2017.

When trying to run my codebase, I am having an error that says:

"'Packet': no appropriate default constructor available."

I have an idea that this could be caused by BST.h:

#ifndef BST_H
#define BST_H

// using namespace std;

template <typename T>
class Node {
    public:
        Node() : rlink(nullptr), llink(nullptr) {}
        ~Node() {}
    private:
        T data;
        Node *rlink, *llink;

};

template <typename T>
class BST {
public:
    BST();
    void insert(T &p);
private:
    Node<T> * root; 
};

#endif

Or if not that then caused by this function which is part of BST.cpp:

template <typename T>
void BST<T>::insert(T &p) {
    if (root != nullptr) {

    }
    else {
        Node<T> *newNode = new Node<T>;
        cout << "UPD" << endl;
    }
}

The cout is there for test purposes. I am aware of the usage of namespace std; that is just there for quick-testing-purposes. That's not my priority, but fixing this error is.

Here's my current main.cpp:

using namespace std;

#include <iostream>

#include "BST.h"
#include "BST.cpp"
#include "Packet.h"

int main()
{
	BST<Packet> test;
	Packet one(1, "testPacket", 1, 1);
	test.insert(one);
	system("Pause");
}

My intention is to do something like this:

1
2

Node *newNode = new Node;
newNode->data = new Packet(p);

in my main.cpp but in a template version. How can I achieve this and fix this critical error?

P.S.: Don't really know how to use the formatting tools. It doesn't seem to work for me when I press the code button.

Please let me know if you need more of my code to analyze how to fix the problem, would really appreciate it.

Edit:

Here's my Packet.h code:

#ifndef PACKET_H
#define PACKET_H

#include <string>

using namespace std;

class Packet {
public:
	Packet(int partId, string description, double price, int partCount) :
		partId(partId), description(description), price(price), partCount(partCount) {}
	int getPartId() const { return partId; }
	string getDescription() const { return description; }
	double getPrice() const { return price; }
	int getPartCount() const { return partCount; }
private:
	int partId;
	string description;
	double price;
	int partCount;
};

#endif

Last edited on

Niccolo (720)

The message is about the Packet class, but that's the one thing you didn't post any code for.

H3110w0rld (3)

The message is about the Packet class, but that's the one thing you didn't post any code for.

I did a modification to BST.h:
T* data
I thought if I did
T data
it would take in the pointer too though? Or is that not how it works?
Was this truly the fix? Because once I modified it, my program started running again.

Last edited on

Niccolo (720)

T* data would mean the stores a pointer to T, so you'd have to create a "new T()" for it, or otherwise assign data to a valid instance (or nullptr, and deal with what nullptr means within the node.

T data means that the node stores and instance of T. A "new Node<T>()" incorporates the creation of a T (but as a member of Node). This means T would have to offer a default constructor (sound familiar?).

There are means of providing parameters for the creation of T (instead of T*) if you can't create a default T.

Back to T* data, note that if Node is expected to "own data", then Node will be required to call "delete" for data (you are basically creating a container, like a smart pointer).

So, you may be better off with something like

std::unique_ptr< T > data;

That way, deletion would be automatic when Node is deleted, but this does impose restrictions. It makes the Node non-copyable. You could provide move semantics, or use

std::shared_ptr< T > data;

Which does support copying the pointer to data, and exhibits shared ownership (at a performance cost).

H3110w0rld (3)

Hello. I modified my code so that BST can look inside the Node class and its private members. Please take a look and tell me if I'm doing it right:

BST.cpp which has begun working again:

template <typename T>
void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
		newNode->data = new Packet(p);
		root = newNode;
		cout << root->data->getDescription() << endl;
	}
}

Node.h and BST.h (BST is the friend of Node so it can access Node's private members now; allowing manipulation like you saw above):

template <typename T>
class Node {
	template <typename> friend class BST;
	public:
		Node() : rlink(nullptr), llink(nullptr) {}
		~Node() {}
	private:
		T* data;
		Node *rlink, *llink;

};

template <typename T>
class BST {
public:
	BST();
	void insert(T &p);
private:
	Node<T> * root; 
};

Does it look right to you? Can it really be done this way? I'm beginning to see the program how I want it. Just this step, I want to make sure is correct too. You can see Packet.h's content above in my OP.

Last edited on

Niccolo (720)

While the notion of making classes friends of each other can fall into the category of opinion, I don't think so in this case.

One of the advantages of objects comes from making them function as independent components in a machine, the way an alternator, a water pump or a power steering unit bolt onto an engine.

I have a Mitsubishi with a 4 Cyl Mivec engine. The design puts several bolts of the water pump, and some of the flanges for those bolts, underneath the timing belt. This means that to replace the water pump, one must pull the timing belts off. Perhaps it seems reasonable because by the time the timing belts require replacement, the water pump probably does, too, but I didn't think so when the water pump required replacement, but the timing belts did not.

The primary reason I see you've befriended BST to Node is to create a copy of the object parameter "p". While the function accepts the parameter, it should not be messing with Node's responsibilities. The Node holds the pointer Data, and it should be responsible for deleting Data when the Node falls from scope. You do not want to place that responsibility on another component, BST, every time a Node is deleted. Likewise, creating the copy of "p" doesn't fall into BST's responsibilities. That's Node's job.

So, make a Node constructor that takes a T & p, and have that create the copy to be held by Data, and remember to create a destructor which will delete Data (if not nullptr).

As a result, you have no need to befriend the two classes. At least, not for this.

JLBorges (13770)

I would tend to make node an encapsulated implementation detail of bst;
ie. make node a private (nested) member class of bst.

For example:

#include <iostream>
#include <utility>
#include <functional>

// the binary predicate CMP is used to compare objects of type T
// invariant: CMP meets the requirements of Compare
// https://en.cppreference.com/w/cpp/named_req/Compare
// the default comparison predicate is std::less<> (a la std::set)
// https://en.cppreference.com/w/cpp/utility/functional/less
template < typename T, typename CMP = std::less<> >
struct bst {

    explicit bst( const CMP& c = CMP{} ) : cmp(c) {}

    // TO DO: destructor etc.

    bool insert( const T& v ) {

        if( root != nullptr ) return root->insert( v, cmp ) ;
        else return bool( root = new node{v} ) ;
    }

    std::ostream& print( std::ostream& stm = std::cout ) const {

        stm << "\nthis bst contains [ " ;
        if(root) root->print(stm) ;
        return stm << "]\n" ;
    }

    // TO DO: find, erase etc.

    private:

        struct node {

            const T data ; // data can't be modified (node holds a value in the bst)

            node* left_child = nullptr ;
            node* right_child = nullptr ;

            bool insert( const T& v, const CMP& cmp ) ;
            std::ostream& print( std::ostream& stm ) const ;
        };

        node* root = nullptr ;
        CMP cmp ;
};

template < typename T, typename CMP >
bool bst<T,CMP>::node::insert( const T& v, const CMP& lt ) {

    const bool less = lt(v,data) ; // v < data
    const bool greater = lt(data,v) ; // data < v

    // v is not less than data and v is not greater than data,
    // ie. !lt(v,data) && !lt(data,v). ergo v and data are equivalent
    if( !less && !greater ) return false ; // duplicate, do not insert

    node*& child = less ? left_child : right_child ; // note: reference

    if( child == nullptr ) return bool( child = new node{v} ) ; // updates the referred to object
    else return child->insert( v, lt ) ;
}

template < typename T, typename CMP >
std::ostream& bst<T,CMP>::node::print( std::ostream& stm ) const {

    if(left_child) left_child->print(stm) ;
    stm << data << ' ' ;
    if(right_child) right_child->print(stm) ;

    return stm ;
}

int main() {

    struct packet {

        explicit packet( int i ) : v(i) {} // note: not default constructible
        int v ;
        operator int() const { return v ; } // make it LessThanComparable, output streamable
    };

    bst<packet> test ;

    for( int v : { 1, 8, 5, 1, 6, 3, 9, 2, 6, 7, 5, 3, 0, 4 } ) {

        packet pkt(v) ;
        std::cout << pkt ;
        if( test.insert(pkt) ) std::cout << " inserted\n" ;
        else std::cout << " duplicate, not inserted\n" ;
    }

    test.print() ;

    // bst<packet>::node* this_is_not_allowed ; // *** error: private member of 'bst<packet>'
}

http://coliru.stacked-crooked.com/a/126eab833e573697
https://rextester.com/YUSR46115

Niccolo (720)

@H3110w0rld,

Notice how @JLBorges version holds T as a value, not via a pointer, and takes a T & in the constructor of
BST<>::Node.

It seems the primary reason you switched to a pointer is because of the original error from the compiler regarding your test class (did not have a default constructor).

This isn't a good design justification, as most containers in the STL (and elsewhere) have a few requirements of the objects they store, such as having default construction.

@JLBorges implementation would likely be faster because a copy of the type of objects typically held via pointer is less work than allocating a new object from the heap (and deleting it later). It is the dynamic allocation that makes the performance hit (construction/destruction still occur).

Note, too, that @JLBorges version still allows the user to elect to store via pointer if that is the type supplied to the container (and should be a smart pointer if possible).

keskiverto (10402)

Note, on line 61 of JLBorges' code:
child = new node{v} A node object is created into dynamically allocated memory.

If the node would have a pointer to data and the pointed to object is dynamically allocated too, then you would end up allocating separately for node object (that would be just three pointers) and for the actual data object.

In the JLBorges' version one allocation covers both because node contains the data as a value.

H3YW0R1Ddispos (5)

I got locked out of my other account. This is me.

I would tend to make node an encapsulated implementation detail of bst;
ie. make node a private (nested) member class of bst.

For example:

Hey, I actually took a look at your codebase multiple times (for a good # of days and ran it). I still cannot really quite grasp it and got lost in it. I've never seen a codebase like this before in school. Specifically:

1) When node is created, where is data initialized in the node?
2) Where is memory allocated if data is a pointer or is it not? And it is a value? It cannot store the whole packet?

Notice how @JLBorges version holds T as a value, not via a pointer, and takes a T & in the constructor of
BST<>::Node.

It seems the primary reason you switched to a pointer is because of the original error from the compiler regarding your test class (did not have a default constructor).

My intention has always been to allocate memory to data and take in the address of the inserting packet via. pointer. Is that not a good idea? What you're saying is to copy the contents of Packet into data instead, creating a new copy?

Note, too, that @JLBorges version still allows the user to elect to store via pointer if that is the type supplied to the container (and should be a smart pointer if possible).

At this time, I want to avoid using smart pointers. I don't have an extensive history with them and I'm more comfortable with manual pointers. I'd like to keep it like that just for now but possible in the future, an investigation into this may be on the cards.

How does @JLBorges version allow the user to store via. pointer? I'm having a hard time finding where data is initiated, taking in packet.

In the JLBorges' version one allocation covers both because node contains the data as a value.

If a pointer is provided, then data will also take in the pointer to the object correct? Then when that happens, you may do cout << data->v << endl; is that right?

Please take a look at my old codebase:

In the BST.h:

template <typename T>
class Node {
	template <typename> friend class BST;
	public:
		Node() : rlink(nullptr), llink(nullptr) {}
		~Node() {}
	private:
		T data;
		Node *rlink, *llink;

};

In the insert function of BST.cpp:

template <typename T>
void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
	}
}

The intention is to take in p and plug it into data which is now just a value. In what ways can this be achieved? I just want a small snapshot example for this problem. I've read JLB's example but it was hard for me to decipher so a small example for this would do me wonders.

Currently, I am getting an error:

'Packet': no appropriate default constructor available." Of course, I also have the working variant that uses a pointer data in the .h which I posted previously. But let me know!

Last edited on

Niccolo (720)

@H3YW0R1Ddispos,

1) When node is created, where is data initialized in the node?

child = new node{v}

This uses initialization syntax, and older compilers might not understand it, though they should.

2) Where is memory allocated if data is a pointer or is it not? And it is a value? It cannot store the whole packet?

If any container from the STL is given a pointer type, that is the calling code's responsibility

std::vector< Packet * > vptr;

Since this vector is configured to accept Packet *, and not Packet, it operates as if the value is Packet *. The responsibility for allocation is the calling code (your code if you wrote it this way). That also means calling code is responsible for deleting all the Packets, as the container won't do it. This isn't commonly done this way. Instead, this concept may more commonly be used to prepare an alternate order of existing data. I sense you're not quite at that point, but consider something like:

1
2

VDat v[ 100 ];
std::map< std::string, VDat * > vkeyed;

Assume VDat is some kind of structure with various fields of data. It is in an array and could be sorted, but suppose you needed a separate lookup into v by other "keys" (like a list of customers, and you want to look up by phone).

This allows each instance in v to be keyed in vkeyed, where the pointer to any entry in v can be cross referenced. In this case v is the storage, so the pointers in vkeyed do not require deletion.

template <typename T>
void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
		newNode->data = new Packet(p);
		root = newNode;
		cout << root->data->getDescription() << endl;
	}
}

This is from your second version posted above. Notice "new Packet( p )".

I didn't think of this before, by what is "Packet"? Is that not "T". That should have read "new T( p )".

That said, the real point here is that "new T( p )" invokes what appears to be a copy constructor. So, this copies anyway.

JLB's code copies, but does not have the additional workload of allocating a "new" P to do it.

That has been the history of smart pointers for most early C++ programmers (before smart pointers and templates existed). I can't say it makes sense to me.

Contemplate what a node is. Did you ever stop to think it is a specialized type of smart pointer? Nodes hold objects in various ways (they're a loosely defined concept). As you've implemented Node, storing via pointer, you've created an object which holds a pointer and (at least should) deletes it when the node falls from scope (or is deleted). That's what smart pointers do.

How does a node give you the data? If you sequence through the container, you ultimately require access to the data the user put into the container. Usually that comes from an iterator. An iterator is a kind of pointer into the container. A kind of smart pointer.

The only difference is that smart pointers are not used as links in containers (those which are based on links), or iterators. Well, that and some small interface to get to the data.

I say again, the use of smart pointers is one of the most important aspects of C++. It is central to modern writing. You're already about 40% into writing something that does what smart pointers do, just not called smart pointers because they are intended for something else (links).

In my view, a C++ programmer without smart pointers is a fundamental contradiction. They're simple, easy to learn, save a lot of bugs (you have no idea just how much, I'm sure...but some 30% of ALL bugs from C or pre-98 C++ were associated with raw pointers and related memory management).

Think of that for a moment. A good portion of the reliability of what you're now building will be on the point of memory control. I can't see logic in avoiding a tool so fundamentally aimed a memory control.

No doubt, there are plenty of times we must write with raw memory management. There can be no way around it under certain circumstances. The most natural response a C++ developer has to such situations is to encapsulate the "nastiness" of that, get it seriously well tested and debugged, and close up tightly so no one else has to ever deal with it.

That's what smart pointer do for all dynamically allocated instances of objects. Containers, like the one you're building, do that for collections of objects.

If I lose you on everything else, the one, single, most important thing any C++ programmer should learn post 2010 is how to use smart pointers, which would take maybe two sessions of about 2 hours each, soup to nuts. There is just not that much about them to learn.

How does @JLBorges version allow the user to store via. pointer? I'm having a hard time finding where data is initiated, taking in packet.

JLB's code does not explicate the usage of pointers. Like the standard containers, it takes no account of pointers, but also does nothing to prevent them.

  bool insert( const T& v ) {

        if( root != nullptr ) return root->insert( v, cmp ) ;
        else return bool( root = new node{v} ) ;
    }

If "T" is "Packet *" and not "Packet", then "Insert" will require a pointer, which makes "v" and reference to a Packet *, and Node stores such a pointer initialized with "new node{v}". Like the standard containers, this would mean calling code must provide a pointer, and perhaps both allocation and deletion (it's uncomfortable with the standard containers, too...unless they don't own what they point to).

Now, consider your code:

void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
		newNode->data = new Packet(p);
		root = newNode;
		cout << root->data->getDescription() << endl;
	}
}

Could you prevent the user from providing "Packet *" as the type for "T".

Since I suspect "new Packet( p )" is an error, and that should be new "T( p )", what would that mean if T is a "Packet *", not a "Packet"?

This is long for a post by now, and I'm changing directions for the evening...I'll consider a simplified example for you in a while. In the meantime, think upon these points and we'll continue later.

deleted account xyzzy (5768)

Niccolo wrote:
This uses initialization syntax, and older compilers might not understand it

The OP said they are using VS 2017, so initialization syntax shouldn't be a problem.

JLBorges (13770)

> How does @JLBorges version allow the user to store via. pointer?
> I'm having a hard time finding where data is initiated, taking in packet.

The member data is initialised when the node is constructed.
this may be clearer in the Visual Studio 2017 version (which requires a constructor):
https://rextester.com/YUSR46115 line #38

new node{v} constructs a new node; its data holds a copy of v,
the child pointers are initialised to nullptr (the default member initialiser is nullptr).

Here are three different ways in which this bst can be used:
1. bst<Packet>: Holds packets by value
2. bst<Packet*>: Holds pointers to packets; uses std::less to compare pointers
3. bst<Packet*, cmp_fn>: Holds pointers to packets; uses a custom predicate to compare pointers

#include <iostream>
#include <utility>
#include <functional>
#include <type_traits>
#include <string>

// the binary predicate CMP is used to compare objects of type T
// invariant: CMP meets the requirements of Compare
// https://en.cppreference.com/w/cpp/named_req/Compare
// the default comparison predicate is std::less<> (a la std::set)
// https://en.cppreference.com/w/cpp/utility/functional/less
template < typename T, typename CMP = std::less<> >
struct bst {

    explicit bst( const CMP& c = CMP{} ) : cmp(c) {}

    // TO DO: destructor etc.

    bool insert( const T& v ) {

        if( root != nullptr ) return root->insert( v, cmp ) ;
        else return bool( root = new node{v} ) ;
    }

    std::ostream& print( std::ostream& stm = std::cout ) const {

        const auto type_name = typeid( typename std::remove_pointer<T>::type ).name() ;

        stm << "\nthis bst contains " ;
        if( std::is_pointer<T>::value ) std::cout << "pointers to " << type_name ;
        else std::cout << "objects of type " << type_name ;

        std::cout << "\n[ " ;
        if(root) root->print(stm) ;
        return  stm << "]\n" ;
    }

    // TO DO: find, erase etc.

    private:

        struct node {

            const T data ; // data can't be modified (node holds a value in the bst)

            node* left_child = nullptr ;
            node* right_child = nullptr ;

            node( const T& v ) : data(v) {

                 std::cout << "constructed a node holding data == " << data << '\n' ;
            }

            bool insert( const T& v, const CMP& cmp ) ;
            std::ostream& print( std::ostream& stm ) const ;
        };

        node* root = nullptr ;
        CMP cmp ;
};

template < typename T, typename CMP >
bool bst<T,CMP>::node::insert( const T& v, const CMP& lt ) {

    const bool less = lt(v,data) ; // v < data
    const bool greater = lt(data,v) ; // data < v

    // v is not less than data and v is not greater than data,
    // ie. !lt(v,data) && !lt(data,v). ergo v and data are equivalent
    if( !less && !greater ) return false ; // duplicate, do not insert

    node*& child = less ? left_child : right_child ; // note: reference

    if( child == nullptr ) return bool( child = new node{v} ) ; // updates the referred to object
    else return child->insert( v, lt ) ;
}

template < typename T, typename CMP >
std::ostream& bst<T,CMP>::node::print( std::ostream& stm ) const {

    if(left_child) left_child->print(stm) ;
    stm << data << ' ' ;
    if(right_child) right_child->print(stm) ;

    return stm ;
}

struct Packet {

	Packet( int partId, std::string description, double price, int partCount) :
		partId(partId), description(description), price(price), partCount(partCount)
    { std::cout << "constructed " << *this << " at address " << this << '\n' ; }

	int getPartId() const { return partId; }
	std::string getDescription() const { return description; }
	double getPrice() const { return price; }
	int getPartCount() const { return partCount; }

    private:
        int partId;
        std::string description;
        double price;
        int partCount;

    // make packet LessThanComparable (compare partIds)
    friend bool operator< ( const Packet& a, const Packet& b )
    { return a.getPartId() < b.getPartId() ; }

    // make packet output streamable
    friend std::ostream& operator<< ( std::ostream& stm, const Packet& pkt )
    {
        return stm << "Packet{ " << pkt.getPartId() << ", " << pkt.getDescription()
                   << ", " << pkt.getPrice() << ", " << pkt.getPartCount() << " }" ;
    }
};

// binary predicate to compare pointed to objects
struct cmp_pointed_to_packets
{
    bool operator() ( const Packet* a, const Packet* b ) const
    {
        // nullptr compares less than non-null ptr
        if( a == nullptr ) return b != nullptr ;
        else if( b == nullptr ) return false ;

        // compare pointed to objects
        else return *a < *b ;
    }
};

int main() {

    Packet my_packets[] { { 8, "eight", 8.8, 88 }, { 1, "one", 1.1, 11 },
                          { 5, "five", 5.5, 55 }, { 1, "one", 1.1, 11 },
                          { 6, "six", 6.6, 66 }, { 3, "three", 3.3, 33 }
                        };

    std::cout << "\n------------------\n\n" ;

    {
        std::cout << "1. *** hold packets by value ***\n\n" ;

        // create a binary search tree holding Packets
        bst<Packet> test ;

        for( const auto& pkt : my_packets )
        {
            const bool inserted = test.insert(pkt) ;
            std::cout << "copy of packet " << pkt << " was "
                      << ( inserted ? "inserted" : "***not*** inserted (duplicate id)" )
                      << "\n\n" ;
        }

        test.print() ;
    }

    std::cout << "\n------------------\n\n" ;

    {
        std::cout << "2. *** hold pointers to packets ***\n\n" ;

        // create a binary search tree holding pointers to Packets
        // note that the specialization of std::less for pointer types
        // gives us a strict total order (meets the requirements of Compare)
        // even when the built-in operator < for pointers may not.
        bst< Packet* > test ;

        for( auto& pkt : my_packets )
        {
            const auto addr = std::addressof(pkt) ;
            const bool inserted = test.insert(addr) ;
            std::cout << "pointer " << addr << " was "
                      << ( inserted ? "inserted" : "***not*** inserted (duplicate pointer)" )
                      << "\n\n" ;
        }

        test.print() ;
    }

    std::cout << "\n------------------\n\n" ;

    {
        std::cout << "3. *** hold pointers to packets, but compare values of pointed to packets ***\n\n" ;

        // create a binary search tree holding pointers to Packets
        // however, instead of comparing the pointers, we compare the pointed to packets
        bst< Packet*, cmp_pointed_to_packets > test ;

        for( auto& pkt : my_packets )
        {
            const auto addr = std::addressof(pkt) ;
            const bool inserted = test.insert(addr) ;
            std::cout << "pointer to " << pkt << " at address " << addr << " was "
                      << ( inserted ? "inserted" : "***not*** inserted (duplicate id)" )
                      << "\n\n" ;
        }

        test.print() ;
    }
}

http://coliru.stacked-crooked.com/a/ab93b8af0adad678
https://rextester.com/YUSR46115

H3YW0R1Ddispos (5)

@Niccolo,

Since this vector is configured to accept Packet *, and not Packet, it operates as if the value is Packet *. The responsibility for allocation is the calling code (your code if you wrote it this way). That also means calling code is responsible for deleting all the Packets, as the container won't do it. This isn't commonly done this way. Instead, this concept may more commonly be used to prepare an alternate order of existing data. I sense you're not quite at that point, but consider something like:

I've actually used STL containers before. I'm actually starting to see the prevalent use of STL containers/methods in this post. For my schooling, I've rarely used the STL and if I do it's used specifically for a specific thing. Because it's not code that you really write or author, it means you need an understanding of it. My BST implementation has been pretty simple so far and I don't rly. use STL in it.

JLB's code copies, but does not have the additional workload of allocating a "new" P to do it.

He uses the STL and other methods from containers. Is there a variant of that that does not use any STL/container/and pretty much basic way of achieving that? Or am I not reading the code correctly? I'd like to stay away from usage of those since I'm wanting to keep my BST bare bones like the codebase that I've written so far. Do you have such example in that case?

That has been the history of smart pointers for most early C++ programmers (before smart pointers and templates existed). I can't say it makes sense to me...There is just not that much about them to learn.

I've actually never been taught to use smart pointers in most of my schooling. It's all been manual bread-and-butter. The reasoning is to keep it simple and bare-bones. I'm wanting to avoid that because this project is mostly going to be used for school-purposes and it's a risk to implement smart pointers into such projects. I know of its existence. Most likely, if this was on my own terms (a.k.a own project) then I would've investigated further. But I want to keep things simple (because it's just overkill to do more...) here like the codebase I've written so far.

Since I suspect "new Packet( p )" is an error, and that should be new "T( p )", what would that mean if T is a "Packet *", not a "Packet"?

Such an event would likely not occur since this codebase would most likely be ran in a school environment meaning there will be an assumption that Packet will always be fed to this function and so-on-so-forth.

I'll consider a simplified example for you in a while. In the meantime, think upon these points and we'll continue later.

Thanks so much. If you could, I just need the part where

void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
		newNode->data = new Packet(p);
		root = newNode;
		cout << root->data->getDescription() << endl;
	}
}

is done and nothing more. Can you achieve my intention (I believe you already know what it is already, it's what I did in the code above) without using STL/keeping it as simple as possible? And what would that look like?

@JLBorges

new node{v} constructs a new node; its data holds a copy of v,
the child pointers are initialised to nullptr (the default member initialiser is nullptr).

Much thanks for the codebase you've written. I've actually never used CMP or any of those (STL?) functions you've written so far. In my previous examples, I used none of them. I'm trying to keep this simple and as bare-bones as possible since this is for school pretty much and we never use these things (it's just overkill for simple projects for school and similar...)

That being said, you didn't need to write all of this but it makes for good reference in the future so thanks for that. I'm specifically looking for:

void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T>;
		newNode->data = new T(p);
		root = newNode;
		cout << root->data->getDescription() << endl;
	}
}

Packet's structure is specifically this:

private:
int partId;
string description;
double price;
int partCount;

Where insert takes in packet, it then dynamically allocates memory for newNode's data, taking in this packet. From there to access a node's data, you would do: newNode->data->getDescription(); or something similar as that's one of the methods in the .h of Packet.

Do you have something similar there but without using T* data in BST.h?
If I read correctly, you did with T data taking in as value or something similar. But you used (STL?) or other C++ functions. Can you do the same w/out any STL or such functions while keeping it simple and bare-bones like my example above? How?

Niccolo (720)

There maybe some confusion as to what is in the STL vs what is in the standard libary. The STL is in the standard library at this point, but the standard library contains more than the STL.

Every modern C++ programmer uses the standard library. I understand what you're saying about class assignments, but those of us who have long histories beyond academia have considerable disagreement with what is taught in schools. While it is clearly recognizable that some professors insist on their approach, there is no question there are flaws in it. It is all but impossible for professionals and highly experienced developers to stop themselves from using the standard library, as that has been drilled into our minds from both experience and engineering. We have even stronger objections to that path than you can imagine.

That said, take, for example, CMP, which you mentioned. That is just a parameter in JLB's example. It isn't the STL or standard library. Where you see CMP, you're seeing a generic representation of a type of comparison operator, which can be satisfied with a simple function object. The STL provides "less<>", which JLB uses as a default. Merely remove the default and you have non-STL version of that requirement. Remove CMP entirely and you can "hard wire" a "less than" comparison, which is nothing more than "<".

JLB uses std::is_pointer, in the printout, to modify text based on whether the parameter is or is not a pointer. You could merely remove that, leaving the "else" clause only.

As to "new Packet( p )" - I'm fairly sure even your professor would see that as an error. Where the container takes a type T, it is an error not to use T wherever that type is represented.

I've actually never been taught to use smart pointers in most of my schooling. It's all been manual bread-and-butter.

Like I pointed out above, this is one of those subjects with which most of us could never agree with your professor. "Manual" in this context means you're actually not being taught C++, and it isn't bread and butter unless you're writing in C. Factually, it has not been so for many, many years now.

If this were 2010, I might have more understanding for this. Prior to C++11, the smart pointers were from the Boost library (which has brought several innovations to the language that are now standard).

Your teacher is, in effect, stuck in 2010. I know you have to live with it, I get that part. I just want you to realize there is a loss you can't possibly recognize at this point in time, and you would be well advised to run as fast as you can for the standard books by Stroustrup (C++ Principles and Practices) the moment you are out of this class.

What you'll get is at lest up to 2014, a very key moment in this language's development.

In the meantime, you actually have most of the answers you just asked.

For example, to answer the point about copying Packet, note that Packet has the responsibility of copying Packets. Thats why = new Packet( p ) needs no modification or explanation by itself. For the Packet layout you show, the language's default copy constructor should do all that is required, or you could write one in Packet. That is still C++ from the 90's.

Last edited on

keskiverto (10402)

1
2

Node<T> *newNode = new Node<T>;
newNode->data = new T(p);

The second line looks like part of initialization of the Node object.
Why it is not done within the constructor of Node?
Node<T> *newNode = new Node<T>(p);

Your original issue "no appropriate default constructor available." shows that you don't cope that subject yet.
Note also that same constructor works with both types of allocation:

1
2

Node<T> stack(p);
Node<T> *heap = new Node<T>(p);

I want to keep things simple

There is a tradeoff.
If you use raw pointers, then you have to write all necessary code. (*)
If you use smart pointers, then that code has already been written for you.

Typename of a raw pointer might look simpler than typename of smart pointer, but the responsibilities that raw pointer puts on you are far from simple.

(*) It seems that the school has not yet succeeded to list all the necessities.

H3YW0R1Ddispos (5)

@Niccolo,

My bad. But you knew what I was trying to refer to.

It is all but impossible for professionals and highly experienced developers to stop themselves from using the standard library, as that has been drilled into our minds from both experience and engineering. We have even stronger objections to that path than you can imagine.

Oh no, the school(s) isn't/aren't trying to stop me from using the standard library. Rather they keep a simplistic approach so that it's easier for everyone to learn (like building blocks) if you will. Creating a personal project, etc. it's completely our choice to do as we wish.

Thanks so much.

In addition to that, I've changed my codebase:

BST.h:

template <typename T>
class Node {
	template <typename> friend class BST;
	public:
		Node(T p) : data(p), rlink(nullptr), llink(nullptr) {}
		~Node() {}
	private:
		T data;
		Node *rlink, *llink;

};

BST.cpp:

template <typename T>
void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T> (p);
		root = newNode;
		cout << root->data.getPartId() << endl;
	}
}

What are your thoughts on these changes now?

@keskiverto,

The second line looks like part of initialization of the Node object.
Why it is not done within the constructor of Node?

Actually, you got me thinking here. I decided to look up some source codes regarding BST. What I have now is the code above that I'm showing to Niccolo. Any thoughts regarding that now?

There is a tradeoff.
If you use raw pointers, then you have to write all necessary code. (*)
If you use smart pointers, then that code has already been written for you.

Typename of a raw pointer might look simpler than typename of smart pointer, but the responsibilities that raw pointer puts on you are far from simple.

(*) It seems that the school has not yet succeeded to list all the necessities.

The reason why I'm using raw pointers is because up to this point, that's the only pointer that's been introduced to me. This, I'm doing mostly for school. I think this smart pointer thing warrants an investigation in the future though, I'll hopefully see to it then but for now I will be using raw. How does my changed code look (the code above)? Much thanks.

JLBorges (13770)

Version without the CMP template parameter, and without node being a nested class:

// **** in bst.h ****
#include <iostream>

template < typename T > struct bst ; // declare bst<T>

template < typename T > struct node {

    private: // everything is private, bst<T> is a friend class and can access everything

        const T data ; // data can't be modified (node holds a value in the bst)

        node* left_child = nullptr ;
        node* right_child = nullptr ;

        node( const T& v ) : data(v) {}

    friend bst<T> ; // declare that bst<T> is a friend
};

template < typename T > // required: type T is EqualityComparable and LessThanComparable
struct bst {

    // *** note that we use < to compare objects of type T
    // *** this will engender unspecified behaviour if T is a pointer type
    // *** see: http://eel.is/c++draft/expr.rel#4.3
    //
    // std::less<> does not have this problem;
    // it imposes a strict total order for pointer types
    // see: https://en.cppreference.com/w/cpp/utility/functional/less#Specializations

    // TO DO: destructor etc.

    bool insert( const T& v ) { // return true if inserted

        if( root != nullptr ) return do_insert( v, root ) ;
        else return bool( root = new node<T>{v} ) ;
    }

    std::ostream& print( std::ostream& stm = std::cout ) const {

        stm << "\nthis bst contains \n[ " ;
        do_print( stm, root ) ;
        return  stm << "]\n" ;
    }

    // TO DO: find, erase etc.

    private:

        node<T>* root = nullptr ; // default member initialiser

        // (private) operations on sub-trees (on nodes) of the bst
        bool do_insert( const T& v, node<T>* n ) ; // insert into the sub-tree
        std::ostream& do_print( std::ostream& stm, const node<T>* n ) const ; // print he sub-tree
};

// note: these functions are defined in the header file itself; there is no bst.cpp
// see: https://isocpp.org/wiki/faq/templates#templates-defn-vs-decl
template < typename T >
bool bst<T>::do_insert( const T& v, node<T>* n ) { // return true if inserted

    if( n==nullptr || v==n->data ) return false ; // duplicate, do not insert

    node<T>*& child = v < n->data ? n->left_child : n->right_child ; // note: reference

    if( child == nullptr ) return bool( child = new node<T>{v} ) ; // updates the referred to object
    else return do_insert( v, child ) ;
}

template < typename T >
std::ostream& bst<T>::do_print( std::ostream& stm, const node<T>* n ) const {

    if( n != nullptr ) {

        do_print( stm, n->left_child ) ;
        stm << n->data << ' ' ;
        do_print( stm, n->right_child ) ;
    }

    return stm ;
}

// **** in packet.h ****
// include bst.h
#include <string>

struct Packet {

	Packet( int partId, std::string description, double price, int partCount ) :
		partId(partId), description(description), price(price), partCount(partCount) {}

    // these are inline; they may be defined separately in a packet.cpp file
	int getPartId() const { return partId; }
	std::string getDescription() const { return description; }
	double getPrice() const { return price; }
	int getPartCount() const { return partCount; }

    private:
        int partId;
        std::string description;
        double price;
        int partCount;

    // make packet LessThanComparable (compare partIds with < )
    friend bool operator< ( const Packet& a, const Packet& b )
    { return a.getPartId() < b.getPartId() ; }

    // make packet EqualityComparable (compare partIds with == )
    friend bool operator== ( const Packet& a, const Packet& b )
    { return a.getPartId() == b.getPartId() ; }

    // make packet output streamable
    friend std::ostream& operator<< ( std::ostream& stm, const Packet& pkt )
    {
        return stm << "Packet{ " << pkt.getPartId() << ", " << pkt.getDescription()
                   << ", " << pkt.getPrice() << ", " << pkt.getPartCount() << " }" ;
    }
};

// **** in main.cpp ****
// include bst.h
// include packet.h

int main() {

        const Packet my_packets[] {
                          { 8, "eight", 8.8, 88 }, { 1, "one", 1.1, 11 },
                          { 5, "five", 5.5, 55 }, { 1, "one", 1.1, 11 },
                          { 6, "six", 6.6, 66 }, { 3, "three", 3.3, 33 }
                        };

        // create a binary search tree holding Packets
        bst<Packet> test ; // empty bst (root is nullptr)

        for( const auto& pkt : my_packets ) // for each packet in my_packets
        {
            const bool inserted = test.insert(pkt) ; // try to insert it in the bst

            std::cout << "copy of packet " << pkt << " was "
                      << ( inserted ? "inserted" : "***not*** inserted (duplicate id)" )
                      << "\n\n" ;
        }

        test.print() ;
}

http://coliru.stacked-crooked.com/a/b1ee1bbf41ccd9c0
https://rextester.com/JAV35890

H3YW0R1Ddispos (5)

Version without the CMP template parameter, and without node being a nested class:

Thank you. This version seems clearer and more readable to me, so far...

Can I also know about my snippet of code and your thoughts regarding it:

BST.h:

template <typename T>
class Node {
	template <typename> friend class BST;
	public:
		Node(T p) : data(p), rlink(nullptr), llink(nullptr) {}
		~Node() {}
	private:
		T data;
		Node *rlink, *llink;

};

BST.cpp:

template <typename T>
void BST<T>::insert(T &p) {
	if (root != nullptr) {

	}
	else {
		Node<T> *newNode = new Node<T> (p);
		root = newNode;
		cout << root->data.getPartId() << endl;
	}
}

So how does that fare?

keskiverto (10402)

1. Const correctness.
* If you have BST<int>, can you insert(42) ?
void BST<T>::insert(T &p) would create a non-const reference, but you can't do that to literal constant.

* If the 'p' in insert() is a reference, then does the by value 'p' in Node(T p) gain you something?
You apparently have to copy-construct the Node<T>.data, but where and how many copy operations?

Look at JLBorges' examples.

2. Which translation unit will use the BST<T>::insert()?
C++ compiler (at least used to) has to see whole templates where it instantiates a template.

Lets say that you have BST.cpp and main.cpp. They are compiled separately.
When you compile BST.cpp, you don't know what types of BST there will be.
When you compile main.cpp, you don't have the template to create implementation for void BST<std::map<std::string,std::vector<double>>>::insert.

3. Who does delete the Nodes?

Pages: 12

Implementation of BST using templates but error no default constructor available, help???

C++

Forum