c++ Most clean way to implement duplicate Binary Search Tree for complex type

Question

I have tried to make my own implementation for a BST task I was given for a complex type (Transaction), that should be able to store duplicate values as well.

However, I am not sure if I have gone about it the right, way and if there is anything I could do to make my code cleaner / more to c++ best practices?

I was told multiset/multimap is something I could use and decided to go with multimap and everything seems to be working ok unless anyone can spot things I could have done better.

(Still very new to c++ and coding in general, just looking for some better coding practices).

#include<iostream>
using namespace std;
#include <algorithm>
#include <cctype>
#include <string>
#include <memory>
#include <map>

// Complex type used for the BST
class Transaction
{
private:
    std::string desc;
    time_t timestamp;
    std::string value;
    bool isWithdrawal;

public:

    Transaction(const std::string& value, std::string reason = "None.")
    : desc(reason), timestamp(time(nullptr)), value(value) { // timestamp is current date/time based on current system

        // Lambda to convert reason to lower to we can identify elements easier
        std::transform(reason.begin(), reason.end(), reason.begin(),
            [](unsigned char c) { return std::tolower(c); });
    
        this->isWithdrawal = (reason.find("withdrawal") != std::string::npos) ? true : false;
    } 

    std::string toString() const {
        // convert timestamp to string form
        const char* string_timestamp = ctime(&timestamp);
    
        if(this->isWithdrawal) { return "-- " + desc + ": -£" + value + " on " + string_timestamp;}
        else {return "-- " + desc + ": £" + value + " on " + string_timestamp;}
    }
    
    // Gets the amount, converts it to a double and returns it
    double getAmount() const {
        return std::stod(this->value);
    }
};


// The binary search tree implementation
class BST {
    
    struct node {
        multimap<const double, std::shared_ptr<Transaction>> data;
        node* left;
        node* right;
    };

    node* root;

    node* makeEmpty(node* t) {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(std::shared_ptr<Transaction> x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data.insert(pair<const double, std::shared_ptr<Transaction>>(x->getAmount(), x));
            t->left = t->right = NULL;
        }
        else if(x->getAmount() == getFirstData(t->data)){
            t->data.insert(pair<const double, std::shared_ptr<Transaction>>(x->getAmount(), x));
        }
        else if(x->getAmount() < getFirstData(t->data)){
            t->left = insert(x, t->left);   
        }
        else if(x->getAmount() > getFirstData(t->data)){
            t->right = insert(x, t->right);   
        }
        return t;
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t) {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    void inorder(node* t) {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << getFirstData(t->data) << " ";
        inorder(t->right);
    }

    node* find(node* t, double x) {
        if(t == NULL)
            return NULL;
        else if(x < getFirstData(t->data))
            return find(t->left, x);
        else if(x > getFirstData(t->data))
            return find(t->right, x);
        else
            return t;
    }

public:
    BST() {
        root = NULL;
    }

    ~BST() {
        root = makeEmpty(root);
    }

    void insert(std::shared_ptr<Transaction> x) {
        root = insert(x, root);
    }

    void display() {
        inorder(root);
        cout << endl;
    }

    std::string search(double x) {
        node* result = find(root, x);
        if(result != NULL) { return loopNode(result->data); }
        else { return "N/A"; }
    }
    
    

    // Gets the first pair key from a multimap
    double getFirstData(const multimap<const double, std::shared_ptr<Transaction>>& m){
        // Declare an iterator to first element
        auto itr = m.begin();
          
        return itr->first;
    }
    
    // Loop through a node and return its values
    std::string loopNode(const multimap<const double, std::shared_ptr<Transaction>>& m){
        std::string result;
        
        for (auto it = m.begin(); it != m.end(); ++it){
            result += (*it).second->toString();
        }
        
        return result;
    }
};

int main() {
    BST t;
    
    t.insert(std::make_shared<Transaction>("1400", "Withdrawal"));
    t.insert(std::make_shared<Transaction>("1400.59", "Deposit"));
    t.insert(std::make_shared<Transaction>("1400.59", "Deposit - test"));
    t.display();
    
    std::cout << t.search(1400.59);
    
    return 0; 
}

IMPROVED VERSION

#include<iostream>
using namespace std;
#include <algorithm>
#include <cctype>
#include <string>
#include <memory>
#include <set>

// Complex type used for the BST
class Transaction
{
private:
    std::string desc;
    time_t timestamp;
    std::string value;
    bool isWithdrawal;

public:

    Transaction(const std::string& value, std::string reason = "None.")
    : desc(reason), timestamp(time(nullptr)), value(value) { // timestamp is current date/time based on current system

        // Lambda to convert reason to lower to we can identify elements easier
        std::transform(reason.begin(), reason.end(), reason.begin(),
            [](unsigned char c) { return std::tolower(c); });
    
        this->isWithdrawal = (reason.find("withdrawal") != std::string::npos) ? true : false;
    } 

