关于由外部系统删除 O(1) 列表的迭代器使用的架构 C++/STL 问题

Question

这是一个非常简单的架构问题，但它多年来一直困扰着我。

无论如何，对我来说，使用列表的全部意义在于它的插入/删除时间复杂度为 O(1)。 进行 O(1) 删除的唯一方法是使用擦除（）的迭代器。 获取迭代器的唯一方法是从初始 insert() 中保留它或通过迭代找到它。

那么，要传递什么；迭代器还是指针？

看起来，如果快速删除很重要，例如某种经常更改的大型列表，您应该传递迭代器，并且如果您不担心在列表中查找项目的时间，然后传递指针。

这是一个典型的简化示例：

在这个示例中，我们有一些名为 Foo 的类型。 Foo 很可能是一个基类指针，但为了简单起见，它不在这里。

然后我们有 FooManger，它保存了一个shared_ptr、FooPtr 的列表。一旦对象被传递给管理器，管理器就对其生命周期负责。

现在，addFoo() 返回什么？ 如果我返回 FooPtr，那么我永远无法在 O(1) 中将其从列表中删除，因为我必须在列表中找到它。 如果我返回一个 std::list::iterator FooPtrListIterator，那么在任何需要删除 FooPtr 的地方我都可以，只需取消引用迭代器即可。

在这个例子中，我有一个 Foo 的人为示例，它可以在某些情况下自杀，Foo::killWhenConditionMet()。

想象一下某个 Foo 的计时器正在计时至 0，此时它需要要求管理器删除自身。问题在于“this”是一个裸露的 Foo*，因此删除自身的唯一方法是使用原始指针调用 FooManager::eraseFoo()。现在，管理器必须搜索对象指针以获取迭代器，以便可以将其从列表中删除并销毁。

解决这个问题的唯一方法是将迭代器存储在对象中。即 Foo 有一个 FooPtrListIterator 作为成员变量。

struct Foo;

typedef boost::shared_ptr<Foo> FooPtr;
typedef std::list<FooPtr> FooPtrList;
typedef FooPtrList::iterator FooPtrListIterator;

struct FooManager
{
    FooPtrList l;

    FooPtrListIterator addFoo(Foo *foo) {
        return l.insert(l.begin(), FooPtr(foo));
    }
    void eraseFoo(FooPtrListIterator foo) {
        l.erase(foo);
    }
    void eraseFoo(Foo *foo) {
        for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
            if ((*it).get()==foo){
                eraseFoo(it);
                return;
            }
        }
        assert("foo not found!");
    }
};

FooManager g_fm;

struct Foo
{
    int _v;

    Foo(int v):_v(v) {
    }
    ~Foo() {
        printf("~Foo %d\n", _v);
    }
    void print() {
        printf("%d\n", _v);
    }
    void killWhenConditionMet() {
        // Do something that will eventually kill this object, like a timer
        g_fm.eraseFoo(this);
    }
};

void printList(FooPtrList &l)
{
    printf("-\n");
    for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
        (*it)->print();
    }
}   

void test2()
{
    FooPtrListIterator it1=g_fm.addFoo(new Foo(1));
    printList(g_fm.l);
    FooPtrListIterator it2=g_fm.addFoo(new Foo(2));
    printList(g_fm.l);
    FooPtrListIterator it3=g_fm.addFoo(new Foo(3));
    printList(g_fm.l);

    (*it2)->killWhenConditionMet();

    printList(g_fm.l);
}

所以，我的问题是： 1. 如果一个对象需要删除自身，或者让其他系统删除它，在 O(1) 中，我是否必须在对象内部存储一个对象的迭代器？如果是这样，是否存在与迭代器由于其他容器迭代而变得无效有关的问题？

2. 是否有其他方法可以做到这一点？

3. 作为一个附带问题，有谁知道为什么“push*”stl 容器操作不返回结果迭代器，这意味着必须诉诸“insert*”。

拜托，没有答案说“不要预先优化”，这让我发疯。 ;) 这是一个架构问题。

Answer 1

C++ 标准在其 [list.modifiers] 部分中表示，任何列表插入操作“不会影响迭代器和引用的有效性”，并且任何删除操作“仅使迭代器和对已擦除元素的引用无效” ”。因此，保留迭代器是安全的。

将迭代器保留在对象内部似乎也是明智的。特别是如果您不将它们称为迭代器，而是将它们命名为 FooManagerHandlers 之类的名称，它们由删除函数以不透明的方式进行处理。事实上，您不存储“迭代器”，而是将对象的“代表”存储在有组织的结构中。这些代表用于定义该结构内对象的位置。这是一个独立的、相当高级的概念，实现它并没有什么不合逻辑的。

然而，使用列表的目的不仅仅是 O(1) 插入/删除，而且还可以保持元素按顺序排列。如果您不需要任何顺序，那么您可能会发现哈希表更有用。

Answer 2

我在对象中存储迭代器时看到的一个问题是，您必须小心从其他迭代器中删除该对象，因为您的对象析构函数不知道它是从哪里销毁的，因此您最终可能会得到一个无效的迭代器析构函数。

Push* 不返回迭代器的原因是它与 pop* 相反，允许您将容器视为堆栈、队列或双端队列。