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

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

## 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 on other sites
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 on other sites
Aye...

I s'pose that would work. I'll plug it in and reply. Thanks, mate. ^^

##### 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 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 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 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 on other sites
Quote:
 Original post by kittycat768I'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 on other sites
Quote:
 Original post by PCNI 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 on other sites
Quote:
Original post by jyk
Quote:
 Original post by kittycat768I'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 on other sites
std::sort is about as good as you're going to get for an arbitrary array: O(N lg N). If you have pre-existing knowledge that your list is nearly sorted already, insertion sort might be a little faster.

You don't have to override operator< for your classes, you can provide custom comparison function objects (as I showed in my example), allowing for multiple ways to sort/compare objects of a given type.

EDIT: An additional benefit of std::sort over say the old-skool c-style qsort is that it can inline the comparison as part of the template code generation, which for sorting can often be a significant cost savings.

##### Share on other sites
std::sort is an algorithm.
std::set is a data structure.

These are fundamentally different concepts.

sort orders the elements to which the function is applied, while set/map maintain its members in order as a balanced binary tree.

Both can be composed with custom Comparator functions/objects that factor out the comparison from their internal workings.

##### Share on other sites
Quote:
 Original post by emeyexstd::sort is about as good as you're going to get for an arbitrary array: O(N lg N). If you have pre-existing knowledge that your list is nearly sorted already, insertion sort might be a little faster.

If applicable a counting sort can be optimal with a much better runtime depending on the range: http://en.wikipedia.org/wiki/Counting_sort

##### Share on other sites
Quote:
 Original post by kittycat768Well, "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.
Wow that statement really made me cringe. To think that an n-squared sort could be the fastest you could get. I had forgotten there were people out there who didn't know about anything better.
You've actually got it backwards. Of all the sorting routines out there, the one you posted is about the slowest. The only slower ones are really just novelty ones that are designed to be slower.
Not talking about a few percentage difference here either. We're talking somewhere around 100 times faster using an O(n*log n) sort algorithm for a mere 1000 items!
In fact when profiling sorting algorithms such as you posted, I never profile them above about 50000 items because it takes so long that it's not worth waiting for it to finish. It'd probably take longer than typing this reply anyway. Whereas others are still taking a reasonable amount of time at 1 million items or more.
I actually have a website all about sorting algorithms, linked in my sig.

##### Share on other sites
And just to put another nail in the coffin of this discussion. Even if the data is already nearly sorted, std::sort is likely *still* going to do just fine, because nearly every STL implementation uses intro-sort which dynamically switches to insertion sort once you're in the right neighborhood.

##### Share on other sites
Quote:
 Original post by osmanbAnd just to put another nail in the coffin of this discussion. Even if the data is already nearly sorted, std::sort is likely *still* going to do just fine, because nearly every STL implementation uses intro-sort which dynamically switches to insertion sort once you're in the right neighborhood.
Actually Intro-Sort dynamically switches to Heap Sort when it detects a degredation to O(n*n) running time. Switching to Insertion Sort doesn't help with that. However, an Insertion Sort is always performed over the almost sorted array regardless with Intro-Sort.
Assuming an Intro-Sort internal implementation of std::sort, this does mean that using std::sort on an almost sorted array is actually sub-optimal compared to using Insertion Sort directly.
In any case, what kittycat768 posted isn't Insertion Sort (you probably realised this) and performs with O(n*n) running time in every case, even when already sorted.

##### Share on other sites
To the OP: I would say that a "sprite" is just data representing a region on a spritesheet (and the spritesheet's ID); it doesn't have a z-index, but instead some other game objects do. Let's say we call them Characters; then we use the sprite's name as a handle for the character's sprite, keep the sprites in the map, and sort characters by z-index. The characters draw themselves by looking up their sprite via the handle and telling the sprite to draw itself.

struct Sprite {  int x, y, w, h, spritesheet;  void drawAt(const Viewport& v, int x, int y);};struct Character {  std::string sprite_handle;  double x, y, z;  // If you're doing a 3D game, then you'll need to handle the Viewport  // projection more sensibly, since distance to camera will not match the  // world-space Z value. But if you're doing a 3D game, why are you using  // sprites for world-space objects? :)  bool operator<(const Character& c) { return z < c.z; }  typedef std::map<std::string, Sprite> spritemap;  void draw(const Viewport& v, const spritemap& sprite_data) {    std::pair<int, int> projection = v.project(x, y);    // in a 2D game, that will probably just do a simple translation and    // maybe scaling to support multiple screen resolutions...    spritemap::const_iterator it = sprite_data.find(sprite_handle);    if (it == sprite_data.end()) {      throw no_sprite_named(sprite_handle);    }    it->drawAt(v, projection.first, projection.second);  }};// ...typedef std::vector<Character> charlist;charlist characters;// ...std::sort(characters.begin(), characters.end());// Characters are sorted from smallest Z to largest; largest is furthest away// (presumably) so we want to draw them first. Thus the reverse iterators.for (charlist::reverse_const_iterator it = characters.rbegin(),                                      end = characters.rend();     it != end;     ++it) {  it->draw(myViewport, mySprites);}

##### Share on other sites
You should probably use Boost.MultiIndex