2

当我从像向量这样的非嵌套容器中删除时,我正在做类似的事情:

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> >or deque<vector<unsigned int> >,我想根据 bitset 删除外部容器元素(它本身就是内部类型的容器)。

  • 是否可以在此嵌套容器类型上使用擦除删除习语?
  • 如果是,怎么可能?
  • 有限制吗?(比如: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() );
}

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

谢谢你的帮助。

萨沙

更新和警告

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

任何人都可以验证吗?

4

1 回答 1

3

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

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

多亏了向量,您可以通过元素本身轻松获取元素索引。

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因此,您可以通过算法谓词中的索引轻松识别向量元素。看看下面的例子。它非常愚蠢并使用 hard-coded 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 
于 2010-12-07T22:19:21.840 回答