How to guard data structure consistency when calling external logic via observers?

Question

I am currently refactoring an application in which classes can call observers if their state changes. This means that observers are called whenever:

• the data in an instance the class changes
• new instances of the class are created
• instances of the class are deleted

It is this last case that makes me worry.

Suppose that my class is Book. The observers are stored in a class called BookManager (the BookManager also keeps a list of all Books). This means we have this:

class Book
   {
   ...
   };

class BookManager
   {
   private:
      std::list<Book *> m_books;
      std::list<IObserver *> m_observers;
   };

If a book is deleted (removed from the list and deleted from memory), the observers are called:

void BookManager::removeBook (Book *book)
   {
   m_books.remove(book);
   for (auto it=m_observers.cbegin();it!=m_observers.cend();++it) (*it)->onRemove(book *);
   delete book;
   }

The problem is that I have no control over the logic in the observers. The observers can be delivered by a plugin, by code that is written by developers at the customer.

So, although I can write code like this (and I make sure of getting the next in the list in case the instance is deleted):

auto itNext;
for (auto it=m_books.begin();it!=m_books.end();it=itNext)
  {
  itNext = it:
  ++itNext;
  Book *book = *it;
  if (book->getAuthor()==string("Tolkien"))
     {
     removeBook(book);
     }
  }

There is always the possibility of an observer removing other books from the list as well:

void MyObserver::onRemove (Book *book)
   {
   if (book->getAuthor()==string("Tolkien"))
      {
      removeAllBooksFromAuthor("Carl Sagan");
      }
   }

In this case, if the list contains a book of Tolkien, followed by a book of Carl Sagan, the loop that deletes all books of Tolkien will probably crash since the next iterator (itNext) has become invalid.

The illustrated problem can also appear in other situations but the delete-problem is the most severe, since it can easily crash the application.

I could solve the problem by making sure that in the application I first get all instances that I want to delete, put them in a second container, then loop over the second container and delete the instances, but since there is always the risk that an observer explicitly deletes other instances that were already on my to-be-deleted list, I have to put explicit observers to keep this second copy up to date as well.

Also requiring all application code to make copies of lists whenever they want to iterate over a container while calling observers (directly or indirectly) makes writing application code much harder.

Are there [design] patterns that can be used to solve this kind of problem? Preferably no shared-pointer approach since I cannot guarantee that the whole application uses shared-pointers to access the instances.

Answer 1

The basic problem here is that the Book collection gets modified (without knowledge by the application) while the application is iterating over that same collection.

Two ways to deal with that are:

1. Introduce a locking mechanism on the collection. The application takes a lock on the collection and as long as that lock exists, no actions that modify the collection (add/remove books) are allowed. If an observer needs to perform a modification during that time, they will have to remember it and perform the modification when they are notified of the lock's release.
2. Use your own iterator class, which can deal with the collection changing underneath it. For example, by using the Observer pattern to inform all iterators that an element is about to be deleted. If that would invalidate the iterator, it could advance itself internally to remain valid.

---

If the delete-loop is part of BookManager, then it could be restructured like this:

• Loop over the collection and move all elements that should be deleted to a separate, local, 'deleted' collection. At this stage, only inform the iterators (if you implemented option 2 above) about the changes to the collection.
• Loop over the 'deleted' collection and inform the observers about each deletion. If an observer tries to delete further elements, that is no problem as long as deleting non-existing items is not a fatal error.
• Perform memory cleanup on the elements in the 'deleted' collection.

Something similar could be done for other multi-element modifications in BookManager.