Comments (6)
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?
from sg14.
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.
from sg14.
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)
.
from sg14.
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
.
from sg14.
Fixed by #133
from sg14.
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?
from sg14.
Related Issues (20)
- [slot_map] constructors HOT 1
- [inplace_function] benchmark HOT 4
- [slot_map] Can you get a key using an iterator? HOT 5
- [slot_map] R1/R2 criticisms HOT 12
- [inplace_function] Ambiguous overloads. HOT 5
- [inplace_function] Should [](){return 42;} be convertible to inplace_function<void()>? HOT 1
- [inplace_function] make it usable without exceptions HOT 2
- inplace_function doesn't handle arguments with rvalue references well HOT 1
- [inplace function] Problems assigning if my starting point is empty/nullptr HOT 4
- [inplace_function] Const-callability means thread-safety HOT 4
- [inplace_function] Giant Sized Buffers Required for Compilation HOT 5
- volatile inplace_function fails to compile HOT 6
- License is missing on some includes HOT 1
- `sg14::ring_span`: clear () member function gone awol HOT 2
- [inplace_function] Opt-in "safe" default constructed inplace_function HOT 7
- Provide CMake & Conan installation support
- slot_map: custom key causing clang to seg fault. HOT 1
- [inplace_function] usage at shared library boundaries HOT 5
- sg14::span_ring: class template argument deduction
- [inplace_function.h] Copyright holder HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from sg14.