Sorting a vector in descending order

Question

Should I use  std  sort numbers begin    numbers end    std  greater lt int gt        or  std  sort numbers rbegin    numbers rend          note  reverse iterators   to sort a vector in descending order  Are there any benefits or drawbacks with one approach or the other

User · Answer

Actually  the first one is a bad idea  Use either the second one  or this   struct greater       template lt class T gt      bool operator   T const  amp a  T const  amp b  const   return a  gt  b        std  sort numbers begin    numbers end    greater       That way your code won t silently break when someone decides numbers should hold long or long long instead of int

User · Answer

TL DR  Use any  They are almost the same   Boring answer  As usual  there are pros and cons   Use std  reverse iterator    When you are sorting custom types and you don t want to implement operator gt    When you are too lazy to type std  greater lt int gt      Use std  greater when    When you want to have more explicit code When you want to avoid using obscure reverse iterators   As for performance  both methods are equally efficient  I tried the following benchmark    include  lt algorithm gt   include  lt chrono gt   include  lt iostream gt   include  lt fstream gt   include  lt vector gt   using namespace std  chrono      64 Megabytes      define VECTOR SIZE    1  lt  lt  20    64    sizeof int      Number of elements to sort      define SORT SIZE 100000  int main int argc  char   argv        std  vector lt int gt  vec      vec resize VECTOR SIZE           We generate more data here  so the first SORT SIZE elements are evicted        from the cache         std  ifstream urandom   dev urandom   std  ios  in   std  ifstream  binary       urandom read  char  vec data    vec size     sizeof int        urandom close         auto start   steady clock  now     if USE REVERSE ITER     auto it rbegin   vec rend   - SORT SIZE      std  sort it rbegin  vec rend      else     auto it end   vec begin     SORT SIZE      std  sort vec begin    it end  std  greater lt int gt       endif     auto stop   steady clock  now         std  cout  lt  lt   Sorting time               lt  lt  duration cast lt microseconds gt  stop - start  count              lt  lt   us   lt  lt  std  endl      return 0      With this command line   g   -g -DUSE REVERSE ITER 0 -std c  11 -O3 main cpp        amp  amp  valgrind --cachegrind-out-file cachegrind out --tool cachegrind   a out        amp  amp  cg annotate cachegrind out g   -g -DUSE REVERSE ITER 1 -std c  11 -O3 main cpp        amp  amp  valgrind --cachegrind-out-file cachegrind out --tool cachegrind   a out        amp  amp  cg annotate cachegrind out   std  greater demo std  reverse iterator demo  Timings are same  Valgrind reports the same number of cache misses

User · Answer

First approach refers           std  sort numbers begin    numbers end    std  greater lt  gt        You may use the first approach because of getting more efficiency than second  The first approach s time complexity less than second one

User · Answer

According to my machine  sorting a long long vector of  1  3000000  using the first method takes around 4 seconds  while using the second takes about twice the time  That says something  obviously  but I don t understand why either  Just think this would be helpful   Same thing reported here   As said by Xeo  with -O3 they use about the same time to finish

User · Answer

What about this   std  sort numbers begin    numbers end     std  reverse numbers begin    numbers end

User · Answer

bool comp int i  int j    return i  gt  j    sort numbers begin    numbers end    comp

User · Answer

Use the first   std  sort numbers begin    numbers end    std  greater lt int gt        It s explicit of what s going on - less chance of misreading rbegin as begin  even with a comment  It s clear and readable which is exactly what you want   Also  the second one may be less efficient than the first given the nature of reverse iterators  although you would have to profile it to be sure

User · Answer

I don t think you should use either of the methods in the question as they re both confusing  and the second one is fragile as Mehrdad suggests   I would advocate the following  as it looks like a standard library function and makes its intention clear    include  lt iterator gt   template  lt class RandomIt gt  void reverse sort RandomIt first  RandomIt last        std  sort first  last           std  greater lt typename std  iterator traits lt RandomIt gt   value type gt

User · Answer

With c  14 you can do this   std  sort numbers begin    numbers end    std  greater lt  gt

User · Answer

You can either use the first one or try the code below which is equally efficient  sort  amp a 0    amp a n   greater lt int gt

User · Answer

Instead of a functor as Mehrdad proposed  you could use a Lambda function   sort numbers begin    numbers end       const int a  const int b   return a  gt  b

[c++] Sorting a vector in descending order

Examples related to c++

Examples related to sorting

Examples related to stl

Examples related to vector

Examples related to iterator