0

I want to use the stl sort algorithm to sort some numbers, but i also want to remember their initial position. I have a data structure like this:

struct Numbers {
     int position;
     int value;
};

I have created a vector of Numbers like this:

vector<Numbers> a;

How to use the stl sort algorithm, such that i sort the data structures based on the value?

user2653125
  • 185
  • 2
  • 9

3 Answers3

4

You'll need to overload the "<" operator, like so:

bool Numbers::operator<(Numbers temp)
{
    return value < temp.value;
}
IllusiveBrian
  • 3,105
  • 2
  • 14
  • 17
4

You can use a functor too :

struct comp {

bool operator()(const Numbers &lhs, const Numbers& rhs) const{

  lhs.value < rhs.value;
}

};

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

With C++11, you can use a lambda function :

std::sort( a.begin() , a.end() , 
          [](const Numbers& lhs , const Numbers& rhs) 
           { return lhs.value < rhs.value; } 
          );
P0W
  • 46,614
  • 9
  • 72
  • 119
  • is using const obligatory? and can i use the comp function without enclosing it inside struct? if not, why? thanks – user2653125 Oct 27 '13 at 17:23
  • 1
    @user2653125 Yes you can Using `bool comp(const Numbers &lhs, const Numbers& rhs) const{lhs.value < rhs.value;}` Then only `comp`, in `std::sort`, no `()` . Also, `const` reference are used to avoid copying of `Number` objects – P0W Oct 27 '13 at 17:27
  • @P0W He was asking if the `const` qualification is obligatory. It isn't. `const` isn't used to avoid copying, `&` (the reference qualifier) is. –  Oct 27 '13 at 17:29
  • @H2CO3 I wrote `const` reference – P0W Oct 27 '13 at 17:31
  • well, what does const really do in this case then? – user2653125 Oct 27 '13 at 17:32
  • @P0W But your response could be misunderstood. –  Oct 27 '13 at 17:33
  • @user2653125 It does the same thing it always does: it prevents the modification of the qualified object. –  Oct 27 '13 at 17:33
  • @user2653125 Well, `foo(const Number x)` and `foo(Number x)` are same. The _magic_ is done by `const` **reference** `foo(const Number& x)`. See other related post on SO or google, it can't be explained all here in comments ;) – P0W Oct 27 '13 at 17:35
1

Use std::sort and provide a custom comparator (template arg Compare)

#include <algorithm>
#include <vector>

//...
std::vector<Numbers> a;

//fill the vector a and set Numbers::position of each element accordingly...

struct {
    bool operator()(const Numbers& a,const Numbers& b)const
    {   
        return a.value < b.value;
    }   
} my_comparator;

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

//...
Sam
  • 7,778
  • 1
  • 23
  • 49