News for hackers. Stuff that matters.

A comment on Linked lists in C, with open source ADT. Parent comment

Re:Linked lists in C, with open source ADT by marshray on Saturday January 19, 2013 @10:28PM (#5085875)
You have a magic allocator for your list nodes that does better than O(1) amortized?
[ Parent | on HN ]
Re:Linked lists in C, with open source ADT by shrughes on Saturday January 19, 2013 @11:11PM (#5085972)
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.
[ Parent | on HN ]
Re:Linked lists in C, with open source ADT by spinlocked on Saturday January 19, 2013 @10:54PM (#5085940)
Do you need magic to create an O(1) allocator for a pool of fixed size objects?
[ Parent | on HN ]
Re:Linked lists in C, with open source ADT by marshray on Saturday January 19, 2013 @11:39PM (#5086026)
Yes, when (as in the general case of std::list) the number of objects is not known in advance.
[ Parent | on HN ]
Re:Linked lists in C, with open source ADT by spinlocked on Sunday January 20, 2013 @12:29AM (#5086102)
true. however, libstdc++ implements __pool_alloc for a reason.
[ Parent | on HN ]