std::map的remove_if等价函数

Question

我想根据特定条件从 map 中删除一定范围的元素，如何使用 STL 算法实现？

最初我考虑使用 remove_if，但是它不适用于关联容器。

有没有类似于 "remove_if" 的算法可以在 map 中使用？

作为一个简单的选择，我考虑循环遍历 map 并进行删除。但是循环遍历并删除是否安全？（因为迭代器在 erase 后会变为无效）

我使用了以下示例：

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

- aJ.

---

你的意思是说remove_if没有起作用？ - dirkgently

我不能使用 remove_if 在 map 中查找元素，对吗？它会产生编译时错误。我有什么遗漏的东西吗？ - aJ.

不行 - remove_if 函数通过重新排序序列，将未通过条件的元素移到末尾来实现。因此，它适用于 T[n]，但不适用于 map<T,U>。 - MSalters

使用C++11，你可以使用for(auto iter=aMap.begin(); iter!=aMap.end(); ){ ....}来减少混乱。其他部分与其他人所说的相同。这个问题刚刚让我省了些头发分叉;-) - Atul Kumar

我看到C++20为std::map引入了std::erase_if，但愿我能把我的代码带到未来。 - wcochran

Answer 1

几乎正确。

for(; iter != endIter; ) {
     if (Some Condition) {
          iter = aMap.erase(iter);
     } else {
          ++iter;
     }
}

如果你使用原来的方法在迭代器中删除元素，它会使迭代器增加两次；这可能会跳过需要删除的元素。

我看到很多地方都使用和记录了这种常见的算法。

[编辑] 你是正确的，erase后迭代器无效，但只有引用被删除元素的迭代器无效，其他迭代器仍然有效。 因此在 erase() 调用中使用 iter++。

- Steve Folly

---

我感到困惑，你为什么会使用for (; ... ;)而不是while(...)? 此外，尽管这很可能有效，但.erase不是返回下一个迭代器吗？因此，似乎if (某些条件)的代码块应该是iter = aMap.erase(iter)才能最兼容。也许我漏掉了什么？我缺乏你们一些人拥有的经验。 - taxilian

注意，在 C++11 中，所有关联式容器，包括 map，返回从 erase(iter) 开始的下一个迭代器。更加简洁的方式是使用 iter = erase(iter)。 - Potatoswatter

@taxilian（晚了几年），while()或for()都可以使用，但从语义上讲，人们通常使用for()来迭代已知范围，而使用while()来进行未知次数的循环。由于在这种情况下范围是已知的（从开头到 endIter），for()不会是一个不寻常的选择，并且可能更常见。但是再次强调，两者都可以接受。 - Jamin Grey

更重要的是：使用“for”循环，你可以将迭代器定义放在循环的作用域内，这样它就不会影响程序的其他部分。 - Sanchises

@athos 这个问题用被动语态表达，“建议使用”。并没有普遍的建议。我认为我上一条评论是最直接的方法。它确实涉及到两个迭代器变量的副本，这会损失一些效率，正如有人在这里指出的那样。你可以自行决定什么对你来说是合适的。 - Potatoswatter

Answer 2

std::map（以及其他容器）的erase_if函数

我使用以下模板来实现这个功能。

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

这不会返回任何东西，但它会从std::map中删除项目。

用法示例：

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

第二个示例（允许您传入测试值）：

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

- Iron Savior

---

谢谢你的询问 —— 对我来说，std 中没有类似的函数似乎有些奇怪。虽然我理解为什么它不是 std::map 的成员函数，但我认为标准库应该包含类似的函数。我会在翻译时尽力保持原意并简化语言。 - Iron Savior

C++20 for std::map 和其他容器也将增加该功能。 - Roi Danton

Answer 3

现在，std::experimental::erase_if 已经可以在头文件 <experimental/map> 中使用。

参见： http://zh.cppreference.com/w/cpp/experimental/map/erase_if

- user1633272

---

现在它已经使用了C++20。 - L. F.

Answer 4

对于使用C++20的人，map和unordered_map都有内置的std::erase_if函数：

std::unordered_map<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                                    {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};
 
const auto count = std::erase_if(data, [](const auto& item) {
    auto const& [key, value] = item;
    return (key & 1) == 1;
});

- MartinBG

Answer 5

这里有一些优雅的解决方案。

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

- Mandrake Root

---

这取决于在调用map.erase(...)之前完全评估it++（当然，它会这样做）_并且_它依赖于map.erase(...)不使除被删除的内容以外的任何迭代器无效。所有这些都是真实的。我只是认为值得明确说明一下，以防有人无意中将此模式应用到另一个容器中。 - Matthew M.

Answer 6

我从优秀的SGI STL参考文献获得了这份文档:

Map有一个重要的特性，那就是在将新元素插入到Map中时，不会使指向现有元素的迭代器失效。从Map中删除元素也不会使任何迭代器失效，除了当然指向正在被删除的元素的迭代器。

所以，指向需要被删除的元素的迭代器当然会失效。可以采取像这样的做法:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

- 1800 INFORMATION

---

这段代码与原始代码没有区别。iter++会增加迭代器的值，并返回指向增加前元素的迭代器。 - Steve Folly

但是，由于我们随后在此处的位置擦除，因此iter不会失效。 - 1800 INFORMATION

@1800INFORMATION：输入函数调用是一个序列点，递增的副作用在调用“erase”之前被评估。因此它们确实是等价的。尽管如此，我仍然强烈建议您使用您的版本而不是原始版本。 - peterchen

它适用于数组或向量，但在STL映射中会导致意外的结果。 - hunter_tech

Answer 7

这段代码只有一个问题：

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

在这个for循环中，iter被增加了一次，在erase中又被增加了一次，这可能会导致某些无限循环。

- partha biswas

Answer 8

基于 Iron Savior的回答，对于那些想要提供更接近于std functional采用迭代器的范围的人。

template< typename ContainerT, class FwdIt, class Pr >
void erase_if(ContainerT& items, FwdIt it, FwdIt Last, Pr Pred) {
    for (; it != Last; ) {
        if (Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

想知道是否有办法从迭代器中删除ContainerT项并获取它。

- Greg Domjan

---

以下划线开头并后跟大写字母的标识符被实现保留，用于所有用途。 - YSC

Answer 9

第一

Map有一个重要的属性，即向Map中插入新元素不会使指向现有元素的迭代器失效。从Map中删除元素也不会使任何迭代器失效，当然，除了实际指向正在被删除的元素的迭代器。

第二，以下代码是好的

for(; iter != endIter; )
{
    if(Some Condition)
    {
        aMap.erase(iter++);
    }
    else
    {
        ++iter;
    }
}

在调用函数时，参数会在调用该函数之前进行评估。

因此，在调用 erase 函数之前对 iter++ 进行评估时，迭代器的 ++ 运算符将返回当前项，并指向调用后的下一项。

- Vincent

Answer 10

从底部注释：

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

一个成对关联容器不能提供可变迭代器（按照 Trivial 迭代器的定义），因为可变迭代器的值类型必须是可赋值的，而 pair 不是可赋值的。然而，一个成对关联容器可以提供不完全常量的迭代器：这样的迭代器使得表达式 (*i).second = d 是有效的。

- piotr