Sign in to follow this  
Servant of the Lord

Map containers with the value containing the key

Recommended Posts

I occasionally find I want to do something like this: (pseudocode)

struct MyStruct
{
    int uniqueID;
    Data otherData;
    Data moreData;
};
 
std::map<MyStruct::uniqueID, MyStruct> myMap;

The key for the map is actually contained within the value that is being mapped.

This only makes sense when each Value is actually unique (otherwise you might want to map multiple keys to equal values).

 

I could use a std::unordered_set<MyStruct>, and pass in a custom comparison operator that only works on the unique ID, I suppose.

Or maybe std::map<std::reference_wrapper<int>, MyStruct> ?

 

Is this commonly done, and what is the recommended practice for it?

Share this post


Link to post
Share on other sites
alvaro    21246
I've seen code like that, but for the most part the uniqueID has no business being part of the struct. Perhaps it is required in your situation, but I'm starting to believe it's a bit of a code stink.

Perhaps you can give us an actual example, so we can try to evaluate how appropriate each alternative is?

Share this post


Link to post
Share on other sites

It is a bit of a code-stink, isn't it?

 

Here's my animation details:

//This is what is serialized into files for re-constructing the Animation later.
struct AnimationDetails
{
public:
	struct Frame
	{
		ImageFileID id = 0; //16 bits
		short delay = 0;    //16 bits
	};

public:
	std::string displayName; //4 byte overhead (a null pointer) when empty with GCC on a 32 bit machine.
	StringList tags;		 //16 byte overhead (pointer to memory, size, capacity-size) when empty with GCC on a 32 bit machine.
	bool standardTileSized = false;  //If true, this Animation is the standard tile size.
	bool coversEntirely = false; //If true, this image covers everything beneath it 100%, with no transparency and no fully-clear portions.
	bool suggestedSolid = false; //If true, this image is suggested to be solid, but doesn't have to be.

	std::vector<Frame> frames;
	MaterialID primaryMaterial;
	MaterialID secondaryMateral;
};

Each one is unique, not by requirement, just by nature. There is no need for me to have two or more identical animations.

That alone doesn't mean the ID should be part of the struct, ofcourse - and currently it's not.

 

This is how I currently have it (which works fine):

//This is what is serialized into a file for re-constructing the animations later.
//This is saved for the entire game - loaded at startup.
std::unordered_map<AnimationID, AnimationDetails> animationDetails;

The only "issue" is that in a different part of my code that I'm just now writing, because of third-party API issues, I find myself passing around both the AnimationID and the AnimationDetails to separate functions:

void Animation_SetModelItemFromStruct(QStandardItem &item, AnimationID id, const AnimationDetails &animationDetails);
std::pair<AnimationID, AnimationDetails> Animation_GetStructFromModelItem(const QStandardItem &item);

void Animation_AddAnimationToModel(AnimationID id, const AnimationDetails &animationDetails);
void Animation_RemoveAnimationFromModel(AnimationID id);

I figured, if I keep passing them around with each other, maybe that's an indicator that they belong together, especially since the third-party API has me putting them together into a key-value property map anyway.

 

But you're right, they really shouldn't be together. I think it's just the generic nature of the API I'm putting the data into that was misleading me. I'm only using that API in one section of the code, so I really shouldn't let that tiny section of code dictate the architecture of the rest of my code-base.

 

I think I'll do this:

typedef std::pair<const AnimationID, Engine::AnimationDetails> AnimationKVPair; //Key-value pair.

...which will make those functions make more sense, in the few parts where I have to deal with the API.

Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
SeanMiddleditch    17565
Use a std::set instead. You can give the set a custom comparator that only compares the key field of the value type intead of the whole object. C++11-compliant standard library will be required to ensure that you can use .find() with your key type and have a heterogeneous comparator. You'll need to write your own comparator functor that knows how to compare the value type vs itself (using only its key field), or values of the key field vs the value type in either direction (key vs value and value vs key).

Also consider using a flat_map or flat_set instead of a std::set. A flat_map/flat_set is just a sorted std::vector searched via std::lower_bound, which has better data locality (cache) behavior with mostly similar asymptotic computation complexities (both are average/worst case O(log(N)) for the most frequent operation, search).

Share this post


Link to post
Share on other sites

You can't change the object if you put it in a std::set though once you inserted it (even if you don't change the key, just the other data) without the compiler complaining... which caused a lot of pain with legacy code when we moved over to VS2008 (or was it VS2010). Lots of const_cast or mutable was required.

 

I'd use a map and separate the key from the value but if you need to refer to them both afterwards it is a problem unless you hold on to the iterator.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
SeanMiddleditch    17565

You can't change the object if you put it in a std::set though once you inserted it


Ah, gotcha. I honestly forgot that bit. I haven't myself touched std::map or std::set in years - the memory behavior of them are pretty much the antithesis of games. Hence the flat_set suggestion. You can make flat_set elements mutable if you write your own implementation or use an existing sensible one (just be sure not to mutate the key!).

Share this post


Link to post
Share on other sites

It used to be OK to change it but because it then allowed you to change the key all sorts of nastiness could happen, so now you can only get a const_iterator for a set or map (dunno if that is a C++11 thing or not).

Share this post


Link to post
Share on other sites

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