Структура данных "2 массива в одном"

Как реализовать/как нызывается структура данных (контейнер), которая может быстро выполнять следующие операции?

1. итерация по всем элементам 1 контейнера;
2. итерация по всем элементам 2 контейнера;
3. итерации по элементам контейнера из элементов 1, а потом 2 (без проверок на каждой итерации, надо ли переходить в следующий контейнер)
4. вставка (можно в конец)/удаление по указателю; могут быть отложенными, т.е. смысл в том, чтобы они были/их не было на следующей итерации по элементам, необязательно сразу вставлять/удалять.

Идея в том, чтобы хранить 2 массива в 1, чтобы быстро итерироваться как по отдельности, так и по 2 сразу, при этом иметь возможность вставлять и удалять из обоих. Произвольный доступ не нужен.

Как вариант думаю о списке, растущем одновременно влево и вправо для 2 контейнеров, но проблема в том что итерация будет медленной из-за нелокальности данных = кеша.

Если можно, то реализация на C++/Python, но достаточно алгоритма.