Equal Range with a 3D multimap

[carebearboy]

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
go.get(x, y);

This is what I have so far:

std::pair<std::multimap<int, std::multimap<int, GameObject*>>::iterator,
std::multimap<int, std::multimap<int, GameObject*>>::iterator> it;

Here is a function I made that will get the pairs of the x values:

// returns all characters at identical x chunk
std::pair<std::multimap<int, std::multimap<int, GameObject*>>::iterator,
std::multimap<int, std::multimap<int, GameObject*>>::iterator>
Game::getXChunkRange(const int& xChunk)
{

    return go.equal_range(xChunk);

}

Now what is needed is to plug that value into another equal_range function to find pairs of the 'y' chunks.

Any ideas?

[Cubbi]

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

std::vector<GameObject*> get(int x, int y)
{
    std::vector<GameObject*> result;
    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)
            result.push_back(j->second);
    }
    return result;
}

[carebearboy]

Thank you for typing that out for me!

I hadn't thought of using a vector to store the values. This would definately work but I question the speed. This function will be executed thousands of times per second so I'm not sure its an option.

Would it be possible to do something like this:

Pseodo code....

std::pair<std::multimap<int, std::multimap<int, GameObject*>>::iterator,
std::multimap<int, std::multimap<int, GameObject*>>::iterator>
Game::getRange(const int& x, const int& y)
{
    auto p = go.equal_range(x);
    auto p2 = p->equal_range(y);

    return p2;
}

... and just return the iterator?

[Cubbi]

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.

[carebearboy]

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.

[carebearboy]

Well, I guess I just can't keep away, :/... For anyone that is interested I've made a solution with some of Cubbi's advice:

std::vector<GameObject*> Game::getXY(const int& x, const int& y, const int& xRange, const int& yRange)
{
    // below declaration to be made elsewhere and used in this function:
    std::multimap<int, std::multimap<int, GameObject*>*> go;
    
    std::vector<GameObject*> result;
    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)
            result.push_back(it2->second);
    }

    // could be easily used in another function like this:
    for(auto& it3 : result)
    {
         (void)it3; // do stuff here
    }

    return result;

}

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.

[Cubbi]

Why map integers to pointers to multimaps? That's a very unnecessary indirection.

[carebearboy]

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.

[Cubbi]

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.

[carebearboy]

To use (x,y) composite key, you will have to define ordering on those keys.

Here's what I came up with by looking on the net and some other forums input:

    std::multimap<Keys, GameObject> go2;

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

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

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


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

This will iterate through x, y values but I'm not sure how to implement a system to use with specific x & y 'ranges.'

Here is the Key class:

class Keys {


    public:

        Keys(const int k1, const int k2) : key1(k1), key2(k2) { }

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

            return key2 < right.key2;
        }

        const int getKey1() const { return key1; }   // kinda pointless being its not private :/
        const int getKey2() const { return key2; }

        int key1;
        int key2;
};

I'll take a look into the quad tree tomorrow. Thank you! :)