Jump to content
  • Advertisement
Sign in to follow this  
Maverick Programmer

std::map and std::sort. Why can't they be friends?

This topic is 3566 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 thought I had a devilish and grand scheme of having a map of sprites that I could call by string and in the update function, sort the 2d sprites by their z values. I found out that std::sort is not compatible with std::map. It seems like STL has gazed into my future coding attempts and foiled every possible turn I make. I *always* come across something I can't do with STL that I thought would 100% work. Ah well. Anyway, how would one go about this without chucking two code-filled documents? I'd like to simply sort my sprites. Thank you for your time. :D

Share this post


Link to post
Share on other sites
Advertisement
std::map maintains it's own "sorting", in your case by string; that's what enables the quick access. sorting by some other value would completely invalidate the map.

instead, it sounds like you want to copy sprite pointers from your map to something like this
std::vector<Sprite*> zSortedSprites;
then write a custom compare functor, i.e.:
struct CompareSprites
{
bool operator()( const Sprite* a, const Sprite* b ) const
{
return a->z < b->z;
}
};
then sort the vector, i.e.:
std::sort( zSortedSprites.begin(), zSortedSprites.end(), CompareSprites() );


Then render from your temporary vector.

Share this post


Link to post
Share on other sites
I've tried touching stuff like STL and I get burned every time. Have you considered just writing a sorting loop?


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Object
{
unsigned int index;
unsigned int value;
};



int main(int, char**)
{
Object objects[10], buffer;

// Assigned set indices and random values to the objects.
srand(time(0));
for(int i = 0; i < 10; i++)
{
objects.index = i;
objects.value = rand() % 100;
}

// Print the objects before they get sorted.
printf("Unsorted:\n");
for(int i = 0; i < 10; i++) printf("Index: %i Value: %i\n", objects.index, objects.value);

// Sort the objects
for(int i = 0; i < 9; i++)
{
for(int i2 = i + 1; i2 < 10; i2++)
{
if(objects[i2].value < objects.value)
{
buffer.index = objects.index;
buffer.value = objects.value;

objects.index = objects[i2].index;
objects.value = objects[i2].value;

objects[i2].index = buffer.index;
objects[i2].value = buffer.value;
}
}
}

// Print the objects after sorting.
printf("Sorted by value:");
for(int i = 0; i < 10; i++) printf("\nIndex: %i Value: %i", objects.index, objects.value);

return 0;
}




Not 100% sure that'd work but it seems solid "in my mind." The code'd be soemting like that anyway.

EDIT: There. It took me about 5 mins to write. That's a complete simple sorting application. Just cuz we use C++ doesn't mean that something can't be easily done with just C.

[Edited by - kittycat768 on January 12, 2009 8:35:43 PM]

Share this post


Link to post
Share on other sites
I did but it became much more complex with the map container so I scratched the idea. It was too complex and I assumed it would be wayyy slower that the std::sort method. *still implementing possible solution btw*

Share this post


Link to post
Share on other sites
As a bit of an aside, if you find that the STL (or BOOST) doesn't easily enable what you are attempting, then one of the three following scenarios is most likely:

1 - What you want to do is illogical (given your container and algorithm choice) -- as in this case.

2 - What you want to do is very specific and the STL is too general.

3 - The STL provides a better way to do it in some other fashion.


The STL is designed and maintained by some of the top minds in computer science, so feeling that they've left out some important functionality is not the first thing you should think. If what you wanted to do was a good idea, it would likely be represented by now (and it likely is).

I suggest you read "The Standard Template Library: A tutorial and Reference" and/or "Effective STL" to better learn what is available and what each component is good for.

Share this post


Link to post
Share on other sites
Thanks Ravyne. I'll check those out. I managed to get it working after messing with emeyex's suggestion. Thanks. It works smashingly now. ^^

Thank you for your answers. Maybe now I can get back to the more important code...

Share this post


Link to post
Share on other sites
Quote:
Original post by kittycat768
I've tried touching stuff like STL and I get burned every time.
Can you give an example of how you've been burned? What were you trying to do? Which part of the SC++L were you using? And in what way did it not work?

Note that in this case, by making use of the standard C++ library we can reduce this:

struct Object
{
unsigned int index;
unsigned int value;
};

for(int i = 0; i < 9; i++)
{
for(int i2 = i + 1; i2 < 10; i2++)
{
if(objects[i2].value < objects.value)
{
buffer.index = objects.index;
buffer.value = objects.value;

objects.index = objects[i2].index;
objects.value = objects[i2].value;

objects[i2].index = buffer.index;
objects[i2].value = buffer.value;
}
}
}


To this:

