avoiding dangling reference in array subscription operator

Question

How to avoid dangling reference in array subscription operator in some vector implementation below? If realloc changes the pointer then references previously obtained from operator[] are no longer valid. I cannot use new/delete for this. I have to use malloc/realloc/free.

template <class T>
class Vector
{
  public:
  typedef size_t size_type_;

  ...

  T& operator[] (const size_type_);
  void push_back (const T&);

  ...

  private:
  const size_type_ page_size_;
  size_type_ size_;
  size_type_ capacity_;
  T* buffer_;
};


template<class T>
inline
T&
some_namespace::Vector<T>::operator[] (const size_type_ index)
{
  ASSERT(index < size_);
  return buffer_[index];
}


template<class T>
inline
void
some_namespace::Vector<T>::push_back(const T& val)
{
  if (size_ >= capacity_)
  {
    capacity_ += page_size_;
    T* temp = (T*)(realloc(buffer_, capacity_*sizeof(T)));

    if (temp != NULL)
    {
      buffer_ = temp;
    }
    else
    {
      free(buffer_);
      throw some_namespace::UnexpectedEvent();
    }
  }

  buffer_[size_++] = val;
}

By the way, the source of dangling reference in the code was this:

v_.push_back(v_[id]);

where v_ is an instance of Vector. To guard against this the new push_back is:

template<class T>
inline
void
some_namespace::Vector<T>::push_back(const T& val)
{
  if (size_ >= capacity_)
  {
    const T val_temp = val; // copy val since it may come from the buffer_
    capacity_ += page_size_;
    T* temp = (T*)(realloc(buffer_, capacity_*sizeof(T)));

    if (temp != NULL)
    {
      buffer_ = temp;
    }
    else
    {
      free(buffer_);
      throw some_namespace::UnexpectedEvent();
    }

    buffer_[size_++] = val_temp;
  }
  else
  {
    buffer_[size_++] = val;
  }
}

Daniel Frey · Accepted Answer · 2013-09-24 20:32:47Z

4

There are basically three things you can do:

Accept it as is and document it. This is what the STL does and it's actually quite reasonable.
Don't return a reference, return a copy. Of course, this means you can't assign to the vector's element anymore (v[42] = "Hello"). In that case you want a single operator[] which is marked const.
Return a proxy object which stores a reference to the vector itself and the index. You add an assignment to the proxy from const T& to allow writing to the vector's element and you need to provide some way to access/read the value, most likely an implicit operator const T&. Since the proxy object asks the vector on each access for the current position of the element, this works even if the vector changed the location of those elements between calls. Just be careful with multi-threading.

Here's a sketch for the proxy, untested and incomplete:

template<typename T> class Vector
{
private:
    // ...

    // internal access to the elements
    T& ref( const size_type_ i );
    const T& ref( const size_type_ i ) const;

    class Proxy
    {
    private:
        // store a reference to a vector and the index
        Vector& v_;
        size_type_ i_;

        // only the vector (our friend) is allowed to create a Proxy
        Proxy( Vector& v, size_type_ i ) : v_(v), i_(i) {}
        friend class Vector;

    public:
        // the user that receives a Proxy can write/assign values to it...
        Proxy& operator=( const T& v ) { v_.ref(i_) = v; return *this; }

        // ...or the Proxy can convert itself in a value for reading
        operator const T&() const { return v_.ref(i_); }
    };

    // the Proxy needs access to the above internal element accessors
    friend class Proxy;

public:
    // and now we return a Proxy for v[i]
    Proxy operator[]( const size_type_ i )
    {
        return Proxy( *this, i );
    }
};

Note that the above is incomplete and the whole technique has some drawbacks. The most significant problem is that the Proxy "leaks" in the API and therefore some use cases are not met. You need to adapt the technique to your environment and see if it fits.

edited Sep 24, 2013 at 20:32

answered Sep 24, 2013 at 6:44

Daniel Frey

57.2k13 gold badges129 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Dimon Over a year ago

Thanks :-). Proxy sounds interesting. Would you have a code snippet for this?

Daniel Frey Over a year ago

@user1806925 I'm having a barbeque right now, will add a sketch for the proxy later...

Daniel Frey Over a year ago

@user1806925 As promised, I added a sketch. Hope it helps.

Dimon Over a year ago

Thanks! I'll try to integrate it tonight. Will let you know

Dimon Over a year ago

Btw. STL vector doesnt cover dangling references? Before putting memory allocation I had an STL vector underneath. Was working just fine. I guess allocation size was bigger?

|

Collectives™ on Stack Overflow

avoiding dangling reference in array subscription operator

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related