Структура данных для z-index

Вам нужен лишь список z-индексов (тогда базируйтесь на std::set), или z-index для группы объектов (тогда например std::map<double, VisualObject*>)?

Смотрите. Если у вас есть std::set<double>, то все операции выполняются просто.

1. Уникальность — свойство std::set.
2. Сравнимость: элементы типа double сравниваются «из коробки».
3. Добавление индекса после данного:
   • убеждаетесь, что элемент есть во множестве;
   • получаете следующий (upper_bound);
   • подсчитываете среднее арифметическое этих элементов и вставляете во множество
4. добавление элемента меньше минимального: получаете минимальный (begin, т. к. множество отсортировано), вставляете среднее арифметическое минимального и DOUBLE_MIN. То же для максимального.
5. Удаление из коробки.

Единственный «скользкий» случай — если при вычислении среднего арифметического в пункте 3 оно окажется равным одному из чисел. Такое может быть, если вы вставляете очень много элементов. В этом случае придётся перенумеровать все индексы: подсчитать количество элементов, и в i-ый по порядку элемент записать число i.