从无序映射中删除满足谓词条件的元素

Question

我希望能够从一个std::unordered_map（直方图）中删除元素（直方图条），该直方图满足以下lambda表达式所表示的预测条件（直方图条计数为零）：

std::remove_if(begin(m_map), end(m_map), [](const Bin & bin) { return bin.second == 0; });

但是GCC-4.6.1会报以下错误：

/usr/include/c++/4.6/bits/stl_pair.h:156:2: error: assignment of read-only member ‘std::pair<const unsigned char, unsigned char>::first’
/usr/include/c++/4.6/bits/stl_pair.h: In member function ‘std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) [with _T1 = const unsigned char, _T2 = long unsigned int, std::pair<_T1, _T2> = std::pair<const unsigned char, long unsigned int>]’:
/usr/include/c++/4.6/bits/stl_algo.h:1149:13:   instantiated from ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::__detail::_Hashtable_iterator<std::pair<const unsigned char, long unsigned int>, false, false>, _Predicate = pnw::histogram<V, C, H>::pack() [with V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >]::<lambda(const Bin&)>]’
tests/../histogram.hpp:68:13:   instantiated from ‘void pnw::histogram<V, C, H>::pack() [with V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >]’
tests/../histogram.hpp:85:13:   instantiated from ‘void pnw::histogram<V, C, H>::normalize(uint) [with V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >, uint = unsigned int]’
tests/../histogram.hpp:121:51:   instantiated from ‘H& pnw::histogram<V, C, H>::add(It, It) [with It = __gnu_cxx::__normal_iterator<const unsigned char*, std::vector<unsigned char> >, V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >]’
tests/../histogram.hpp:129:55:   instantiated from ‘H& pnw::histogram<V, C, H>::add(const V&) [with V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >]’
tests/../histogram.hpp:57:60:   instantiated from ‘pnw::histogram<V, C, H>::histogram(const V&, pnw::histogram<V, C, H>::TYPE_t) [with V = std::vector<unsigned char>, C = long unsigned int, H = std::unordered_map<unsigned char, long unsigned int, std::hash<unsigned char>, std::equal_to<unsigned char>, std::allocator<std::pair<const unsigned char, long unsigned int> > >]’
tests/t_histogram.cpp:38:61:   instantiated from ‘void test_dense_histogram() [with T = unsigned char, C = long unsigned int]’
tests/t_histogram.cpp:64:5:   instantiated from ‘void test_histograms() [with C = long unsigned int]’
tests/t_histogram.cpp:200:29:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:156:2: error: assignment of read-only member ‘std::pair<const unsigned char, long unsigned int>::first’
make: *** [tests/t_histogram.o] Error 1

std::remove_if适用于std::unordered_map吗？

- Nordlöw

---

我也曾陷入这个陷阱，但现在想想 std::remove（将元素移动到容器的末尾）无法与关联容器一起使用。 “容器的末尾”不再具有实际意义。 - RichardBruce

Answer 1

答案是否定的（你不能在关联容器上使用remove_if）。你需要使用一个简单的循环；erase(iterator)成员现在返回下一个有效迭代器 - 所以你的循环变成了：

答案是否定的（你不能在关联容器上使用remove_if）。你需要使用一个简单的循环；erase(iterator)成员现在返回下一个有效迭代器 - 所以你的循环变成了：

for(auto it = begin(m_map); it != end(m_map);)
{
  if (it->second == 0)
  {
    it = m_map.erase(it); // previously this was something like m_map.erase(it++);
  }
  else
    ++it;
}

- Nim

Answer 2

Stephan T. Lavavej提出了一种统一容器擦除的提案：Uniform Container Erasure

。

template <class K, class T, class H, class P, class A, class Predicate>
void erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);

即 (i.e.)

std::erase_if(m_map, [](const Bin& bin) { return bin.second == 0; });

不幸的是，它没有成为C++17的一部分。我想这可能与Ranges TS的采用有关。

- akim

Answer 3

自从c++20，可以在unordered_map上使用erase_if。
它将返回已删除元素的数量。

来自cpp reference：

std::erase_if (std::unordered_map)
从容器中删除满足谓词pred的所有元素。

在您特定的用例中（删除第二个元素为0的所有元素），它看起来像：

const auto count = std::erase_if(m_map, [](const auto& item) {
    auto const& [key, value] = item;
    return (value == 0);
});

- zerocukor287