Jump to content

  • Log In with Google      Sign In   
  • Create Account


Map containers with the value containing the key


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Servant of the Lord   Crossbones+   -  Reputation: 18242

Like
0Likes
Like

Posted 14 February 2014 - 05:45 PM

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?


It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.

[Fly with me on Twitter] [Google+] [My broken website]

All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.                                                                                                                                                            [Need web hosting? I personally like A Small Orange]
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12500

Like
0Likes
Like

Posted 14 February 2014 - 05:58 PM

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?

#3 Servant of the Lord   Crossbones+   -  Reputation: 18242

Like
0Likes
Like

Posted 14 February 2014 - 06:33 PM

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, 14 February 2014 - 06:35 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.

[Fly with me on Twitter] [Google+] [My broken website]

All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.                                                                                                                                                            [Need web hosting? I personally like A Small Orange]
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal


#4 SeanMiddleditch   Members   -  Reputation: 4826

Like
0Likes
Like

Posted 14 February 2014 - 07:07 PM

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).

#5 Paradigm Shifter   Crossbones+   -  Reputation: 5233

Like
0Likes
Like

Posted 14 February 2014 - 07:13 PM

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, 14 February 2014 - 07:13 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#6 SeanMiddleditch   Members   -  Reputation: 4826

Like
0Likes
Like

Posted 14 February 2014 - 07:54 PM

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!).

#7 Paradigm Shifter   Crossbones+   -  Reputation: 5233

Like
0Likes
Like

Posted 14 February 2014 - 07:58 PM

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).


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS