I'm a bit lost looking at your code, I guess I'm not advanced enough in C++ to understand that at a glance. I don't know why you'd need more than one way to sort it .. I think it comes down to your level/slice being a more advanced implementation than I am doing. I consider everything to be on the same "level".
A slice is a horizontal row at the screen, or a diagonal line on the grid. One tile position is actually a stack of tiles, as you can have things above each other. Within a tile stack, you sort on height from low to high (low gets drawn first, so higher things stay visible). Within a single tile at a single height I draw several things, again from back to front, eg first fences in the background, then people, then fences near the front.
In my game (FreeRCT), there are actually 4 views; the user can rotate the world 90 degrees. To implement, you either need to rotate the entire map-data, or you rotate the view. I chose the latter, which means "in front of" above changes with rotation.
But I could change it to
* Find all gameObjects within a set distance from the player
- Add them to drawObjects
* sort drawObjects;
* loop through all drawObjects
- gameObject.draw();
This is one of the points I was trying to get across. This is how I draw things currently. The std::multiset uses '<' order to sort its values internally.
So std::multiset<int> will work out of the box, std::multiset<MyClass> needs a '<' operator.
Now the clever bit that I do is the 'MyClass::operator<' (written as function 'bool operator<(const MyClass &c1, const MyClass &c2)') uses the sort order you need for "sort drawObjects". Thus when I insert an object into 'std::multiset<MyClass> drawObjects', it uses the drawing order sort to place the new element in its storage. As a result, when I am done adding all drawObjects, it is already sorted in the order I want. I can go straight to drawing them.
frob is correct in stating that you don't actually need to do sort (at least not on this scale). If you know the direction of viewing, you can compute the visible tiles, and code the sorting order into a "draw-tile" routine (I'd need 4 such routines, but still very doable). Call that routine fro every visible tile, (from back to front) and done! That does imply that you can quickly find tile contents by map coordinate though.
I could code such a drawing routine (my map has all tile contents), and have plans to eventually do that. My sorting was added in the beginning of the project, before I really knew what I had to do for drawing. One of the nice things is that changing order of drawing is simple, just change the '<' implementation. That has proven beneficial for development a few times. For this reason I am not in a big hurry to replace it until development is close to completion.
Performance is horrible in my game currently, as indeed access to the GPU and video memory is too slow, as already stated by frob. This problem is a lot higher on my list of things to fix, but not at the top.