Boost.Intrusive - Итератор с постоянным временем

Question

Boost.Intrusive может получать Iterator из Object-Ref или Object-Pointer за постоянное время (см. Здесь: https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html). Как это работает? Почему это невозможно для стандартных контейнеров?

Answer 1

Контрастные контейнеры по определению содержат информацию, содержащуюся внутри элементов, чтобы знать, как они расположены в контейнере. Простым примером является навязчивый связанный список:

struct Object {
    Object* next;
    int some_data;
};

Очевидно, что если у меня есть ссылка или указатель на Object, я легко могу найти поле next и оттуда перейти к следующему элемент, это просто доступ к члену, который является O (1), таким образом, итераторы с постоянным временем.

С неинтрузивными контейнерами это будет выглядеть так:

struct Object {
    int some_data;
};

Предположим, я у меня есть std::vector из них и указатель или ссылка на Object, я не могу работать в обратном направлении от того, где он находится в std::vector, не сканируя контейнер, чтобы найти его (операция O (n)) .