Architectural C++/STL question about iterator usage for O(1) list removal by external systems.

Question

This is a pretty straightforward architectural question, however it's been niggling at me for ages.

The whole point of using a list, for me anyway, is that it's O(1) insert/remove. The only way to have an O(1) removal is to have an iterator for erase(). The only way to get an iterator is to keep hold of it from the initial insert() or to find it by iteration.

So, what to pass around; an Iterator or a pointer?

It would seem that if it's important to have fast removal, such as some sort of large list which is changing very frequently, you should pass around an iterator, and if you're not worried about the time to find the item in the list, then pass around the pointer.

Here is a typical cut-down example:

In this example we have some type called Foo. Foo is likely to be a base class pointer, but it's not here for simplicity.

Then we have FooManger, which holds a list of shared_ptr, FooPtr . The manager is responsible for the lifetime of the object once it's been passed to it.

Now, what to return from addFoo()? If I return a FooPtr then I can never remove it from the list in O(1), because I will have to find it in the list. If I return a std::list::iterator, FooPtrListIterator, then anywhere I need to remove the FooPtr I can, just by dereferencing the iterator.

In this example I have a contrived example of a Foo which can kill itself under some circumstance, Foo::killWhenConditionMet().

Imagine some Foo that has a timer which is ticking down to 0, at which point it needs to ask the manager to delete itself. The trouble is that 'this' is a naked Foo*, so the only way to delete itself, is to call FooManager::eraseFoo() with a raw pointer. Now the manager has to search for the object pointer to get an iterator so it can be erased from the list, and destroyed.

The only way around that is to store the iterator in the object. i.e Foo has a FooPtrListIterator as a member variable.

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);
}

So, the questions I have are: 1. If an object needs to delete itself, or have some other system delete it, in O(1), do I have to store an iterator to object, inside the object? If so, are there any gotchas to do with iterators becoming invalid due other container iterations?

1. Is there simply another way to do this?

2. As a side question, does anyone know why and of the 'push*' stl container operations don't return the resultant iterator, meaning one has to resort to 'insert*'.

Please, no answers that say "don't pre-optimise", it drives me nuts. ;) This is an architectural question.

Answer 1

C++ standard in its [list.modifiers] section says that any list insertion operation "does not affect the validity of iterators and references", and any removal operation "invalidates only the iterators and references to the erased elements". So keeping iterators around would be safe.

Keeping iterators inside the objects also seems sane. Especially if you don't call them iterators, but rather name like FooManagerHandlers, which are processed by removal function in an opaque way. Indeed, you do not store "iterators", you store "representatives" of objects in an organized structure. These representatives are used to define a position of an object inside that structure. This is a separate, quite a high-level concept, and there's nothing illogical in implementing it.

However, the point of using lists is not just O(1) insert/remove, but also keeping elements in an order. If you don't need any order, then you would probably find hash tables more useful.

Answer 2

The one problem I see with storing the iterator in the object is that you must be careful of deleting the object from some other iterator, as your objects destructor does not know where it was destroyed from, so you can end up with an invalid iterator in the destructor.

The reason that push* does not return an iterator is that it is the inverse of pop*, allowing you to treat your container as a stack, queue, or deque.