struct Object
{
unsigned int index;
unsigned int value;

bool operator<(const Object& object) const { return value < object.value; }
};

std::sort(objects, objects + 10);



There are a number of benefits here:

1. Less code to write. It doesn't matter if the sort routine in the first example only took you 5 minutes to write; the corresponding line in the second example took me 5 seconds to write. That's 4 minutes and 55 seconds I can spend working on more important things.

2. You're pretty sure your version works, and I'm willing to give you the benefit of the doubt. However, we can both be just about 100% sure that std::sort() will work as advertised. Not only do we not have to write the code in the first place, we also don't have to debug it, or wonder whether it will fail somewhere down the line when we least expect it.

3. The containers and algorithms in the C++ standard library are well-known and understood by many (if not most) C++ programmers. When you make use of these parts of the language in your own code, you make your code clearer and more immediately comprehensible to other C++ programmers.

The SC++L is not the optimal solution to every problem, but when you say you've been 'burned' by it I can't help but think that you've been using it incorrectly, or that you haven't really given it a chance. I'd certainly be interested to know what sort of problems you've run into (depending on the nature of the problems, there may very well be ways to get around them).

Share this post


Link to post
Share on other sites
Quote:
Original post by PCN
I thought I had a devilish and grand scheme of having a map of sprites that I could call by string and in the update function, sort the 2d sprites by their z values.

I found out that std::sort is not compatible with std::map. It seems like STL has gazed into my future coding attempts and foiled every possible turn I make. I *always* come across something I can't do with STL that I thought would 100% work.

Ah well.

Anyway, how would one go about this without chucking two code-filled documents?
I'd like to simply sort my sprites.
A map is designed for looking things up quickly.
For example you could have a map from std::string to int than contains:
"zero" -> 0
"one" -> 1
"two" -> 2
"three" -> 3
etc. Then given a string you can lookup whether there is a corresponding entry in the map and if so, what the mapped value is. E.g. looking up "two" would give you an entry that mapped from "two" to 2.
If that is the kind of thing you want to do, then say what types you want to map from and two, and assuming one of those is your sprite, give its definition. We'll show you exactly how to do it. It's a piece of cake.

If that isn't what you want to do, then perhaps you just want your spries, ordered by the z value? If the z value of a sprite doesn't change then you can simply use a std::set and they will stay in sorted order permanently, and you can add and remove at will. Again, this is very easy stuff, we'll show you how.

Or if you just want to sort them periodically, such as for each frame, then all you probably need is a std::vector. emeyex has already given a sample for this.

Whatever you do, DONT WRITE THE SORTING BY HAND! That is a sure way to:
1. Waste time
2. Produce buggy code
3. Cause scalability issues

Edit: Well it sounds like it's all working for you. Good stuff.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by kittycat768
I've tried touching stuff like STL and I get burned every time.
Can you give an example of how you've been burned? What were you trying to do? Which part of the SC++L were you using? And in what way did it not work?

Note that in this case, by making use of the standard C++ library we can reduce this:

*** Source Snippet Removed ***
To this:

*** Source Snippet Removed ***

There are a number of benefits here:

1. Less code to write. It doesn't matter if the sort routine in the first example only took you 5 minutes to write; the corresponding line in the second example took me 5 seconds to write. That's 4 minutes and 55 seconds I can spend working on more important things.

2. You're pretty sure your version works, and I'm willing to give you the benefit of the doubt. However, we can both be just about 100% sure that std::sort() will work as advertised. Not only do we not have to write the code in the first place, we also don't have to debug it, or wonder whether it will fail somewhere down the line when we least expect it.

3. The containers and algorithms in the C++ standard library are well-known and understood by many (if not most) C++ programmers. When you make use of these parts of the language in your own code, you make your code clearer and more immediately comprehensible to other C++ programmers.

The SC++L is not the optimal solution to every problem, but when you say you've been 'burned' by it I can't help but think that you've been using it incorrectly, or that you haven't really given it a chance. I'd certainly be interested to know what sort of problems you've run into (depending on the nature of the problems, there may very well be ways to get around them).


Well, "getting burned" wasn't necessarily the best way to word it. I just could never figure out STL. Error after Error. After posting in this thread so many hours ago, I actually googled STL and tried again. So far, I've figured out how to use std::vector and std::string. For a long time, STL seemed alien. That and I thought it was MSVC specific. I dug around in my MinGW include folder and found all the STL includes. I also found that www.cppreference.com has a decent reference. As for the sorting method, I doubt that std::sort could be any faster, but it could probably save a lot of time coding. Wouldn't I also have to override my object class's < operator? Meh... I don't remember. Templates have alwasy scared the crap out of me.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!