如何创建过滤向量的迭代器？

问题描述 投票：0回答：5

假设我有一个名为 

spot_deals
的 
SpotDeal
向量，它是一个类：

class SpotDeal
{
public:
    int deal_id_; // primary key, and vector is sorted by id
    string ccy_pair_; // ccy pair, e.g. GBPUSD, AUDUSD
    double amount_;
}

假设我需要将 

spot_deals
的两个子集传递给函数 
foo
进行一些计算。我可以复印，但是，这会消耗内存和时间。实际上 
foo
只需要交易的迭代器。那么我可以制作 2 个 
vector<SpotDeal>
的迭代器，即 
it1
和 
it2
并将它们传递给 
foo
吗？

spot_deals
的两个子集可以通过
ccy_pair_
过滤，例如GBPUSD 和 AUDUSD 交易，或按其他条件。所以我正在寻找一种方法来定义由向量和 lambda 函数定义的迭代器（不过也可以等效为函子）。

有没有办法编写一个辅助函数

make_filtered_iterator
，这样我就可以得到像下面这样的东西？

auto it1 = make_filtered_iterator(spot_deals, filter_lambda1);
auto it2 = make_filtered_iterator(spot_deals, filter_lambda2);
foo(it1, it2);
c++ lambda filter iterator containers
5个回答
6
投票

答案当然是“是”。 STL 风格的 C++ 迭代器可以执行各种操作。 一个常见但基本的方法是为 

std::map
创建一个迭代器，当取消引用时，它只给出键或值。

在您的特定情况下，简单的实现可能如下所示：

template <typename BaseIterator>
struct filtered_iterator : BaseIterator
{
    typedef std::function<bool (const value_type&)> filter_type;

    filtered_iterator() = default;
    filtered_iterator(filter_type filter, BaseIterator base, BaseIterator end = {})
        : BaseIterator(base), _end(end), _filter(filter) {
        while (*this != _end && !_filter(**this)) {
            ++*this;
        }
    }

    filtered_iterator& operator++() {
        do {
            BaseIterator::operator++();
        } while (*this != _end && !_filter(**this));
        return *this;
    }

    filtered_iterator operator++(int) {
        filtered_iterator copy = *this;
        ++*this;
        return copy;
    }

private:
    BaseIterator _end;
    filter_type _filter;
};

template <typename BaseIterator>
filtered_iterator<BaseIterator> make_filtered_iterator(
        typename filtered_iterator<BaseIterator>::filter_type filter,
        BaseIterator base, BaseIterator end = {}) {
    return {filter, base, end};
}

我为 

end
设置了默认值，因为通常您可以为此使用默认构造的迭代器。 但在某些情况下，您可能只想过滤容器的子集，在这种情况下指定结尾会很容易。

4
投票

是的，可以创建迭代器类型。 然而，我怀疑你的问题是 XY 问题的一个例子（https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem） - 你想找到一种不同的操作方法在向量的两个子集 (X) 上，已决定解决方案必须涉及实现专用迭代器 (Y)，并询问如何执行 Y 而不是 X。我将提供一个选项来执行 X，而无需做Y.

我建议使用标准算法

std::stable_partition()
将容器分为两个范围会更容易。

 auto false_partition = std::stable_partition(your_vector.begin(), your_vector.end(), your_filter);

向量的 

begin()
和 
end()
迭代器不会改变（即不会失效），但它们之间的元素被重新组织为两个范围，使得 
your_filter
返回 
true
的元素位于集合之前
your_filter
返回 
false
的元素的数量。因此，
false_partition
同时是第一个范围的“过去结束”迭代器，也是第二个范围的开始。 每个范围中元素的顺序与原始向量中的顺序相同。

这些可以按如下方式使用

 //   a loop to operates on the elements for which your_filter returned true

 for (auto i = your_vector.begin(); i != false_partition; ++i)
 {
      // do whatever
 }

 //   a loop to operates on the elements for which your_filter returned false

 for (auto i = false_partition; i != your_vector.end(); ++i)
 {
      // do whatever
 }

在 C++11 之前，

