How can I initialize a std::map with opposite signature coordinate keys?

Question

For some background information, I am trying to create a quick quadtree generation algorithm using a dictionary lookup. The basic concept involves mapping coordinates to quadtree nodes via binary representation:

struct vec2 { // Test coordinate object
    double x, y; // replacing double with signed int everywhere does not achieve results either
    vec2(const double& x = NULL, const double& y = NULL)
        : x(x), y(y) {}
    friend std::ostream& operator<<(std::ostream& os, vec2 vector)
    {
        return os << "(" << vector.x << ", " << vector.y << ")\n";
    }
    bool operator()(const vec2& lhs, const vec2& rhs) const
    {
        /* TODO: make proper sorting function */
        if ((lhs.x < rhs.x) && (lhs.y < rhs.y)) {
            return true;
        }
        if (std::hypot(lhs.x, lhs.y) < std::hypot(rhs.x, rhs.y)) {
            return true;
        }
        
        return false;
    }
};

std::map<vec2, std::bitset<4>, vec2> nodeLoc = { // quadtree node mapping
            { ( 1, 1), 1000 }, // first quadrant
            { (-1, 1), 0100 }, // second quadrant
            { (-1,-1), 0010 }, // third quadrant
            { ( 1,-1), 0001 }, // fourth quadrant
            { ( 0, 0), 0000 }, 
            { ( 0, 1), 1100 }, // first and second
            { ( 0,-1), 0011 }, // third and fourth
            { ( 1, 0), 1001 }, // first and fourth
            { (-1, 0), 0110 }, // second and third
};

int main() {

    std::cout << nodeLoc[(-1, -1)];

    return 0;
}

The main function should print 0010 to the console, but it prints 1000 instead. The map function is identifying (-1, -1) with (1, 1), but I thought that the definition for the bool operator() would prevent these from being identified as the same input. I tried creating a hash function to use with an std::unordered_map, but wound up with a similar problem (albeit a little different since (-1,1) would map the same as (1,-1) instead).

How can I appropriately create a map between signed coordinates and their binary node representation?

Answer 1

A compiler can point out two crucial mistakes in your code:

There are no null references

warning: converting to non-pointer type 'double' from NULL [-Wconversion-null]
    9 |     vec2(const double& x = NULL, const double& y = NULL)
      |                            ^~~~

Firstly, what you're doing is essentially const double& x = 0 in that code. There is no such thing as a null reference in C++, which seems like what you're trying to create. Also not that a const& can bind to a temporary value (temporary materialization), so that the code compiles.

To solve this, either delete the constructor completely, which makes vec2 an aggregate type. Alternatively:

// note: don't use default arguments because they would allow initialization
//       with just one argument, which is undesirable
vec2(double x, double y) : x(x), y(y) {}
vec2() : vec2(0, 0) {}

(1, 1) is a comma expresssion, not a constructor call

The second mistake is using this syntax:

warning: left operand of comma operator has no effect [-Wunused-value]
   30 |             { ( 1, 1), 1000 }, // first quadrant
      |                 ^

(1, 1) is not doing vec2(1, 1), it's using the comma operator, where the left 1 is discarded, and the right 1 is used to call vec2(1). Your original constructor can be called with just one argument, and isn't explicit, so an implicit conversion from 1 to vec2 was possible.

To fix this, use { { 1, 1}, 1000 }, where the inner { 1, 1} is equivalent to vec2(1, 1).

Further notes

• 1000 is a decimal literal; you should provide a binary literal 0b1000 when initializing a std::bitset
• vec2 should not be the function object provided to std::map; you can simply turn operator() into operator< and use std::map<vec2, std::bitset<4>>
  • alternatively, define a three-way comparison operator
• nodeLoc should be declared as const ideally, and instead of nodeLoc[(x, y)] (which also uses the comma operator), write nodeLoc.at({x, y})

---

See live example at Compiler Explorer with all changes implemented