[inetknght]

> 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

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 \*/>.

Indexing does come with a wart: you'd need a sentry value for a "no prev" or "no next" value, I'd just use std::numeric_limits<size_t>::max() for that. And of course when you move objects within the container you'd need to update the indices.

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).

[kentonv]

In most (quite possibly all) cases I don't know the upper bound even at runtime. So, this ends up requiring allocation.

[inetknght]

You don't think it's useful to calculate some reasonable upper bound if only to avoid resource exhaustion?

[kentonv]

Not really:

* 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.

[inetknght]

So you don't know how much to allocate and you also don't want to allocate too much.

It sounds like you want something built on top of std::vector but with your own rules about when to reserve() and how much.

[kentonv]

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?

(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.)

[inetknght]

Let me remind you what you said which I quoted:

> 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.