    std::string toString() const {
        // convert timestamp to string form
        const char* string_timestamp = ctime(&timestamp);
    
        if(this->isWithdrawal) { return "-- " + desc + ": -£" + value + " on " + string_timestamp;}
        else {return "-- " + desc + ": £" + value + " on " + string_timestamp;}
    }
    
    // Gets the amount, converts it to a double and returns it
    double getAmount() const {
        return std::stod(this->value);
    }
    
    // Overloading comparision operators by value (transaction amount)
    bool operator < (const Transaction& rhs){
      return this->value < rhs.value;
    }
    
    bool operator > (const Transaction& rhs){
      return this->value > rhs.value;
    }
    
    bool operator == (const Transaction& rhs){
      return this->value == rhs.value;
    }
    
    bool operator != (const Transaction& rhs){
      return this->value != rhs.value;
    }
};


// The binary search tree implementation
class BST {
    
    struct node {
        std::multiset<std::shared_ptr<Transaction>> data;
        node* left;
        node* right;
    };

    node* root;

    node* makeEmpty(node* t) const {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(std::shared_ptr<Transaction> x, node* t) {
        
        if(t == NULL)
        {
            t = new node;
            t->data.insert(x);
            t->left = t->right = NULL;
        }
        else if(*x == getFirstData(t->data)){
            t->data.insert(x);
        }
        else if(*x < getFirstData(t->data)){
            t->left = insert(x, t->left);   
        }
        else if(*x > getFirstData(t->data)){
            t->right = insert(x, t->right);   
        }
        return t;
    }

    node* findMin(node* t) const {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t) const {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* find(node* t, double x) {
        if(t == NULL)
            return NULL;
        else if(x < getFirstData(t->data).getAmount())
            return find(t->left, x);
        else if(x > getFirstData(t->data).getAmount())
            return find(t->right, x);
        else
            return t;
    }

public:
    BST() {
        root = NULL;
    }

    ~BST() {
        root = makeEmpty(root);
    }

    void insert(std::shared_ptr<Transaction> x) {
        root = insert(x, root);
    }

    std::string search(double x) {
        node* result = find(root, x);
        if(result != NULL) { return loopNode(result->data); }
        else { return "N/A"; }
    }
    
    
    // Gets the first pair key from a multimap
    Transaction getFirstData(const multiset<std::shared_ptr<Transaction>>& m) const{
        // Declare an iterator to first element
        auto itr = m.begin();
        
        return *(*itr);
    }
    
    // Loop through a node and return its values
    std::string loopNode(const multiset<std::shared_ptr<Transaction>>& m) const{
        std::string result;
        
        for (auto it = m.begin(); it != m.end(); ++it){
            result += (*it)->toString();
        }
        
        return result;
    }
};


int main() {
    BST t;
    
    t.insert(std::make_shared<Transaction>("1400", "Withdrawal"));
    t.insert(std::make_shared<Transaction>("1400.59", "Deposit"));
    t.insert(std::make_shared<Transaction>("1400.59", "Deposit - test"));
    
    std::cout << t.search(1400.58);
    
    return 0; 
}
```

Answer 1

Don’t Write using namespace std

Before anyone else says it, here is the answer everybody always links to. It’s good advice.

Personally, I think there are some times when it’s a good idea to import a few things from namespace std. For example, you want to use STL classes such as std::multimap<double, Transaction> that are verbose to write out and a real hassle to change to another data structure. So I often write something like

using TransactionDB = std::multimap< double, Transaction >;

This lets me change the implementation to a multiset if I want to do a comparison on the transactions themselves, or use a different allocator to avoid heap contention, or switch to a hash table if I don’t need the data to be sorted by key. Most of the code will still work after changing one line.

I also still prefer cout to std::cout, ptrdiff_t to std::ptrdiff_t, and so on—especially for identifiers that I’ve been using since before there was a STL and that will never be confused for anything else. A big part of the rationale of the answers I linked to is that there have been many different classes named vector, map and especially string, but nobody who isn’t deliberately obfuscating has ever redefined cout.

Don’t Reinvent the Wheel

In the real world, you would just use std::multiset. (This doesn’t officially have to be a self-balancing binary search tree, but it must have similar time complexity on its operations.) To sort your objects, you want to implement operator< on your class. If you cannot, an alternative is to write your own Compare class and use std::multiset< SomeType, SomeTypeCompare >.

Your current implementation has a std::multimap in each node with a double (holding the amount) as the key and a unique pointer to the Transaction as the data. Storing a unique pointer rather than an object only makes sense if you are planning on transferring ownership. If you’re not planning to pluck and delete nodes from the tree when you extract them, you probably want to emplace the transactions into the database, which constructs them in place, and return references or a weak_ptr to them. Another alternative, if you expect the references to outlive the tree itself, is to store a shared_ptr.

I don’t see a reason to store a different tree in every node of your BST. if you want to store a key and value in each node, you can just give them key and data members.

If you want to use the STL data structure internally, but wrap it in a different interface, the internal tree should be a private: data member, or you could possibly inherit using : private std::multiset<Transaction> or whatever you go with.

Store Financial Data as Fixed-Point

You don’t want floating-point math on them, or round-off error. Decide whether to store them as cents, mils or milrays and whether you need long or long long width. Divide by 100, 1,000 or 10,000 when you print them, and use correct precision specifiers so $4.50 doesn’t print as $4.5. You also don’t want amounts like $10.99998.

Use the Right Keys

Do you really want to sort your transactions and iterate through them by the transaction amount? Would it make more sense to sort them by date? Or allow them to be sorted in different ways, by specifying a different Compare object? If you do want to sort by the amount, does it make more sense to store this as a separate key variable than to make it part of the Transaction data, and define

bool Transaction::operator< (const Transaction& y)
{
  return amount < y.amount;
}

This particular member function can and should be declared as const, constexpr and noexcept.

Or you could define multiple classes implementing the comparison template parameter, allowing you to declare different trees that sort transactions by amount, time posted, customer ID, transaction type, and so on.

Let your Trees be const

Right now, if you declare a const BST, you couldn’t do anything with it, because it has no const methods defined. You also can’t use any of its methods in a constexpr expression.

You should mark methods as const or constexpr where you can, and perhaps add both a const overload that looks up and returns const data and a non-const overload that looks up and returns a mutable reference to data.

If You Do Reinvent the Wheel, Do it Right

I get the impression that you were assigned this as a learning exercise that you want to solve yourself.

In that case, you should pick a self-balancing tree that you like, read how they work (but not look at an existing implementation until later), and implement that from scratch, without using STL set or map classes at all. Red-black trees are a great, standard choice (especially if you don’t need to delete from them). AVL or scapegoat trees are worth looking at.

A Second Round

You wrote an improved version and requested my feedback, so here it goes.

You’re still doing the unusual thing where you both have a vestigial implementation of a BST with left and right node pointers, but you also separately store a STL binary search tree in the root node. This isn’t what you want to do. In the real world, you wouldn’t reinvent the wheel. For the sake of this learning exercise, you want to write your own. You might try to implement part of the same interface as the STL, using the same names for things both implementations have, such as BST::value_type and insert, but the spirit of the assignment is to write your own.

I would therefore recommend you delete all use of STL containers other than string, string_view, and possibly vector and array. Look up the algorithms (but not the implementation) of a red-black tree and try to implement that. That is, you’ll add two bool values like left_is_red and right_is_red. (Alternatively, you could have a polymorphic node type, and implement a 2-3-4 tree, with very similar logic.) Your original idea of storing a std::unique_ptr<Transaction> is a good one when you’ll be moving the data around between nodes as the tree self-balances, and returning a reference or weak_ptr to it. Deleting values is more complicated than inserting them, so you might want to leave that for last.

You use C-style node pointers, which commits you to C-style memory management. You would be better off using std::unique_ptr<node>, which is just as easy to test for validity, and manages its memory automatically. You can move subtrees around with statements such as right = std::move(subtree);. This is just as fast as assigning a C-style pointer.

Coding Style

You’re still using namespace std; after #include <iostream> and before your other headers. I suspect that what you want is to import only the identifiers from <iostream>. If so, there are ways to.

The most robust one, which you’ll often see me do, is to list the specific declarations you want to use. I never really got into the habit of doing this the C++17 way, but the modern way to write this would be:

using std::cin, std::cout, std::endl;

I always make sure to list them in alphabetical order, so it’s easy to look one up. This makes your code as future-proof as possible. Good implementations of the standard library usually try to avoid declaring global identifiers that might clash with yours, although this has often happened in the past. This method also has the advantage that you’ll see exactly what you’re using from each header file you include, and have a good idea when it’s safe to remove one, although I often leave a short comment such as

#using <utility> // For from_chars, move

There is also an older way to get only the identifiers from one header file in the global namespace. You can write

#include <iostream.h>

This is how all all C++ programs were originally written. At one point, the C++ standards committee actually thought it could break all existing code in the language, but compilers never stopped supporting this syntax. Inevitably, the committee gave in and tried to regularize this de facto standard: every standard header comes in another version with .h that declares every identifier in both the global namespace and also with ::std.

You name a method toString, but snake_case is more conventional here than camelCase. The C++ standard library provides both std::to_string, which follows the current locale’s rules for a thousands and decimal separator, and std::to_chars, which is locale-independent. The former might give you 1.234,56 rather than 1,234.56.

You can still keep the interface that lets you convert either to a double value or a human-readable string. Good job of encapsulation! It would be much more annoying to make this change if you hadn’t thought of that.

Data Types

You often take std::string arguments, either by copy or by reference. It’s good practice to accept std::string_view instead. This is a light-weight object that it’s efficient to copy, and both C and C++ strings convert to it implicitly. So, you could instead write

Transaction( const std::string_view value, const std::string_view reason = "None." )

One reason you might not want to do this is if you’re passing in an temporary value that it’s more efficient to move than copy. For example, if you write Transaction("10.99"), the string "10.99" will convert to an expiring temporary. If you write an overload that accepts std::string&&, you can make a more-efficient shallow copy, instead of a deep one.

Speaking of which, you have the right idea about storing monetary values in an exact-precision type and having a member to convert them to either a human-readable string or a floating-point number, but the format I would suggest is an integral type with one or two extra sig figs of precision. I might store the result in a long long int, denominated in milrays, and then the conversion to dollars would be dividing by 10000.0. You might keep accepting monetary strings in your constructor, so you can parse them for validity, but you generally want to do math on them, not sort their string representations in alphabetical or lexicographic order.

const and constexpr

Right now, you have

bool operator < (const Transaction& rhs){
  return this->value < rhs.value;
}

This has two main flaws: it will not work with a const Transaction on the left, and it performs a string comparison. If you store the value as a numeric type, and update the qualifiers, it could become something like,

constexpr bool operator< (const Transaction& rhs) const noexcept {
   return value_milrays < rhs.value_milrays;
}

This works for const objects on both sides of the comparison, enables constant-folding optimizations in expressions that can be evaluated at compile time, and also allows certain optimizations related to exception-handling.

Follow-up on Return Types

Our discussion in the comments got me thinking about the return type of functions like BST::find. The STL containers have a member function with the same name, and the Principle of Least Surprise would be that your container’s tree.find(key_value) would behave similarly.

The STL’s find returns an iterator, which can be dereferenced to get the value of the element. Returning a node* isn’t great, both because *tree.find(key_value) gives you something completely different, and because this exposes the entire internal structure of the tree.

So, a quick fix would be to put this in the class definition:

using key_type = double;
using value_type = Transaction;
using iterator = value_type*; // Can be dereferenced, but NOT incremented!
using const_iterator = const value_type*; // Ditto.

constexpr const_iterator end() const noexcept { return nullptr; }
constexpr const_iterator cend() const noexcept { return nullptr; }
iterator find(key_type x);
const_iterator find(key_type x) const;

This is the fastest way to get a STL-like interface, where code like this will still work:

 while ( const auto it = tree.find(current_key); it != tree.end() ) {
    const auto value = *it;

On the other hand, if you call Transaction* an iterator, programmers might think they can increment it to do an in-order traversal. This will compile, but actually cause a memory-corruption bug. If you wanted to make an iterator that works as expected, you would need to write your own class that wraps a node*, add a pointer in each node to the parent node to enable always finding the successor or predecessor, then write operator++ and operator-- to find the successor or predecessor, respectively. It would also need operator* to get the stored data and operator-> to access its fields. This is probably overkill here.

But if you’re going to make BST::find behave differently from stl::set::find, which is a reasonable choice, I’d suggest calling it something else, like BST::lookup. Your interface should probably not return a node*.

Answer 2

  Transaction(const std::string& value, std::string reason = "None.")
    : desc(reason),

Why are you passing reason by value? If you meant to use the "sink" idiom, you are missing the call to move in the initializer list.

---

this->isWithdrawal
Don't write this-> everywhere! Your members are in scope when you are writing member functions.

this->isWithdrawal = (reason.find("withdrawal") != std::string::npos) ? true : false;

why would you ever write: somebool ? true : false ? How is that any different from somebool by itself? I think you're not internalizing that boolean values are values like anything else, not something that can only be used as a condition in a special kind of statement.

---

        std::string result;
        
        for (auto it = m.begin(); it != m.end(); ++it){
            result += (*it)->toString();
        }

First, use a range-based for loop!
Second, this is just a transformation of each element. Look at standard algorithms or "range" operators that let you traverse one collection and generate another.

---

   // Overloading comparision [sic] operators by value (transaction amount)
    bool operator < (const Transaction& rhs){
      return this->value < rhs.value;
    }

Why don't you allow comparing two Transaction objects when the one on the left is const?

If you are using C++20, you only need define a single three-way comparison and get all the relational operations available.

---

std::string toString() const {

Follow standards. I can generally call (non-member) to_string(x) for any type of x... but not your type! Besides being odd and different and something people need to remember, it will break any generic code where the type of x is allowed to by anything that works.