CODEWITHSUNDEEP
c++dynamiciteration
Bill Kotsias
Bill Kotsias

Reputation: 3358

Iterating a changing container

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

Upvotes: 9

Views: 558

Answers (3)

Arun
Arun

Reputation: 20383

The operations which mutate the set structure are insert() and erase().

While iterating, consider using the iterator returned by the mutating operations.

it = myset.erase( it );

http://www.cplusplus.com/reference/stl/set/erase/

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

There is a way to do it in two steps: first, go through the original set, and make a set of action items. Then go through the set of action items, and apply them to the original set.

An action item is a base class with subclasses. Each subclass takes in a set, and performs a specific operation on it, for example:

struct set_action {
    virtual void act(std::set<int> mySet) const;
};
class del_action : public set_action {
private:
    int item;
public:
    del_action(int _item) : item(_item) {}
    virtual void act(std::set<int> mySet) const {
        // delete item from set
    }
};
class upd_action : public set_action {
private:
    int from, to;
public:
    upd_action(int _from, int _to) : from(_from), to(_to) {}
    virtual void act(std::set<int> mySet) const {
        // delete [from], insert [to]
    }
};

Now you can create a collection of set_action*s in the first pass, and run them in the second pass.

Upvotes: 3

sehe
sehe

Reputation: 392843

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:

(adding links shortly)

Upvotes: 4

Related Questions