Followers 0

# Sorting a std::map

## 7 posts in this topic

Hi.

Sorry for the topic title, I don't really know how to explain it in a short sentence.

I'm making a game and all my entities are stored in a std::map<std::string, Entity*>  and I'd want to sort them by their Y axis position(to draw them from top to bottom of the screen), the Entity class has a method getYPos, but I can't figure out how to sort them. I'd appreciate if any of you guys have some advices.

Thanks.

Edit: I wanted to use std::sort but I never used this and don't really understand how to make it works with a std::map.

Edited by Borax Kid
0

##### Share on other sites

std::map is an "ordered" container, meaning it is already sorted internally based on the Compare template parameter of the type (less<Key> by default). You can't change the sorting of a map, because that would violate its type properties. Basically, it does not make sense to sort a map.

What you probably want is a separate container that stores your entities in sorted order specifically for drawing. Perhaps you could keep an std::list that you sort each frame, or each time an entity's Y position moves it could be removed from the list an reinserted in the proper location.

0

##### Share on other sites

Thanks, I tried to implement this, but that didn't work, I searched on google but I did it right (I think) but I got these errors :

C:\Code\Survival\PlayState.cpp||In member function 'void PlayState::sortEntities()':|
C:\Code\Survival\PlayState.cpp|144|error: no matching function for call to 'std::list<std::basic_string<char> >::sort(<unresolved overloaded function type>)'|
C:\Code\Survival\PlayState.cpp|144|note: candidates are:|
c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc|364|note: void std::list<_Tp, _Alloc>::sort() [with _Tp = std::basic_string<char>; _Alloc = std::allocator<std::basic_string<char> >]|
c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc|364|note:   candidate expects 0 arguments, 1 provided|
c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc|441|note: void std::list<_Tp, _Alloc>::sort(_StrictWeakOrdering) [with _StrictWeakOrdering = bool (PlayState::*)(const std::basic_string<char>&, const std::basic_string<char>&); _Tp = std::basic_string<char>; _Alloc = std::allocator<std::basic_string<char> >]|
c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\list.tcc|441|note:   no known conversion for argument 1 from '<unresolved overloaded function type>' to 'bool (PlayState::*)(const std::basic_string<char>&, const std::basic_string<char>&)'|
||=== Build finished: 1 errors, 0 warnings (0 minutes, 1 seconds) ===|



My code looks like this :

(PlayState.hpp)

#include <list>
#include <algorithm>
#include <vector>
#include <string>

class PlayState : public GameState
{
public:
/*
methods
*/
private:
std::list<std::string> _sortedEntities;
}


(PlayState.cpp)

bool PlayState::compareYAxisPosition(const std::string& first, const std::string& second)
{
/*
Compare and return a bool
*/
}

void PlayState::sortEntities()
{
//std::sort(this->_sortedEntities.begin(), this->_sortedEntities.end(), this->compareYAxisPosition);
this->_sortedEntities.sort(this->compareYAxisPosition);
//I tried these two differents types of writing it, but same errors occured
}


Is there something I missed ?

0

##### Share on other sites

I can't tell from the code snippet but the compareYAxisPosition function needs to be either static, a standalone function, or a c++ 11 lambda function.

Edit: what Sean said

0

##### Share on other sites

Thanks a lot to all of you, especially you Sean. I wasn't using C++11 so I just downloaded a new version of Code::Blocks, I think that might make my life easier!

The system works, so this topic is solved.

Thanks again.

0

##### Share on other sites
For anyone else not using a C++11 compiler with lambdas but still wanting to use a member function for sorting, the other option is to use std::bind (also C++11, but more compilers supported this for longer via a TR or Boost). Using Boost it would look something like:

void PlayState::sortEntities()
{
std::sort(this->_sortedEntities.begin(), this->_sortedEntities.end(), boost::bind(std::mem_fn(&PlayState::compareYAxisPosition), this, _1, _2));
}
I always have trouble getting the _1 (and so on) identifiers to resolve right with Boost and have to fiddle with includes and namespaces a lot until it works, but that's the gist of it.

The way without boost or any C++11 would involve writing a custom Functor:


bool PlayState::compareYAxisPosition(const std::string& first, const std::string& second) { /*logic*/ }
struct CompareYAxisPositionFunctor
{
PlayState& state;
CompareYAxisPositionFunctor(PlayState& state) : state(state) {}
bool operator()(std::string const& lhs, std::string const& rhs) { return state.compareYAxisPosition(lhs, rhs); }
};
void PlayState::sortEntities()
{
std::sort(this->_sortedEntities.begin(), this->_sortedEntities.end(), CompareYAxisPositionFunctor(*this));
}
The boost::bind/std::bind is just a template library facility that generates functor types like the above. C++11 lambdas are a language facility that does the same.

It's important to remember when writing C++ code that these kinds of functor types are fundamental to how the STL (and similar algorithm and high-level libraries) operate and that all the newer library/language features do is make it easier to generate functors with less boilerplate, not remove them.
1

## Create an account

Register a new account