Sorting a vector of custom objects

Question

How does one go about sorting a vector containing custom  i e  user defined  objects  Probably  standard STL algorithm sort along with a predicate  a function or a function object  which would operate on one of the fields  as a key for sorting  in the custom object should be used  Am I on the right track

User · Answer

typedef struct Freqamp      double freq      double amp   FREQAMP   bool struct cmp by freq FREQAMP a  FREQAMP b        return a freq  lt  b freq     main         vector  lt FREQAMP gt  temp      FREQAMP freqAMP       freqAMP freq   330      freqAMP amp   117 56      temp push back freqAMP        freqAMP freq   450      freqAMP amp   99 56      temp push back freqAMP        freqAMP freq   110      freqAMP amp   106 56      temp push back freqAMP        sort temp begin   temp end    struct cmp by freq       if compare is false  it will do  swap

User · Answer

In your class  you may overload the   lt   operator   class MyClass     bool operator  lt  const MyClass amp  rhs          return this- gt key  lt  rhs key

User · Answer

Below is the code using lambdas   include  stdafx h   include  lt vector gt   include  lt algorithm gt   using namespace std   struct MyStruct       int key      std  string stringValue       MyStruct int k  const std  string amp  s    key k   stringValue s         int main         std  vector  lt  MyStruct  gt  vec       vec push back MyStruct 4   test         vec push back MyStruct 3   a         vec push back MyStruct 2   is         vec push back MyStruct 1   this          std  sort vec begin    vec end                 const MyStruct amp  struct1  const MyStruct amp  struct2                        return  struct1 key  lt  struct2 key                        return 0

User · Answer

You could use functor as third argument of std  sort  or you could define operator lt  in your class   struct X       int x      bool operator lt   const X amp  val   const            return x  lt  val x             struct Xgreater       bool operator    const X amp  lx  const X amp  rx   const           return lx x  lt  rx x            int main          std  vector lt X gt  my vec          use X  operator lt  by default     std  sort  my vec begin    my vec end              use functor     std  sort  my vec begin    my vec end    Xgreater

User · Answer

Yes  std  sort   with third parameter  function or object  would be easier  An example   http   www cplusplus com reference algorithm sort

User · Answer

A simple example using std  sort  struct MyStruct       int key      std  string stringValue       MyStruct int k  const std  string amp  s    key k   stringValue s         struct less than key       inline bool operator    const MyStruct amp  struct1  const MyStruct amp  struct2                return  struct1 key  lt  struct2 key             std  vector  lt  MyStruct  gt  vec   vec push back MyStruct 4   test     vec push back MyStruct 3   a     vec push back MyStruct 2   is     vec push back MyStruct 1   this      std  sort vec begin    vec end    less than key         Edit  As Kirill V  Lyadvinsky pointed out  instead of supplying a sort predicate  you can implement the operator lt  for MyStruct   struct MyStruct       int key      std  string stringValue       MyStruct int k  const std  string amp  s    key k   stringValue s          bool operator  lt   const MyStruct amp  str  const               return  key  lt  str key              Using this method means you can simply sort the vector as follows   std  sort vec begin    vec end       Edit2  As Kappa suggests you can also sort the vector in the descending order by overloading a  gt  operator and changing call of sort a bit    struct MyStruct       int key      std  string stringValue       MyStruct int k  const std  string amp  s    key k   stringValue s          bool operator  gt   const MyStruct amp  str  const               return  key  gt  str key              And you should call sort as   std  sort vec begin    vec end   greater lt MyStruct gt

User · Answer

In the interest of coverage   I put forward an implementation using lambda expressions   C  11   include  lt vector gt   include  lt algorithm gt   using namespace std   vector lt  MyStruct  gt  values   sort  values begin     values end          const MyStruct amp  lhs  const MyStruct amp  rhs        return lhs key  lt  rhs key        C  14   include  lt vector gt   include  lt algorithm gt   using namespace std   vector lt  MyStruct  gt  values   sort  values begin     values end          const auto amp  lhs  const auto amp  rhs        return lhs key  lt  rhs key

User · Answer

To sort a vector you can use the sort   algorithm in    sort vec begin   vec end   less lt int gt        The third parameter used can be greater or less or any function or object can also be used  However the default operator is  lt  if you leave third parameter empty      using function as comp std  sort  myvector begin   4  myvector end    myfunction   bool myfunction  int i int j    return  i lt j         using object as comp std  sort  myvector begin    myvector end    myobject

User · Answer

You can use user defined comparator class   class comparator       int x      bool operator    const comparator  amp m   const comparator  amp n                 return m x lt n x

User · Answer

