Cache-friendly массив списков

Есть много массивов/векторов, по которым можно быстро итерироваться, т.к. данные расположены близко друг к другу, что способствует кешированию.

Как называется/сделать структуру данных, которая помимо итерации по отдельным логическим массивам может быстро проитерироваться по нескольким сразу? То есть можно быстро проитерироваться по логическому объединению первого и второго массива, с третьего по пятый, всем массивам подряд и т.п..

Если бы все массивы были неизменны, то можно было бы просто расположить их друг за другом последовательно в одном массиве. Но они могут меняться и быть разной длины. Как тогда реализовать это оптимально?

Необходимые операции:

1. O(1) в среднем вставка в непроизвольное место произвольного массива (например, вставить в конец 3 массива)
2. аналогичное удаление (например, удалить первый/последний элемент 2 массива)
3. O(n) cache-friendly итерация по любому массиву длины n
4. O(m) cache-friendly итерация по произвольному последовательному набору массивов, где m = n_i + n_i+1 + ... + n_j = сумма размеров этих массивов от i-ого до j-ого.

Вставка/удаление может быть отложенным, т.е. элемент должен/не должен учитываться в 3/4 операции, но на момент вставки/удаления может реально не быть добавленным/удалённым из массивов.

Константный доступ к произвольному элементу произвольного массива не нужен.