Custom comparator to insert unique elements into a set in c++

Question

I have following code snippet for the purpose of insert elements into a set and retrieve them. But as you can see from the sample output, Somehow the name for student 1 (i.e., "stud1") is not printed even thought it is sorted by their arrival time. Can anyone help to figure out what is wrong with this approach?

Student.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 */

Student.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;
}

Sample Output

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

Answer 1

Look at your comparison function. You're returning true if the arrival times are the same, but with the items in different order.

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

Assume that s1 and s2 arrival times are the same. Your function returns true. Then let's say that we call your comparison function, but this time with s2 and s1. You still return true. How can that be? How can you say that s1 is placed in the container before s2, and then at the same time, s2 should be placed in the container before s1? The compiler is asking you which comes first, and you gave an impossible answer when the items are equal. This is where the std::set sorting criteria gets confused and ultimately, gives you incorrect results.

That in a nutshell is what the strict-weak-ordering is all about, with @Slava giving the details on what the solution is.

BTW, the test for switching items and checking the return value is done by the debug Visual C++ runtime. Your code would probably have asserted right away, since the runtime calls the ordering routine twice, first with s1, s2 and then with s2, s1. If you returned true for both scenarios, the runtime would have aborted your application.

---

The other issue is that you are storing pointers to items in your Student vector here:

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)

You are adding items to the g_stud_pool vector and then immediately using the pointer to the item you just placed In your vector to reference the item by placing that pointer in your std::set.

The problem with this is that each time you add an item to the vector, any pointers to previous items may become invalidated. What winds up happening is that the comparison function that your set uses will be using addresses that have been invalidated.

The quickest way to solve this (not the only way) is to change to a container that doesn't invalidate pointers (and iterators) when resized. Such a container is std::list. So changing to this:

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

resolves the invalidation issue, since a std::list doesn't invalidate pointers and iterators when a list is resized.

Here is a live example

Answer 2

Your comparator is incorrect as it breaks "strict weak ordering relation", it should be something like:

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

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

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

or even simpler:

bool CompareStudByArrivaltime::operator()(const Student* s1, const Student* s2) const
{
   return std::make_tuple( s1->getName(), s1->getArrivalTime() ) <
          std::make_tuple( s2->getName(), s2->getArrivalTime() );
}

details can be found here