4

如何创建自定义类以使用基于范围的循环遍历 STL 容器中的连续项对？

这是我想要的语法和输出：

std::list<int> number_list;
number_list.push_back(1);
number_list.push_back(2);
number_list.push_back(3);

auto paired_list = Paired(number_list);
for (const auto & pair : paired_list) {
  std::printf("The pair is (%d, %d)\n", *(pair[0]), *(pair[1]));
  // or
  //std::printf("The pair is (%d, %d)\n", *(pair.first), *(pair.second));
}
// output:
// The pair is (1, 2)
// The pair is (2, 3)

我知道需要这些（以及更多），但我无法弄清楚：

template <class T>
class Paired {
  ???
  class iterator {
    ???
  }
  iterator begin() {
    ...
  }
  iterator end() {
    ...
  }
}

不用担心const修饰符。

没有提升。

不要修改或复制容器中的对象。

4

4 回答 4

20

这就是我要做的。

#include <iterator>
#include <utility>

template <typename FwdIt> class adjacent_iterator {
public:
    adjacent_iterator(FwdIt first, FwdIt last)
        : m_first(first), m_next(first == last ? first : std::next(first)) { }

    bool operator!=(const adjacent_iterator& other) const {
        return m_next != other.m_next; // NOT m_first!
    }

    adjacent_iterator& operator++() {
        ++m_first;
        ++m_next;
        return *this;
    }

    typedef typename std::iterator_traits<FwdIt>::reference Ref;
    typedef std::pair<Ref, Ref> Pair;

    Pair operator*() const {
        return Pair(*m_first, *m_next); // NOT std::make_pair()!
    }

private:
    FwdIt m_first;
    FwdIt m_next;
};

template <typename FwdIt> class adjacent_range {
public:
    adjacent_range(FwdIt first, FwdIt last)
        : m_first(first), m_last(last) { }

    adjacent_iterator<FwdIt> begin() const {
        return adjacent_iterator<FwdIt>(m_first, m_last);
    }

    adjacent_iterator<FwdIt> end() const {
        return adjacent_iterator<FwdIt>(m_last, m_last);
    }

private:
    FwdIt m_first;
    FwdIt m_last;
};

template <typename C> auto make_adjacent_range(C& c) -> adjacent_range<decltype(c.begin())> {
    return adjacent_range<decltype(c.begin())>(c.begin(), c.end());
}

#include <iostream>
#include <vector>
using namespace std;

void test(const vector<int>& v) {
    cout << "[ ";

    for (const auto& p : make_adjacent_range(v)) {
        cout << p.first << "/" << p.second << " ";
    }

    cout << "]" << endl;
}

int main() {
    test({});
    test({11});
    test({22, 33});
    test({44, 55, 66});
    test({10, 20, 30, 40});
}

这打印：

[ ]
[ ]
[ 22/33 ]
[ 44/55 55/66 ]
[ 10/20 20/30 30/40 ]

笔记：

  • 我没有对此进行详尽的测试，但它尊重前向迭代器（因为它不会尝试使用 ++、!= 和 * 之外的操作）。

  • range-for 的要求极弱；它不需要转发迭代器应该提供的所有东西。因此，我已经达到了 range-for 的要求，但仅此而已。

  • “NOT m_first”注释与如何接近范围末端有关。从空范围构造的相邻迭代器具有 m_first == m_next，它也是 == last。从 1 元素范围构造的相邻迭代器具有 m_first 指向该元素和 m_next == 最后。从多元素范围构造的相邻迭代器具有指向连续有效元素的 m_first 和 m_next。随着它的增加，最终 m_first 将指向最后一个元素，而 m_next 将是最后一个。next_range 的 end() 返回的内容是从 (m_last, m_last) 构造的。对于一个完全空的范围，这在物理上与 begin() 相同。对于 1+ 元素范围，这在物理上与 begin() 不同，它在我们不做之前一直递增 t 有一个完整的对 - 这样的迭代器有 m_first 指向最后一个元素。但是如果我们根据它们的 m_next 比较迭代器，那么我们会得到正确的语义。

  • “NOT std::make_pair()”注释是因为 make_pair() 衰减，而我们实际上想要一对引用。（我本可以使用 decltype，但 iterator_traits 也会告诉我们答案。）

  • 剩下的主要微妙之处在于禁止将右值作为 make_adjacent_range 的输入（这样的临时人员不会延长他们的生命；委员会正在研究这个问题），并播放 ADL 舞蹈以尊重非成员的开始/结束，以及内置 -在数组中。这些练习留给读者。

于 2013-02-12T09:16:23.060 回答
3

编辑我正在使用transform的 .

使用adjacent_difference.

