Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Avoid dangling reference for reverse range-based for-loop implementation

Background and Previous Search

I'm looking for an elegant way to reverse-iterate over a container (e.g. std::vector) using a range-based for-loop in C++14. Searching for a solution I found this Q/A. It basically tells me, that this is not part of the standard library and I have to use boost or implement an adapter myself. I don't want to use boost, so I'm looking for the best own implementation now.

Besides the proposals given in previously mentioned Q/A, I also found this implementation and this blog regarding this topic. Most of the implementations are quite similar and seem quite decent. However they all have a pitfall: As pointed out in this comment you might end up with a dangling reference if you call the reverse-adapter with a temporary object:

for (const auto& v : reverse_iterate(getContainer()))

Regarding the problem with a temporary object in range-based for-loop, this answer really helped my understanding. But what can we do to prevent a dangling reference?

My Solution

Based on this background I'm searching for an implementation that get's rid of this pitfall. In the following implementation I'm using an additional rvalue-reference rx_ to prolong the lifetime of my input parameter iff reverse_iterate is called with rvalue reference.

EDIT: Do not use this solution. It is wrong as pointed out in accepted solution.

template <typename T>
class reverse_range
{
  T &&rx_; // rvalue-reference to prolong livetime of temporary object
  T &x_; // reference to container

public:
  explicit reverse_range(T &x) : rx_(T{}), x_(x) {}
  explicit reverse_range(T &&rx) : rx_(std::move(rx)), x_(rx_) {}

  auto begin() const -> decltype(this->x_.rbegin())
  {
    return x_.rbegin();
  }  
  auto end() const -> decltype(this->x_.rend())
  {
    return x_.rend();
  }
};

template <typename T>
reverse_range<T> reverse_iterate(T &x)
{
  return reverse_range<T>(x);
}
template <typename T>
reverse_range<T> reverse_iterate(T &&rx)
{
  return reverse_range<T>(std::move(rx));
}

Obviously we generate a little overhead of constructing an unused empty container object in the lvalue constructor, but I think that's not too bad. Besides one could probably get rid of this by providing two classes reverse_range_lvalue and reverse_range_rvalue, which each provide the implementation for one of the parameter types...

Questions

Would the above extension solve the dangling reference problem or do I miss something?

Do you have any hints on further problems regarding my code?

Are there better ideas to solve this problem in C++14 or any other (future) version?

like image 966
Don-Umbro Avatar asked Oct 09 '18 13:10

Don-Umbro


1 Answers

That doesn't work. Lifetime extension doesn't work in (that part of) constructors. (It works in the body of the constructor, just not in the member initializer list).

template<class R>
struct backwards_t {
  R r;
  constexpr auto begin() const { using std::rbegin; return rbegin(r); }
  constexpr auto begin() { using std::rbegin; return rbegin(r); }
  constexpr auto end() const { using std::rend; return rend(r); }
  constexpr auto end() { using std::rend; return rend(r); }
};
// Do NOT, I repeat do NOT change this to `backwards_t<std::decay_t<R>>.
// This code is using forwarding references in a clever way.
template<class R>
constexpr backwards_t<R> backwards( R&& r ) { return {std::forward<R>(r)}; }

this does a move when passed an rvalue, and keeps a reference when passed an lvalue.

The trick is that for a forwarding reference T&&, if T&& is an lvalue then T is a reference, and if T&& is an rvalue then T is a value. So we convert lvalues to references (and don't make a copy) while converting rvalues to values (and move the rvalue into said value).

for (const auto& v : backwards(getContainer()))

so that works.

In c++17 you can do a bit "better"; reference lifetime extension can apply to the content of structs if you do aggregate initialization. But I'd advise against it; reference lifetime extension is fragile and dangerous when it breaks.

There is talk in c++20 or later to permit compilers to convert moves into expiring objects into elisions. But I wouldn't bet on it working in an specific case. I also think I saw a paper about marking up ctors and functions with their lifetime dependency information (ie, that the return value depends on the lifetime of an argument), permitting warnings/errors and maybe more generalized lifetime extension.

So this is a known problem. But this is the best generally safe-ish way to solve this today.

like image 148
Yakk - Adam Nevraumont Avatar answered Nov 05 '22 15:11

Yakk - Adam Nevraumont