c++ - 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

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

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

显然，如果我有对 Object的引用或指针，我可以轻松找到 next字段，然后从那里移到下一个元素，这只是访问一个成员，即O(1)，因此是恒定时间迭代器。

使用非侵入式容器时，将如下所示:

struct Object {
    int some_data;
};

假设我有一个 std::vector，以及一个指向 Object的指针或引用，那么我不能不通过扫描容器来查找它而将其倒退到 std::vector中的位置(O(n)操作)。