c++ - 用于在嵌套容器中删除的删除 - 删除成语？ (删除外部的；C++ STL)

Question

当我从非嵌套容器(如 vector )中删除时，我正在做类似的事情:

struct is_to_remove
{
    is_to_remove(dynamic_bitset<>& x) : x(x) {}
    const bool operator()(unsigned int id)
    {
        return x[id];
    }

private:
    dynamic_bitset<> x;
};

inline static void remove_elements_in_vector(vector<unsigned int>& vec, boost::dynamic_bitset<>& to_remove)
{
    // use the erase-remove idiom to remove all elements marked in bitset
    vec.erase( remove_if(vec.begin(), vec.end(), is_to_remove(to_remove)), vec.end() );
}

也就是所谓的erase-remove idiom .

现在，我有了第二个数据结构 vector<vector<unsigned int> >或 deque<vector<unsigned int> > ，我想根据位集删除外部容器元素(它本身就是内部类型的容器)。

• 是否可以在这种嵌套容器类型上使用 erase-remove 习惯用法？
• 如果是，那怎么可能？
• 有限制吗？ (比如:vec 的 vec 是可能的，但不是 vec 的双端队列)？

我的第一个也是天真的方法如下。我假设 remove_if 是按顺序迭代元素并一个接一个地决定的。 这是一个错误的假设吗？

struct is_to_remove_new
{
    is_to_remove_new(dynamic_bitset<>& x, unsigned int index) : x(x), index(index) {}
    const bool operator()(vector<unsigned int> & vec)
    {
        return x[index++];
    }

private:
    dynamic_bitset<> x;
    unsigned int index;
};

inline static void remove_elements_in_vectorvector(vector<vector<unsigned int> >& vec, boost::dynamic_bitset<>& to_remove)
{
    // use the erase-remove idiom to remove all elements marked in bitset
    vec.erase( remove_if(vec.begin(), vec.end(), is_to_remove_new(to_remove, 0)), vec.end() );
}

结果是错误的，因此我在这里寻找正确的解决方案。我想我假设了一些不能保证的事情。对我来说，基本问题如下:如何获取内部容器的身份以检查是否要移除。。
我在上面发布的幼稚方法只是计算并假定顺序处理。

感谢您的帮助。

萨沙

更新和警告

对于 vector o vector ，Stas 解决方案效果很好。但我认为这个解决方案不适用于 vector 的双端队列，因为双端队列不是以连续的方式保存的。这意味着，仿函数中的索引计算失败。

谁能验证一下？

Answer 1

vector 中有哪些元素并不重要。如果您定义应删除其中的哪些，它们将被删除。

如您所说，问题是如何识别 vector 中的元素。最明显的答案是它的索引 [0; vector_size - 1] .

多亏了 vector ，您可以通过元素本身轻松获得元素索引。

std::vector<std::string> vec;
vec.push_back("zero");
vec.push_back("one");
vec.push_back("two");

std::string& elem = vec[2];
int index = std::distance(&vec[0], &elem); // get element index by element itself
// index == 2

因此，您可以通过 remove_if 中的索引轻松识别 vector 元素算法谓词。看看下面的例子。这很傻，使用硬编码 std::bitset<6> ，但这只是一个例子:

#include <vector>
#include <string>
#include <bitset>

struct ToRemove
{
   ToRemove(std::vector<std::string>& vec, const std::string& mask) 
   : m_vec(vec)
   , m_mask(mask) 
   {}

   bool operator()(std::string& obj)
   {
      const int index = std::distance(&m_vec[0], &obj);
      return m_mask[index];
   }

   std::vector<std::string>& m_vec;
   std::bitset<6> m_mask;
};

用法

int main (int argc, char const *argv[])
{
   std::vector<std::string> vec;
   vec.push_back("zero");
   vec.push_back("one");
   vec.push_back("two");
   vec.push_back("three");
   vec.push_back("four");
   vec.push_back("five");

   std::string mask = ("010011"); // Remove "zero", "one" and "four"
   vec.erase(remove_if(vec.begin(), vec.end(), ToRemove(vec, mask)), vec.end());

   for (unsigned i = 0; i < vec.size(); ++i)
   {
      std::cout << vec[i] << " ";
   }
   std::cout << std::endl;

   return 0;
}

结果

 two three five