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>.[/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<int, int> 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<map<Object>> 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<map<Object>> 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();