A simple gradebook using structures I have this basic question about the efficient way to sort user-defined object. It can be done in many ways, but most of sorting algorithms at best cases is \$O(N)\$. I have come up with a fair approach to get \$O(N*log(size() + N))\$ by using std::set.

Is it a good choice in such a case?

#include &lt;iostream&gt;
#include &lt;iomanip&gt;
#include &lt;array&gt;
#include &lt;string&gt;
#include &lt;set&gt;

struct Student
{
    std::string studentName;
    int midTermScore;
    char grade;

    friend bool operator&lt;(Student const &amp; a, Student const &amp; b)
    {
        return a.midTermScore &gt; b.midTermScore;
    }
};

template&lt;typename C&gt;
void display(const C&amp; c)
{
    std::cout &lt;&lt; std::left 
        &lt;&lt; std::setw(10) &lt;&lt; " Names"
        &lt;&lt; std::setw(10) &lt;&lt; "Exam" 
        &lt;&lt; std::setw(10) &lt;&lt; "Grade";

    std::cout &lt;&lt; std::setfill('-') &lt;&lt; std::setw(28) &lt;&lt; '\n';

    for (const auto&amp; i : c)
    {
        std::cout &lt;&lt; "\n " &lt;&lt; std::setfill(' ') &lt;&lt; std::left
            &lt;&lt; std::setw(10) &lt;&lt; i.studentName
            &lt;&lt; std::setw(11) &lt;&lt; i.midTermScore
            &lt;&lt; std::setw(2) &lt;&lt; i.grade;
    }
}

int main()
{
    std::array&lt;Student, 4&gt; a
    {
        {
            { "me",     60, 'D'},
            {"matt",    88, 'B'},
            { "john",   93, 'A'},
            {"jesseca", 82, 'B'}

        }
    };

    display(a);

    std::set&lt;Student&gt; sorted;

    for (auto&amp;&amp; i : a)
    {
        sorted.insert(i); // O(N*log(size() + N))
    }

    std::cout &lt;&lt; "\n\nafter sorting\n\n";

    display(sorted);
}
i have given basic question about the efficient way to sort user-defined object


If you really care about performance, you should measure it. Experience shows that there are many subtle influences to performance, that make it hard to reliably predict it.

Instead of using a std::set, you could try sorting the array directly. It is less code, less memory and probably faster: std::set typically is implemented as a tree, and will allocate each node separately. When inserting elements not in order, the resulting nodes will most likely be scattered in memory. Iterating over such a set might be slower than iterating over a contiguous array or even over a set where the elements have been inserted in order. (Not that it would matter much with the small sample size in this program.)

std::set also provides guarantees that you don't need here: Stability of references/iterator, unique elements, "fast" insertion not just at the end, "fast" removal of elements.

Interestingly, because std::set guarantees unique elements, it might be an incorrect choice in this context. Students will not be inserted into the set if there's already a student with the same midTermScore when using your current definition of operator&lt;. Live example You should either use a total order for the std::set or use a data structure that can contain multiple equivalent elements (equivalent with respect to the order) like std::multiset.

For example, instead of


std::set&lt;Student&gt; sorted;

for (auto&amp;&amp; i : a)
{
    sorted.insert(i); // O(N*log(size() + N))
}



you could sort the original array:

std::sort(begin(a), end(a));


(that is std::begin and std::end, but I'm using ADL because I'm lazy)




friend bool operator&lt;(Student const &amp; a, Student const &amp; b)
{
    return a.midTermScore &gt; b.midTermScore;
}



I don't think it's a good idea to define an operator&lt; for a type that does not provide a total order. We could try to introduce equality between two students by using (a == b) &lt;=&gt; (!(a&lt;b) &amp;&amp; !(b&lt;a))  (I'm using &lt;=&gt; as is equivalent to here). But this notion of equality is strange, since we expect (a == b) =&gt; (a.studentName == b.studentName).

After looking at the code again, I think it's even a worse idea to define the (canonical) operator&lt; for a type be mean greater than.

Therefore, I'd rather use a function, function object type or lambda to introduce this order. For example, using std::sort from above:

auto const larger_midTermScore =
    [](Student const&amp; a, Student const&amp; b)
    { return a.midTermScore &gt; b.midTermScore; }

std::sort(begin(a), end(a), larger_midTermScore);


I you want to use a std::set, you could impose that order on the set as follows:

class larger_midTermScore {
private:
    static auto tie_in_order(Student const&amp; a)
    -&gt; decltype(std::tie(a.midTermScore, a.grade, a.studentName)) {
        return std::tie(a.midTermScore, a.grade, a.studentName);
    }
public:
    bool operator() const (Student const&amp; a, Student const&amp; b) {
        return tie_in_order(a) &lt; tie_in_order(b);
    }
};

// in the main function:
std::set&lt;Student, larger_midTermScore&gt; sorted(begin(a), end(a));


I'm being lazy again by using std::tuple to define a lexicographical comparison of the data members of Student. Include the &lt;tuple&gt; header.




std::string studentName;
int midTermScore;
char grade;



The type Student might have invariants that you should protect.
For example, 'A' &lt;= grade &lt;= 'F' etc. Also, it is unclear (because not documented nor enforced by encapsulation) if there is a maximum length for studentName. The display algorithm suggests there is one.