6

我实现了一个双向迭代器，但是它不是在数据结构上操作，而是返回一个数学序列，可以在两个方向上迭代计算。事实上，我正在遍历整数，在 int 上使用 ++ 和 -- 。这意味着数据不会存储在不同的结构中，因此当迭代器超出范围时，值也会如此。

尽管如此，我希望下一个代码（最小的失败示例）示例能够工作，因为迭代器始终保持在范围内。但它不起作用:(

#include <iostream>
#include <iterator>
#include <vector>

class my_iterator : public std::iterator<std::bidirectional_iterator_tag, int> {
  int d_val = 12;
public:
  my_iterator  operator--(int) { std::cout << "decrement--\n"; return my_iterator(); }
  my_iterator &operator--()    { std::cout << "--decrement\n"; return *this; }
  my_iterator  operator++(int) { std::cout << "increment++\n"; return my_iterator(); }
  my_iterator &operator++()    { std::cout << "++increment\n"; return *this; }

  int &operator*() { std::cout << "*dereference\n"; return d_val; }

  bool operator==(my_iterator const  &o) { return false; }
  bool operator!=(my_iterator const  &o) { return true ; }
};


int main() {
  auto it = std::reverse_iterator<my_iterator>();
  int &i = *it;
  if (true)
  {
    std::cout << i << '\n';
  }
  else
  {
    std::vector<int> vec;
    vec.push_back(i);
    std::cout << vec[0] << '\n';
  }
}

来源：http: //ideone.com/YJKvpl

if-branch 导致内存冲突，正如 valgrind 正确检测到的那样：

--decrement
*dereference
==7914== Use of uninitialised value of size 8
==7914==    at 0x4EC15C3: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4EC16FB: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4EC1C7C: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4ECEFB9: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x40087B: main (divine.cc:25)
==7914== 
==7914== Conditional jump or move depends on uninitialised value(s)
==7914==    at 0x4EC15CF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4EC16FB: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4EC1C7C: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4ECEFB9: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x40087B: main (divine.cc:25)
==7914== 
==7914== Conditional jump or move depends on uninitialised value(s)
==7914==    at 0x4EC1724: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4EC1C7C: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x4ECEFB9: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
==7914==    by 0x40087B: main (divine.cc:25)
==7914== 
12
==7914== 
==7914== HEAP SUMMARY:
==7914==     in use at exit: 0 bytes in 0 blocks
==7914==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==7914== 
==7914== All heap blocks were freed -- no leaks are possible
==7914== 
==7914== For counts of detected and suppressed errors, rerun with: -v
==7914== Use --track-origins=yes to see where uninitialised values come from
==7914== ERROR SUMMARY: 5 errors from 3 contexts (suppressed: 0 from 0)

else-branch 不会导致内存冲突，或者至少在我的 valgrind 可以检测到的范围内。但是，存储在向量中的值是“随机的”：

--decrement
*dereference
-16777520

我对发生的事情感到有些惊讶。迭代器应该一直在范围内，但引用似乎变得无效。为什么在打印 12 时会出现内存违规，或者为什么在存储与 12 不同的内容时我没有得到它们？

4

2 回答 2

10

reverse_iterator不适用于所谓的“存储迭代器”，即返回对自身内部事物的引用的迭代器。operator*of复制包装的迭代器，将其reverse_iterator递减，并返回取消引用该副本的结果。因此，如果解引用迭代器返回对自身内部某物的引用，则该引用将变得悬空。

在 C++11 规范中进行了尝试以使其工作，但事实证明，如果不为非存储迭代器增加大量开销*是不可能实现的，因此规范被恢复为 C++03 版本。

*为了支持“存储迭代器”，必须添加一个额外的数据成员来存储递减的当前迭代器，使 ; 的大小增加一倍reverse_iterator。然后必须使用某种形式的同步，因为operator *is const- 因此必须可以同时从多个线程调用而不会导致数据竞争 - 但必须修改这个额外的数据成员。reverse_iterator对于这种不常见的用例，添加到所有 s 中会产生很多开销。

于 2015-02-19T01:20:56.843 回答
1

如前所述，C++03 和 C++14 标准reverse_iterator::operator*以这种方式定义：

24.5.1.3.4 operator*[reverse.iter.op.star]

reference operator*() const;

1 效果：

Iterator tmp = current;
return *--tmp;

tmp返回后被销毁operator*，因此对存储在其中的数据的任何引用都tmp将变为无效。C++11 标准改变了这一点并添加了一个注释：

24.5.1.3.4 operator*[reverse.iter.op.star]

reference operator*() const;

1 效果：

deref_tmp = current;
--deref_tmp;
return *deref_tmp;

2 [注意：此操作必须使用辅助成员变量而不是临时变量，以避免返回持续超过其关联迭代器生命周期的引用。（见 24.2。）——尾注]

这实际上是不可能实现的，因为const限定符 on operator*，所以在 C++11 和 C++14 之间的措辞被恢复了。

reverse_iterator最好的解决方案可能是根据 C++11 的措辞为您所针对的任何 C++版本实现您自己的版本。幸运的是，该规范非常简单易懂。作为一个工作示例，这是我为 C++14 编写的示例：

template <class Iterator>
class stashing_reverse_iterator :
  public std::iterator<
    typename std::iterator_traits<Iterator>::iterator_category,
    typename std::iterator_traits<Iterator>::value_type,
    typename std::iterator_traits<Iterator>::difference_type,
    typename std::iterator_traits<Iterator>::pointer,
    typename std::iterator_traits<Iterator>::reference
  > {
  typedef std::iterator_traits<Iterator> traits_type;
public:
  typedef Iterator iterator_type;
  typedef typename traits_type::difference_type difference_type;
  typedef typename traits_type::reference       reference;
  typedef typename traits_type::pointer         pointer;

  stashing_reverse_iterator() : current() {}

  explicit stashing_reverse_iterator(Iterator x) : current(x) {}

  template <class U>
  stashing_reverse_iterator(const stashing_reverse_iterator<U>& u) : current(u.current) {}

  template <class U>
  stashing_reverse_iterator& operator=(const stashing_reverse_iterator<U>& u) {
    current = u.base();
    return *this;
  }

  Iterator base() const {
    return current;
  }

  // Differs from reverse_iterator::operator*:
  // 1. const qualifier removed
  // 2. current iterator is stored in a member field to ensure references are
  //    always valid after this function returns
  reference operator*() {
    deref_tmp = current;
    --deref_tmp;
    return *deref_tmp;
  }

  pointer operator->() const {
    return std::addressof(operator*());
  }

  stashing_reverse_iterator& operator++() {
    --current;
    return *this;
  }

 stashing_reverse_iterator operator++(int) {
    stashing_reverse_iterator tmp = *this;
    --current;
    return tmp;
  }

  stashing_reverse_iterator& operator--() {
    ++current;
    return *this;
  }

  stashing_reverse_iterator operator--(int) {
    stashing_reverse_iterator tmp = *this;
    ++current;
    return tmp;
  }

  stashing_reverse_iterator  operator+ (difference_type n) const {
    return stashing_reverse_iterator(current - n);
  }

  stashing_reverse_iterator& operator+=(difference_type n) {
    current -= n;
    return *this;
  }

  stashing_reverse_iterator  operator- (difference_type n) const {
    return stashing_reverse_iterator(current + n);
  }

  stashing_reverse_iterator& operator-=(difference_type n) {
    current += n;
    return *this;
  }

  // Differs from reverse_iterator::operator[]:
  // 1. const qualifier removed because this function makes use of operator*
  reference operator[](difference_type n) {
    return *(*this + n);
  }

protected:
  Iterator current;
private:
  Iterator deref_tmp;
};

template <class Iterator1, class Iterator2>
bool operator==(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return x.base() == y.base(); }

template <class Iterator1, class Iterator2>
bool operator<(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return x.base() > y.base(); }

template <class Iterator1, class Iterator2>
bool operator!=(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return !(x.base() == y.base()); }

template <class Iterator1, class Iterator2>
bool operator>(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return x.base() < y.base(); }

template <class Iterator1, class Iterator2>
bool operator>=(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return x.base() <= y.base(); }

template <class Iterator1, class Iterator2>
bool operator<=(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y)
{ return x.base() >= y.base(); }

template <class Iterator1, class Iterator2>
auto operator-(
  const stashing_reverse_iterator<Iterator1>& x,
  const stashing_reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base())
{ return y.base() - x.base(); }

template <class Iterator>
stashing_reverse_iterator<Iterator> operator+(
  typename stashing_reverse_iterator<Iterator>::difference_type n,
  const stashing_reverse_iterator<Iterator>& x)
{ return stashing_reverse_iterator<Iterator>(x.base() - n); }

template <class Iterator>
stashing_reverse_iterator<Iterator> make_stashing_reverse_iterator(Iterator i)
{ return stashing_reverse_iterator<Iterator>(i); }

用法与以下相同reverse_iterator：

// prints 5,4,3,2,1, for a sanely implemented number_iterator
std::copy(
  make_stashing_reverse_iterator(number_iterator(5)),
  make_stashing_reverse_iterator(number_iterator(0)),
  std::ostream_iterator<int>(std::cout, ","));
于 2015-11-22T05:32:00.340 回答