c++ - 自定义比较器以将唯一元素插入到 C++ 中的集合中

Question

我有以下代码片段，用于将元素插入集合并检索它们。但是正如您从示例输出中看到的那样，学生 1 的名字(即“stud1”)并没有被打印出来，即使它是按到达时间排序的。任何人都可以帮助找出这种方法有什么问题吗？

学生.h

#ifndef Student_h
#define Student_h

#include "string"

class Student
{

public:
    Student();
    ~Student();

    void setName(const std::string& p_name)     { _name = p_name; }
    void setArrivalTime(const int p_arr_t)      { _arrivalTime = p_arr_t; }

    const std::string& getName() const         { return _name; }
    const int getArrivalTime() const           { return _arrivalTime; }

private:
    std::string _name;
    int _arrivalTime;

};

struct CompareStudByArrivaltime
{
    const bool operator()(const Student* s1, const Student* s2) const;
};

#endif /* Student_h */

学生.cpp

#include <stdio.h>
#include "Student.h"

Student::Student()
{

}

Student::~Student()
{

}

const bool CompareStudByArrivaltime::operator()(const Student* s1, const Student* s2) const
{

    if (s1->getName() == s2->getName())
    {
        return false;
    }

    return (s1->getArrivalTime() <= s2->getArrivalTime());
}

main.cpp

#include <iostream>
#include <set>
#include <map>
#include <vector>

#include "Student.h"

typedef std::vector<Student> StudentsPool;
typedef std::set<Student*, CompareStudByArrivaltime> Students;
typedef std::map<std::string,Students> SchoolStudentsMap;

SchoolStudentsMap g_school_studs;
StudentsPool g_stud_pool;

Student* getStud(const std::string& n)
{
    for(StudentsPool::iterator itr = g_stud_pool.begin(); itr != g_stud_pool.end(); ++itr)
    {
        if (itr->getName() == n)
        {
            return &(*itr);
        }
    }

    return NULL;
}

void initObj()
{
    /** School 1 Record */
    std::string school_name = "school1";

    char c1 [] = {'s','t','u','d','1','\0'};
    std::string n1(c1);
    //Student* s1 = new Student();
    Student s1;
    s1.setName(n1);
    s1.setArrivalTime(10);
    g_stud_pool.push_back(s1);

    Student* tmp = NULL;

    tmp = getStud("stud1");
    g_school_studs[school_name].insert(tmp);

    char c2 [] = {'s','t','u','d','2','\0'};
    std::string n2(c2);
    Student s2;
    s2.setName(n2);
    s2.setArrivalTime(2);
    g_stud_pool.push_back(s2);

    tmp = getStud("stud2");
    g_school_studs[school_name].insert(tmp);

    char c3 [] = {'s','t','u','d','3','\0'};
    std::string n3(c3);
    Student s3;
    s3.setName(n3);
    s3.setArrivalTime(5);
    g_stud_pool.push_back(s3);

    tmp = getStud("stud3");
    g_school_studs[school_name].insert(tmp);
}

void processObj()
{
    for(SchoolStudentsMap::iterator itr = g_school_studs.begin(); itr != g_school_studs.end(); ++itr)
    {
        Students& studs = itr->second;

        for(Students::iterator sitr = studs.begin(); sitr != studs.end(); ++sitr)
        {
            Student* s = (*sitr);
            std::cerr << "Name: " << s->getName() << ", Arr Time: " << s->getArrivalTime() << std::endl;
        }
    }

}

int main(int argc, const char * argv[])
{

    initObj();
    processObj();

    return 0;
}

示例输出

Name: stud2, Arr Time: 2
Name: stud3, Arr Time: 5
Name: , Arr Time: 10

Answer 1

看你的比较函数。如果到达时间相同，但元素的顺序不同，您将返回 true。

const bool CompareStudByArrivaltime::operator()(const Student* s1, const Student* s2) const
{
    if (s1->getName() == s2->getName())
    {
        return false;
    }

    return (s1->getArrivalTime() <= s2->getArrivalTime());  
   // what if s1 and s2 are equal, but switched?  You still return true.
}

假设s1和s2到达时间相同。您的函数返回 true。那么假设我们调用了您的比较函数，但这次使用的是 s2 和 s1。您仍然返回 true。怎么可能？怎么能说s1放在s2之前的容器中，然后同时s2应该放在s1之前的容器中呢？编译器问你哪个先出现，当项目相等时你给出了不可能的答案。这就是 std::set 排序标准变得困惑并最终为您提供错误结果的地方。

简而言之，这就是严格弱排序的全部内容，@Slava 给出了解决方案的详细信息。

顺便说一句，切换项目和检查返回值的测试是由调试 Visual C++ 运行时完成的。您的代码可能会立即断言，因为运行时调用排序例程两次，第一次使用 s1, s2，然后使用 s2, s1。如果您为这两种情况返回 true，运行时将中止您的应用程序。

---

另一个问题是您将指向项目的指针存储在此处的 Student vector 中:

g_stud_pool.push_back(s1);
tmp = getStud("stud1");  // <-- gets pointer to item just placed in g_stud_pool
g_school_studs[school_name].insert(tmp);  // <-- pointer to Student from the vector being stored

//...

g_stud_pool.push_back(s2); // <-- invalidates previous pointer
tmp = getStud("stud2");
g_school_studs[school_name].insert(tmp); // <-- map now contains invalid pointer(s)

您正在向 g_stud_pool vector 中添加项目，然后立即使用指向您刚刚放置在 vector 中的项目的指针，通过将该指针放置在您的 std::set 中来引用该项目。

问题在于，每次向 vector 添加一个项目时，指向先前项目的任何指针都可能失效。最终发生的是您的 set 使用的比较函数将使用已失效的地址。

解决此问题的最快方法(不是唯一方法)是更改为在调整大小时不会使指针(和迭代器)失效的容器。这样的容器就是 std::list。所以改成这样:

#include <list>
typedef std::list<Student> StudentsPool;

解决了失效问题，因为 std::list 在调整列表大小时不会使指针和迭代器失效。

Here is a live example