在自定义迭代器上应用reverse_iterator后，引用无效 [英] Reference invalidation after applying reverse_iterator on a custom made iterator

问题描述

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

I implemented a bidirectional iterator, however instead of operating on a data structure, it returns a mathematical series which one can iteratively calculate through in both directions. In fact, I'm iterating through the integers, using ++ and -- on an int. This means that the data is not stored in a different structure, and hence when the iterator goes out of scope, so does the value.

不过，我希望下一个代码（最小的失败示例）示例可以正常工作，因为迭代器始终处于作用域内。但这不起作用：（

Nevertheless, I would expect the next code (minimal failing example) sample to work, as the iterator stays in scope the whole time. But it does not work :(

#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分支会导致内存冲突，因为由valgrind正确检测：

The if-branch results in memory violations, as properly detected by 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分支不会导致内存冲突，或者至少不会影响我的valgrind。但是，向量中存储的值是随机：

The else-branch doesn't result in memory violations, or at least as far as my valgrind can detect. However, the value stored in the vector is 'random':

--decrement
*dereference
-16777520

我对发生的事情感到有些惊讶。迭代器应该一直处于作用域内，但该引用似乎已失效。为什么在打印12时出现内存冲突，或者为什么在存储不同于12的内存时却没有内存冲突？

I'm a bit surprised by what happens. The iterator should be in scope all the time, yet the reference seems to get invalidated. Why do I get the memory violations, whilst 12 is printed or why don't I get them whilst something different from 12 is stored?

推荐答案

reverse_iterator 不适用于所谓的隐藏迭代器，即迭代器返回对自身内部事物的引用。 reverse_iterator 的 operator * 制作包装的迭代器的副本，将其递减，然后返回解引用该副本的结果。因此，如果取消对迭代器的引用返回对自身内部内容的引用，则该引用将变得悬而未决。

reverse_iterator does not work with so-called "stashing iterators", iterators that returns references to things within themselves. The operator* of reverse_iterator makes a copy of the wrapped iterator, decrements it, and returns the result of dereferencing the copy. Hence, if dereferencing iterator returns a reference to something inside itself, the reference will become dangling.

在C ++ 11规范中曾试图使其工作，但是事实证明，如果不为非隐藏式迭代器添加大量开销 ^* ，就不可能实现，因此规范已还原为C ++ 03版本。

An attempt was made in the C++11 specification to make it work, but it turns out that it's impossible to implement without adding massive overhead^* for non-stashing iterators, so the specification was reverted to the C++03 version.

_{^* 为了支持隐藏式迭代器，必须添加一个额外的数据成员来存储递减的当前迭代器，使 reverse_iterator ;然后必须使用某种形式的同步，因为 operator * 是 const -因此必须可以同时从多个线程调用而不引起数据争用-但必须修改此其他数据成员。对于这种不常见的用例，要添加到所有 reverse_iterator 中会产生很大的开销。}

_{^* To support "stashing iterators", an additional data member must be added that stores the decremented current iterator, doubling the size of reverse_iterator; and then some form of synchronization must be used since operator * is const - and so must be simultaneously callable from multiple threads without causing a data race - but must modify this additional data member. That's a lot of overhead to add to all reverse_iterators for such an uncommon use case.}

这篇关于在自定义迭代器上应用reverse_iterator后，引用无效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！