Module rads::order::ofm
[−]
[src]
Order File Maintenance
This structure is similar to a vector supporting fast insertion. In a
traditional vector, insertion/deletion requires O(n) time to shift all the
succeeding elements around. By carefully maintaining constant-sized gaps
between elements, we can speed up insertion/deletion to requiring O(log^2 n)
time.
This could better be accomplished by a linked list. However, this structure is cache-oblivious, meaning it performs an asymptotically optimal number of memory transfers between all cache hierarchy levels. In effect, in order traversal becomes much faster due to fewer cache-misses.
Structs
| Index |
An opaque wrapper |
| Ofm |
Order File Maintenance |
| OfmIter |
Traits
| Indexable |