间接地在迭代std::vector时删除元素

Question

这个问题已经被多次提出，但我的情况略有不同。假设我有一个观察者的std::vector，当发生某个事件时，我会通知它们：

void SomeClass::doThing() {
    // do things ...
    // notify observers
    for (auto* o : mObservers) {
        o->thingHappened();
    }
}

如果在实现thingHappened时，观察者调用SomeClass中的一个方法来将自己从观察者列表中移除怎么办？有哪些最好的处理方式？

一种可能性是在for循环之前对mObservers进行复制并使用复制品，但额外的复制可能会浪费资源。

另一种可能性是将数组的更改委托给在循环结束后运行，或者在循环开始时设置锁（只是一个布尔值），当锁被设置为true时，更改向量的方法委托自身在循环完成后被调用，当锁被设置为false时（可以使用lambda向量来完成……相当繁琐）。

- xissburg

---

你已经描述了我能想到的处理这种情况的唯一两种方式。你希望还有第三种方法吗？ - Mark Ransom

@xissburg 那是相对便宜的复印件，所以制作一份复印件没有问题。 - Xirema

我们需要多少观察者？如果不是很多的话，您可以使用std::list来轻松解决这个问题。 - NathanOliver

@MarkRansom 你不能直接获取，但可以先获取下一个迭代器。我正在撰写答案。 - NathanOliver

我在这里支持@Rakete1111的观点：复制的性能成本应该是可以忽略不计的，无论是速度还是内存使用方面。复制n个元素的向量很可能比对n个元素调用函数要快得多。测量复制所需的时间：如果实际上可以忽略不计，那么选择更简单、更清晰的代码：复制向量并忘记“被调用的函数可能会使我正在使用的迭代器失效”的问题。比起所有其他建议的方法，这种方法更容易编写（和维护）。 - Gian Paolo

Answer 1

如果您可以控制thingHappened()的签名，那么你可以将其更改为返回一个bool，表示是否应该删除它。然后，您可以删除所有返回true（或false；取决于您想要的语义）的值。

幸运的是，std::remove_if和std::partition保证会针对范围内的每个对象仅调用一次谓词。

void SomeClass::doThing() {
    // do things ...
    // notify observers
    auto newEnd = std::remove_if(mObservers.begin(), mObservers.end(), [](auto *o) {
        return o->thingHappened();
    });
    // assuming mObservers is a vector
    mObservers.erase(newEnd, mObservers.end());
}

- Justin

---

我觉得我应该修改这个问题的标题。它不仅仅是关于删除，而是关于对向量进行任何变异的问题。可能会有多个变异。 - xissburg

@xissburg 那将是一个单独的问题。 - Justin

Answer 2

解决这个问题的一种方法是改变数据结构。使用 std::list，删除一个元素只会使该元素的迭代器/引用/指针失效。由于列表的其余部分保持不变，我们只需要在处理当前元素之前获取下一个元素的迭代器即可。代码如下：

for (auto it = the_list.begin(); it != the_list.end();)
{
    auto next = std::next(it);
    it->call_the_possibly_removing_function();
    it = next;
}

- NathanOliver

---

很好。现在唯一可能失败的方式是，如果从列表中删除了一个无关的观察者，并且该观察者恰好是next指向的观察者。 - Mark Ransom

@Xirema 这种情况可能发生在非多线程代码中：如果一个观察者有另一个观察者的引用，它可以调用成员函数来移除另一个观察者。 - Justin

@Xirema Justin是正确的。我曾经处理过类似的代码，让它正常工作真的很麻烦。希望这不是一个普遍存在的情况。 - Mark Ransom

Answer 3

如果在thingHappened的实现中，观察者调用SomeClass中的一个方法将自己从观察者中移除，如何处理这种情况？以下方法过去对我有效：

1.注意要遍历观察者。

2.当客户端请求删除一个观察者时，请检查是否正在遍历观察者。如果是，则将其放在另一个向量中。如果不是，则将其从观察者中移除。

3.完成对观察者的遍历后，删除所有需要删除的观察者。

4.注意已经完成对观察者的遍历。

void SomeClass::removeObserver(Observer* o) {
   if ( this->isIterating  )
   {
      observersToRemove.push_back(o);
   }
   else
   {
      // Code for real removal of the observer
   }
}

