Читая ссылку boost :: multi_index, я обнаружил, что iterator_to
Метод имеет постоянный порядок. Как это возможно? Я имею в виду, что если итератор является объектом, отличным от представляемого им значения, то как контейнер может найти свой соответствующий внутренний узел без поиска по индексу?
Единственное решение, о котором я могу подумать, это то, что адрес «внутреннего узла» контейнера (или чего бы то ни было) такой же, как и у value_type, который он содержит (например, помещая заголовок узла чуть ниже value_type или что-то в этом роде). Если переданный аргумент является ссылкой на целочисленный тип value_type, соответствующий итератор можно легко построить по адресу аргумента, чтобы получить красно-черный узел.
Но!! Как насчет стандартного ограничения C ++, что не может быть двух объектов с одинаковым адресом? Как насчет выравнивания, заполнения, заполнения или любых других вещей, которые могут произойти на уровне памяти?
Ваша интуиция верна: значение является частью большей структуры узла (как объяснено, например, Вот) а также iterator_to
просто вычисляет адрес узла из адреса value_type
субобъект. Теперь используемая арифметика указателей основана на том факте, что узел (или базовый класс, в котором хранится значение) стандартный макет, который гарантирует, что указатель на первый подобъект (значение) может быть приведен к указателю на структуру (узел): соответствующий код можно посмотреть Вот.
Других решений пока нет …