Jump to content
  • Advertisement
Sign in to follow this  
bedtime

How do I insert a multimap into another multimap?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've looked around and can't seem to find the answer.

Here is my multimap and an attempt at my idea of what I want to do:

[source lang="cpp"] // declared multimap of x/y/object
std::multimap<int, std::multimap<int, GameObject*>*> gameObj;

// pseodo code of what I want to do:
GameObject* tempObj = new GameObject;
gameObj.insert({ 1, { 1, tempObj });[/source]


Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
Your multimap has a pointer to a multimap as the value, so you need to pass a pointer when you insert into it. Probably by using new to allocate a multimap. So something like:

gameObj.insert(std::make_pair(1, new std::multimap<int, GameObject *>()));

Share this post


Link to post
Share on other sites

Your multimap has a pointer to a multimap as the value, so you need to pass a pointer when you insert into it. Probably by using new to allocate a multimap. So something like:

gameObj.insert(std::make_pair(1, new std::multimap<int, GameObject *>()));



Thank you. Worked perfectly!

Here's what I did:

[source lang="cpp"] std::multimap<int, std::multimap<int, GameObject*>*> go2;
std::multimap<int, std::multimap<int, GameObject*>*>::iterator it1, itlow1, ithigh1;
std::multimap<int, GameObject*>::iterator it2;

// just return first result (better used with map than multimap)
it1 = go2.find(x);
it1->second->find(y);//->second;

// inserting a new object
go2.insert(std::make_pair( 1, new std::multimap<int, GameObject *>() ));

// make object to insert
std::multimap<int, GameObject*> gameObj;
GameObject* insertedGameObject = new GameObject;


// inserting object
gameObj.insert({ 1, insertedGameObject });
go2.insert(std::make_pair( 1, &gameObj ));


itlow1 = go2.lower_bound(x);
ithigh1 = go2.upper_bound(x);

// interate through all uppper/lower x/y values
for (it1 = itlow1 ; it1 != ithigh1; ++it1)
{
for (it2 = it1->second->lower_bound(y); it2 != it1->second->upper_bound(y); ++it2)
{
// do something
}
}[/source]

Share this post


Link to post
Share on other sites
When doing containers within containers, it helps to typedef them (if it makes sense in whatever context your code is in).
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap*> gameObj;


Second, you 'new' a GameObject, but call it 'tempObj'. A new'd variable is definitely not temporary. Anything you new must be deleted. Your map will not delete it for you.
Likewise, following SiCrane's suggestion, you need to remember to delete any std::multimap<int, GameObject*> you new.

If you use smart pointers, the smart pointers will delete the memory for you - but as it stands, you'll have multiple massive memory leaks (depending on the number of GameObjects and how hefty they are).

I like to typedef my smart pointers within GameObject class itself, so I can use GameObject::Ptr instead of std::shared_ptr<GameObject>.

This will result in code that looks like this:
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap> gameObjects;

gameObject.insert({1, {1, std::make_shared<GameObject>(...arguments for GameObject constructor...)}});

Share this post


Link to post
Share on other sites
A multimap inside a multimap sounds like quite the hairy data structure, not to mention the extra memory management you incur by having the outer multimap store pointers to the inner multimaps! You could accomplish the same thing with a single multimap to your objects and a composite key :)

Share this post


Link to post
Share on other sites

When doing containers within containers, it helps to typedef them (if it makes sense in whatever context your code is in).
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap*> gameObj;


Second, you 'new' a GameObject, but call it 'tempObj'. A new'd variable is definitely not temporary. Anything you new must be deleted. Your map will not delete it for you.
Likewise, following SiCrane's suggestion, you need to remember to delete any std::multimap<int, GameObject*> you new.

If you use smart pointers, the smart pointers will delete the memory for you - but as it stands, you'll have multiple massive memory leaks (depending on the number of GameObjects and how hefty they are).

I like to typedef my smart pointers within GameObject class itself, so I can use GameObject::Ptr instead of std::shared_ptr<GameObject>.

This will result in code that looks like this:
typedef std::multimap<int, GameObject*> GameObjectMap;
std::multimap<int, GameObjectMap> gameObjects;

gameObject.insert({1, {1, std::make_shared<GameObject>(...arguments for GameObject constructor...)}});


Thank you for this info. It's embarrassing how neglectful I've been with deleting my 'new' objects. I also for some reason thought that when the object went out of scope it was delete automatically but after hearing you and reading a little it isn't. A good find here. As far as smart pointers I, they seem like a lazy way to do things but perhaps that's perfect for me for now. :)

A multimap inside a multimap sounds like quite the hairy data structure, not to mention the extra memory management you incur by having the outer multimap store pointers to the inner multimaps! You could accomplish the same thing with a single multimap to your objects and a composite key[/quote]
A composite key? I don't think I've heard of this before. I've just dabbled into this on google and it looks like I have a little reading to do, thanks.

Share this post


