How do I insert a multimap into another multimap?

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 *>()));


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*> go2;
std::multimap*>::iterator it1, itlow1, ithigh1;
std::multimap::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() ));

// make object to insert
std::multimap 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]

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

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


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

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

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.

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 such as std::multimap, GameObject *>.

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 such as std::multimap, 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 go2;

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

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

GameObject* gameObj3 = new GameObject;
gameObj3->val()->newNum("test", 30);
go2.insert(std::pair( 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.

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

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"?

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. [/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.

Congratulations, you've re-implemented std::pair ... 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.[/quote]
Thank you so much for that explanation. Now I know.

Also, it's kind of pointless to create getters for public member variables.[/quote]
Lol, yeah. I noticed that too. I'm so used to declaring class variables private and making a get function for it... Why stop now??

What do you mean by "iterate in ranges"?
[/quote]

I want to be able to do something like this:

[source lang="cpp"]void getXY(const int& x, const int& y, const int& xRange, const int& yRange)
{

// pseodo code:
for(it = xlow; it != xhigh; ++it)
for(it2 = ylow; it != yhigh; ++it2)
// do something
}[/source]

This way I can print out only certain x/y chunks whilst in my game. If std::pair works thats great but I don't know where to find a good tutorial or an example.

Let's step back a second. What are you actually trying to do? Not, "how are you trying to implement it", but what is your overall design problem you are solving?

Do you have a grid of spaces, and a game object might be on that grid?

Let's step back a second. What are you actually trying to do? Not, "how are you trying to implement it", but what is your overall design problem you are solving?

Do you have a grid of spaces, and a game object might be on that grid?

I'm making a mario-style side-scroller. My map is made up of x and y chunks, but it is not a grid. They are more like a list of chunks. This way I can skip chunks (or sections, whatever you want to call it) for areas that don't have any objects. So this is not tile-based. I would like to make a board map that is speed and memory efficient that can do positive and negative chunks. This is important because I want the map to be realtime expandable during runtime. There will be a lot of objects in the game so I want to be able to focus on only displaying the very minimum. There may be more then one object on the same chunk as well, hence the multimap. Levels might just go up 0 degrees. They might go backwards (270 deg). They might 'squiggle' or go in a circle.

I've done this all before but only with an X chunk and not with a Y chunk as well. So the map was only cut into X sections which led to inefficiencies if the level went straight upward. Since then I've since learned some new concepts such as component/entity programming so I'm changing things up and starting over.

If what you want to do is to do some operation on every element with x_begin <= x < x_end and y_begin <= y < y_end, one way to do that would be like:

typedef std::pair<int, int> Key;
typedef std::multimap<Key, GameObject *> Map;

template <typename Operation>
void loop(const Map & map, int x_begin, int x_end, int y_begin, int y_end, Operation operation) {
if (x_end <= x_begin) return;
if (y_end <= y_begin) return;

Key lower(x_begin, y_begin);
Key upper(x_end - 1, y_end);
auto first = map.lower_bound(lower);
auto last = map.lower_bound(upper);

for (auto itr = first; itr != last;) {
int x = itr->first.first;
int y = itr->first.second;

if (y < y_begin) {
itr = map.lower_bound(Key(x, y_begin));
} else if (y >= y_end) {
itr = map.lower_bound(Key(x + 1, y_begin));
} else {
//do whatever
operation(*itr);

++itr;
}
}
}


Excellent description of your intents. If you can't describe it, you have a problem - but you described it very succinctly.

Are chunks are composed of tiles? Or objects?

Programming rule #3421: Premature optimization is the root of many evils.
Programming rule #745: KiSS: Keep it Stupidly Simple ([size=2]alternatively, Keep it Simple, Stupid)

Have you actually tried just making a grid of uniform chunks, and actually seeing if it's too slow for your program?

But that aside, let's see what we can do. It helps simplify things if you put stuff into their own classes or structs.

Your game world is composed of Objects (enemies, walls, the player, moving platforms, spikes, etc...).

Each object has a location in the world, probably in a pixel-like measurement unit.
So: World has 100,000+ objects. Obviously we can't load and process all those at the same time. (Actually with modern computers, we probably could - but we'll pretend we can't).

So you break your world into 'chunks'. World has a grid of smart pointers to Chunks (yes, a grid). Each location on the grid can either be a null smart pointer (thus saving you your precious memory ), or can have a smart pointer to a valid Chunk.

A World:

• Has a grid of chunks.
  
• Streams chunks in and out around the player.
  
• Tells chunks to draw, update, etc...
  
  A chunk is just a "bucket" of entities. Any solid who's center is over the chunk's boundaries, belongs to that chunk.
  A Chunk:
  
  
  • Manages it's own loading and saving from file.
    
  • Tells the Objects within it to draw, think, etc...
    
  • If an Object Entity walks off of one chunk, that chunk passes ownership of that object to the next chunk.
    
    When 'unloaded', the Chunk still exists, the Objects are destroyed (until the next reload), unless that particular Object is persistent and needs to think even when distant from the player, in which case they aren't drawn and only need to be updated at a much slower update rate.
    Almost all walls are persistent, but don't need to think when the player isn't near. Almost all enemies need to think, but don't need to be persistent. Some enemies need to think and be persistent (a special enemy hunting the player from a million miles away, for example).
    
    Maybe you want to specify to only keep an object in memory if it's within a certain range.
    
    Let's convert this directly to pseudo-code:
    Object
{
Position
IsPersistent
RangeToKeepInMemory //The distance away the player needs to be before it is destroyed.

bool SaveStateWhenDestroyed() -> (IsPersistant && hasChanged)
bool KeepInMemory(playerDistance) -> (playerDistance > RangeToKeepInMemory)

Save()
Load()

Draw()
Update(deltaTime) //Think, animate, etc...
}

Chunk
{
Vector<Object::Ptr> Objects

StreamOut() //Unloads all objects except those it needs to keep in memory.
StreamIn() //Loads all persistent objects, like walls and enemies that don't spawn but have preset locations like bosses.

Draw() -> Draw every object
Update(deltaTime) -> Update every object
}

World
{
Grid<Chunk::Ptr> Chunks;

LoadNewWorld();
StreamChunksAround(location);

Draw() -> Draws all chunks nearby.
Update(deltaTime) -> Updates chunks (which in turn updates objects)
}

    
    This can be improved upon, but it's a good start and really straightforward and simple. It also does not waste much memory or speed.
    
    You can steal my C++ Grid class here - re-sizable and permits negative indices. If you know the size of your World ahead of time, and it doesn't change during the course of that play, you could use a std::vector of size (width*height) instead.
    
    The whole map> thing just doesn't seem like good design.

If what you want to do is to do some operation on every element with x_begin <= x < x_end and y_begin <= y < y_end, one way to do that would be like:

typedef std::pair<int, int> Key;
typedef std::multimap<Key, GameObject *> Map;

template <typename Operation>
void loop(const Map & map, int x_begin, int x_end, int y_begin, int y_end, Operation operation) {
if (x_end <= x_begin) return;
if (y_end <= y_begin) return;

Key lower(x_begin, y_begin);
Key upper(x_end - 1, y_end);
auto first = map.lower_bound(lower);
auto last = map.lower_bound(upper);

for (auto itr = first; itr != last;) {
int x = itr->first.first;
int y = itr->first.second;

if (y < y_begin) {
itr = map.lower_bound(Key(x, y_begin));
} else if (y >= y_end) {
itr = map.lower_bound(Key(x + 1, y_begin));
} else {
//do whatever
operation(*itr);

++itr;
}
}
}

[/quote]

Thank you so much for taking the time to type that up. This was exactly what I was looking for; iterating within a range of x/y chunks. Took me a few times reading it over to understand most of what's going on. One thing that puzzles me is the operator input within the parameters. I'm not entirely sure how to supply that parameter input or what it does. If I had to guess its something to do with iterating... I noticed you left out the 3rd parameter in the for loop and incremented it within the loop below the 'operator'. Looks intriguing. Could you explain this?

Also, I see you made map a const in the parameters. Was there a reason for that? I'm likely going to be changing some object within the loop if that's advisable to do.

Once again, I really appreciate you taking the time write all that out for me.

Are chunks are composed of tiles? Or objects?

Objects. Each x/y map cooridinate is loaded with a GameObject which stores the 'components' such as rendering values and instructions for that specific character, the character itself, and sound components...[/quote]

Have you actually tried just making a grid of uniform chunks, and actually seeing if it's too slow for your program?[/quote]
Yes, I had started out with a vector tile-based situation. I profiled it (bare text run, no graphics), testing it with various chunk sizes and getting best performance at around 250 - 500 fps. This was with little characters on the screen and no AI, graphics, at all yet. More characters slowed it right down, 25 - 100 fps. Just not cutting it. I then profiled a system based on a 'list' of airborne x/y chunks, which only had chunks that held objects, and fps went to 4000 -10000 fps. When I first jumped I thought it was broken because I couldn't see the character jump! When I loaded the board and level with characters, massively, it still did 150 - 500 fps, which was good enough.

So you break your world into 'chunks'. World has a grid of smart pointers to Chunks (yes, a grid). Each location on the grid can either be a null smart pointer (thus saving you your precious memory ), or can have a smart pointer to a valid Chunk.[/quote]
I like the smart pointer idea and I like the idea of maybe using something to say if a character is enabled or not. Objects not enabled could be used as pooled objects, which is fine. By 'chunks' I see you mean a 'grid' but I do not want a tile-based grid. I'd rather a list (map, vector....whatever container) 'within' a chunk. So anything on that list that is processed if that chunk is on the screen.

A chunk is just a "bucket" of entities. Any solid who's center is over the chunk's boundaries, belongs to that chunk.
A Chunk:

• Manages it's own loading and saving from file.
  
• Tells the Objects within it to draw, think, etc...
  
• If an Object Entity walks off of one chunk, that chunk passes ownership of that object to the next chunk.[/qoute]
  
  I'll take a look at your code. I'm thinking of maybe having an outside entity control the chunks. As for objects changing chunks, you've described it exactly how I had it before; objects swapping memory positions to different containers. As well, leaving a pooled disabled object in its tracks to be used later.
  
  
  

  Maybe you want to specify to only keep an object in memory if it's within a certain range.[/quote]
  That's a good idea. Perhaps a small loop that runs a list of these characters and runs an update() with full or high range chunks. But that's a while away.
  
  

  Let's convert this directly to pseudo-code:
  Object
{
Position
IsPersistent
RangeToKeepInMemory //The distance away the player needs to be before it is destroyed.

bool SaveStateWhenDestroyed() -> (IsPersistant && hasChanged)
bool KeepInMemory(playerDistance) -> (playerDistance > RangeToKeepInMemory)

Save()
Load()

Draw()
Update(deltaTime) //Think, animate, etc...
}

Chunk
{
Vector<Object::Ptr> Objects

StreamOut() //Unloads all objects except those it needs to keep in memory.
StreamIn() //Loads all persistent objects, like walls and enemies that don't spawn but have preset locations like bosses.

Draw() -> Draw every object
Update(deltaTime) -> Update every object
}

World
{
Grid<Chunk::Ptr> Chunks;

LoadNewWorld();
StreamChunksAround(location);

Draw() -> Draws all chunks nearby.
Update(deltaTime) -> Updates chunks (which in turn updates objects)
}
  
  This can be improved upon, but it's a good start and really straightforward and simple. It also does not waste much memory or speed.
  
  You can steal my C++ Grid class here - re-sizable and permits negative indices. If you know the size of your World ahead of time, and it doesn't change during the course of that play, you could use a std::vector of size (width*height) instead.
  
  The whole map> thing just doesn't seem like good design.
  [/quote]
  Thank you for all that info! I'll take a look at your Grid class tomorrow when my mind is more agile and has had some rest. Been at this all day. Negative indices and resizable definately sounds good. It's just what I need.

One thing that puzzles me is the operator input within the parameters. I'm not entirely sure how to supply that parameter input or what it does. If I had to guess its something to do with iterating...

As written you can supply anything function like that would take a reference to a const value_type including function pointers, function objects, lambdas, etc. If you don't understand it, you can just replace the call with the actual functionality you want to do on each element.

I noticed you left out the 3rd parameter in the for loop and incremented it within the loop below the 'operator'. Looks intriguing. Could you explain this?[/quote]
There's not much to explain. All three parts that go inside the parenthesis for a for loop are optional. for (A; B; C) is just syntactic sugar for

{ A;
while (B) {
// body of for loop
C;
}
}

With the exception that if you leave out the second part the while loop looks like while (true). If you leave off the first part, nothing is done before the going through the loop for the first time. If you leave out third part, nothing extra happens after the body of the for loop. So for (;;) {} would be the same as while (true) {}. Since in this loop what happens to itr is different depending on what itr refers to, trying to stick it in the third part of the for loop, while possible, would be horribly unreadable.

Also, I see you made map a const in the parameters. Was there a reason for that? I'm likely going to be changing some object within the loop if that's advisable to do.[/quote]
This code doesn't handle the situation of adding or removing nodes from the map while it's looping. Ex: if for some reason you remove the element pointed to by last, it'll keep looping until it crashes. However, one of the interesting things about std::map is that if you have a map with pointers as the values, you can call non-const functions on the pointed to objects from a const_iterator. That is to say, this is legal:

std::map<int, Foo *> foo_map;
// fill the map
std::map<int, Foo *>::const_iterator itr = foo_map.begin();
itr->second->non_const_function();