c++ - 使用外部条件修改序列操作

Question

我经常发现自己在使用一些 STL 容器，并希望根据一些外部条件对其进行修改。我所说的外部是指不能从容器中的对象单独派生的东西。

例如，假设我已经根据一些不仅涉及元素本身的详细标准计算出我想保留容器的哪些元素。保留标志存储在与原始容器大小相同的容器中。现在我想使用 std::remove_if 删除标志为零的那些。我该怎么做？

std::vector<Foo> container_of_foos;
std::vector<int> to_keep(container_of_foos.size(), 0); 
// ... code calculates which foos to keep and stores a flag for each one
// NOTE: the condition relies information external to the Foo class (could be relation to other Foo instances)
auto i_new_end = std::remove_if(begin(container_of_foos), end(container_of_foos), [&to_keep](const Foo& foo) {
    // can't tell whether to keep, because I don't know which object is iterated now
});

Answer 1

使用boost::zip_iterator

boost::zip_iterator 在一组元组迭代器上确实简化了删除。

std::vector<int> numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<bool> selectors = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1};

auto zip_first = boost::make_zip_iterator(
    boost::make_tuple(selectors.begin(), numbers.begin()));
auto zip_last = zip_first + std::min(selectors.size(), numbers.size());

auto removed_first = std::remove_if(zip_first, zip_last, [](const auto& tup) {
  return boost::get<0>(tup) == 0;
});

Live example on Wandbox.

使用算法(非提升)

编写您自己的 remove/remove_if，它接受两个范围(值和选择器)和一个值/谓词。您必须决定如何处理不匹配的距离。一旦您有两个范围处于预期状态，您就可以通过删除来运行压缩。下面是一个压缩范围的示例，该范围使用另一个范围进行过滤，并终止于最短序列。

按值和谓词删除

template <typename FwdIt1, typename FwdIt2, typename ValueType>
auto remove(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2,
            const ValueType value) {
  FwdIt1 curr1 = first1;
  FwdIt2 curr2 = first2;

  for (; curr1 != last1 && curr2 != last2; ++curr1, ++curr2) {
    if (value != *curr2) {
      *first1++ = std::move(*curr1);
      *first2++ = std::move(*curr2);
    }
  }
  return std::make_pair(first1, first2);
}

template <typename FwdIt1, typename FwdIt2, typename Predicate>
auto remove_if(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2,
               Predicate pred) {
  FwdIt1 curr1 = first1;
  FwdIt2 curr2 = first2;

  for (; curr1 != last1 && curr2 != last2; ++curr1, ++curr2) {
    if (!pred(*curr2)) {
      *first1++ = std::move(*curr1);
      *first2++ = std::move(*curr2);
    }
  }
  return std::make_pair(first1, first2);
}

基于容器的压缩(删除和删除)助手

template <typename Container, typename Selector, typename ValueType>
auto compress(Container& values, Selector& selectors, const ValueType& value) {
  const auto remove_iters =
      remove(std::begin(values), std::end(values), std::begin(selectors),
             std::end(selectors), value);
  return std::make_pair(
      values.erase(remove_iters.first, std::end(values)),
      selectors.erase(remove_iters.second, std::end(selectors)));
}

template <typename Container, typename Selector, typename Predicate>
auto compress_if(Container& values, Selector& selectors, Predicate pred) {
  const auto remove_iters =
      remove_if(std::begin(values), std::end(values), std::begin(selectors),
                std::end(selectors), pred);
  return std::make_pair(
      values.erase(remove_iters.first, std::end(values)),
      selectors.erase(remove_iters.second, std::end(selectors)));
}

Live Example on Wandbox.