CODEWITHSUNDEEP
c++inheritanceliskov-substitution-principle
Str-Gen
Str-Gen

Reputation: 33

Does this class setup violate the Liskov Substitution Principle

I have this piece of code for a Tree. The BSTnodes contain the actual data. BST is a wrapper around them by inheriting from unique_ptr<BSTnode<Key,Data>>. BST doesn't add any new fields to the class.

The inheritance makes it so that my tree is a unique_ptr<BSTnode>, but is that a correct way of implementing it? The added operations for the BST like rotate() / insert() or remove() are specific to the data structure. You wouldn't and shouldn't expect them for a regular unique_ptr, but this does mean that a BST can't be used interchangeably with a unique_ptr.

If this implementation strategy is incorrect, how should I solve it?

template <class Key, class Data>
class BST : public unique_ptr<BSTnode<Key, Data>>
{
using unique_ptr<BSTnode<Key, Data>>::unique_ptr;
// operations ...
};

template <class Key, class Data>
class BSTnode
{
friend class BST<Key, Data>;

public:
//constructors ...

protected:
Key key;
Data data;
BSTnode<Key, Data> *parent;
BST<Key, Data> left, right;
};

Upvotes: 0

Views: 110

Answers (1)

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39390

LSP aside, inheriting standard classes is generally problematic and not a recommended solution for most cases. In this case, as @SomeProgrammerDude suggests, it's better to use composition and put the pointer inside your class:

template <class Key, class Data>
class BST
{
    std::unique_ptr<BSTnode<Key, Data>> root;
    // operations ...
};

Noone would want to use your BST class to replace the unique_ptr anyway. It's a separate data container that just happens to utilize unique_ptr to store its data.

Upvotes: 1

Related Questions