I would default to just using std::unique_ptr<Node> in a situation like this, especially since using std::list suggests performance isn't critical here, so the additional indirection probably doesn't matter.
In fact, full-on garbage collection wouldn't have prevented the bug here, and could arguably have made it worse. The problem is that nodes were unexpectedly being copied and then the originals deleted. With GC, you'd still have the copy, but never delete the originals, so you end up with split brain where there are multiple copies of each node and various pointers point to the wrong ones. That'd be pretty painful to debug!
IMO the language-level problem, if there is one, is that C++ is too willing to copy in cases where you would expect it to move instead. This is, of course, for backwards compatibility with the before-times when there was no move and copying was the only logical thing to do. But I think life would be better these days if all non-trivial copies had to be requested explicitly.
std::shared_ptr comes with std::weak_ptr. Referencing counting is rather ham-fisted approach but is certainly a solution.
> IMO the language-level problem, if there is one, is that C++ is too willing to copy in cases where you would expect it to move instead.
IMO that's not a problem in the language but a problem with the engineer (misunderstanding when std::move is necessary) and the tooling (linter/static analyzer not clearly identifying that something should be moved instead, and raising a linter warning for it).
For that matter, the places where I see std::list used aren't places where "performance isn't important" but rather places where an inexperienced engineer was put in charge of implementation and a senior engineer accepted it. I can't remember the last time I accepted someone using std::list in a code review because there has always been a better design available even if it necessitated some teaching. If a stable pointer address is needed then indeed a smart pointer is the correct solution (perhaps std::vector<std::unique_ptr>). There are other reasons I've had coworkers cite for using std::list (eg constant allocation time) but that's generally resolved with std::vector.reserve(upper bound to size) or eg a slab allocator (unfortunately, I'm not aware of a standard-provided slab allocator, though to be fair I'm not very familiar with C++ standard allocators in general).
> I think life would be better these days if all non-trivial copies had to be requested explicitly
While I don't agree superficially (smells like bringing along deep-copy problems), I think the idea merits some thought experiments.
It would be fairly trivial to do that for non-plain-old-data types by deleting the copy constructor/operator (so it cannot happen implicitly) and providing a `make_copy(...)` function instead.
No it isn't.
std::array<std::optional<std::pair<T, std::pair<std::size_t /* prev index */, std::size_t /* next index */>>>, 256U /* or whatever your maximum size is \*/>.
If you don't know your upper size bound at compile time, then replace `array` with `vector`, and reserve your runtime-known upper bound. As long as you never violate your upper bound then no (re-)allocations occur (unless T's constructor allocates).
* In my experience arbitrary limits intended to prevent "resource exhaustion" tend to lead to incidents where the limit was hit but resources weren't really exhausted, so it just caused failures for no reason. Very common example is the ulimit on open file descriptors. The default limits feel like they were set last century and haven't been updated to account for the fact that we have way more memory these days. We should really just be enforcing an overall limit on memory usage (per-user or per-cgroup) and expect that to include the file descriptor table.
* If I did choose a limit, it would be quite high (to avoid aforementioned unnecessary incidents), but in practice most of the lists I'm thinking of would never get near that size, so pre-allocating arrays would waste a lot of memory.
It sounds like you want something built on top of std::vector but with your own rules about when to reserve() and how much.
(Example use case: Some number of objects want to register themselves as observers on some event, and unregister themselves later, in arbitrary order. The same object may register and unregister itself many times. std::unordered_set<Observer*> would be the best fit if performance doesn't matter but an intrusive linked list requires no allocation at all on behalf of the list.)
> I want to be able to dynamically add and remove objects from the list without any allocations at all. The only way to achieve that is an intrusive linked list design
So with that, let me reply to your most recent comment:
> No, for the use cases I'm thinking of, I really do just want an intrusive linked list. Why would I want to invent a convoluted way to adapt std::vector when an intrusive linked list does exactly what I want?
You said an intrusive linked list is the only way to achieve that design. I'm telling you it's not the only way to implement a zero-allocation linked list.
If an intrusive linked list is exactly what you want then great for you. You haven't clearly articulated exactly why you must have an intrusive linked list. I've given you an alternative. You're rejecting it out-of-hand because you don't want to "invent a convoluted way to adapt" already-existing containers.
> Why would I want to invent a convoluted way...
You only think it's convoluted. I argue that it's not convoluted at all.
There are many reasons you would not always be able to use an intrusive linked list. Intrusive linked lists are... intrusive. They require that you:
- directly modify T (again, might not be possible if you don't own the code for T, eg it comes from a third party library)
- or have T as a member (which also might not be possible, particularly whether T must be created by a factory and how convoluted that factory is)
- or else have capability to inherit from T (which might not be possible, see `final` keyword).
You haven't stated any of these (or any other) reasons. You simply stated that an intrusive linked list is the "only" way to achieve zero-allocation linked lists. Without stating why you must have an intrusive list, I have merely offered another option. If you think using the standard library is convoluted here then I wonder what other data structure concepts you will have trouble understanding and suggest that C++ isn't the right language for you.
... and yet, almost all vulnerabilities in C++ code are still written in C style, not even legacy C++.
[0] https://github.com/capnproto/capnproto/blob/v2/kjdoc/tour.md
We did use some C++ standard library but very sparingly. For example, std::unique_ptr<> was fine, but std::shared_ptr<> was not because of the way it implicitly stores it's reference, so we had our own implementation that exposed the reference.
When I was doing console games this was a must. You would often have restrictions where the container itself should live in a different area of memory to the items which is much easier to manage with your own classes.
Aside, it's embarrassing that all these alternative libraries fail to implement automatic correct signed/unsigned mixing. It's not like it's particularly hard to implement!
They just got tripped up by an obscure language feature that made the Nodes move anyway.