I know many people do not like the idea of having containers within containers as they can get complicated. I agree it's complicated but I think it's doable and once it gets done it'll be encapsulated in a component class that rarely gets looked at anyways and would be accessed like so:
// access go (aka gameObject) @ x, y location
There's nothing wrong or uncommon about containers within containers.
If I follow your question, you want a function ??? get(int, int) that obtains all GameObject* from multimap<int, multimap<int, GameObject*>> where the int keys are specified by get()'s arguments?
Yes, you can do it with two equal-ranges. The first one will select the range of multimaps, the second will select a subrange within each nested multimap. The question is how do you combine those subranges for the final return from get()?
You could build a new container, which could be as unsophisticated as
1 2 3 4 5 6 7 8 9 10 11 12
std::vector<GameObject*> get(int x, int y)
auto p = go.equal_range(x);
for(auto i = p.first; i != p.second; ++i)
auto p2 = i->second.equal_range(y);
for(auto j = p2.first; j!=p2.second; ++j)
If allocation of the container to hold the results is a concern, yes, you could return a pair of iterators, similar to what equal_range() returns.
But you'd have to actually write that new iterator type: it would hold two pairs of iterators as data members (outer pair of iterators from the outer equal_range and inner pair of iterators from the current inner equal_range). Dereferenceing your iterator would dereference the current inner iterator member, incrementing your iterator would increment the current inner iterator member, but if it becomes end(), it would increment the outer and call another equal_range to get the new values for the inner pair.
It's a worthwhile exercise, but I'd profile the performance with a regular vector return first, especially if the number of elements it would return is small and you could use a faster allocator.
Thanks for this information Cubbi. I wont be writing a new iterator type any time soon, but it's good to know that this issue requires it so I'm not looking around trying to find an easy solution that doesn't exist.
As for now I'm going to use just a regular multimap and gain proficiency until I'm confident enough to start nesting containers easily.
std::vector<GameObject*> Game::getXY(constint& x, constint& y, constint& xRange, constint& yRange)
// below declaration to be made elsewhere and used in this function:
std::multimap<int, std::multimap<int, GameObject*>*> go;
std::multimap<int, std::multimap<int, GameObject*>*>::iterator it1, itlow1, ithigh1;
std::multimap<int, GameObject*>::iterator it2, itlow2, ithigh2;
itlow1 = go.lower_bound(x - xRange);
ithigh1 = go.upper_bound(x + xRange);
// interate through a range of upper/lower x/y values
for (it1 = itlow1 ; it1 != ithigh1; ++it1)
itlow2 = it1->second->lower_bound(y - yRange);
ithigh2 = it1->second->upper_bound(y + yRange);
for (it2 = itlow2; it2 != ithigh2; ++it2)
// could be easily used in another function like this:
for(auto& it3 : result)
(void)it3; // do stuff here
The great thing about this component style programming is that this complex container nesting only has to be done once and then it's hidden away and encapsulated. I hope this info helps someone. I know I would have loved to read a post about this.
Why map integers to pointers to multimaps? That's a very unnecessary indirection.
True. I'm just learning so that's what I came up with, but I heard on another forum about using a composite key to hold x/y values and that seems like the thing to do. So I guess I have a little reading ahead of me.
To use (x,y) composite key, you will have to define ordering on those keys.
The usual ordering is lexicographical (compare x's first, if they are equal, compare y's). With that, you will be able to call go.equal_range() and fetch your pair of iterators for all GameObject* for the given x and the given y.
It won't help your new example, however: lower_bound/upper_bound from (x - xRange, y-yRange) to (x + xRange, y+yRange) will include coordinate pairs that are not in your range. If you're going to need that a lot, you could probably do it fast with a quadtree.