Теоретически, я бы сказал, что правильная структура данных - это многомерное дерево, предпочтительно что-то вроде дерева B +. Традиционно это дисковая структура данных, но современная основная память имеет много схожих характеристик из-за слоев кеша и виртуальной памяти.
Итерация по порядку дерева B + очень эффективна, потому что (1) вы перебираете только связанный список конечных узлов - узлы ветвления не нужны, и (2) вы получаете чрезвычайно хорошую локальность.
Поиск, удаление и вставка произвольных элементов - это log (n), как и для любого сбалансированного дерева, хотя и с различными постоянными коэффициентами.
Использование дерева - это в основном вопрос выбора алгоритма, который дает хорошую производительность при работе со связанным списком блоков (конечных узлов), сводя к минимуму необходимость использования конечных узлов - варианты быстрой сортировки или слияния кажутся вероятными кандидатами , После сортировки элементов в узлах ветвления просто распространяйте сводную информацию через конечные узлы.
НО - прагматически, это всего лишь то, что вы бы сделали, если уверены, что вам это нужно. Хорошие шансы, что вам лучше использовать какой-нибудь стандартный контейнер. Оптимизация алгоритма / структуры данных - лучший вид оптимизации, но он все еще может быть преждевременным.