0

I am working with an older C (compiling with clang++) codebase that used some global variables to store the heads of linked lists, with many points throughout the code that iterate over those lists.

struct global_st *global_list; // awful global

// ... somewhere down in the code
for (struct global_st *it = global_list; it; it = it->next)
    operation(it);

At some point, some geniuses figured out that operation() could result in the removal of items from the list, especially (but not limited to) current object of iteration. So some loops look more like this:

for (struct global_st *it = global_list, *next_it; it; it = next_it) {
    next_it = it->next;
    operation_that_could_remove_object(it);
}

However, many of the less safe loops use the other method, especially if using a relatively "safe" operation (this codebase suffers from almost complete lack of const). I have located a few bugs with this, which are masked by the use of object pooling for the allocated structs that never have their next pointers cleared.

I have been tasked with changing this linked list to a std::vector or std::list. From this question, which is 7 years old but I assume is still true, I can't check if the iterator is still valid for dereferencing. Assuming that the current object of iteration is the only element that can be removed by an operation in the loop, would this loop be considered safe?

for (auto it = global_list.begin(), next_it; it != global_list.end(); it = next_it) {
    next_it = it;
    next_it++;
    operation_that_could_remove_object(*it);
}

If so, is there a simpler way (or a safer data structure) that would help prevent programmer error? I would like to use the ranged-for semantics, but that doesn't seem possible when the iterator could be removed.

My alternative option would be to utilize the object pool and set an 'is_valid' flag, and then defer removal to a later time. However, I don't particularly want to require every loop to check if the object is still valid.

EDIT: To clarify, the container is filled with unique pointers to objects, and the possible removal (by operation(Obj *obj)) will be by matching the pointer to a member of the container. Since they're unique, are there semantics that could be applied to iteration/potential removal from a std::set that would work?

Rakurai
  • 974
  • 7
  • 15
  • 1
    Use the erase and remove idiom. It makes this stuff safe. – NathanOliver Jun 21 '17 at 14:59
  • @NathanOliver I'm sorry, I don't understand how to apply that to this situation. I don't need to remove elements matching a condition. I have an operation that *could* result in removal of the element from the container, but that removal may be buried in several levels of code. Poor design probably, but that's what I have :) Could you give an example? – Rakurai Jun 21 '17 at 15:16
  • [Here are some examples](https://stackoverflow.com/questions/347441/erasing-elements-from-a-vector). Really though it sounds like you need a design change. – NathanOliver Jun 21 '17 at 15:18
  • @NathanOliver So the solution might be that operation() could return whether or not the element should be removed, rather than removing from the global list? And yes, I think "design change" every time I type "global". – Rakurai Jun 21 '17 at 15:24
  • 1
    _I think "design change" every time I type "global"_ I like that – Baldrickk Jun 21 '17 at 15:28
  • @Rakurai That sounds like an acceptable solution. – NathanOliver Jun 21 '17 at 15:30

0 Answers0