第二个版本采用二进制函数，将两个值转换为新的（不同的）值：

string make_message(int first, int second) {
    ostringstream oss;
    oss << "The pair is (" << first << ", " << second << ")";
    return oss.str();
}

我们现在可以将相邻对转换为第三个范围。我们将使用ostream_iteratortocout像一个范围：

list<int> numbers;
//...
adjacent_difference(numbers.begin(), numbers.end(),
                    ostream_iterator<string>(cout, "\n"),
                    make_message);

第二次编辑

我在comp.lang.c++.moderated上发现了一个问题，询问为什么标准库中没有更多的“相邻”函数，例如for_each_adjacent. 回复说他们使用std::mismatch.

我认为这将是比实现特殊的相邻迭代器更好的方向。

于 2013-02-12T07:57:43.863 回答
0

试试这个。

#include <list>
#include <iostream>

template<class T, class TIter = typename T::iterator, class TVal = typename T::value_type>
class PairedImpl {
    T& m_t;
public:
    class Iter {
        TIter m_it;
    public:
        Iter(const TIter & it) : m_it(it)  {}

        bool  operator!=(const Iter& it)   {         return m_it != it.m_it; }
        Iter& operator++()                 { ++m_it; return *this; }
        const Iter & operator *() const    {         return *this; }
        const TVal & first()      const    {         return *m_it; }
        const TVal & second()     const    {         return *std::next(m_it); }
    };

    PairedImpl(T& t) : m_t(t) {}

    Iter begin() { return Iter(m_t.begin()); }

    Iter end() {
        TIter end = m_t.end();
        return Iter(m_t.empty() ? end : --end);
    }
};

template<class T>
PairedImpl<T> Paired(T& t) {
    return PairedImpl<T>(t);
}

用法

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(3);
    lst.push_back(4);
    lst.push_back(5);

    for (const auto & pair : Paired(lst)) {
        std::cout << "(" << pair.first() << ", " << pair.second() << ")" << std::endl;
    }
    return 0;
}
于 2013-02-12T08:46:39.600 回答
-1

好的，一个小时没有答案，我想出了一个可行的解决方案。请注意，这使用了我自己的FixedLengthVector，这正是它听起来的样子。

template <class T>
class Grouped {
private:
  // length of grouped objects
  static const unsigned length_ = 2;
  // hold pointer to base container to avoid comparing incompatible iterators
  T * base_container_;
public:
  // constructor
  Grouped(T & base_container) :
      base_container_(&base_container) {
  }
  // iterator
  class iterator {
  private:
    // hold pointer to base container to avoid comparing incompatible iterators
    T * base_container_;
    // hold pointers to objects in base container
    FixedLengthVector<length_, typename T::value_type *> ptr_;
    // hold iterator to last object
    typename T::iterator last_iterator_;
  public:
    // constructor
    iterator(T & base_container, typename T::iterator & it)
        : base_container_(&base_container),
          last_iterator_(it) {
      // set up pointers if possible
      unsigned i = 0;
      // check for end iterator
      if (last_iterator_ == base_container_->end()) {
        ptr_.fill(NULL);
        return;
      }
      // set up first object
      ptr_[0] = &*last_iterator_;
      // set up next objects
      for (unsigned i = 1; i < length_; ++i) {
        ++last_iterator_;
        if (last_iterator_ == base_container_->end()) {
          ptr_.fill(NULL);
          return;
        }
        ptr_[i] = &*last_iterator_;
      }
    }
    // dereference operator
    FixedLengthVector<length_, typename T::value_type *> & operator * (void) {
      assert(ptr_[0] != NULL);
      return ptr_;
    }
    // pre-increment
    iterator & operator ++ (void) {
      // can't increase past end
      assert(last_iterator_ != base_container_->end());
      // find next iterator
      ++last_iterator_;
      if (last_iterator_ == base_container_->end()) {
        ptr_.fill(NULL);
        return * this;
      }
      // cycle pointers left
      for (unsigned i = 1; i < length_; ++i) {
        ptr_[i - 1] = ptr_[i];
      }
      ptr_[length_ - 1] = &*last_iterator_;
      return * this;
    }
    // equality comparison
    bool operator == (const iterator & that) const {
      return base_container_ == that.base_container_ &&
             last_iterator_ == that.last_iterator_;
    }
    // inequality comparison
    bool operator != (const iterator & that) const {
      return !(*this == that);
    }
  };
  // end iterator
  iterator end() {
    return iterator(*base_container_, base_container_->end());
  }
  // begin iterator
  iterator begin() {
    return iterator(*base_container_, base_container_->begin());
  }
};
于 2013-02-12T08:01:10.943 回答