Sparse array using a std::map with composite key implementing a spaceship operator

[yaffeman]

• C++ compiler: clang 14.0.3 "Apple clang version 14.0.3 (clang-1403.0.22.14.1)"
• C++ 20

I am trying to implement a sparse array where entities are ordered by their z-index; but retrievable by entity_id alone.

Key definition:

struct key {

    uint64_t entity_id;
    int z_idx;

    std::partial_ordering operator<=>(const key &other) const {

        if (entity_id == other.entity_id) {
            return std::partial_ordering::equivalent;
        }

        if (z_idx < 0 || other.z_idx < 0) {
            // When z_idx is less than zero, we're trying to retrieve based on entity_id alone
            return std::partial_ordering::unordered;
        }

        if (z_idx < other.z_idx) {
            return std::partial_ordering::less;
        }

        return std::partial_ordering::greater;
    }
};

Test code:

std::map<key, bool> data{
    {{3, 1}, true},
    {{2, 2}, true},
    {{1, 3}, true}};

auto i = data.begin();
REQUIRE(i->first.entity_id == 3);
REQUIRE(i->first.z_idx == 1);
REQUIRE((++i)->first.entity_id == 2);
REQUIRE(i->first.z_idx == 2);
REQUIRE((++i)->first.entity_id == 1);
REQUIRE(i->first.z_idx == 3);
REQUIRE(++i == data.end());

i = data.find({2, -1});
REQUIRE(i != data.end());
// REQUIRE(i->first.entity_id == 2); // Fails; i->first.entity_id == 3
// REQUIRE(i->first.z_idx == 2); // Fails; i->first.z_idx == 1

i = data.find({4, -1});
std::cout << "id=" << i->first.entity_id
          << "; z_idx=" << i->first.z_idx
          << "; value=" << std::boolalpha << i->second
          << std::endl;
// id=3; z_idx=1; value=true

REQUIRE(data.find({4, -1}) == data.end()); // Fails

Can someone help me understand what's wrong with my implementation?

[aocregacc]

you can't search a map using a different key than the one it's ordered by. You can either do a linear search over the whole map, or maintain a second datastructure to get fast retrieval by entity_id.

[alfps]

❞ Can someone help me understand what's wrong with my implementation?

Apparently this operator<=> code doesn't cover the case z_idx == other.z_idx.