void SomeClass::doThing() {
   this->isIterating = true;
   for (auto* o : mObservers) {
      o->thingHappened();
   }

   for ( auto* o : observersToRemove )
   {
      // Code for real removal of the observer
   }

   observersToRemove.clear();

   this->isIterating = false;
}

- R Sahu

---

我对这种方法的主要问题是，存在许多额外的变量，但额外的灵活性可能使其更有价值。可能可以将其中大部分封装在一个对象内，以便更轻松地跟踪发生了什么。 - Justin

@Justin，正如你从三个不同的答案中可以看到，解决这个问题有多种方法。选择你感觉最舒适的方式来解决。 - R Sahu

@Justin，是的，这会让其他函数变得有些复杂，但你拥有正确实现 isObserving 的所有必要数据。你需要先检查输入是否在 mObservers 中。如果在那里，你需要检查它是否在 observersToRemove 中。 - R Sahu

@xissburg，您可以简化这种方法。不要基于标志执行两个不同的操作，而是将您想要删除的观察者始终添加到第二个列表中。然后在您的for循环之前，删除该列表中的所有观察者并清空该列表即可。 - Mark Ransom

@RSahu 我假设 mObservers 的内容只在 for 循环中有关，延迟删除不会造成任何损害。我知道这是一个很大的假设。 - Mark Ransom

Answer 4

R Sahu的答案 提供了一种灵活的方法来解决这个问题。唯一让我担心的是引入了多个需要管理的变量。然而，完全可以将功能包装在实用类中。

以下是您可以使用的简要草图：

#include <functional>
#include <utility>
#include <vector>

// Note that this is not threadsafe
template <typename Type>
class MutableLock {
    bool locked = false;
    Type value;
    // std::function gives us a more general action,
    // but it does come at a cost; you might want to consider using
    // other techniques.
    std::vector<std::function<void(Type&)>> actions;

public:
    class AutoLocker {
        MutableLock& lock;

        friend class MutableLock<Type>;

        explicit AutoLocker(MutableLock& lock)
            : lock{ lock }
        {
        }

    public:
        ~AutoLocker()
        {
            lock.unlock();
        }
    };

    MutableLock() = default;

    // The [[nodiscard]] is a C++17 attribute that
    // would help enforce using this function appropriately
    [[nodiscard]] AutoLocker lock()
    {
        locked = true;
        return AutoLocker{ *this };
    }

    void unlock()
    {
        for (auto const& action : actions) {
            action(value);
        }
        actions.clear();

        locked = false;
    }

    template <typename F>
    void action(F&& f)
    {
        if (!locked) {
            f(value);
        } else {
            actions.emplace_back(std::forward<F>(f));
        }
    }

    // There needs to be some way to expose the value
    // not under the lock (so that we can use it when
    // we call `lock()`).
    //
    // Even if your `Type` is not a range, this would
    // be fine, as member functions of a template class
    // aren't instantiated unless you call them.
    //
    // However, you may want to expose other ways to
    // access the value
    auto begin() { return std::begin(value); }
    auto end() { return std::end(value); }
    auto begin() const { return std::begin(value); }
    auto end() const { return std::end(value); }
};

使用它看起来会像这样：

#include <algorithm>
#include <iostream>

class Observer {
public:
    virtual void thingHappened() = 0;

protected:
    ~Observer() = default;
};

class SomeClass {
    MutableLock<std::vector<Observer*>> observers;

public:
    void addObserver(Observer* observer)
    {
        observers.action([observer](auto& observers) {
            observers.push_back(observer);
        });
    }

    void remove(Observer const* observer)
    {
        observers.action([observer](auto& observers) {
            observers.erase(std::remove(observers.begin(), observers.end(), observer), observers.end());
        });
    }

    void doSomething()
    {
        auto lock = observers.lock();
        for (auto* observer : observers) {
            observer->thingHappened();
        }
        // when `lock` goes out of scope, we automatically unlock `observers` and
        // apply any actions that were built up
    }
};

class Observer1 : public Observer {
public:
    SomeClass* thing;

    void thingHappened() override
    {
        std::cout << "thing 1\n";
        thing->remove(this);
    }
};

int main()
{
    SomeClass thing;
    Observer1 obs;
    obs.thing = &thing;

    thing.addObserver(&obs);
    thing.doSomething();
    thing.doSomething();
}

^{On Coliru}

- Justin