在迭代集合时，最有效的从集合中删除元素的方法是什么？

Question

在迭代集合时，最有效的删除方式是什么？我想到了两种方法，哪个更好？还有其他更好的方法吗？

void WaitForFiles(std::set<string> files) {
  while (files.size() > 0) {
    std::set<string> found_files;
    for (const auto& file : files) {
      if (Exists(file)) {
        found_files.insert(file);
      }
    }
    for (const auto& found_file : found_files) {
      files.erase(file);
    }
  }
}

使用 set_difference：

void WaitForFiles(std::set<string> files) {
  while (files.size() > 0) {
    std::set<string> found_files;
    for (const auto& file : files) {
      if (Exists(file)) {
        found_files.insert(file);
      }
    }
    std::set<string> difference;
    std::set_difference(files.begin(), files.end(),
                        found_files.begin(), found_files.end(),
                        std::inserter(difference, difference.end()));
    files = difference;
  }
}

请注意以下崩溃情况：

void WaitForFiles(std::set<string> files) {
  while (files.size() > 0) {
    for (const auto& file : files) {  // <-- seg fault after first erase
      if (Exists(file)) {
        files.erase(file);
      }
    }
  }
}

对于确定效率，请记住，在我的情况下，文件可能需要30分钟才能存在，因此Exists函数将被调用多次，并且与循环迭代的次数相比，文件集合不会经常更改。

- AffluentOwl

---

将 found_files 从一个 set 改为一个 vector。 - Mark Ransom

与其无限期地使用100％的线程时间，您最好使用一些操作系统设施，例如在文件夹或类似位置上更改通知。 “基于事件”的好处还在于，只要文件出现，您就可以立即擦除它，并且您的“迭代时擦除”问题甚至不存在。 - BitTickler

好的，但是如果你无论如何都要循环，为什么还要考虑效率呢？如果你的永久循环每500微秒循环一次或每1毫秒循环一次，这有什么关系呢？ - BitTickler

从集合中删除元素会使得基于范围的for循环使用的隐藏迭代器失效。相反，您需要使用显式迭代器编写循环，并使用erase方法返回的新迭代器。 - Jonathan Potter

我的意思是向量比集合更有效，而你在使用found_files的方式中没有任何优势。但是Chris Drew的答案向你展示了如何完全消除它，这是100％更好的。 - Mark Ransom

Answer 1

在使用基于范围的for循环从set中删除元素是未定义行为（即使看起来可以工作）。基于范围的for循环在内部使用迭代器，而删除元素会使迭代器失效。

但是std::set::erase返回指向std::set中下一个元素的有效迭代器，因此可以使用显式迭代器循环来代替。

for(auto itr = files.cbegin(); itr != files.cend();) {
  if (exists(*itr)) {
    std::cout << "Found file: " << *itr << "\n";
    itr = files.erase(itr);
  } else
    ++itr;
}

演示链接。

- Chris Drew

---

旁边的问题。files.erase(itr)比files.erase(*itr)更快吗？还是这是实现定义的？ - AffluentOwl

@AffluentOwl 第一个肯定会更快。第二个需要在集合中查找元素，而第一个则不需要。 - Chris Drew

@AffluentOwl，对于这个问题，files.erase（*itr）不是一个选项；它不会返回迭代器（也不能，因为它可能会删除多个元素）。 - Don Hatch

Answer 2

使用库基础 TS v2 中的 std::experimental::erase_if：

std::experimental::erase_if(files, Exists);

如果Exists被重载或是一个函数模板，则使用lambda表达式：

std::experimental::erase_if(files, [](const auto& f) { return Exists(f); });

这已经在VS2015中实现。

- T.C.

---

我非常喜欢这个答案，因为链接解释了erase_if等价于什么。 - AffluentOwl

Answer 3

你的前两个例子看起来不够优化，因为它们都需要遍历集合两次。第三个例子不稳定，因为你在使用std::set::erase更改集合后，继续使用迭代器，从而使其无效。

我认为以下代码应该是相当高效的。但是，正如其他人提到的那样，将std::set<std::string> found_files替换为std::vector可能值得考虑。

#include <set>
#include <string>
#include <iostream>

/**
 * Return true for every other call
 */
bool Exists(std::string const&)
{
    static int i = 0;
    return ++i % 2;
}

std::set<std::string> find_existing_files(std::set<std::string>& files)
{
    std::set<std::string> found_files;

    for(auto file = files.begin(); file != files.end();)
    {
        if(!Exists(*file))
            ++file; // not erasing, keep going
        else
        {
            found_files.insert(*file);
            // replacing iterator with result of erase()
            // keeps the iterator valid
            file = files.erase(file);
        }
    }
    return found_files;
}

int main()
{
    std::set<std::string> files {"a", "b", "c", "d", "e"};

    for(auto const& file: find_existing_files(files))
        std::cout << "exists : " << file << '\n';

    for(auto const& file: files)
        std::cout << "missing: " << file << '\n';
}

输出：

exists : a
exists : c
exists : e
missing: b
missing: d

- Galik

---

现在你总是返回一个空集合 :) - T.C.

@T.C. 呵呵，这就是同时编辑太多东西的问题。 - Galik