Hacker News Reader

You have a magic allocator for your list nodes that does better than O(1) amortized?

Being better than O(n) worst case is the target here, not O(1) amortized. For example, O(1) amortized and O(log n) worst case is a thing.

Do you need magic to create an O(1) allocator for a pool of fixed size objects?

Yes, when (as in the general case of std::list) the number of objects is not known in advance.

true. however, libstdc++ implements __pool_alloc for a reason.