Last time I had to do something similar (for TCP reassembly) I simply used a sorted array. I didn't think it though fully, but did you consider using a bit set

Last time I had to do something similar (for TCP reassembly) I simply used a sorted array. I didn't think it though fully, but did you consider using a bit set only storing gap/non-gap transitions and vice versa then compressing it in a rank-select data structure? The even-odd result of a rank query will tell you if you are in a gap or not. It should also be possible to use select to find the closest hole. The problem is that AFAIK rank-select structures cannot be modified, so you will need to regenerate it from scratch at every update. That (or an hybrid scheme) will work only if updates are rare enough.