Keeping "children" components sorted and accessible through a parent range

[CharlesJQuarra]

I was looking for a way to keep components of children entities in a compact sequential range. I came up with the following, but I am not sure it is reliable, and it doesn't seem to be a supported approach as view iterators do not support random access (++ is supported, but operator+(unsigned int) doesn't seem to)

In any case, the scheme I have is a component of children I care about with a entity reference to the parent:

struct ChildData {
  Data mData;
  entt::entity parent;
};

Parents on the other hand, have the following component to retrieve a children (component) range:

struct ParentInfo {
 std::size_t nb_children;
 std::size_t children_offset;
};

then after adding or removing ChildData components, I rerun a registry.sort call:

registry.sort<ChildData>([&registry](const auto& lhs, const auto& rhs) { return lhs.parent < rhs.parent; });

and then run an update loop on the ParentInfo component:

auto v = registry.view<ChildData>();
entt::entity next_parent = entt::null;
ParentInfo* p = nullptr;
std::size_t next_size = 0;
std::size_t next_offset = 0;
for (auto e : v) {
auto [cd] = v.get(e);
if (next_parent != cd.parent) {
    if (p != nullptr) {
      p->nb_children = next_size;
      next_offset += next_size;
      next_size = 0;
    }
    p = & registry.get<ParentInfo>(cd.parent);
    p->children_offset = next_offset;
    next_parent = cd.parent;
  }
next_size++;
}
if (p != nullptr) {
  p->nb_children = next_size;
}

The good thing of this is that it (almost) allows me to do the following:

auto v = registry.view<ChildData>();
auto& ginfo = registry.get<ParentInfo>(parent);
for (auto it = v.begin() + ginfo.children_offset; it != v.begin() + ginfo.children_offset + ginfo.nb_children; ++it) {
 \\\ iterate over childrens of parent
}

the problem is that v.begin() + unsigned int doesn't seem to compile. Perhaps there is a better way to access the children range in a similar way?

[skypjack]

as view iterators do not support random access

🤔 iterators for single component views do, unless you enabled pointer stability.
If this is the case, they don't because they don't know in advance where the holes are. Therefore, a += would risk to jump on a tombstone or to a misplaced position.

As for your sorting function:

registry.sort<ChildData>([&registry](const auto& lhs, const auto& rhs) { return lhs.parent < rhs.parent; });

It doesn't work probably because it doesn't infer a strict weak ordering. That is, if lhs < rhs is true, rhs < lhs must be false. However, in your case, when both elements have the same parent, the two conditions return true. You can get around it by comparing the entities when the parent is the same. You may also be interested in these posts to find about another approach to the same problem.