Time difference when sorting vector of structs

Question

I'm trying to sort vectors of 2 structs of different number of element:

    struct1 {
      int id1;
      int id2;
      string name;
      double ts1;
      double ts2;
    }

    struct2 {
      int id1;
      int id2;
      //string name; <-- this was left out
      double ts1;
      double ts2;
    }
std::vector<struct1> vec1;
std::vector<struct2> vec2;

When I tried to sort vec1 and vec2 based on ts1, there is a big difference in the sorting time. The sizes of vec1 and vec2 are large (>100k elements). Does the size of struct affect the sorting?

EDIT: my sorting function

inline bool sorting(const Type &lhs, const Type &rhs) {
    if (lhs.ts1 < rhs.ts1) {return true;}
    else {return false; }
}

std::sort(vec.begin(),vec.end(),
          [this] (Type lhs, Type rhs) { return sorting(lhs,rhs); });

Depending on whatever "big difference" means, It might be the fact that the assignment of an trivial struct struct2 is much faster than manually have to call the assignment operator as in struct1 for std::string. — WolverinDEV
– WolverinDEV, Commented Apr 30, 2020 at 14:04
Why is the lambda in sort taking the arguments by value? Copying bigger things is definitely more expensive. — cigien
– cigien, Commented Apr 30, 2020 at 14:04
Unrelated, but your sorting function could just be return lhs.ts1 < rhs.ts2;. — François Andrieux
– François Andrieux, Commented Apr 30, 2020 at 14:06
@cigien: I believe you might have spotted the problem! I suspect that every time a comparison is made, two new string elements have to be created, which is obviously catastrophic. Ha An Tran, try replacing [this] (Type lhs, Type rhs) with [this] (const Type& lhs, const Type& rhs) and let us know what you see. — TonyK
– TonyK, Commented Apr 30, 2020 at 14:06

TonyK · Accepted Answer · 2020-04-30 14:23:11Z

4

Your sorting function is invalid. The way you have written it, it is possible that two structures are each less than the other. If this can happen, the sorting algorithm can go on for ever.

Instead of

    if (lhs.ts1 < rhs.ts2) {return true;}

you need

    if (lhs.ts1 < rhs.ts1) {return true;}

or possibly

    if (lhs.ts2 < rhs.ts2) {return true;}

answered Apr 30, 2020 at 14:23

TonyK

17.2k4 gold badges41 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Caleth Over a year ago

or better yet return (lhs.ts1 < rhs.ts1); or return (lhs.ts2 < rhs.ts2);

Ted Lyngmo Over a year ago

Mentioning that the comparison does not fulfill the strict weak ordering requirement of a Compare function would probably be good. I wouldn't be surprised if a sorting algorithm could end up in an endless loop with lhs.ts1 < rhs.ts2.

Ted Lyngmo Over a year ago

@TonyK No need to scream, I'm on your side :-) I just don't see where you mention that specific requirement.

Ha An Tran Over a year ago

I edited my question, this is actually just a typo I made. Sorry for the inconvenience :(

Ted Lyngmo Over a year ago

@HaAnTran You must realize that people spend time trying to answer your questions based on what you publish here, not on what you have in your real code. The answer by TonyK is a perfect example. TonyK wouldn't even have written this answer if you had asked the question with code that could be used to reproduce the problem - the problem only you see. We don't.

|

Collectives™ on Stack Overflow

Time difference when sorting vector of structs

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related