删除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

写像这样的地图，因为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

这个成语仅适用于序列类似容器 - 在地图（关联）项不能被重新排序（该键不改变 - 那么您如何您可能希望移动一个条目一些其他的位置 - 例如结束）。要做到这一点，正确的方法是找到该条目并删除它 - 即it = map.find(); map.erase(it++)

Answer 3

因为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 4

“与其他序列容器” 是你的错误 - map是关联容器！在关联容器，元件由它们的键定义的（而不是它们的插入顺序中的序列容器），并且由键擦除元件：

m.erase(12); 

擦除由密钥值具有相同的复杂性，因为查找（例如O（log n）for map，O（1）for unordered map等）。另外，你也可以在迭代器中不断擦除。删除一个迭代器失效是迭代器，但没有其他人（也不同于在序列容器），所以如果你想遍历地图，典型的成语是：

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

Answer 5

尝试是这样的

#include <iostream> 
#include <map> 
#include <algorithm> 

class foo 
{ 
public: 
    enum CompType { GREATER=1, LESS=-1 }; 
    foo(int nVal=15, enum CompType ctype=GREATER) 
    : m_nVal(nVal) 
    , m_bGreater(ctype==GREATER) 
    { 
    } 
    bool operator()(std::pair<int, int> p) 
    { 
     if (m_bGreater) 
      return p.second > m_nVal; 
     else 
      return p.second < m_nVal; 
    } 
private: 
    int m_nVal; 
    bool m_bGreater; 
}; 

void MapRemove(std::map<int, int> &m, foo &pred) 
{ 
    auto itr = std::find_if(m.begin(), m.end(), pred); 
    while (itr != m.end()) 
     itr = std::find_if(m.erase(itr), m.end(), pred); 
} 

int main(int argc, char *argv[]) 
{ 
    std::map<int, int> m; 

    m.insert(std::make_pair(0, 0)); 
    m.insert(std::make_pair(1, 10)); 
    m.insert(std::make_pair(2, 20)); 
    m.insert(std::make_pair(3, 30)); 

    MapRemove(m, foo()); 

    for (auto itr=m.begin(); itr!=m.end(); ++itr) 
     std::cout << "(" << itr->first << ", " 
        << itr->second << ")" << '\n'; 

    return 0; 
} 

Answer 6

，但它不是地图编译。为什么？

当使用remove_if时，解除引用的迭代器的类型必须满足CopyAssignable的要求。这是应该可以分配一个值到另一个。

对于std::map<int, int>，该值为std::pair<const int, int>，它表示映射的关键值对并且不是CopyAssignable。这个关键的const int的原因是地图如同其他人已经指出的那样在内部工作。

顺便说一句，你将获得的序列容器相同的编译错误是这样的：

std::vector<std::pair<const int, int>>;