[slot_map] partition and underlying_swap

[p-groarke]

When using slot_map for components and such, one would usually implement a disable feature. This is done using a pivot, and swapping disabled elements to the end of your contiguous container. Iterating the "enabled" data will thus be contiguous.

I don't think the standard would ever accept a container with this kind of state. So a way to enable this should be provided. From my uses so far, I think a simple id_swap(Key old, Key new) would enable a lot of needed flexibility.

For disabling components, one could create 2 slot_maps, enabled and disabled, and move objects between the 2. The only problem then is users will have copies of the original id. Adding id_swap lets you move into a disabled slot_map, swap the id to the old one, never invalidating user owned ids.

There are other uses for id_swap. When using RAII to keep user ids valid, the copy constructor would need such a thing.

Ultimately, you want to keep iterators valid when moving/swapping/deleting objects. id_swap is just an idea, there may be better ways.

[Quuxplusone]

I think the constructor thing should be a separate GitHub issue from the id_swap thing.

I doubt I understand your id_swap use-case, but superficially it sounds an awful lot like the std::remove_if and std::partition algorithms which can be used with containers such as vector. They could be used with slot_map too, if we just add a bit of code to maintain the slot/reversemap indices... so, I've done that (see #133). Would your use-case be adequately addressed by this partition member function, or have I misunderstood some aspect of your use-case?

[p-groarke]

If I read the partition description correctly, that is the perfect tool for the job. I still believe id_swap is essential for RAII, I will come up with a code example shortly.

If you are interested, let me try to clarify expected partition behavior in a game engine using a slot_map-like container. Take for example a class Baddie, which is AI enemies. All the baddies are is stored in a slot_map. Every frame you call functions (update, late_update, physics, pre_render, render, post_render, etc) on all the baddies. If the slot_map is interspersed with disabled baddies, you are getting cache-misses everytime you "jump over" a disabled baddie. So one would partition the slot_map first, then call whichever function on only enabled things.

If you are interested in more game engine oriented details, you can read the bitsquid blog series on his entity component system http://bitsquid.blogspot.com/2014/08/building-data-oriented-entity-system.html. From what I read in the slot_map paper, it seems the container was in part inspired by those posts.

[Quuxplusone]

I think you're probably right that id_swap is needed (although I don't like the name... key_swap? except we're not swapping keys, we're swapping underlying positions but not keys or values...). If you have an already-partitioned slot_map with the "live" baddies at the front, and then one of those baddies "dies," you'll want to id_swap the newly dead baddie with the last "live" baddie and then decrement your "last live baddie" iterator. You don't want to call slot_map.partition() on the entire range again; that would be very inefficient. So you do want something like id_swap.

slot_map<Key, Baddie> sm = ...;
auto first_dead_baddie = sm.partition(is_alive);

void inefficient_kill_baddie(Key deceased) {
    sm.find(deceased)->living = false;
    first_dead_baddie = sm.partition(is_alive);
}

void efficient_kill_baddie(Key deceased) {
    auto it = sm.find(deceased);
    it->living = false;
    sm.underlying_swap(it, --first_dead_baddie);
}

I think that's a correct implementation of efficient_kill_baddie. Also underlying_swap (whose name I still don't like) might need two overloads — one for (const Key&, const Key&) and one for (const_iterator, const_iterator).

[p-groarke]

I have no attachment to naming. I'm fine with underlying_swap or any other name you prefer. I'll offer some name ideas further down.

Initially, I really did think swapping ids was essential. That's why id_swap made sense. For example, having 2 objects with 2 ids, and changing the ids so id1 points to obj2 and id2 points to obj1. I can't rule that out as a desired behavior. I'll open a different issue if I ever have a compelling use case (that would be id_swap or key_swap). Lets put that aside. I'm renaming the issue to clarify.

Concerning partition in a game engine, I would never recommend you partition the whole vector every baddie death ;) One usually accumulates what is dead until the end of a frame. Only then do you partition your container. Some engines partition every "event" call. So before calling update on all baddies, one would partition first. However, I did write an engine at some point that swapped on death like your example. So both behaviors are essential IMHO.

To recap :
partition fixes the ubiquitous game engine scenario of enabling/disabling elements and sorting them.
underlying_swap is absolutely crucial in this type of container.

underlying_swap name brainstorm : value_swap, position_swap, storage_swap, element_swap, location_swap.

[p-groarke]

Fixed by #133

[Quuxplusone]

Well, I haven't merged #133 yet, so I'm reopening this. But yeah, I have no particular reason to mistrust #133, except for the naming issue.

@Masstronaut, are you still interested in slot_map's direction, and do you have any opinion on #133's functionality, naming, etc etc?