std::forward_list -- erasing with a stored iterator

Question

I'm trying to keep a global list of a particular (base) class's instances so that I can track them down by iterating through this global list at any time.

I believe the most proper way to address this is with an intrusive list. I have heard that one can encounter these creatures by digging into the Linux kernel, for example.

In the situation where I'm in, I don't really need such guarantees of performance, and using intrusive lists will complicate matters somewhat for me.

Here's what I've got so far to implement this concept of a class that knows about all of its instances.

class A {
    static std::forward_list<A*> globallist;
    std::forward_list<A*>::iterator listhandle;
public:
    A() {
        globallist.push_front(this);
        listhandle = globallist.begin();
    }
    virtual ~A() {
        globallist.erase_after(...);  // problem
    }
};

The problem is that there is no forward_list::erase(), and it really does not appear like saving globallist.before_begin() in the ctor would do me much good. I'm never supposed to dereference before_begin()'s iterator. Will it actually hold on to the position? If I save out before_begin's iterator, and then push_front() a new item, that iterator is probably still not capable of being dereferenced, but will it be serviceable for sending to erase_after()?

score 4 · Accepted Answer · answered Sep 20 '13 at 04:15

4

forward_list is a singly linked list. To remove a node in the middle of that, you must have a pointer to previous node, somehow. For example, you could do something like this:

class A {
    static std::forward_list<A*> globallist;
    std::forward_list<A*>::iterator prev_node;
public:
    A() {
        A* old_head = globallist.front();
        globallist.push_front(this);
        prev_node = globallist.before_begin();
        old_head->prev_node = globallist.begin();
    }
};

The case of pushing the first element into an empty list, as well as the removal logic, are left as an exercise for the reader (when removing, copy your prev_node to the next node's prev_node).

Or, just use std::list and avoid all this trouble.

answered Sep 20 '13 at 04:15

Igor Tandetnik

50,461
4
56
85

I was hoping all of these gymnastics wouldn't be necessary. Wouldn't the assignment of the removed node's prev to the next node's prev be performed by the `erase_after()`? – Steven Lu Sep 20 '13 at 04:22
How would `erase_after` know what's inside your class? All it knows is it's holding some pointer. Use `std::list`, and those gymnastics *will* in fact become unnecessary. – Igor Tandetnik Sep 20 '13 at 04:25
my class isn't meant to hold the previous node. It's meant to hold the place in the list (so a removal can be O(1)). I just want to call an `erase()` to erase the about-to-be defunct pointer at that location (which points to myself, who is in the process of destructing). At any rate, thanks, I am definitely going to make it a `std::list`. – Steven Lu Sep 20 '13 at 04:26
Read about a singly linked list in your favorite data structures textbook. That's not how it works. – Igor Tandetnik Sep 20 '13 at 04:27
Oh I think I see the problem. The previous node must be known for a proper removal from the singly linked list... but since the singly linked list doesnt track that or even know about it, the management thereof is left up to me. All i'd save by doing this is the space taken up by N-1 pointers. – Steven Lu Sep 20 '13 at 04:29
Yes. `A::prev_node` effectively turns this singly-linked list into a "semi-intrusive" doubly-linked one. `forward_list` manages forward pointers, and you end up with an unenviable task of managing back pointers. – Igor Tandetnik Sep 20 '13 at 04:35

std::forward_list -- erasing with a stored iterator

1 Answers1