I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. Updates would be typically be localized to certain areas.

I could probably make do with mapping a 1d vector onto 2 dimensions, but is there something better?

Background: I would like to implement a kind of cellular automaton where history is preserved to a degree.

  • $\begingroup$ When you say "appending in any direction", what do you mean? Adding a whole row or column? $\endgroup$ – jbapple Mar 29 '15 at 1:18
  • $\begingroup$ Yes, appending or prepending columns and rows. $\endgroup$ – Justin Kaeser Mar 29 '15 at 8:53
  • $\begingroup$ Are these "empty" rows, or do they have data in them already? $\endgroup$ – jbapple Mar 29 '15 at 15:50
  • 1
    $\begingroup$ It would help this question if you did three things: 1. Describe what you already know, like "I can do this in log n time with red-black trees". 2. Describe what you want, like "I want log log n time". 3. Enumerate and describe precisely which operations you're interested in, like cs.stackexchange.com/questions/6455/… $\endgroup$ – jbapple Mar 29 '15 at 15:54

Your Answer


Browse other questions tagged or ask your own question.