对对象指针向量进行排序和使用二进制搜索

Question

我正在尝试编写一些 C++ 代码来对对象指针向量执行二进制搜索。作为参考，我的程序就像一个银行账户系统，用户可以在其中开设一个银行账户并在该银行账户上进行 deposits/withdrawals，这反过来又会创建一个新的交易对象，该对象被推回交易指针对象列表，例如所以：在 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();
                }
            }

在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
}

如您所见，主要思想是每次进行新交易时，无论是调用存款还是取款，都会创建一个交易对象，然后将其添加到向量中，然后按升序排序.为了进行排序，我尝试遵循使用结构对象而不是 class 对象（Sorting a vector of custom objects）的旧堆栈溢出消息的指南，该消息似乎在结构对象上使用 < 运算符的运算符重载然后允许对结构对象的向量进行排序，我尝试在我的交易 class 中将其调整为友元函数，如下所示：在 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.
}

但是，我已经测试了 sort 方法，它似乎没有像我期望的那样对对象进行排序，因为它似乎根本没有对对象进行排序，导致我的 TransactionNotFound 异常被抛出。我真的不确定我做错了什么，我假设这是我完成运算符重载的方式，但我不知道我需要做什么来修复它。对不起，如果我的代码看起来很糟糕，我想我意识到我的 try 和 catch 块可以超出 if 语句。此外，如果可能需要有关我的代码的任何信息，请告诉我，我一般是堆栈溢出的新手，所以我不确定是否需要我包含的内容。非常感谢人们可以提供的任何帮助！

Answer 1

除了许多设计缺陷外，您还有几个主要的语义错误。

第一个，也是最重要的，也是为什么排序不起作用的原因：

您将指针存储在 std::vector“历史记录”中。但是在比较函数中，你比较引用，所以比较值而不是指针。

因此，排序函数不会根据存储在交易中的值进行排序，而是根据它们在内存中的地址进行排序，您不知道并且可能是随机的（但不受您的控制），

如果您一个接一个地创建事务，那么它们可能会以递增的内存地址创建。然后 std::sort 什么都不做。但这纯属巧合。

因此，您需要更改自定义排序功能。为了简单起见，我将使用 Lambda。那么 sort 语句将如下所示：

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

然后排序函数将执行您想要的操作。

2、搜索功能实现错误

递归的停止条件不正确。必须是if (end < start)。 mid 的计算也是错误的。用一张纸画一幅画，然后你就会看到它。正确的说法是：

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

您总是需要添加新的起始值。否则你永远无法到达区间的上半部分。

然后，一个非常重要的声明。您不能依赖浮点类型的相等比较。因此，如果要使用货币进行计算，则不要使用 float 或 double 值。使用整数类型 * 100.

现在让我们看一个最小的可重现示例：

#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;
}

所以，也许你明白了。

但是现在，更重要了。设计缺陷。

您正在使用大量异常。你可以像 if 语句一样使用它们。

不要这样做。将异常用于异常问题，而不是用于可以通过简单 if 语句处理的小问题。

你应该使用 C++ 和面向对象编程。

“存款”和“取款”都是交易。因此，创建一个基础 class“交易”并从中派生一个 class“存款”和一个 class“取款”。

不要对拥有的内存使用原始指针，但是std::unique_ptr。否则，您会造成大量内存泄漏。如果你写new，那么，有些时候，你还需要写delete。

或者使用智能指针，比如unique_ptr。这将为您完成工作。

总的来说，一个好的提示是，总是先做一个设计，例如在一张纸上，然后开始编程。

无论如何，请继续努力。

对对象指针向量进行排序和使用二进制搜索

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

c++

sorting

pointers

vector

binary-search