I was curious if there is any measurable impact on performance between the various ways one can call std  sort  so I ve created this simple test     cat sort cpp  include lt algorithm gt   include lt iostream gt   include lt vector gt   include lt chrono gt    define COMPILER BARRIER   asm volatile         memory     typedef unsigned long int ulint   using namespace std   struct S     int x    int y       define BODY   return s1 x s2 y  lt  s2 x s1 y     bool operator lt   const S amp  s1  const S amp  s2   BODY bool Sgreater func  const S amp  s1  const S amp  s2   BODY  struct Sgreater     bool operator    const S amp  s1  const S amp  s2   const BODY     void sort by operator vector lt S gt   amp  v     sort v begin    v end        void sort by lambda vector lt S gt   amp  v     sort v begin    v end        const S amp  s1  const S amp  s2   BODY       void sort by functor vector lt S gt   amp v     sort v begin    v end    Sgreater        void sort by function vector lt S gt   amp v     sort v begin    v end     amp Sgreater func      const int N   10000000  vector lt S gt  random vector   ulint run void foo vector lt S gt   amp v      vector lt S gt  tmp random vector     foo tmp     ulint checksum   0    for int i 0 i lt tmp size     i        checksum    i  tmp i  x   tmp i  y        return checksum     void measure void foo vector lt S gt   amp  v     ulint check sum   0        warm up   const int WARMUP ROUNDS   3    const int TEST ROUNDS   10     for int t WARMUP ROUNDS t--        COMPILER BARRIER        check sum    run foo       COMPILER BARRIER           for int t TEST ROUNDS t--        COMPILER BARRIER        auto start   std  chrono  high resolution clock  now        COMPILER BARRIER        check sum    run foo       COMPILER BARRIER        auto end   std  chrono  high resolution clock  now        COMPILER BARRIER        auto duration ns   std  chrono  duration cast lt std  chrono  duration lt double gt  gt  end - start  count         cout  lt  lt   Took    lt  lt  duration ns  lt  lt   s to complete round   lt  lt  endl         cout  lt  lt   Checksum     lt  lt  check sum  lt  lt  endl      define M x      cout  lt  lt   Measure    x   on    lt  lt  N  lt  lt    items    lt  lt  endl     measure x    int main      random vector reserve N      for int i 0 i lt N   i       random vector push back S rand    rand             M sort by operator     M sort by lambda     M sort by functor     M sort by function     return 0      What it does is it creates a random vector  and then measures how much time is required to copy it and sort the copy of it  and compute some checksum to avoid too vigorous dead code elimination    I was compiling with g    GCC  7 2 1 20170829  Red Hat 7 2 1-1     g   -O2 -o sort sort cpp  amp  amp    sort   Here are results   Measure sort by operator on 10000000 items  Took 0 994285s to complete round Took 0 990162s to complete round Took 0 992103s to complete round Took 0 989638s to complete round Took 0 98105s to complete round Took 0 991913s to complete round Took 0 992176s to complete round Took 0 981706s to complete round Took 0 99021s to complete round Took 0 988841s to complete round Checksum  18446656212269526361 Measure sort by lambda on 10000000 items  Took 0 974274s to complete round Took 0 97298s to complete round Took 0 964506s to complete round Took 0 96899s to complete round Took 0 965773s to complete round Took 0 96457s to complete round Took 0 974286s to complete round Took 0 975524s to complete round Took 0 966238s to complete round Took 0 964676s to complete round Checksum  18446656212269526361 Measure sort by functor on 10000000 items  Took 0 964359s to complete round Took 0 979619s to complete round Took 0 974027s to complete round Took 0 964671s to complete round Took 0 964764s to complete round Took 0 966491s to complete round Took 0 964706s to complete round Took 0 965115s to complete round Took 0 964352s to complete round Took 0 968954s to complete round Checksum  18446656212269526361 Measure sort by function on 10000000 items  Took 1 29942s to complete round Took 1 3029s to complete round Took 1 29931s to complete round Took 1 29946s to complete round Took 1 29837s to complete round Took 1 30132s to complete round Took 1 3023s to complete round Took 1 30997s to complete round Took 1 30819s to complete round Took 1 3003s to complete round Checksum  18446656212269526361   Looks like all the options except for passing function pointer are very similar  and passing a function pointer causes  30  penalty    It also looks like the operator lt  version is  1  slower  I repeated the test multiple times and the effect persists   which is a bit strange as it suggests that the generated code is different  I lack skill to analyze --save-temps output

User · Answer

In C  20 one can default operator lt   gt  without a user-defined comparator  The compiler will take care of that   include  lt iostream gt   include  lt compare gt   include  lt vector gt   include  lt algorithm gt   struct MyInt       int value      MyInt int val    value val         auto operator lt   gt  const MyInt amp  other  const   default       int main         MyInt Five 5       MyInt Two 2       MyInt Six 6            std  vector V Five  Two  Six       std  sort V begin    V end              for  const auto amp  element   V          std  cout  lt  lt  element value  lt  lt  std  endl     Output  2 5 6

User · Answer

