Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
marshray
on Jan 20, 2013
|
parent
|
context
|
favorite
| on:
Linked lists in C, with open source ADT
You have a magic allocator for your list nodes that does better than O(1) amortized?
shrughes
on Jan 20, 2013
|
next
[–]
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.
spinlocked
on Jan 20, 2013
|
prev
[–]
Do you need magic to create an O(1) allocator for a pool of fixed size objects?
marshray
on Jan 20, 2013
|
parent
[–]
Yes, when (as in the general case of std::list) the number of objects is not known in advance.
spinlocked
on Jan 20, 2013
|
root
|
parent
[–]
true. however, libstdc++ implements __pool_alloc for a reason.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
