unordered_map 个元素正在删除

Question

我将 {string, MyStruct} 对象插入到 unordered_map 中，稍后遍历 unordered_map 并选择擦除该元素。但是，在擦除元素之前，我有一个断言显示 unordered_map 为空。

这是我的插页：

my_umap.insert(std::make_pair(key.toString(), my_struct));

该结构包含一个记录其插入时间的成员。然后我定期检查地图并删除在 unordered_map 中时间过长的元素：

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry){
        const string& key = it->first;    // Cannot access memory for 'key'
        assert(my_umap.size() >= 1);       // This is failing
        my_umap.erase(key);
    }
}

我是运行 gdb 中的代码，断言失败。当我查询 key 的值时，它显示

cannot access memory

当我查询 my_umap 的大小时，它说大小为零。

如果 unordered_map 的大小为零，for 循环如何检测元素？没有其他线程访问此容器。我以为 unordered_map::insert() 将对象复制到容器中，所以被删除的原始对象应该无关紧要？

Answer 1

erase() 使您正在擦除的迭代器无效。当您随后在 for 循环中递增它时，您会得到未定义的行为。 assert() 可能会在循环的第二次迭代时触发，而不是第一次。

您必须像这样重构您的循环：

for(auto it = my_umap.begin(); it != my_umap.end(); /* nothing */){

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry) {
        // either use the return
        it = my_umap.erase(it); // NB: erase by it, not by key, why
                                // do an extra lookup?       

        // or post-increment
        my_umap.erase(it++);
    }
    else {
        ++it;
    }
}

就个人而言，我更喜欢 it = map.erase(it) 而不是 map.erase(it++) 但是 YMMV。

我只是将其包装在函数模板中，这样您就不必继续重写此类内容：

template <class Container, class F>
void erase_if(Container& c, F&& f) {
    for (auto it = c.begin(); it != c.end(); ) {
        if (f(*it)) {
            it = c.erase(it);
        }
        else {
            ++it;
        }
    }
}

然后：

erase_if(my_umap, [](const auto& pr){
    MyStruct& myStruct = pr.second; 
    return myStruct.ts.IsElapsed(std::chrono::seconds(5));
});

Answer 2

调用 my_umap.erase(...) 后，您的迭代器将失效：

cppreference.com 说：

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

这意味着一旦项目被擦除，指向它的迭代器就不再有效。

您有几个选择：

1。使用迭代器擦除，使用`erase()`

的return值

自 C++11 起，通过迭代器擦除将 return 指向映射中下一项的迭代器。所以你可以用它来保持你的迭代器有效：

auto it = my_umap.begin();

while (it != my_umap.end()) {

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry){
        assert(my_umap.size() >= 1);
        it = my_umap.erase(it);  // <-- Return value should be a valid iterator.
    }
    else{
        ++it;  // Have to manually increment.
    }
}

2。将迭代器存储在列表对象中并在迭代后擦除。

或者，您可以将删除候选对象存储在列表对象中（例如向量并在初始迭代后删除它们：

std::vector<MapType::iterator> deleteCandidates;

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry)
        deleteCandidates.push_back(it);
}

for (auto it : deleteCandidates) {
    my_umap.erase(it);
}

至于你的断言失败的原因，你可能遇到了访问无效迭代器的未定义行为，使你的 for 循环相信映射仍然不为空（因为 invalidIterator != my_umap.end()） .

Answer 3

问题是你搞砸了迭代器。当您在迭代过程中删除元素时，您会删除本应指向下一个迭代器的当前迭代器。

有几种方法可以解决这个问题。第一个是我刚刚从 c++ 参考中复制的内容：

int main()
{
    std::map<int, std::string> c = { { 1, "one" }, { 2, "two" }, { 3,     "three" },
    { 4, "four" }, { 5, "five" }, { 6, "six" } };
    // erase all odd numbers from c
    for (auto it = c.begin(); it != c.end();)
        if (it->first % 2 == 1)
            it = c.erase(it);
        else
            ++it;
    for (auto& p : c)
        std::cout << p.second << ' ';

注意循环。它不会推进迭代器。相反，它将迭代器分配给从已擦除元素返回的迭代器 - 擦除 returns 下一个迭代器，或者，如果不擦除，它会显式推进它。

解决此问题的第二个选项是我对第一个程序所做的以下更改：

int main()
{
    std::map<int, std::string> c = { { 1, "one" }, { 2, "two" }, { 3, "three" },
{ 4, "four" }, { 5, "five" }, { 6, "six" } };

    // collect all odd numbers from c into a vector
    vector<int> to_delete;
    for (auto pair : c) if (pair.first % 2 == 1) to_delete.push_back(pair.first); 

    // now delete them all
    for (auto k : to_delete) c.erase(k);

    for (auto& p : c)
        std::cout << p.second << ' ';
}

这次我将所有的键都收集到一个向量中，然后扫描向量并从地图上擦除每个键。这样您就不会在迭代地图时从地图上擦除。

Answer 4

实际上，@barry 建议的 erase_if() 已经是 TS Library Fundamentals V2（统一容器擦除）的一部分。我现在找不到它是否会成为 C++17 的一部分。

这里有一个参考： http://en.cppreference.com/w/cpp/experimental/unordered_map/erase_if

Visual Studio 2015 附带的标准库已经实现了它。

从libstdc++（gcc附带的标准库）的状态页面我们可以看到它也实现了它，但它只在开发版本中，而不是在任何特定版本中。 (https://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.201z)

请注意，与大多数当前算法不同，这些函数位于相关容器的 header 中（不在算法 header 中）并且它们引用容器本身（而不是一对迭代器）。这些更改是因为这些函数必须了解容器才能正确实现循环并使用容器成员函数 erase()。因此，如果您只想对容器中的特定范围应用此擦除操作，您仍然必须使用 hand-written 循环，如其他答案中所述（也许 Ranges TS 也改进了这一点？）。

unordered_map 个元素正在删除

unordered_map element being deleted

c++

unordered-map

c++11

1。使用迭代器擦除，使用`erase()`

2。将迭代器存储在列表对象中并在迭代后擦除。

unordered_map 个元素正在删除

unordered_map element being deleted

c++

unordered-map

c++11

1。使用迭代器擦除，使用erase()

2。将迭代器存储在列表对象中并在迭代后擦除。

1。使用迭代器擦除，使用`erase()`