Аннулирование ссылки после применения reverse_iterator на заказном итераторе
Я реализовал двунаправленный итератор, однако вместо того, чтобы работать со структурой данных, он возвращает математический ряд, который можно итеративно вычислять в обоих направлениях. На самом деле, я перебираю целые числа, используя ++ и — в 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 приводит к нарушениям памяти, как это правильно обнаруживает 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)
Другая ветвь не приводит к нарушениям памяти, или, по крайней мере, так, как мой валгринд может обнаружить. Однако значение, сохраненное в векторе, является «случайным»:
--decrement
*dereference
-16777520
Я немного удивлен тем, что происходит. Итератор должен постоянно находиться в области видимости, но ссылка, похоже, становится недействительной. Почему я получаю нарушения памяти, в то время как 12 напечатано или почему я не получаю их, пока что-то отличается от 12 хранится?
Решение
reverse_iterator не работает с так называемыми «скрывающими итераторами», итераторами, которые возвращают ссылки на вещи внутри себя. operator* из reverse_iterator создает копию обернутого итератора, уменьшает его и возвращает результат разыменования копии. Следовательно, если разыменовывающий итератор возвращает ссылку на что-то внутри себя, ссылка становится висячей.
В спецификации C ++ 11 была предпринята попытка заставить его работать, но оказалось, что это невозможно реализовать без значительных накладных расходов.* для незапоминающихся итераторов, так спецификация была возвращена к версии C ++ 03.
* Чтобы поддерживать «скрывающие итераторы», необходимо добавить дополнительный элемент данных, который хранит уменьшенный текущий итератор, удваивая размер reverse_iterator; и тогда должна использоваться какая-то форма синхронизации, так как operator * является const — и поэтому должен одновременно вызываться из нескольких потоков, не вызывая гонки данных, — но должен изменить этот дополнительный элемент данных. Это много накладных расходов, чтобы добавить ко всем reverse_iterators для такого необычного варианта использования.
Другие решения
Как уже упоминалось, стандарты 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 классификатор на 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, ","));