undefined | Better HN

0 pointsghj5y ago0 comments

You would probably enjoy reading about an alternative implementation for STL's std::deque, called a tier vector[1][2].

It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!!

The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I still wonder why this design lost to the std::deque we have in STL today.

[1] http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-repor...

[2] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

[3] https://news.ycombinator.com/item?id=20872696

0 comments

twotwotwo5y ago

This made me search around about unsorted B-tree-like collections. Turns out Clojure[1] and the im immutable-collections crates in Rust[2] use a structure called an RRB-tree, and searching 'blist' (because why not) turned up a Python module[3]. So, yes, a thing!

Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?

Anyway, just neat that it's been taken further than I realized!

[1] https://infoscience.epfl.ch/record/213452/files/rrbvector.pd...

[2] https://docs.rs/im/15.0.0/im/struct.Vector.html

[3] https://pypi.org/project/blist/

j / k navigate · click thread line to collapse