时间戳

首页 > 解决方案 > Round-Robin Iterator 和 STL 的按值传递策略

c++ - Round-Robin Iterator 和 STL 的按值传递策略

问题描述

我正在编写一个迭代器round_robin_iter，它保留了一堆迭代器。无论何时round_robin_iter递增，它都会递增当前迭代器并以循环方式传递到下一个迭代器。这使我可以轻松地交错来自不同容器的项目。然而，随着迭代器数量的增加，我不能再使用 STL 的算法了，round_robin_iter因为 STL 喜欢按值传递迭代器，在这种情况下成本很高。

我解决这个问题的粗略想法是将按reference_wrapper<rouund_robin_iter>值传递给 STL 算法，但这对我来说似乎是一个肮脏的 hack。STL 肯定为我的问题提供了一些更优雅的解决方案，不是吗？

编辑：正如 HolyBlackCat 所指出的，reference_wrapper没有实现正确的接口，所以我必须编写自己的包装器来绕过对round_robin_iter...

EDIT2：根据要求，这是迭代器的粗略骨架：

template<class Iter>
struct round_robin_iterator
{
  using IterList = list<pair<Iter, Iter>>;
  using reference = typename iterator_traits<Iter>::reference;
  IterList others;
  typename IterList::iterator current = others.end();

  bool is_end() const { return current == others.end(); }

  void operator++() {
    if(!others.empty()) {
      if(++(current->first) == current->second)
        current = others.erase(current);
      else ++current;
      if(is_end()) current = others.begin();
    }
  }

  reference operator*() { return *(current->first); }

  void add_iters(const Iter& _begin, const Iter& _end) {
    others.emplace_back(_begin, _end);
    if(others.size() == 1) current = others.begin();
  }

  bool operator!=(const round_robin_iterator& rr_it) const {
    if(!is_end()){
      if(!rr_it.is_end()){
        return current != rr_it.current;
      } else return true;
    } else return !rr_it.is_end();
  }
};

标签： c++stliterator

解决方案

从对问题的非常有用的评论中，我收集了以下内容以将“重”迭代器传递给 STL 算法：

  • 如果我不再需要迭代器，那么我将移动它（通过std::move(iter)）
  • 如果我仍然需要迭代器，那么根据定义，我在某个时候需要 2 个不同的此类迭代器，因此无法避免复制
  • 将“状态”放在堆上并进行浅拷贝似乎假装是一个副本，而实际上是一个动作（或者更糟糕的是，有副作用，比如更改我没有触及的迭代器）

在讨论使用哪个容器来存储迭代器时，我已经对以下底层容器进行了一些基准测试std::accumulate（round_robin_iterators以及如何处理达到其末端的迭代器的策略）：

  1. std::list(O(1)-擦除)
  2. std::vector(O(n)-擦除)
  3. std::deque(O(n)-擦除)
  4. std::vector(O(n)-跳过)
  5. std::deque(O(n)-跳过)

（很抱歉没有std::tuple在基准测试中包含 -version，但我需要动态大小）

基准测试迭代 (a) 1 个大（大小 Z）+ 许多（X-1）个小（大小 Y）范围和（b）许多（X）个逐渐增加的大小范围（从 Y 到 Z）。没有复制（实际上，我删除了std::list-version 的复制构造函数 + 复制赋值），迭代器通过 move 传递。代码可以在这里找到，但要点如下：

  • 存储对象的大小对相对性能几乎没有影响
  • std::list在这种情况下很难被击败，即使 Y 接近 Z
  • std::deque（擦除）节拍std::vector（擦除）大约 X > 100
  • （擦除）几乎总是节拍（跳过）

推荐阅读