sorting a vector of structs

Question

I have a vector<data> info where data is defined as:

struct data{
    string word;
    int number;
};

I need to sort info by the length of the word strings. Is there a quick and simple way to do it?

score 114 · Accepted Answer · edited Dec 14 '15 at 20:06

114

Use a comparison function:

bool compareByLength(const data &a, const data &b)
{
    return a.word.size() < b.word.size();
}

and then use std::sort in the header #include <algorithm>:

std::sort(info.begin(), info.end(), compareByLength);

edited Dec 14 '15 at 20:06

TryToSolveItSimple

873
1
12
23

answered Feb 03 '11 at 22:52

Oliver Charlesworth

267,707
33
569
680

2

What if I wish to sort the vector in a lexicographic manner according to the string filed ? (I'm using C++11 if it matters). Is there a way to approach it other than defining a comparison function /use lambda and instead use the integral operator< of std::string ? Below is my solution using lambda: sort(info.begin(),info.end(), [](const data& d1, const data& d2) { return (d1.word.compare(d2.word) < 0); }); – Guy Avraham Jul 06 '17 at 06:31

Murilo Vasconcelos · Answer 2 · 2011-02-03T23:26:16.150

48

Just make a comparison function/functor:

bool my_cmp(const data& a, const data& b)
{
    // smallest comes first
    return a.word.size() < b.word.size();
}

std::sort(info.begin(), info.end(), my_cmp);

Or provide an bool operator<(const data& a) const in your data class:

struct data {
    string word;
    int number;

    bool operator<(const data& a) const
    {
        return word.size() < a.word.size();
    }
};

or non-member as Fred said:

struct data {
    string word;
    int number;
};

bool operator<(const data& a, const data& b)
{
    return a.word.size() < b.word.size();
}

and just call std::sort():

std::sort(info.begin(), info.end());

edited Feb 03 '11 at 23:26

answered Feb 03 '11 at 22:52

Murilo Vasconcelos

4,677
24
27

Op< should be a non-member and number should probably be considered in op< so other algorithms, such as std::unique, behave as expected when used with the default std::less; otherwise spot on. – Fred Nurk Feb 03 '11 at 23:06
Why `operator<()` should be non-member? – Murilo Vasconcelos Feb 03 '11 at 23:09
@MuriloVasconcelos: So implicit conversions apply to the left-hand side. – Fred Nurk Feb 03 '11 at 23:16
4

IMHO, you shouldn't use operator overloading to wrap behaviour that isn't immediately intuitive. In this situation, it doesn't really make any sense to say that `data a` is "less than" `data b` if its string member is shorter, so I wouldn't use `operator<` to express that idea. – Oliver Charlesworth Feb 03 '11 at 23:26
Added but I don't see problem with the "member-way" – Murilo Vasconcelos Feb 03 '11 at 23:28
2

In this case I agree with you and is why I write about the "function-way" first and then I explained the other ways for learning purposes. – Murilo Vasconcelos Feb 03 '11 at 23:31
@MuriloVasconcelos Why we need `const` function for `operator <` ? – EmptyData Jul 07 '14 at 08:30

score 5 · Answer 3 · answered Feb 03 '11 at 22:52

Yes: you can sort using a custom comparison function:

std::sort(info.begin(), info.end(), my_custom_comparison);

my_custom_comparison needs to be a function or a class with an operator() overload (a functor) that takes two data objects and returns a bool indicating whether the first is ordered prior to the second (i.e., first < second). Alternatively, you can overload operator< for your class type data; operator< is the default ordering used by std::sort.

Either way, the comparison function must yield a strict weak ordering of the elements.

user470379 · Answer 4 · 2011-02-03T23:08:27.107

4

As others have mentioned, you could use a comparison function, but you can also overload the < operator and the default less<T> functor will work as well:

struct data {
    string word;
    int number;
    bool operator < (const data& rhs) const {
        return word.size() < rhs.word.size();
    }
};

Then it's just:

std::sort(info.begin(), info.end());

Edit

As James McNellis pointed out, sort does not actually use the less<T> functor by default. However, the rest of the statement that the less<T> functor will work as well is still correct, which means that if you wanted to put struct datas into a std::map or std::set this would still work, but the other answers which provide a comparison function would need additional code to work with either.

edited Feb 03 '11 at 23:08

answered Feb 03 '11 at 22:56

user470379

4,879
16
21

Interestingly, while `std::map` and `std::set` default to using `std::less`, `std::sort` and the rest of the sorting functions default to using `operator<`. You'll only notice a difference if you specialize `std::less` to do something other than what `operator<` does. – James McNellis Feb 03 '11 at 23:00
When I said "you'll only notice a difference if...," I was wrong. You'll also notice a difference if you have a container of pointers, e.g. `std::vector v; v.insert(new int); v.insert(new int); std::sort(v.begin(), v.end());`, since the behavior is undefined if you compare unrelated pointers using `<`. That said, why you'd want to sort a container of pointers by the pointer value and not the value of the pointed-to object, I don't know. – James McNellis Feb 03 '11 at 23:57

sorting a vector of structs

4 Answers4

Linked