c++ - 比较不同的 vector 迭代器并从第一个 vector 中删除元素

Question

我已经为这个问题苦苦挣扎了大约一个星期。我不知道问题出在哪里，或者我是否在错误的地方更新了迭代器。

让我们进入正题。我正在尝试制作一个掉落系统，在玩家杀死怪物后，随机元素会从怪物身上掉落。我从下面的容器中取出元素。从 gear 容器收到项目后，我还想从 gear vector 中删除收到的项目。 IE。如果“板甲”掉落，我想将其从 gear 容器中删除。

我有一个 Gears vector ，我在其中注册了不同的装备，例如武器、盔甲或配件。在我们的案例中，我将只关注装甲。

std::vector<std::unique_ptr<Armor>> gear;

/* This is the simplified version of the vector. 
 I register different elements into my gear vector. Now is only armor focused on.
*/
gear.emplace_back(new Armor("Great pauldron", 25, 100));
gear.emplace_back(new Armor("Holy armor", 3, 18));
gear.emplace_back(new Armor("Dominic's eye", 18, 73));
gear.emplace_back(new Armor("Plate armor", 23, 21));
gear.emplace_back(new Armor("Poor armor", 57, 7));
gear.emplace_back(new Armor("Good shield", 91, 5));
gear.emplace_back(new Armor("Jodin's boots", 18, 66));
gear.emplace_back(new Armor("Ivona's gauntlets", 25, 100));

下一步，我创建了一个类，我在其中接收给定的项目数作为 vector 迭代器的 vector 。 (我使用公共(public)函数进行此类操作。)

class Maker {
private:

    template<typename Iter, typename RandomGen>
    Iter randomSelection(Iter begin, Iter end, RandomGen& ran) {
        std::uniform_int_distribution<> dist(0, std::distance(begin, end) - 1);
        std::advance(begin, dist(ran));
        return begin;
    }
public:

    template<typename Iter>
    std::vector<Iter> randomSelection(Iter& begin, Iter& end, int amount) {
        std::vector<Iter> it;
        std::random_device randDev;
        std::mt19937 gen(randDev());
        for (int i = 0; i < amount; i++)
            it.push_back(randomSelection<>(begin, end, gen));
        return it;
    }
};

接下来，我制作了一个 vector 迭代器 vector ，用于从 gear 容器中接收随机项。

Maker mak;
std::vector<std::vector<std::unique_ptr<Armor>>::iterator>& droppedItems = 
    mak.randomSelection(gear.begin(), gear.end(), 5);

问题出在我尝试比较两个 vector 中的盔甲名称，如果找到的话；从我们的第一个 gear vector 中删除它。我几乎总是遇到访问冲突错误。有时可以在不产生任何错误的情况下删除项目。但是每一次，即 20 次尝试。

for (auto& i = gear.begin(); i != gear.end();) {
        for (auto& j = droppedItems.begin(); j != droppedItems.end(); j++) {
            /* This if statement is where I get the access violation error; 0x05.*/
            if (i->get()->getName() == (*j)->get()->getName()) {
                std::cout << std::endl << i->get()->getName() << " has been deleted!\n";
                i = gear.erase(i);
            }
            else
                i++;
        }
    }

我假设我在错误的地方增加了迭代器。我假设我很好地执行了删除操作，但我确实没有想法。

Answer 1

std::vector<T>::erase(iter)使 iter 处或之后的迭代器和引用无效(包括 end() )，但您仍然尝试使用来自 droppedItems 的这些无效迭代器之后的容器。

例如，如果我们说 droppedItems还包含一个指向 gears 的最后一个元素的迭代器，还有一些其他的迭代器。当您删除 gears 的任何其他元素时，它使指向最后一个元素的迭代器无效。所以当你最终调用gears.erase()将(无效的)迭代器传递给最后一个元素，它将导致未定义的行为。

std::vector<int> test{1,2,3,4};
auto firstIter = test.begin();
auto secondIter = firstIter + 1;
auto thirdIter = secondIter + 1;
auto fourthIter = thirdIter + 1;
test.erase(secondIter); // Invalidates secondIter, thirdIter and fourthIter
                        // but not firstIter

可以想到std::vector<T>迭代器作为指向 T 的指针.如果删除一个元素，它后面的元素将在内存中移动，以将 vector 元素保留为动态数组。因此，“指向”那些元素的迭代器将不会继续指向正确的元素。

之前test.erase(secondIter) :

address: | 0x0 | 0x1 | 0x2 | 0x3 |
value:   |   1 |   2 |   3 |   4 |

firstIter  = 0x0 // Points to element with value 1
secondIter = 0x1 // Points to element with value 2
thirdIter  = 0x2 // Points to element with value 3
fourthIter = 0x3 // Points to element with value 4

在 test.erase(secondIter) 之后:

address: | 0x0 | 0x1 | 0x2 |
value:   |   1 |   3 |   4 |

firstIter  = 0x0 // Still points to element with value 1
secondIter = 0x1 // no longer points to element with value 2
thirdIter  = 0x2 // no longer points to element with value 3
fourthIter = 0x3 // out of vector bounds

我建议改为设置 gears 的随机元素至 nullptr然后压缩 vector :

template <typename T>
void freeRandomItems(std::vector<std::unique_ptr<T> > & vec,
                     std::size_t amount)
{
    if (amount == 0u)
        return; // Nothing to do

    // Setup RNG:
    std::random_device randDev;
    std::mt19937 gen(randDev());

    if (amount == 1u) { // Remove only one random element:
        vec.erase(randomSelection(vec.begin(), vec.end(), gen));
        return;
    }

    // Deallocate amount pointed elements in vector, reset pointers:
    do {
        randomSelection<>(vec.begin(), vec.end(), gen)->reset();
    } while (--amount);

    // Remove all nullptr elements from vec:
    vec.erase(
            std::remove_if(
                    vec.begin(),
                    vec.end(),
                    [](std::unique_ptr<T> const & v) noexcept { return !v; }),
            vec.end());
}