You don't have to copy everything.

Look up persistent data structures [0]

The main trick is to store everything in a tree with a large branching factor.

The elements are on your leaves. When you want to make an edit you need to create only the nodes from the root to the actual leaf. Then you return the new root. Everything else you can share.

This is a log operation, normally implemented with branch 32.

It works with vectors as well as dicts. Creating a copy is constant, it's immutable can be shared freely (especially on GC'd languages).

Insert/Delete are O(log32(n)) instead of O(n) they'd be with a full copy.

[0] https://en.wikipedia.org/wiki/Persistent_data_structure#Pers...