The Gap Buffer

Before committing to vector-of-lines forever, build the classic alternative well enough to respect it. The gap buffer is how Emacs has stored text since the 1970s, and it's founded on one empirical observation: edits cluster. You type a character at position 100, the next lands at 101, then 102. A flat string pays a full memmove for each. The gap buffer prepays one move, then rides the cluster for free.

The idea: store the text in one array with a hole — the gap — at the cursor:

        "the qick fox"  with the cursor after "q", gap size 4:
        the q[____]ick fox
              ^gap_start           text[gap_start..gap_end) is dead space

• Insert at the cursor: write into the gap, gap_start++. O(1).
• Delete before the cursor: gap_start--. O(1). Delete after: gap_end++. O(1). Nothing is moved; the dead zone just swallows the character. (This should remind you of the append buffer trick: reserve space once, then cheap operations amortize against it.)
• Move the cursor to position p: slide the gap there by memmove-ing the characters between the old and new gap position — cost proportional to the distance moved, not the file size. A cursor that moves one line pays ~80 bytes; jumping from top to bottom of a 10 MB file pays 10 MB, once, and then edits are O(1) again.
• Gap exhausted (gap_start == gap_end): reallocate bigger, like std::vector growth — doubling gives amortized O(1) inserts.

The "logical" text is the array minus the gap, so reading position i must skip it:

char at(size_t i) {                     // logical index -> physical
    return i < gap_start ? buf[i] : buf[i + gap_size()];
}

That translation is the gap buffer's tax: every read pays a branch, and substring extraction must be gap-aware. It's also why "vector of lines where each line is a gap buffer" — plausibly the best of both — is rarely worth it: the constant factors eat the win for ordinary line lengths.

Complexity summary, honestly stated: for a buffer of n characters and an edit at distance d from the previous edit — flat string: O(n) per edit, always. Gap buffer: O(d) to seek + amortized O(1) per edit; the pathological case is alternating edits at opposite ends (O(n) each). Vector of lines: O(line length) per edit regardless of distance. Ropes and piece tables: O(log n), for 10× the code. Emacs bets edits cluster (they do), vi bets lines are short (they are). Both bets are 50 years old and still paying out.