Link to post
Share on other sites
A composite key would be instead of using a multimap with an int key containing multimaps with int keys, instead use a single multimap with a key that contains two ints like a std::pair<int, int> such as std::multimap<std::pair<int, int>, GameObject *>.

Share this post


Link to post
Share on other sites

A composite key would be instead of using a multimap with an int key containing multimaps with int keys, instead use a single multimap with a key that contains two ints like a std::pair<int, int> such as std::multimap<std::pair<int, int>, GameObject *>.


This sounds like a great idea and I don't want to keep bugging you for examples. Is there perhaps a good tutorial on this? I have several C++ books but they don't seem to go this in depth. If you can recommend a book that will help me with this I'll read it.

There seems to be a another way. That is to use a Key class to store the keys. How does that compare to using a 'pair' of keys?

Here's what I have played with so far ('val' is encapsulated code that allows me to store to that object and test it):

[source lang="cpp"]class Keys {
public:
Keys(int k1, int k2) : key1(k1), key2(k2) { }
bool operator<(const Keys &right) const
{
return (key1 < right.key1 && key2 < right.key2);
}
const int getKey1() const { return key1; }
const int getKey2() const { return key2; }
int key1;
int key2;
}
[/source]

[source lang="cpp"] std::multimap<Keys, GameObject> go2;

GameObject* gameObj1 = new GameObject;
gameObj1->val()->newNum("test", 10);
go2.insert(std::pair<Keys, GameObject>( Keys(1, 2), *gameObj1) );

GameObject* gameObj2 = new GameObject;
gameObj2->val()->newNum("test", 20);
go2.insert(std::pair<Keys, GameObject>( Keys(3, 4), *gameObj2) );

GameObject* gameObj3 = new GameObject;
gameObj3->val()->newNum("test", 30);
go2.insert(std::pair<Keys, GameObject>( Keys(1, 2), *gameObj3) );


for(auto& i : go2)
{
std::cout << "x: " << i.first.getKey1() << " y: " << i.first.getKey2()
<< " test: " << i.second.val()->getNum("test") << std::endl;
}
[/source]

The above code seems to print out the results just fine, but I question how easy it'll be to get this to iterate in ranges. I do think it might be nice as it would allow multiple ways to sort but I'm new to all this. Edited by bedtime

Share this post


Link to post
Share on other sites

There seems to be a another way. That is to use a Key class to store the keys. How does that compare to using a 'pair' of keys?

Congratulations, you've re-implemented std::pair<int, int> ... incorrectly. For an operator < overload to be valid for use in a std::map or std::multimap it needs to be a strict weak ordering. Some of the qualities of a strict weak ordering are irreflexivity (x < x is false), antisymmetry (if x < y then y < x must be false) and transitivity (if x < y and y < z then x < z). You've got these three. However, the last quality of a strict weak ordering is transitivity of equivalence (also called transitivity of incomparability). Under a strict weak ordering, two objects x and y are equivalent if x < y and y < x are both false. With transitivity of equivalence if x and y are equivalent and y and z are equivalent then x and z must be equivalent. Here your operator < fails. With your function (1, 2) and (3, 2) are equivalent and (3, 2) and (3, 4) are also equivalent. However (1, 2) is less than (3, 4).

One way to fix it is to change your operator < implementation:

bool operator<(const Keys &right) const
{
if (key1 < right.key1) return true;
if (key1 > right.key1) return false;
return key2 < right.key2;
}

Or you could just use std::pair<int, int>.

Also, it's kind of pointless to create getters for public member variables.


The above code seems to print out the results just fine, but I question how easy it'll be to get this to iterate in ranges. I do think it might be nice as it would allow multiple ways to sort but I'm new to all this.
[/quote]
What do you mean by "iterate in ranges"?

Share this post


Link to post
Share on other sites

Thank you for this info. It's embarrassing how neglectful I've been with deleting my 'new' objects. I also for some reason thought that when the object went out of scope it was delete automatically but after hearing you and reading a little it isn't.

Variables on the stack are deleted automatically when they go out of scope (if they have a destructor, it is also called).
Variables on the heap (dynamic allocation) are only deleted manually.

Stack = Automatic allocation, automatic deallocation.
Heap = Manual allocation, manual deallocation (so you can control the lifetime so the memory can exist beyond the scope).

Smart pointers themselves are on the stack, but they point to data on the heap. So when the smart pointer goes out of scope, its destructor is called (being on the stack), which then manually deletes the memory pointed to for you (but only if no other smart pointer is pointing to the same memory).

Prefer everything on the stack whenever possible, but when needed otherwise, use smart pointers to handle the allocation and deallocation for you, except in the 1% of times when you really truly do need to manage it yourself.

A good find here. As far as smart pointers I, they seem like a lazy way to do things but perhaps that's perfect for me for now. smile.png[/quote]
They are the safe way of doing things, and safe is good. The laziest AND safest method is putting memory on the stack instead; but in this situation, your GameObjects probably want to be smart pointers (std::shared_ptr is the smart pointer you'll most likely want). Your keys should be on the stack though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!