sort algorithm example      include  lt iostream gt         std  cout      include  lt algorithm gt        std  sort      include  lt vector gt           std  vector     using namespace std      int main              char myints       F   C   E   G   A   H   B   D            vector lt char gt  myvector  myints  myints 8                    32 71 12 45 26 80 53 33            using default comparison  operator  lt            sort  myvector begin    myvector end                  12 32 45 71 26 80 53 33            print out content          cout  lt  lt   myvector contains            for  int i 0  i  8  i                cout  lt  lt       lt  lt myvector i           cout  lt  lt    n           system  PAUSE        return 0

User · Answer

You are on the right track   std  sort will use operator lt  as comparison function by default   So in order to sort your objects  you will either have to overload bool operator lt   const T amp   const T amp    or provide a functor that does the comparison  much like this    struct C       int i      static bool before  const C amp  c1  const C amp  c2     return c1 i  lt  c2 i          bool operator lt   const C amp  c1  const C amp  c2     return c1 i  gt  c2 i      std  vector lt C gt  values    std  sort  values begin    values end         uses operator lt   std  sort  values begin    values end    C  before      The advantage of the usage of a functor is that you can use a function with access to the class  private members

User · Answer

Sorting such a vector or any other applicable  mutable input iterator  range of custom objects of type X can be achieved using various methods  especially including the use of standard library algorithms like    sort   stable sort   partial sort or partial sort copy    Since most of the techniques  to obtain relative ordering of X elements  have already been posted  I ll start by some notes on  why  and  when  to use the various approaches   The  best  approach will depend on different factors    Is sorting ranges of X objects a common or a rare task  will such ranges be sorted a mutiple different places in the program or by library users   Is the required sorting  natural   expected  or are there multiple ways the type could be compared to itself  Is performance an issue or should sorting ranges of X objects be foolproof    If sorting ranges of X is a common task and the achieved sorting is to be expected  i e  X just wraps a single fundamental value  then on would probably go for overloading operator lt  since it enables sorting without any fuzz  like correctly passing proper comparators  and repeatedly yields expected results   If sorting is a common task or likely to be required in different contexts  but there are multiple criteria which can be used to sort X objects  I d go for Functors  overloaded operator   functions of custom classes  or function pointers  i e  one functor function for lexical ordering and another one for natural ordering    If sorting ranges of type X is uncommon or unlikely in other contexts I tend to use lambdas instead of cluttering any namespace with more functions or types   This is especially true if the sorting is not  clear  or  natural  in some way  You can easily get the logic behind the ordering when looking at a lambda that is applied in-place whereas operator lt  is opague at first sight and you d have to look the definition up to know what ordering logic will be applied   Note however  that a single operator lt  definition is a single point of failure whereas multiple lambas are multiple points of failure and require a more caution   If the definition of operator lt  isn t available where the sorting is done   the sort template is compiled  the compiler might be forced to make a function call when comparing objects  instead of inlining the ordering logic which might be a severe drawback  at least when link time optimization code generation is not applied    Ways to achieve comparability of class X in order to use standard library sorting algorithms  Let std  vector lt X gt  vec X  and std  vector lt Y gt  vec Y   1  Overload T  operator lt  T  or operator lt  T  T  and use standard library templates that do not expect a comparison function   Either overload member operator lt    struct X     int i       bool operator lt  X const  amp r  const   return i  lt  r i               std  sort vec X begin    vec X end       or free operator lt    struct Y     int j        bool operator lt  Y const  amp l  Y const  amp r    return l j  lt  r j           std  sort vec Y begin    vec Y end       2  Use a function pointer with a custom comparison function as sorting function parameter   struct X     int i         bool X less X const  amp l  X const  amp r    return l i  lt  r i           std  sort vec X begin    vec X end     amp X less     3  Create a bool operator   T  T  overload for a custom type which can be passed as comparison functor   struct X     int i        int j       struct less X i       bool operator   X const  amp l  X const  amp r  const   return l i  lt  r i       struct less X j       bool operator   X const  amp l  X const  amp r  const   return l j  lt  r j          sort by i std  sort vec X begin    vec X end    less X i        or sort by j std  sort vec X begin    vec X end    less X j       Those function object definitions can be written a little more generic using C  11 and templates   struct less i        template lt class T  class U gt      bool operator   T amp  amp  l  U amp  amp  r  const   return std  forward lt T gt  l  i  lt  std  forward lt U gt  r  i         which can be used to sort any type with member i supporting  lt    4  Pass an anonymus closure  lambda  as comparison parameter to the sorting functions   struct X     int i    j       std  sort vec X begin    vec X end       X const  amp l  X const  amp r    return l i  lt  r i        Where C  14 enables a even more generic lambda expression   std  sort a begin    a end       auto  amp  amp  l  auto  amp  amp  r    return l i  lt  r i        which could be wrapped in a macro   define COMPARATOR code     auto  amp  amp  l  auto  amp  amp  r  - gt  bool   return code       making ordinary comparator creation quite smooth      sort by i std  sort v begin    v end    COMPARATOR l i  lt  r i       sort by j std  sort v begin    v end    COMPARATOR l j  lt  r j

[c++] Sorting a vector of custom objects

Examples related to c++

Examples related to stl

Examples related to sorting