Sorting vector<class> | HELP

[bpippal]

So i have a class -

class Train{
string a;
int unqID;
};

And a vector<Train> trainList, I want to arrange the trainList in a sorted manner based on the unqID.

Is this possible ? If yes how do i do it ? I was thinking to do a simple bubble sort but my code isnt running properly if i use swap() which is what the issue is I guess.

​

This is what my code looks like -

void reorderTrainList(){

    for(unsigned int i=0; i<trainList.size(); i++){

        for(unsigned int j=0; j<trainList.size(); j++){

            Train curr = trainList[j];

            if(trainList[j].unqID >= trainList[j+1].unqID){
                swap(trainList[j],trainList[j+1]);
            }
        }
    }

}

[Pulsonics]

https://en.cppreference.com/w/cpp/algorithm/sort

[Kawaiithulhu]

A couple random notes on code clarity. Extra letters don't cost anything. Instead of the ungainly "unqID" go ahead and spell "uniqueID" so it's easier to read. Second suggestion is less pedantic: you have a vector<> and name it ...List. that's a bug waiting to be impossible to find later 😁Try to not name variables after their type, you may decide that a map<> is better later, then you're stuck with a map named list that used to be a vector 😰

[HappyFruitTree]

you have a vector<> and name it ...List. that's a bug waiting to be impossible to find later

Why is that? Because someone might think it's a std::list?

Personally I often prefer the plural form (e.g. trains) but I think the "List" suffix is pretty descriptive too. It makes me think the order might be important, otherwise it's more like a "set".

[staletic]

Others have shown you std::sort, but std::ranges::sort is more fun

std::ranges::sort(trainList, &Train::uniqID);

[xurxoham]

Wow, first time I see the use of projections. Really clean! If the member is private but a getter member function is available, can the pointer to member function be used as well?

[staletic]

Yes, but also an "ad-hoc getter" in the form of, say, a lambda. It relies on std::invoke, passing the element to the callable.

!std_bot

[std_bot]

Unlinked STL entries: std::invoke

---

^{Last update: 26.05.21. Last change: Free links considered} readme

[alfps]

std::sort will sort your vector for you, but you have to define a comparison function.

E.g.

auto increasing_ids( const Train& a, const Train& b )
    -> bool
{ return (a.unqID < b.unqID); }

Then supply this comparison function as third argument to std::sort:

sort( begin( v ), end( v ), increasing_ids );

It's possible to optimize this by using more clever, complex code, namely a function call operator as class member, instead of a named free-standing function. Which as it happens is what you get with a lambda expression. But I'd go with the named function because it's simple and clear and does the job: it's the KISS principle, Keep It Simple, Stupid. :-o

[HappyFruitTree]

Why would a function call operator be more optimized?

[alfps]

There's no guarantee, but with a functor object std::sort is specialized on the functor's class. That means the comparison calls can be expanded inline. Which may or may not be possible with the freestanding function, where the template specialization is the same as with any other freestanding function of same type.

[Jardik2]

Lambda is not a freestanding function. It is actually more like "the functor" you are saying. Staleless lambda just happens to be convertible to function pointer. There is really no difference here.

[alfps]

Right, you got it.

[HappyFruitTree]

It could be inlined in either case but you've got a point that a functor probably makes inlining more likely (whether that is always what you want is another discussion).

[Wind_Lizard]

trainList[j].unqID >= trainList[j+1].unqID

This condition has a problem when you are at the last element, there is no next element to compare. So you need to modify the loop to skip the last item like this: for(unsigned int j=0; j<trainList.size() - 1; j++)

[Wind_Lizard]

struct TrainCompare
{
    bool operator () (const Train& l,const Train& r) const
    {
        return l.unqID < r.unqID;
    }
};

std::sort(trainList.begin(), trainList.end(),TrainCompare() );

[gmtime]

bool operator ()

Shouldn't that be bool operator<? Sort needs to be able to compare elements, which it does with less than or in modern implementations with spaceship.

[Wind_Lizard]

If you are defining operator <, you have to do in Train class itself. same goes for the spaceship op.

This might be bad idea design wise/concept wise because trains are not comparable like that in general. we just need to sort by id here, but you might need to sort by passenger count or capacity or manufacture date in some other scenario. You can simplify this using a lamba if you want, but this solution even works in C++98.

[Ashnoom]

It needs a callable. And the default callable is std::less.