package varray

  1. Overview
  2. Docs
Resizable arrays with fast insertion/deletion

Install

Authors

Maintainers

Sources

varray-0.1.tbz
sha256=69a22c87d9eb4cd27ddd74b24d9fd6fe4e3ec28781012f6eb99203a9fb78e167
sha512=c5c2292a1eff693d8f10a7b398b1924b17ab3d7b84788f94e689460106df5f41f7bba3e0e30b51f9faaba88db7b502448f4850c344a4765bfd2e37da7fe7f460

Description

  • O(1) constant time for random access arr.(i) and updates arr.(i) <- v
  • O(1) amortized for push_front and pop_front, push_back and pop_back to add or remove an element to the start or the end
  • O(sqrt N) for insert_at arr i x and delete_at arr i to insert or delete an element anywhere else

This datastructure was invented by Goodrich and Kloss and is described in their paper "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences".

Published: 10 Apr 2022

Dependencies (2)

  1. ocaml >= "4.08"
  2. dune >= "2.8"

Dev Dependencies (2)

  1. odoc with-doc
  2. monolith with-test

Used by

None

Conflicts

None