擦除std :: map中的特定元素

Question

我想删除我的std :: map中的一些元素.
我写了erase + remove_if技术,我总是使用其他序列容器.
但它不是用地图编译的.为什么？
我怎么能做这个工作？

std::map<int, int> m;

bool foo(const std::pair<int, int>& p)
{
    return p.second > 15;
}

int _tmain(int argc, _TCHAR* argv[])
{
    m.insert(make_pair(0, 0));
    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));

    m.erase(
        remove_if(m.begin(), m.end(), foo),
        m.end()); // compile error

    return 0;
}

Answer 1

这样写一下map,因为它remove_if不适用于map迭代器(它只是将违规元素放在最后,而map迭代器不允许这样做):

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    typename Map::iterator i = m.begin();
    while ((i = std::find_if(i, m.end(), pred)) != m.end())
        m.erase(i++);
}

或者如果你喜欢单行:

template <typename Map, typename F>
void map_erase_if(Map& m, F pred)
{
    for (typename Map::iterator i = m.begin();
         (i = std::find_if(i, m.end(), pred)) != m.end();
         m.erase(i++));
}

Answer 2

因为std::map不是"序列容器":) remove_if会尝试将无用的元素放到地图的末尾,但这会导致违反地图的隐式数据结构(大多数情况下为红黑树).隐式数据结构定义了每个元素在地图中的位置,这就是remove_if不允许的原因std::map.

你应该std::map循环擦除一个接一个(或给出一些间隔)的元素.

有点像这样:

it = m.begin();
while ((it = std::find_if(it, m.end(), pred)) != m.end())
    m.erase(it++);

Answer 3

"使用其他序列容器"是您的错误 - map是一个关联容器!在关联容器中,元素由其键定义(而不是它们在序列容器中的插入顺序),并且您按键擦除元素:

m.erase(12);

按键值擦除具有与查找相同的复杂度(例如,映射的O(log n),无序映射的O(1)等).或者,您可以在恒定时间内通过迭代器擦除.擦除迭代器会使迭代器无效,但不会使其他迭代器失效(再次与序列容器不同),因此如果要迭代地图,典型的习惯用法如下:

for (auto it = m.cbegin(); it != m.cend(); ) // no "++"!
{
  if (it->second > 15)  // your own condition goes here
  {
    m.erase(it++);
  }
  else
  {
    ++it;
  }
}