3

I have a struct of data, for example:

struct Data
{
string firstname;
string lastname:
string age;
}

I've placed every struct within one vector (VectorOfData). Is it possible to loop through this vector and sort each struct in the vector by descending age? using something like:

for(std::vector<Data>::const_iterator it = VectorOfData.begin(); it != VectorOfData.end(); ++it)
{

//sorting by age here?

}

I'm assuming it wouldnt be that simple because the it iterator is only accessing one struct within the vector at a time?

I realize i could probably do the sorting before i even put the structs in the vector, but my problem isn't that simple. This is just the simplest way i could explain it. Any advice would be much appreciated, thanks

GeorgeCostanza
  • 395
  • 1
  • 6
  • 19
  • 2
    You can just use `operator<`and `std::sort` from `` – Karthik T Sep 12 '13 at 09:07
  • _"I'm assuming it wouldnt be that simple"_ ? You have STL with you, and its lot simpler – P0W Sep 12 '13 at 09:12
  • @sinsedrix thanks. that really was simple. running on 3 hrs sleep, got lazy – GeorgeCostanza Sep 12 '13 at 09:32
  • As a side note: Using a single for loop to sort a collection of items, is theoretically impossible, btw. since, in the general case, you *cannot* be better than Θ(n*log(n)) with a comparison based sorting algorithm. – bitmask Sep 12 '13 at 09:41

2 Answers2

18

You can use std::sort with a custom comparison function:

bool is_younger(const Data& x, const Data& y) { return x.age < y.age; }

sorting:

std::sort(VectorOfData.begin(), VectorOfData.end(), is_younger);

Alternatively, you can define a custom functor (note: this is actually preferred, as it increases the likelihood of inlining, read: faster sorting)

struct is_younger_functor
{
    bool operator()(const Data& x, const Data& y) const
    {
        return x.age < y.age; 
    }
};

sorting:

std::sort(VectorOfData.begin(), VectorOfData.end(), is_younger_functor());

If you want to define a strict ordering relationship for Data, you should consider turning it into a regular type (define operators <, <=, ==, !=, >, >=).

In that case, you will not need to define this is_younger functor and can call std::sort with just the iterators.

Edit: Strictly, you only need to define operator < for std::sort, but if you define it, it is a good idea to define the rest of them.

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
utnapistim
  • 26,809
  • 3
  • 46
  • 82
  • Note: the only operator you need to define is `operator <(const Data& rhs)` if that is the route you take. The stdlib requires a strict weak ordering and *all* the other operators are contrivable from that one. – WhozCraig Sep 12 '13 at 09:13
  • I know (as far as I remember, Alexander Stepanov took great care in his implementation of STL to ensure no other operators were needed). He also stated more than once that if you _do_ define the `<` operator you should also define the others. – utnapistim Sep 12 '13 at 09:17
  • I concur they should be defined, to be accurate. They can (and should) be defined strictly in terms of evals of `operator <`. I really like that design methodology, though it sometimes causes headaches for more than a few engineers that don't grasp it right away, to be sure. (and +1, btw) – WhozCraig Sep 12 '13 at 09:21
  • @utnapistim thanks. that was the simplest thing i've ever done with c++. ha – GeorgeCostanza Sep 12 '13 at 09:35
  • @utnapistim, why do we need the const pointer? We are not modifying it, right? – Anshuman Kumar Jun 18 '20 at 14:50
  • Without the const pointer, you cannot call it with non-const arguments. It will work for `std::vector` and `const std::vector`, but it will not work for `std::vector`. With `const` arguments, it will work for all combinations. Aditionally, by using a `const` reference as an argument type, you communicate to the caller that the referenced argument will not be changed internally. – utnapistim Jun 22 '20 at 15:58
7

You can use std::sort. It's defined in algorithm as

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

where comp is the comparator function of the type

bool cmp(const Type1 &a, const Type2 &b);

that you can define for your needs.

If you've C++11, a lambda function can be passed in. E.g.

std::sort(VectorOfData.begin(), VectorOfData.end(), [](const Data &a, const Data &b)
{
    return (a.age.length() < b.age.length());
});

If you can't use C++11, you can declare and define the comparator function somewhere and then you needn't even pass it to sort. This also works in C++11 too.

bool operator<(const Data& a, const Data& b)
{
    return (a.age.length() < b.age.length());
}

std::sort(VectorOfData.begin(), VectorOfData.end());  // sort's variant without comparator

I'd recommend the second way of declaring a operator< as it makes more sense to have a comparator function defined for a class; the lambda way is more of a write-and-throw-away type of convenience function.

legends2k
  • 31,634
  • 25
  • 118
  • 222
  • i appreciate the education. i accepted the other answer cause i used it first, but this will come in handy as well – GeorgeCostanza Sep 12 '13 at 10:02
  • For this specific example, I do not think it is okay to recommend the second way of doing things; it would only sort the class by its age, firstname and lastname would be completely ignored, and certainly lead to unexpected situations if you expected everything to be sorted. If you define your operators, they may be used at unexpected times (e.g. by the compiler); do not abuse them. – Joeppie Aug 04 '17 at 12:06