Sorting and using a binary search on a vector of object pointers

Question

I'm trying to write some c++ code that will perform a binary search on a vector of object pointers. For reference my program is like a bank account system where a user can open a bank account and make deposits/withdrawals on said bank account, which in turn create a new transaction object that is pushed back to a list of Transaction pointer objects like so: in main.cpp:

else if (userCommand == "withdraw")
                {
                    try
                    {
                        int index;
                        float amount;
                        time_t currentTime = time(nullptr); //gets current time
                        cout << "Please pick the account you wish to withdraw from starting from 1: " << endl;
                        cin >> index;
                        if (index > allAccounts.size() || index <= 0) throw InvalidIndexException(); //0 is not an option for any other command other than withdraw so we include it for the exception
                        cout << "Please give the amount of money you wish to withdraw: " << endl;
                        cin >> amount;
                        if (amount < 0) throw NegativeValue("Withdrawal");
                        allAccounts[index - 1]->withdraw(amount);
                        Transaction* accountTransaction = new Transaction("Withdrawal", currentTime, amount); //creates new Transaction object that will be passed into the account object
                        allAccounts[index - 1]->addTransaction(accountTransaction);
                    }
                    catch (ExceedOverDraftException)
                    {
                        cout << "Current account overdraft exceeded" << endl;
                    }
                    catch (NegativeWithdrawalException)
                    {
                        cout << "Savings account cannot go below 0" << endl;
                    }
                    catch (InvalidIndexException)
                    {
                        cout << "Index given does not exist" << endl;
                    }
                    catch (NegativeValue e)
                    {
                        cout << e.getMessage() << endl;
                    }
                }
else if (userCommand == "deposit")
                {
                    try
                    {
                        int index;
                        float amount;
                        time_t currentTime = time(nullptr);
                        cout << "Please pick the account you wish deposit to starting from 1: " << endl;
                        cin >> index;
                        if (index > allAccounts.size() || index <= 0) throw InvalidIndexException();
                        cout << "Please give the amount of money you wish to deposit: " << endl;
                        cin >> amount;
                        if (amount < 0) throw NegativeValue("Deposit");
                        allAccounts[index - 1]->deposit(amount);
                        Transaction* accountTransaction = new Transaction("Deposit", currentTime, amount);
                        allAccounts[index - 1]->addTransaction(accountTransaction);
                    }
                    catch (InvalidIndexException)
                    {
                        cout << "Index does not exist" << endl;
                    }
                    catch (NegativeValue e)
                    {
                        cout << e.getMessage() << endl;
                    }
                }
else if (userCommand == "search")
            {
                try 
                {
                    int index;
                    float valueAnswer;
                    int transactionsSize;
                    cout << "Please say which account you wish to search transaction for starting from 1" << endl;
                    cin >> index;
                    if (index > allAccounts.size()) throw InvalidIndexException();
                    transactionsSize = allAccounts[index - 1]->getHistorySize();
                    cout << "Please state what value you wish to search for" << endl;
                    cin >> valueAnswer;
                    cout << allAccounts[index - 1]->search(valueAnswer, 0, transactionsSize - 1);
                
                }
                catch (InvalidIndexException) 
                {
                    cout << "Index given does not exist";
                }
                catch (TransactionNotFound e) 
                {
                    cout << e.getMessage();
                }
            }

in account.cpp:

    void Account::addTransaction(Transaction* t)
    {
        history.push_back(t); //as the vector is full of pointers the parameter must also be a pointer.
        sort(history.begin(), history.end());
    }
    Transaction Account::search(float value, int start, int end) throw (TransactionNotFound) //search function is a binary search
{
    if (start <= end)
    {
        for (int i = 0; i < history.size(); i++)
        {
            cout << history[i]->getValue() << endl;
        }
        int mid = (start + end) / 2; //midpoint of the vector
        if (history[mid]->getValue() == value) return *history[mid];
        else if (history[mid]->getValue() < value) return search(value, mid + 1, end);
        else if (history[mid]->getValue() > value) return search(value, start, mid - 1);
    }
    else throw TransactionNotFound(value); //if the array has been searched to the point that start has reached the end the transaction doesn't exist
}

As you can see the main idea is that every time a new transaction is made, either from calling deposit or withdraw, an object of transaction is made which is then added to the vector and then should be sorted in ascending order. To sort I tried to follow a guide from an older stack overflow message that was using struct objects rather than class objects (Sorting a vector of custom objects) which seemed to use operator overloading of the < operator on the struct object that would then allow the vector of struct objects to be sorted, which I tried adapting in my transaction class as a friend function like so: in transaction.cpp:

bool operator <(const Transaction& t1, const Transaction& t2)
{
    return (t1.value < t2.value); //checks if the next value in the vector is greater than the current value in the vector.
}