auto
关键字可以替换为适当的迭代器类型（例如 
std::vector<int>::iterator
或 
std::vector<int>::const_iterator
，具体取决于您是否希望使用迭代器更改元素）。

3
投票

我可能会建议这个问题的观众参加 Eric Nibbler 的 rangev3 速成课程，因为这是 C++20 标准库采用的范例。

https://github.com/ericniebler/range-v3

如何进行过滤器迭代：

for (auto element : spot_deals | views::filter([](auto i) { return condition(i); }))
{ //....
}
3
投票

我不会使用指向原始向量的迭代器，因为它们无法传达子集的大小。 （基本上，每个子集还需要一个迭代器来表示子集的末尾。）从 C++20 开始，我将使用 Ranges 库中的 ranges，如 v.oddou 中所述 回答。更具体地说，对于您的用例，我将使用范围适配器

std::views::filter
，如下所示：

auto gbpusd = [](const auto& sd) { return sd.ccy_pair_ == "GBPUSD"; };
auto audusd = [](const auto& sd) { return sd.ccy_pair_ == "AUDUSD"; };

auto range1 = spot_deals | std::views::filter(gbpusd);
auto range2 = spot_deals | std::views::filter(audusd);

foo(range1, range2);

此解决方案不会为过滤后的现货交易创建临时向量，因为视图适配器创建不包含元素的范围。生成的范围 

range1
和 
range2
只是向量 
spot_deals
的视图，但具有自定义的迭代行为。

foo()
的声明有点棘手，因为范围的数据类型非常复杂。因此，我将使用占位符类型 
auto
作为函数参数，从而使 
foo()
成为 函数模板:

void foo(auto& r1, auto& r2) {
    for (auto const& sd : r1)
        std::cout << sd.deal_id_ << std::endl;
    for (auto const& sd : r2)
        std::cout << sd.amount_ << std::endl;
}

（或者，您可以通过引用 

spot_deals
来传递 
foo()
并在 
foo()
内声明过滤范围。）

Wandbox 上的代码

2
投票

碰巧，我最近正在研究这个问题。事实证明，过滤是容器上众多操作中最复杂的，也包含最多的陷阱。

template<typename Range, typename Pred>
class filter
{
public:
    friend class const_iterator;
    class const_iterator : public std::iterator_traits<typename Range::const_iterator>
    {
        using underlying = typename Range::const_iterator;
    public:
        auto operator*() {return *u;}
        const_iterator& operator++()
        {
            ++u;
            normalize();
            return *this;
        }
        const_iterator operator++(int)
        {
            auto t = *this;
            u++;
            normalize();
            return t;
        }
        bool operator==(const const_iterator& rhs) const {return u == rhs.u;}
        bool operator!=(const const_iterator& rhs) const {return !(*this == rhs);}
    private:
        friend filter;
        const_iterator(underlying u, const filter& f) : u{std::move(u)}, f{f} {normalize();}
        void normalize()
        {
            for(; u != f.r.end() && !f.p(*u); u++);
        }

        underlying u;
        const filter& f;
    };

    filter(const Range& r, const Pred& p) : r{r}, p{p} {}

    auto begin() const {return const_iterator{r.begin(), *this};}
    auto end() const {return const_iterator{r.end(), *this};}

private:
    const Range& r;
    Pred p;
};

我们将其用作（带有 c++17 指南）

vector<int> v{1, 2, 3, 4, 5};
auto f = filter(v, [](int x){return x & 1;});
for(auto i : f)
    // all i in v that is odd

让我解释一下其中的陷阱：

  • 第一个元素可能被过滤掉，
    *r.begin()
    可能不是过滤范围内的元素。这意味着必须在构造时检查迭代器。
  • r.end()
    可能会在不使其他迭代器失效的情况下失效，也就是说，在任何迭代器中保存 
    r.end()
    的副本进行比较是一个逻辑错误。
  • operator==
    不是很简单，引用原始范围中不同元素的两个底层迭代器可能引用过滤视图中的同一元素，因为过滤出的元素不算作元素。
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.