Iterating a changing container

Question

I am iterating over a set of callback functions. Functions are called during iteration and may lead to drastic changes to the actual container of the functions set.

What I am doing now is:

1. make a copy of original set
2. iterate over copy, but for every element check whether it still exists in the original set

Checking for every element's existence is super-dynamic, but seems quite slow too.

Are there other propositions to tackle this case?

Edit : here is the actual code :

    // => i = event id
    template <class Param>
    void dispatchEvent(int i, Param param) {

        EventReceiverSet processingNow;

        const EventReceiverSet& eventReceiverSet = eventReceiverSets[i];
        std::copy(eventReceiverSet.begin(), eventReceiverSet.end(), std::inserter(processingNow, processingNow.begin()));

        while (!processingNow.empty()) {
            EventReceiverSet::iterator it = processingNow.begin();
            IFunction<>* function = it->getIFunction(); /// get function before removing iterator
            processingNow.erase(it);

            // is EventReceiver still valid? (may have been removed from original set)
            if (eventReceiverSet.find(ERWrapper(function)) == eventReceiverSet.end()) continue; // not found

            function->call(param);
        }
    };

Answer 1

Two basic approaches come to mind:

1. use a task based approach (with the collection locked, push tasks onto a queue for each element, then release all parties to do work and wait till completion). You'll still need a check to see whether the element for the current task is still present/current in the collection when the task is actually starting.

   • this could leverage reader-writer locks for the checks, which is usually speedier than fullblown mutual exclusions (especially with more readers than writers)
     
     

2. use a concurrent data structure (I mean, one that is suitable for multithreaded access without explicit locking). The following libraries contain implementations of concurrent data structures:

   • Intel Thread Building Blocks
   • MS ConCrt concurrent_vector
   • libcds Concurrent Data Structures

(adding links shortly)