Boost.Intrusive-恒定时间迭代器

Question

Boost.Intrusive可以在恒定时间内从Object-Ref或Object-Pointer中获得一个迭代器（请参见此处：https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html）。这是如何运作的？为什么这对于标准容器是不可能的？

Answer 1

根据定义，侵入式容器具有元素的[[inside中包含的信息”，以了解它们在容器中的位置。一个简单的示例是侵入式链接列表：

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

[显然，如果我有对Object的引用或指针，我可以轻松找到next字段，然后从那里移到下一个元素，这只是访问一个成员，即O（1），因此是恒定时间的迭代器。
对于非侵入式容器，看起来像这样：
struct Object {
    int some_data;
};

假设我有一个std::vector，并且有一个指向Object的指针或引用，我无法从该索引向后工作到std::vector中的位置，而无需扫描容器来找到它（O（ n）操作）。