137

我试图根据特定条件从地图中删除一系列元素。我如何使用 STL 算法来做到这一点？

最初我想使用remove_if但这是不可能的，因为 remove_if 不适用于关联容器。

是否有任何适用于 map 的“remove_if”等效算法？

作为一个简单的选择，我想循环遍历地图并擦除。但是循环遍历地图并擦除安全选项吗？（因为迭代器在擦除后变得无效）

我使用了以下示例：

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;
}
4

14 回答 14

126

几乎。

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

如果您确实从中删除了一个元素，那么您最初的操作会使迭代器增加两次；您可能会跳过需要删除的元素。

这是我在许多地方看到使用和记录的常用算法。

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

于 2009-04-29T05:20:47.317 回答
83

用于 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
});
于 2013-05-16T20:39:23.073 回答
8

现在，std::experimental::erase_if在 header 中可用<experimental/map>。

请参阅：http ://en.cppreference.com/w/cpp/experimental/map/erase_if

于 2017-04-07T15:41:21.303 回答
3

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

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

因此，您拥有的指向要擦除的元素的迭代器当然会失效。做这样的事情：

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}
于 2009-04-29T05:22:03.303 回答
3

这是一些优雅的解决方案。

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}
于 2019-11-06T13:23:58.867 回答
2

原始代码只有一个问题：

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

在这里，iter在 for 循环中增加一次，在擦除中增加一次，这可能会以无限循环结束。

于 2013-01-16T18:14:38.340 回答
2

对于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;
});
于 2021-11-04T14:59:07.097 回答
1

从底部注释：

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

Pair Associative Container 不能提供可变迭代器（如 Trivial Iterator 要求中所定义），因为可变迭代器的值类型必须是可赋值的，而对是不可赋值的。但是，Pair Associative Container 可以提供不完全恒定的迭代器：使得表达式 (*i).second = d 有效的迭代器。

于 2009-04-29T08:59:08.757 回答
1

恕我直言，没有remove_if()等价物。
您无法重新排序地图。
所以remove_if()不能把你对的兴趣放在你可以跟注的末尾erase()。

于 2009-05-19T09:28:45.980 回答
1

第一的

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

二、下面的代码不错

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

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

所以在调用erase之前计算iter++时，迭代器的++操作符将返回当前项，并在调用后指向下一项。

于 2009-08-25T13:54:35.653 回答
1

基于Iron Savior 的回答对于那些希望提供更多符合 std 函数式迭代器的范围的人。

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项目并从迭代器中获取。

于 2015-06-01T22:52:17.020 回答
0

史蒂夫愚蠢的回答我觉得更有效率。

这是另一个简单但效率较低的解决方案：

该解决方案用于remove_copy_if将我们想要的值复制到一个新容器中，然后将原始容器的内容与新容器的内容交换：

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

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);
于 2009-05-25T18:13:36.040 回答
0

如果要擦除所有 key 大于 2 的元素，那么最好的方法是

map.erase(map.upper_bound(2), map.end());

但仅适用于范围，不适用于任何谓词。

于 2011-08-10T09:33:17.310 回答
0

我这样用

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }
于 2018-11-27T08:13:51.283 回答