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

Question

假设我有一个名为 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只需要交易的迭代器。那么我能否创建vector<SpotDeal>的2个迭代器，即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);

- athos

---

@wallyk 你好，我在寻找一种实现 make_filtered_iterator 帮助函数的方法... 目前还没有可尝试的内容... - athos

你看过http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/filter_iterator.html吗？ - perreal

@perreal 感谢指出这一点.. 但 Boost 有点太重了，我正在尝试使用 STL。 - athos

Answer 1

答案肯定是“是的”。按照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_type) {
        while (*this != _end && !_filter(**this)) {
            ++*this;
        }
    }

    filtered_iterator& operator++() {
        do {
            BaseIterator::operator++();
        } while (*this != _end && !_filter(**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的默认值，因为通常情况下你可以使用一个默认构造的迭代器。但在某些情况下，您可能只想筛选容器的子集，在这种情况下指定结束位置会更加方便。

- John Zwinck

---

我对 BaseIterator end = {} 有点困惑。据我理解，通常情况下，end 迭代器位于容器的最后一个真实元素之后，因此内存中该地址对于不同的容器对象是不同的，并且它仅用于地址比较（即该地址中的内容无效）。那么这样的迭代器如何通过空括号进行默认构造呢？ - athos

@athos：这取决于容器。在某些情况下，iterator()可用作“end”，而在其他情况下则不行。如果您不喜欢默认设置，请将其删除。 - John Zwinck

如果你因为我指出的某些问题而编辑了你的代码，你应该提到这一点。 - Passer By

好的。看来我需要更多地了解迭代。谢谢！ - athos

@PasserBy：我想要感谢NYU的Mark Meretzky，他让我领悟到C++迭代器可以做基本上任何事情。你的留言让我注意到了原始代码中的一个错误，但是那段代码完全没有经过测试，所以这对演示来说并不重要。 - John Zwinck

“Bug”只是实际逻辑的一半，它决定了你的实现是否合理。而无论规模大小，承认错误都是基本的礼貌。 - Passer By

Answer 2

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

我建议使用标准算法std::stable_partition()来将容器分成两个范围，这样会更容易。

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

vector的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，具体取决于您是否希望使用迭代器更改元素）。

- Peter

---

谢谢您的回复，但我的问题是这样的：假设我有一个字符串 AakkafdBlkjfDadfkljXafd，我想生成一个 map<char, string>，如 {['A', "akkafd"], ['B', "lkjf"], ['D', "adfklj"], ['X', "afd"]}。 - athos

感谢确认您提供了一个XY问题，尽管X与我预期的不同。您真的不需要为此创建特殊的迭代器。您所描述的是一个微不足道的解析练习，您已经过度思考了。基本算法：查找大写字母。从空字符串开始。将输入中的字符附加到字符串中，直到找到另一个大写字母或输入结束。执行your_map[uppercase_letter] = copied_string。重复此过程直到完成。您可以使用单个迭代器引用输入字符串的元素来完成此操作。 - Peter

如何找到“下一个”大写字符？当然，这可以通过循环完成，但我正在尝试提出一种STL风格的解决方案。 - athos

“STL风格的解决方案”（无论您认为它是什么意思）并不一定意味着创建时髦的迭代器。请查看各种标准算法的规范。您很可能能够使用标准算法的组合来实现您想要的功能 - 这将被视为“STL风格的解决方案”。关键是以尽可能简单和清晰的方式实现您想要的内容。 - Peter

Answer 3

我建议这个问题的观众们学习Eric Nibbler的rangev3，因为这是C++20标准库采用的范例。

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

如何进行过滤迭代：

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

- v.oddou

Answer 4

最近我恰好处理了这个问题。结果发现，过滤是容器中最复杂的操作之一，也包含最多陷阱。

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==不是非常直观，两个指向原始范围中不同元素的底层迭代器可能指向过滤视图中的同一元素，因为过滤掉的元素不算作元素。

- Passer By

---

auto operator*() { return *u; } 出现了编译错误，提示 "error C3551: expected a trailing return type"，这是不是需要对代码进行修改以适应 VS2013？ - athos

@athos 你需要使用C++14或更高版本。 - Passer By

当我使用这段代码并将带有捕获的lambda作为第二个参数传递给filter()时，我遇到了segfaults。可以通过将filter::p的类型从const Pred＆更改为非引用的Pred来解决此问题。 - BdON003

Answer 5

我不会使用指向您原始向量的迭代器，因为它们无法传达您子集的大小。（基本上，您需要每个子集一个以上的迭代器来表示子集的末尾。）自C++20以来，我会使用Ranges库中提到的范围工作，如v.oddou's答案中所述。更具体地说，针对您的用例，我会使用范围适配器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()成为一个function template。

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上查看：Code on Wandbox）

- honk