Hare Rope
Sona
May 28, 2024
A Rope is a data structure that manages an ordered set of characters. Just like a string!
You can read more about it on its Wikipedia article.)
Some of the key Big-O differences are the following:
| Operation | Rope | String |
|---|---|---|
| Index | O(log n) | O(1) |
| Split | O(log n) | O(1) |
| Concatenate | O(1) amort., O(log n) worst | O(n) |
| Iterate over each character | O(n) | O(n) |
| Insert | O(log n) | O(n) |
| Append | O(1) amort., O(log n) worst | O(1) amort., O(n) worst |
| Delete | O(log n) | O(n) |
| Report | O(j + log n) | O(j) |
| Build | O(n) | O(n) |
Table taken from Comparison with monolithic arrays#Comparison_with_monolithic_arrays)
Discussion in the ATmosphere