c++ - 当成员可能在迭代过程中被删除时，如何遍历集合？

Question

这个简单的程序是我遇到的问题的最小版本。我有一组无序的对象指针，在遍历该集合时，应该从集合中删除一些对象。在我的大型程序中，这导致它崩溃。在这个较小的循环中，它只是删除一个元素然后结束循环。

在下面的示例中，我们有一个以 Units 为特色的游戏。当单位空闲时，游戏会让他们执行一个 Action 。空闲 Units 在名为 idle_units 的 unordered_set 中进行跟踪。

在游戏的更新循环中，它会遍历 idle_units 并让它们执行一个 Action 。当 Unit 的 act() 函数被调用时，它不再空闲，因此从 idle_units

中移除

#include <vector>
#include <memory>
#include <unordered_set>
#include <unordered_map>
#include <cstdlib>
#include <iostream>

// forward declarations
struct Unit;
void set_not_idle(Unit* u_);

struct Unit {  // a simple object with unique identifier
    Unit() { static int id_ = 0; id = id_++; }
    void act() { set_not_idle(this); }
    int id;
};

// data
std::vector<std::unique_ptr<Unit>> unit_storage;
std::unordered_set<Unit*> unit_ptrs;
std::unordered_map<int, Unit*> unit_from_id;
std::unordered_set<Unit*> idle_units;

Unit* get_unit_ptr(Unit u) { return unit_from_id[u.id]; }

void set_idle(Unit* u_) {
    Unit* u = get_unit_ptr(*u_); // ensure we have pointer to unit in storage
    idle_units.insert(u);
}

void set_not_idle(Unit* u_) {
    Unit* u = get_unit_ptr(*u_); // ensure we have pointer to unit in storage
    idle_units.erase(u);
}

void add_unit(Unit u_) {
    unit_storage.push_back(std::make_unique<Unit>(u_));
    Unit* u_ptr = unit_storage.back().get();
    unit_ptrs.insert(u_ptr);
    unit_from_id[u_ptr->id] = u_ptr; // set map from id to pointer in storage
    set_idle(u_ptr); // units start as idle
}

void print() {
    std::cout << "Units in storage: ";
    for (auto a : unit_ptrs) {
        std::cout << a->id << " ";
    }
    std::cout << "  Idle units: ";
    for (auto it = idle_units.begin(); it != idle_units.end(); ++it) {
        std::cout << (*it)->id << " ";
    }
    std::cout << std::endl;
}

int main() {
    srand(25);
    std::vector<Unit> units;

    // randomly populate our unit_storage with 8 units
    for (int i = 0; i < 50; i++) units.push_back(Unit());
    for (int i = 0; i < 8; ) {
        int idx = rand() % units.size();
        if (!get_unit_ptr(units[idx])) {
            add_unit(units[idx]);
            i++;
        }
    }
    print();
    // get all idle units, and have them perform an action
    for (auto it = idle_units.begin(); it != idle_units.end(); ++it) {
        (*it)->act();
    }
    print();
    return 0;
}

这会产生以下输出:

Units in storage: 36 2 15 43 18 10 38 11   Idle units: 36 2 15 43 18 10 38 11 
Units in storage: 36 2 15 43 18 10 38 11   Idle units: 2 15 43 18 10 38 11 

而它应该不会导致 idle_units 中没有剩余 Units。最优雅的解决方案是什么？

在尝试解决这个问题时，我尝试了不同的迭代方法，包括 for (auto it : idle_units) 循环，或者将迭代器增量移动到循环体，但都没有这些解决方案解决了问题。

Answer 1

对此最优雅的解决方案是使用基于迭代器的循环，并在循环体内递增迭代器。这确保迭代器始终有效，即使它指向的元素已从集合中移除。

for (auto it = idle_units.begin(); it != idle_units.end(); ) {
    (*it)->act();
    it = idle_units.erase(it);
}

此代码将遍历集合，对每个元素调用 act()。 act() 将从集合中删除元素，因此迭代器将失效。 erase() 函数返回指向集合中下一个元素的有效迭代器，因此我们可以简单地将迭代器分配回 it 并继续循环。