However, I have tested the sort method and it doesn't seem to be sorted the objects as I expect it to, in that it doesn't seem to be sorted the objects at all, causing my TransactionNotFound exception to be thrown. I'm genuinely not sure what I've done wrong, I'm assuming it is how I've done my operator overload, but I don't know what I need to do to fix it. Sorry if my code looks awful, I think I realised that my try and catch blocks could go outside the if statement. Also if there is any information about my code that might be needed please let me know, I'm new to stack overflow in general so I'm not sure if what I've included is needed or not. Any help people can give is really appreciated!

Answer 1

Besides many many design flaws, you have several major semantic errors.

---

1st, and most important, and the reason, why sort does not work:

You store pointers in your std::vector "history". But in the compare function, you compare references, so values and NOT pointers.

So, the sort function will not sort according to the values stored in the transaction, but according to their address in memory, which you do not know and may be random (but out of your control),

If you create one Transaction after the other, then they may be created in with ascending memory addresses. And then std::sort will do nothing. But that is pure coincidence.

So, you need to change your custom sort function. For the simplicity of it, I will use a Lambda. Then the sortstatement would look like this:

 std::sort(history.begin(), history.end(), 
            [](const Transaction* t1, const Transaction* t2) {return t1->value < t2->value; });

Then the sort function will do what you want.

---

2nd, The search function is implemented wrongly.

The stop condition for the recursion is incorrect. It must be if (end < start). Also the calculation of mid is wrong. Use a piece of paper and draw a picture, then you will see it. The correct statement is:

int mid = start + (end-start) / 2;

You always need to add the new start value. Otherwise you can never reach the upper half of the interval.

Then, a very important statement. You cannot rely on an equal comparison for float types. Therefore, if you want to calculate with currencies, then do not use float or double values. Use integer types * 100.

Now let use look at a minimum reproducible example:

#include <iostream>
#include <string>
#include <ctime>
#include <vector>
#include <algorithm>

struct Transaction {
    std::string type{};
    time_t time{};
    int value{};

    int getValue() { return value; }
   
};
struct Account {
    std::vector<Transaction*> history{};

    void addTransaction(Transaction* t) {
        history.push_back(t);
        std::sort(history.begin(), history.end(), 
            [](const Transaction* t1, const Transaction* t2) {return t1->value < t2->value; });
    }


    Transaction* search(float value) {
        return bsearch(value, 0, history.size()-1);
    }
    Transaction* bsearch(float value, int start, int end) 
    {
        for (unsigned int i = 0; i < history.size(); i++) {
            //    std::cout << history[i]->getValue() << '\n';
        }

        if (end < start) return nullptr;

        int mid = start + (end-start) / 2; //

        if (history[mid]->getValue() == value) 
            return history[mid];

        else if (history[mid]->getValue() < value) return bsearch(value, mid + 1, end);
        else return bsearch(value, start, mid - 1);
    }
};

int main() {

    Account account{};

    // Add some demo transactions
   
    account.addTransaction(new Transaction{ {},{},9 });
    account.addTransaction(new Transaction{ {},{},8 });
    account.addTransaction(new Transaction{ {},{},7 });
    account.addTransaction(new Transaction{ {},{},6 });
    account.addTransaction(new Transaction{ {},{},5 });
    account.addTransaction(new Transaction{ {},{},4 });
    account.addTransaction(new Transaction{ {},{},3 });
    account.addTransaction(new Transaction{ {},{},2 });
    account.addTransaction(new Transaction{ {},{},1 });

    Transaction* searchResult{};

    searchResult = account.search(4);
    if (searchResult)
        std::cout << "\nFound: " << searchResult->getValue() << '\n';
    else
        std::cout << "\nError: 4 not found\n\n";

    searchResult = account.search(42);
    if (searchResult)
        std::cout << "\nFound: " << searchResult->getValue() << '\n';
    else
        std::cout << "\nError: 42 not found\n\n";

    return 0;
}

---

So, maybe you get the idea.

---

But now, and more important. The design flaws.

You are using tons of exceptions. And you use them like if statements.

DO NOT do this. Use exceptions for exceptionally problems, not for minor stuff that can be handled by simple if statements.

---

You should make use of C++ and object oriented programming.

A "deposit" and a "withdrawal" ar both Transactions. So create a base class "Transaction" and derive a class "Deposit" and a class "Withdrawal" from that.

---

Do not use raw pointers for owned memory, but std::unique_ptr. Otherwise, you create tons of memory leaks. If you write new, then, somehwere, you need to write delete as well.

Or use smart pointers, like the unique_ptr. That will do the job for you.

---

In general, a good hint is, to always make a design, for example on a piece of paper or however, and then start programming.

---

Anyway, please continue your good work.