c++ - 标准排序似乎永远循环

Question

现在我有一门课来做二分搜索。该类接受一个向量，但随后我告诉该类进行排序。

我需要能够仅按名字或姓氏对其进行排序，因此我将字符参数设置为该类中的一个选项，以更改对向量进行排序的方式。我还在那个类中创建了一个 operator() 函数来使用 *this，作为对向量进行排序的类指针。但它似乎只是永远循环。谁能告诉我为什么？代码如下。

*请注意，如果有一些我不遵循的一般做法，请随时通知我。我不想现在就开始养成坏习惯。

按要求：Getname

void personType::getName(string& first, string& last)
{
    // get the name and set it
    first = firstName;
    last = lastName;
}


bool sBinary::operator()(studentType student1, studentType student2){
    string toCheck1, toCheck2, fName1,lName1 ,fName2 , lName2;
    student1.getName(fName1, lName1);
    student2.getName(fName2, lName2);
    toCheck1=checkStr(fName1, lName1);
    toCheck2=checkStr(fName2,lName2);
    return toCheck1<toCheck2;
}

string sBinary::checkStr(string fName, string lName){
    string toCheck;
    switch (choice){
    case 'f':
    case 'F':
        toCheck=fName;
        break;
    case 'l':
    case 'L':
        toCheck=lName;
        break;
    case 'r':
    case 'R':
        toCheck=fName+lName;
        break;
    default:
        toCheck=lName+fName;

    }

    return toCheck;

}


sBinary::sBinary(vector<studentType> _sList, char _choice){
    sList=_sList;
    steps=0;
    choice=_choice;
    sort(sList.begin(),sList.end(), *this);
}

score 6 · Accepted Answer

因此，似乎不是永远循环，而是执行时间过长。这是完全不同的故事。您的代码中有一些悲观之处：主要关注的是您将*this, 传递给排序算法：

sort(sList.begin(),sList.end(), *this);

std::sort按值获取比较谓词并将其复制多次。你可以看到它，如果你定义了复制构造函数：

sBinary(const sBinary& r):choice(r.choice), sList(r.sList)
{
    std::cout << "copied\n";
}

并且您的向量与对象本身一起被复制。

例如，如果数组大小为 200，则std::sort复制对象13646 次。这意味着，涉及2700000 个学生复制操作。

所以，你不应该传递*this给std::sort. 您最好定义静态函数lessThen，而不是operator()将其传递给排序算法。

进一步的改进：

按引用传递，而不是按值传递。例如，在您的lessThen函数声明中应如下所示

static bool lessThen(const studentType& student1, const studentType& student2);
                   //^^^^^            ^
                   //constant         reference

重构你的studentType类。

你最好有 2 个单独的函数，返回名字和姓氏（通过常量引用）。在这种情况下，您可以摆脱将名称复制到临时变量。请注意，当您有单个功能时，您必须复制名字和姓氏，即使永远不会使用一个名字：
```
const std::string& first_name() const { return _fname; }
const std::string& last_name() const { return _lname; }
```

score 3 · Accepted Answer

我将其包括在内只是因为您应该知道如何排序此列表的替代方法。Lol4t0 已经谈到了拥有一个复制成本高昂的比较器的可怕之处（而且您将很难拥有一个比您的原始实现更昂贵的比较器）。

当std::sort给定一个尽可能简单的比较器时，算法效果最好，尽可能多地内联它的实现。理想情况下，您可以像这样实现比较器运算符功能：

struct cmpObjects
{
    bool operator ()(const Object& left, const Object& right) const
    {
        return (left compared to right somehow);
    }
}

首先注意 const 引用的使用。您唯一应该考虑不这样做的情况是您的基础数据是本机内在类型（例如int,char等）。在这些情况下，按值传递实际上更快。但在这种情况下，您的学生记录通过引用访问无疑会更有效（无需复制）。

关于您的特定任务，您的任务会稍微复杂一些，因为您的排序标准是基于选择的。如果你想最大化排序速度，你最好为每个选择情况提供一个单一的、紧凑的、廉价的可复制比较器。然后，根据该选择使用适当的比较器，在调用之前std::sort确定。

例如，如果您知道要按姓氏排序，则：

// compares last name
struct cmp_LName
{
    bool operator ()(const studentType& left, const studentType& right) const
    {
        return left.lastName < right.lastName;
    }
}

或者也许是名字，姓氏，例如：

// compares first name, then last name only if first name is identical.
struct cmp_FNameLName
{
    bool operator ()(const studentType& left, const studentType& right) const
    {
        int res = left.firstName.compare(right.firstName);
        return res < 0 || (res == 0 && left.lastName < right.lastName);
    }
}

这使得您的构造函数的部分窥视sBinary现在看起来像这样：

sBinary(const std::vector<studentType>& sList_, char choice)
    : sList(sList_)
{
    switch (choice)
    {
        case 'L':
        case 'l':
            std::sort(sList.begin(), sList.end(), cmp_LName());
            break;

        case 'R':
        case 'r':
            std::sort(sList.begin(), sList.end(), cmp_FNameLName());
            break;

        ....
    }
}

首先请注意，我们在实际调用之前选择了我们选择的比较技术std::sort。当我们这样做时，我们清楚地定义了我们正在使用的自定义比较器中的确切标准，并且管理它的开销为零。

那么有什么取舍呢？您将需要四个比较器（cmp_LName、cmp_FName、cmp_FNameLName 和 cmp_LNameFName），根据您的传入选择触发要使用的比较器。但是，这样做的好处不容小觑：这将是根据选择对列表进行排序的最快方法。

附录：单个比较器

如果您完全赞同使用单个比较器的想法，那么请尽可能降低复制成本，并将排序条件中的选择隐藏在其中，const以便为编译器提供清理代码的最佳机会。我在sBinary下面包含了一个完整的扩展来展示如何做到这一点，但我强调，如果速度是您的主要关注点，这不是最佳选择。

class sBinary
{
    // compare student based on fixed choice determine at construction.
    struct cmp_student
    {
        const char choice;
        cmp_student(char choice) : choice(choice) {};

        bool operator()(const studentType& left, const studentType& right) const
        {
            switch (choice)
            {
                case 'F':
                case 'f':
                    return left.firstName < right.firstName;

                case 'L':
                case 'l':
                    return left.lastName < right.lastName;

                case 'R':
                case 'r':
                {
                    int res = left.firstName.compare(right.firstName);
                    return res < 0 || (res == 0 &&  left.lastName < right.lastName);
                }

                default:
                {
                    int res = left.lastName.compare(right.lastName);
                    return res < 0 || (res == 0 &&  left.firstName < right.firstName);
                }
            }
        }
    };

public:
    sBinary(const std::vector<studentType>& sList, char choice)
        : sList(sList)
    {
        std::sort(sList.begin(), sList.end(), cmp_student(choice));
    }

    std::vector<studentType> sList;
};

c++ - 标准排序似乎永远循环

2 回答 2

进一步的改进：

Related

Reference