Стереть-удалить идиому для удаления во вложенном контейнере? (удаление внешних; C ++ STL) - PullRequest
Новая
       35

Стереть-удалить идиому для удаления во вложенном контейнере? (удаление внешних; C ++ STL)

2 голосов
/ 07 декабря 2010

когда я удаляю из не вложенного контейнера, как вектор, я делаю что-то вроде: 

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 идиома .

Теперь у меня есть вторая структура данных vector<vector<unsigned int> > или deque<vector<unsigned int> >, где я хочу удалить элементы внешнего контейнера (который сам является контейнером внутреннего типа) в соответствии с набором битов.

  • Можно ли использовать итерацию удаления-удаления для этого типа вложенных контейнеров?
  • Если это так, как это возможно?
  • Есть ли ограничения?(например: vec of vec возможен, но не deque of 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 векторов, Стас решение работает отлично,Но я думаю, что это решение не будет работать для двухсторонней векторной развертки, потому что двухсторонняя очередь не сохраняется непрерывно.Это означает, что вычисление индекса в функторе не выполнено.

Кто-нибудь может это проверить?

1 Ответ

3 голосов
/ 08 декабря 2010

Неважно, какие элементы находятся в векторе.Если вы определите, какие из них должны быть удалены, они будут удалены.

Как вы сказали, вопрос заключается в том, как идентифицировать элемент в векторе.Наиболее очевидный ответ - по его индексу [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.Посмотрите на следующий пример.Это довольно глупо и использует жестко 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
...