c++ - 基于上下文的 partition_copy

Question

我正在尝试为我的类(class)实现通用过滤模型 AlignedRead .这个想法是，在程序开始时，用户选项确定应将哪个系列的过滤器应用于每个 AlignedRead。 .困难在于一些过滤器是“基于上下文的”，即它们以先前看到的元素为条件。例如，一个基于上下文的过滤器可能是读取是否重复，这需要最后看到的读取(输入必须排序)。

这是我目前所拥有的:

#include <functional>
#include <vector>
#include <algorithm> // std::all_of, std::partition_copy
#include <iterator>  // std::cbegin etc

template <typename BidirectionalIterator>
class ReadFilter
{
public:
    using ContextFreeFilter  = std::function<bool(const AlignedRead&)>;
    using ContextBasedFilter = std::function<bool(const AlignedRead&, BidirectionalIterator,
                                                  BidirectionalIterator)>;

    void register_filter(ContextFreeFilter a_filter);
    void register_filter(ContextBasedFilter a_filter);
    template <typename OutputIterator1, typename OutputIterator2>
    void filter_reads(BidirectionalIterator first, BidirectionalIterator last,
                      OutputIterator1 good_reads, OutputIterator2 bad_reads) const;

private:
    std::vector<ContextFreeFilter> context_free_filters_;
    std::vector<ContextBasedFilter> context_based_filters_;

    bool filter_read(const AlignedRead& the_read, BidirectionalIterator first,
                     BidirectionalIterator previous) const;
};

template <typename BidirectionalIterator>
void ReadFilter<BidirectionalIterator>::register_filter(ContextFreeFilter a_filter)
{
    context_free_filters_.emplace_back(std::move(a_filter));
}

template <typename BidirectionalIterator>
void ReadFilter<BidirectionalIterator>::register_filter(ContextBasedFilter a_filter)
{
    context_based_filters_.emplace_back(std::move(a_filter));
}

template <typename BidirectionalIterator>
template <typename OutputIterator1, typename OutputIterator2>
void ReadFilter<BidirectionalIterator>::filter_reads(BidirectionalIterator first,
                                                     BidirectionalIterator last,
                                                     OutputIterator1 good_reads,
                                                     OutputIterator2 bad_reads) const
{
    BidirectionalIterator previous {first};
    std::partition_copy(first, last, good_reads, bad_reads,
                        [this, first, &previous] (const AlignedRead& the_read) {
                            return filter_read(the_read, first, (previous != first) ? previous++ :
                                               previous);
                        });
}

template <typename BidirectionalIterator>
bool ReadFilter<BidirectionalIterator>::filter_read(const AlignedRead& the_read,
                                                    BidirectionalIterator first,
                                                    BidirectionalIterator previous) const
{
    return std::all_of(std::cbegin(context_free_filters_), std::cend(context_free_filters_),
                       [&the_read] (const auto& filter) {
                           return filter(the_read);
    }) && std::all_of(std::cbegin(context_based_filters_), std::cend(context_based_filters_),
                      [&the_read, first, previous] (const auto& filter) {
                          return filter(the_read, first, previous);
    });
}

这很好用。但是，我想进行两项我觉得比较困难的更改:

1. 支持移动和复制(目前不可能，因为移动会使之前看到的读取无效)。
2. 将过滤后的“好读物”范围传递给基于上下文的过滤器。

注意解决2.自动解决1.我面临的主要困难是大多数情况下一个std::back_insert_iterator用于OutputIterator1 ，它doesn't seem to be possible将其转换为其底层容器迭代器。

我能想到的唯一解决方案是让用户也提供一个正常的迭代器到“好读”的开始，但显然这有其自身的问题。我可以使用一些巧妙的技巧来解决这个问题吗？

编辑我刚刚意识到，即使传递额外迭代器的想法也行不通，因为如果底层容器调整大小，它可能会失效。

我还会考虑一个解决方案，它只跟踪最后一次看到的“好读”。所以基于上下文的过滤器变成了 std::function<bool(const AlignedRead&, const AlignedRead&)> 的形式.

Answer 1

所以我通过创建一个新的后插入器迭代器来解决这个问题，该迭代器可以访问底层容器的 begin 和 end 方法，以及一些 TMP。

这是新的迭代器:

template <typename Container>
class ContextBackInsertIterator :
public std::iterator<std::output_iterator_tag, void, void, void, void>
{
protected:
    Container* container;

public:
    using container_type = Container;
    explicit ContextBackInsertIterator (Container& x) : container(std::addressof(x)) {}
    ContextBackInsertIterator<Container>& operator= (const typename Container::value_type& value)
    { container->push_back(value); return *this; }
    ContextBackInsertIterator<Container>& operator= (typename Container::value_type&& value)
    { container->push_back(std::move(value)); return *this; }
    ContextBackInsertIterator<Container>& operator* ()
    { return *this; }
    ContextBackInsertIterator<Container>& operator++ ()
    { return *this; }
    ContextBackInsertIterator<Container> operator++ (int)
    { return *this; }

    typename container_type::const_iterator begin() const { return container->begin(); }
    typename container_type::const_iterator end() const { return container->end(); }
    typename container_type::const_iterator cbegin() const { return container->cbegin(); }
    typename container_type::const_iterator cend() const { return container->cend(); }
};

template <class Container>
inline
ContextBackInsertIterator<Container> ContextBackInserter(Container& x)
{
    return ContextBackInsertIterator<Container>(x);
}

现在的诀窍是注意对于插入器-迭代器，++ 运算符什么都不做。这个想法是，每次我们看到“好读”时，我们都会在给定输入迭代器的拷贝上使用 ++。如果给定一个 ContextBackInsertIterator，我们可以调用迭代器的 begin 和 end 方法来获取最后插入的元素，如果给定一个普通迭代器我们只是重复迭代器。我通过检查迭代器的 value_type 是否为 void 来静态确定给定的迭代器是否为 ContextBackInsertIterator - 就像插入迭代器一样 -但我承认可能有更好的方法。

template <typename T>
inline
typename std::enable_if<std::is_void<typename T::value_type>::value,
    typename T::container_type::const_iterator>::type
get_first(T first, T last)
{
    return last.begin();
}

template <typename T>
inline
typename std::enable_if<!std::is_void<typename T::value_type>::value, T>::type
get_first(T first, T last)
{
    return first;
}

template <typename T>
inline
typename std::enable_if<std::is_void<typename T::value_type>::value,
    typename T::container_type::const_iterator>::type
get_last(T first, T last)
{
    return (last.begin() != last.end()) ? std::prev(last.end()) : last.begin();
}

template <typename T>
inline
typename std::enable_if<!std::is_void<typename T::value_type>::value, T>::type
get_last(T first, T last)
{
    return (first != last) ? std::prev(last) : last;
}

最后，filter_reads函数变化如下:

template <typename BidirectionalIterator>
template <typename InputIterator, typename OutputIterator1, typename OutputIterator2>
std::pair<OutputIterator1, OutputIterator2>
ReadFilter<BidirectionalIterator>::filter_reads(InputIterator first, InputIterator last,
                                                 OutputIterator1 good_reads,
                                                 OutputIterator2 bad_reads) const
{
    auto good_reads_last = good_reads;
    return std::partition_copy(first, last, good_reads, bad_reads,
        [this, good_reads, &good_reads_last] (const AlignedRead& the_read) {
        if (filter_read(the_read, get_first(good_reads, good_reads_last),
                        get_last(good_reads, good_reads_last))) {
            ++good_reads_last;
            return true;
        }
        return false;
    });
}

如果有人可以对此进行改进，我很乐意接受另一种解决方案。