Как получить индекс элемента из предиката, переданного в некоторый алгоритм STL? - PullRequest
Новая
       16

Как получить индекс элемента из предиката, переданного в некоторый алгоритм STL?

10 голосов
/ 28 февраля 2012

Скажем, у меня есть вектор элементов и массив масок, и я хочу извлечь элементы из вектора с истинно соответствующим значением маски, чтобы отделить вектор.Есть ли способ использовать std::copy_if для этой цели?Проблема в том, что у меня есть только значение элемента внутри предиката, а не итератор , поэтому я не могу знать фактический индекс для адресации массива маски.

Я могунапрямую манипулировать адресами, например так: 

vector<bool> mask;
vector<int> a, b;
copy_if(a.begin(), a.end(), b.begin(), [&] (int x) -> bool { 
  size_t index = &x - &a[0]; // Ugly...
  return mask[index];
});

Однако я считаю это уродливым решением.Есть идеи лучше?

Обновление : еще одно возможное решение - использовать внешний итератор для маски: 

vector<bool> mask;
vector<int> a, b;
auto pMask = mask.begin();
copy_if(a.begin(), a.end(), b.begin(), [&] (int x) { 
  return *pMask++;
});

Однако для этого решения требуется дополнительная переменная во внешнем пространстве имен, которая все ещене желательно.

Ответы [ 2 ]

6 голосов
/ 15 марта 2012

Хорошо, после небольшого исследования я приведу первый пример, который будет самым простым.Однако не следует забывать передавать значение в лямбда-выражении (const), чтобы не брать адрес локальной копии параметра: 

copy_if(a.begin(), a.end(), b.begin(), 
  [&] (const int& x) -> bool {  // <-- do not forget reference here
    size_t index = &x - &a[0];  // Still ugly... but simple
    return mask[index];
  });
2 голосов
/ 28 февраля 2012

Вы можете объединить несколько итераторов из Boost (не проверено, но компилируется с GCC 4.6): 

#include <algorithm>

#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/tuple/tuple.hpp>

int main() {
  std::vector<bool> mask;
  std::vector<int> a, b;
  boost::counting_iterator<size_t> count_begin(0), count_end(a.size());
  auto zip_begin = boost::make_zip_iterator(boost::make_tuple(count_begin, a.begin()));
  auto zip_end = boost::make_zip_iterator(boost::make_tuple(count_end, a.end()));
  typedef decltype(zip_end) zip_iterator;
  typedef const zip_iterator::value_type& zip_value;
  auto pred = [&mask](zip_value val) {
    auto index = val.get<0>();
    return index < mask.size() ? mask[index] : true;
  };
  auto filter_begin = boost::make_filter_iterator(pred, zip_begin, zip_end);
  auto filter_end = boost::make_filter_iterator(pred, zip_end, zip_end);
  std::transform(filter_begin, filter_end, back_inserter(b), [](zip_value val) {
      return val.get<1>();
    });
}

Однако, я думаю, что явный цикл здесь просто проще.

Вот еще одна более обобщенная версия приведенного выше кода, на этот раз даже протестированная :). Он обеспечивает реализации для Python-подобных функций map, filter и enumerate.Для этого требуется GCC 4.7. 

#include <utility>
#include <vector>
#include <iterator>
#include <type_traits>
#include <iostream>

#define BOOST_RESULT_OF_USE_DECLTYPE

#include <boost/tuple/tuple.hpp>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/size.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/counting_range.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/algorithm_ext/push_back.hpp>

template<typename... ForwardRange>
using zip_range = boost::iterator_range<
  boost::zip_iterator<
    boost::tuple<
      typename boost::range_iterator<
        typename std::remove_reference<ForwardRange>::type>::type...>>>;

template<typename... ForwardRange>
zip_range<ForwardRange...>
zip(ForwardRange&&... ranges) {
  return boost::make_iterator_range(
    boost::make_zip_iterator(
      boost::make_tuple(
        boost::begin(std::forward<ForwardRange>(ranges))...)),
    boost::make_zip_iterator(
      boost::make_tuple(
        boost::end(std::forward<ForwardRange>(ranges))...)));
}

template<typename ForwardRange, typename Index>
using enumerating_range = zip_range<
  boost::iterator_range<boost::counting_iterator<Index>>,
  ForwardRange>;

template<typename ForwardRange, typename Index>
enumerating_range<ForwardRange, Index>
enumerate(ForwardRange&& range, Index start) {
  return zip(
    boost::counting_range(
      start,
      static_cast<Index>(start + boost::size(range))),
    std::forward<ForwardRange>(range));
}

template<typename Predicate, typename ForwardRange>
using filter_range = boost::iterator_range<
  boost::filter_iterator<
    Predicate,
    typename boost::range_iterator<
      typename std::remove_reference<ForwardRange>::type>::type>>;

template<typename Predicate, typename ForwardRange>
filter_range<Predicate, ForwardRange>
filter(Predicate pred, ForwardRange&& range) {
  return boost::make_iterator_range(
    boost::make_filter_iterator(
      pred,
      boost::begin(std::forward<ForwardRange>(range))),
    boost::make_filter_iterator(
      pred,
      boost::end(std::forward<ForwardRange>(range))));
}

template<typename UnaryOperation, typename ForwardRange>
using map_range = boost::iterator_range<
  boost::transform_iterator<
    UnaryOperation,
    typename boost::range_iterator<
      typename std::remove_reference<ForwardRange>::type>::type>>;

template<typename UnaryOperation, typename ForwardRange>
map_range<UnaryOperation, ForwardRange>
map(UnaryOperation operation, ForwardRange&& range) {
  return boost::make_iterator_range(
    boost::make_transform_iterator(
      boost::begin(std::forward<ForwardRange>(range)),
      operation),
    boost::make_transform_iterator(
      boost::end(std::forward<ForwardRange>(range)),
      operation));
}

template<typename UnaryOperation, typename Predicate, typename ForwardRange>
using filter_map_range = map_range<
  UnaryOperation,
  filter_range<Predicate, ForwardRange>>;

template<typename UnaryOperation, typename Predicate, typename ForwardRange>
filter_map_range<UnaryOperation, Predicate, ForwardRange>
filter_map(UnaryOperation operation, Predicate pred, ForwardRange&& range) {
  return map(operation, filter(pred, range));
}

int main() {
  std::vector<int> a { 10, 11, 12, 13, 14 };
  std::vector<bool> mask { false, true, true, false, true };
  std::vector<int> b;
  auto enumerator = enumerate(a, 0u);
  typedef boost::range_value<decltype(enumerator)>::type enum_value;
  boost::push_back(
    b,
    filter_map(
      [](const enum_value& val) {
        return val.get<1>();
      },
      [&mask](const enum_value& val) {
        auto i = val.get<0>();
        return i < mask.size() ? mask[i] : true;
      },
      enumerator));
  boost::copy(b, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}

Если вам не нужно использовать векторы, решение становится несколько скучным: 

#include <valarray>
#include <algorithm>
#include <iterator>
#include <iostream>

int main() {
  using namespace std;
  valarray<int> a { 10, 11, 12, 13, 14 };
  valarray<bool> mask { false, true, true, false, true };
  valarray<int> b = a[mask];
  copy(begin(b), end(b), ostream_iterator<int>(cout, " "));
}
...