Re:Static search trees: 40x faster than binary search
by amelius on Wednesday January 01, 2025 @06:25PM
(#42570163)
Using a Vec for doubly linked lists sounds like overkill. There's got to be more efficient and more elegant way.
Re:Static search trees: 40x faster than binary search
by unrealhoang on Wednesday January 01, 2025 @07:08PM
(#42570384)
Yes, there is, just use plain old pointers. Who cares about UB anyway.
Those are fairly straightforward to implement if you are ok using a reference counted type (along with weak references), although that will hurt performance. That would be similar to using a shared_pointer in c++.
And you can implement code similar to what you would in c or c++ if you use raw pointers and unsafe code.
Where you run into difficulties is if you want something that is fast and safe. And then you need a more complicated design that probably involves using indices into a Vec instead of pointers.