Using std::less to Create an std::map Winding Around the Origin

Question

Introduction

Hello! I'm writing a simulation that operates in a non-trivial space. This system occupies an undetermined amount of space around a centered origin. Right now, I'm implementing an xy point class 'Pos' to join my coordinates and to act as a key for my containers (containing finite blocks of data). I'd like the data around the origin to be spatially coherent in memory.

My goal for this question is to write a specialization for std::less that, if (integral) positions were inserted into the map, they would be ordered according to a counter clockwise winding order.

I imagine that cells :

4 3 2
5 0 1
6 7 8 9

would become

0, 1, 2, 3, ... .

Question

How should I wrap my mind around writing an std::less, so that I can wrap my points around, like this? How can I understand how the solution follows strict weak ordering and avoids other pitfalls?
Finally, how would you best approach or write this function with the tools available in C++11?

(If using an unordered map and iterating linearly through a bounding box surrounding a dynamic origin is a much more flexible and efficient solution for my purposes, feel free to write an implementation for it, but I won't be marking it as the best answer.)

---

Aside

I've been learning by implementing naive attempts, but I believe it would be better for myself to solve this with a discussion and sound explanation than luck.

Here's a snap of context.

struct Pos
{
    short x;
    short y;
    Pos(short x, short y);
    Pos(const Pos& p);
    void operator=(const Pos& p);
    ~Pos() = default;
};
namespace std {
    template<> struct less<Pos> {
        bool operator()(const Pos& p1, const Pos& p2) const {
            //Implementation
        }
    }
}

This is my first question, and I've tried to follow the rules. If I've done anything wrong, please be supportive and I'll do my best to put things in order. Thanks for your support!

Answer 1

Let us try to solve this equivalent problem : Write a function f : (Z, Z) -> Z, where N is the set of integers, such that if you started writing numbers from 0 starting at the origin, and going in a counter-clockwise outward spiral, the number at (x,y) would be f(x,y).

We will using the following observations :

1. The last element of the k-th rung of the spiral, (k, -k) satisfies f(k, -k) = (2k+1)^2 - 1.
2. Every "arm" of the k-th rung(for k>0) has k+1 elements.
3. (x,y) lies on the max(|x|, |y|)-th rung.

Using the above, you can come up with a piece-wise description for f based on which co-ordinate defines the rung. Thus, you have a constant time method to compute f. Functionally, you can define less( (x1,y1), (x2,y2) ) = less(f(x1,y1), f(x2,y2)).