Sign in to follow this  

How to sort a vector and push object down e.g. like a stack...

This topic is 1710 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to figure out how to sort my top 10 score list, and put the greatest  score and players name at the top and then push down the other 9 and make the last one fall off the vector...

 

Is there something in the std:: lib that can do this?

 

struct GameData

{

    irr::core::stringw name;

    long score, level;

    GameData() : name("NA"), score(0), level(0){}

    ~GameData(){}

    inline bool operator < (const GameData& rhs)

    {

        return score < rhs.score;

    }

    static bool SortGreater(const GameData& lhs, const GameData& rhs)

    {

        return lhs.score > rhs.score;

    }

    static bool SortLess(const GameData& lhs, const GameData& rhs)

    {

        return lhs.score < rhs.score;

    }

};

 

that is the struct for the game score data....

 

and I call this for now...

 

for(unsigned int i = 0; i <p->GetScores().size(); ++i)

                {

                    //need to keep old score and shift it down one like a stack?

                    if(player->GetScore() > p->GetScores()[i].score)

                    {

                        p->GetScores()[i].score = player->GetScore();

                        p->GetScores()[i].name  = playerEditbox->getText();

                        p->GetScores()[i].level = player->GetLevel();

                        break;

                    }

                }

                std::sort(p->GetScores().begin(), p->GetScores().end(), NX::GameData::SortGreater);

 

so as you can see the first occurrence is replaced and not pushing the other ones down... do I want to move to a stack or just cheat and push onto the vector and save out the top 10...

 

Thanks!

Share this post


Link to post
Share on other sites

Bah I cheated....

 

for(unsigned int i = 0; i <p->GetScores().size(); ++i)
                {
                    if(player->GetScore() > p->GetScores()[i].score)
                    {
                        temp.name  = playerEditbox->getText();
                        temp.score = player->GetScore();
                        temp.level = player->GetLevel();
                        p->GetScores().push_back(temp);
                        break;
                    }
                }
                std::sort(p->GetScores().begin(), p->GetScores().end(), NX::GameData::SortGreater);
                p->GetScores().pop_back();  

 

still be curious to see how it should be done correctly! :)

 

Thanks!

Share this post


Link to post
Share on other sites
Guest Hiwas

I like SiCrane's solution actually.  10 items is hardly worth worrying about being "perfect" code.  Another simple solution would be a priority queue, insert the new element and drop the last.

Share this post


Link to post
Share on other sites
If I were going to do it "right" I'd use find_if() to find the first vector element the new score is greater than and if that position is not equal to end(), pop_back() the lowest element and use insert() at the point to put the new score in its right place. But honestly, I'd probably do it the easy way first and only change it if the profiler said I was spending significant time there or I was bored. Admittedly tweaking code that doesn't need the attention is one way I enjoy wasting time.

Share this post


Link to post
Share on other sites
Guest Hiwas

Admittedly tweaking code that doesn't need the attention is one way I enjoy wasting time.

 

Yeah, I often get into that mode.  Something that works well enough but I still dislike the code for some reason, I'll fiddle with it for hours sometimes.  Usually I had a reason for disliking the code and eventually figure out what struck me as wrong, but more often than not, I really should just move on. smile.png

Edited by Hiwas

Share this post


Link to post
Share on other sites

Bah I cheated....

 

 

for(unsigned int i = 0; i <p->GetScores().size(); ++i)
                {
                    if(player->GetScore() > p->GetScores()[i].score)
                    {
                        temp.name  = playerEditbox->getText();
                        temp.score = player->GetScore();
                        temp.level = player->GetLevel();
                        p->GetScores().push_back(temp);
                        break;
                    }
                }
                std::sort(p->GetScores().begin(), p->GetScores().end(), NX::GameData::SortGreater);
                p->GetScores().pop_back();  

 

still be curious to see how it should be done correctly! smile.png

 

Thanks!

 

 

That whole loop seems to be not only pointless, but actually a major bug.

 

Test your code with a really bad player that doesn't beat any existing score and your list is most likely going to shrink. After 10 lousy players you are trying to remove an entry from an empty vector and crash. Bottom line: get rid of that pointless loop and either only downsize if there are more than 10 entries or just fill it with 10 dummy values (lots of games are doing that).

Share this post


Link to post
Share on other sites

For a vector that will only contain 10 elements just sorting is dirt cheap anyway (also updating a highscore list is probably not performance critical...). So I don't see a reason to not simply do the following:

p->GetScores().push_back(player->getScore());
std::stable_sort(p->GetScores().begin(), p->GetScores().end(), NX::GameData::SortGreater);
p->GetScores().resize(10);

At least to me this also looks the most expressive and doesn't even need commenting (insert, sort, only keep 10). As opposed to some custom loop or "insertion algorithm".

 

Another approach would be to use a set instead of a vector since that is always sorted. In that case the insertion would be something like:

p->GetScores().insert(player->getScore());
while(p->GetScores().size()>10);
   p->GetScores().erase(--(p->GetScores().end()));

Share this post


Link to post
Share on other sites
Where is there a bug?

The size is fixed to 10 entries.

Pointless? I am sorting the scores so they are listed highest to lowest.


Please point out the bug specifically.


Thanks.

Oh good idea on the set.... I couldn't remember which container sorted automatically

Share this post


Link to post
Share on other sites

Where is there a bug?

The size is fixed to 10 entries.

Pointless? I am sorting the scores so they are listed highest to lowest.


Please point out the bug specifically.

Trienco already stated what exactly the bug is. If the played didn't made it into the high score list, then you don't add it. But then you proceed to sort and delete the last item anyway.

 

Basically, your code adds a new entry to the list if and only if some condition is met, but unconditionally removes one. The net effect is that you may add an element but always removes one. If the condition to add the element is not met, the size of the list shrinks by one entry and you no longer have your 10 highest scores.

 

One easy way has already been proposed; add the new score, sort the list, and remove the last one. If the new score didn't make it into the top 10, then it will be the 11:th entry and will be removed. You don't need to figure out if or where to insert it.

Share this post


Link to post
Share on other sites
template<typename Container, typename T>
void insert_score(Container& scores, const T& score)
{
	auto pos = std::upper_bound(scores.begin(), scores.end(), score, std::greater<T>());
	auto end = scores.end();
	if(pos == end)
		return;
	std::move_backward(pos, --end, scores.end());
	*pos = score;
}

adding, sorting and then popping the value should work fine though

Share this post


Link to post
Share on other sites

This topic is 1710 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this