In C++, how can I get a pointer into a vector?

Question

I'm writing some C++ code that manipulates a bunch of vectors that are changing in size and are thus being reallocated constantly.

I would like to get a "pointer" into these vectors that remains valid even after reallocation of the vector. More specifically, I just want these "pointers" to remember which vector they point into and the index to which they point. When I dereference them using the standard (*ptr) syntax, I just want them to do the obvious lookup.

Obviously, actual pointers will not be valid after reallocation, and my understanding is that iterators aren't valid after reallocation either. Note also that I don't care if elements are inserted before my objects, so these "pointers" really don't have to remember anything but a vector and an index.

Now, I could easily write such a class myself. Has anyone (Boost? STL?) done it for me already?

Edit: The answers don't address my question. I asked if this functionality is any standard library. I take the responses as a "no"?

Answer 1

Unfortunately, once you modify the vector, the iterators that would "point" to an element of the vector are no longer guaranteed to be valid. The only STL structure that I know of which will keep the iterators valid even as the structure is changing is the list<>. If you only want sequential iteration of your structures than you can use std::list<> otherwise I do not know of any other library that can help you; that doesn't mean there isn't one.

Here's some clear documentation on std::list : http://www.cplusplus.com/reference/stl/list/

Answer 2

Unless you write your own version of vector and smart pointer there is no way that a pointer will be valid after a reallocation. If you had your own implementations the smart vector could send notifications to your smart pointers.

However I think that the whole scenario is a bad design and you might be better of redesigning your scenario so that you don't have a requirement like that.

Answer 3

An article on persistent iterators, complete with implementation.

Answer 4

Try a std::pair< vector*, int>, as neither the position of the vector nor the index of the element changes.
Or, as a class:

template<class T> class VectorElementPointer
{
  vector<T>& vectorref;
  vector<T>::size_type index;
public:
  VectorElementPointer(vector<T>& vref, vector<T>::size_type index):vectorref(vref),index(index){}
  T& operator*() const {return vectorref[index];}
  T* operator->() const {return &vectorref[index];}
};

This is the easiest solution that comes to my mind, as neither the STL nor Boost contains anything to do it easier.

Answer 5

Depending on your use pattern, a std::deque may fufil your requirements. Pointers into a deque are only invalidated if you insert or delete items not at the beginning or end - in pother words push_front() and push_back() don't invalidate pointers into the deque, but other changes do. You get basically the same interface as a vector, but of course the underlying storage is not contiguous.

Answer 6

To summarize some ideas. Here is the minimalist wrapper that tries to mimic iterators but stay valid as opposite to vector's ones.

void print(const std::string& i)
{
    std::cout << "<" << i << "> ";
}
int main()
{
    typedef std::vector<std::string> Vector;

    Vector v;
    v.push_back("H");
    v.push_back("E");
    v.push_back("W");
    StrongIterator<Vector> it0(v, 0);
    StrongIterator<Vector> it3(v, v.end());

    std::for_each(it0.it(), it3.it(), print);
    std::cout << std::endl;

    v.push_back("O");
    std::for_each(it0.it(), it3.it(), print);

    std::cout << *it0;
    std::cout << it0->c_str();

    return 0;
}

And the iterator itself.

template <typename TVector>
class StrongIterator
{
public:
    typedef typename TVector::iterator iterator;
    typedef typename TVector::size_type size_type;
    typedef typename TVector::value_type value_type;
    StrongIterator(TVector& vector,
                   size_type index):
        vector_(vector),
        index_(index)
    {}
    StrongIterator(TVector& vector,
                   iterator it):
        vector_(vector),
        index_(std::distance(vector.begin(), it))
    {}
    iterator it()
    {
        iterator it = vector_.begin();
        std::advance(it, index_);
        return it;
    }
    value_type& operator*()
    {
        return vector_[index_];
    }
    value_type* operator->()
    {
        return &vector_[index_];
    }
private:
    TVector& vector_;
    size_type index_;
};

Answer 7

Using boost::iterator_facade :

// Warning: Untested, not even compiled
template<class VectorT>
class VectorIndex : 
    public boost::iterator_facade<VectorIndex, typename VectorT::reference, boost::random_access_traversal_tag>
{
public:
    VectorIndex(VectorT& Vec, typename VectorT::size_type Index)
    : m_Vec(Vec), m_Index(Index)
    {
    }

private:
    friend class boost::iterator_core_access;

    void increment()
    {
        ++m_Index;
    }

    void decrement()
    {
        --m_Index;
    } 

    void advance(difference_type N)
    {
        m_Index += N;
    }

    difference_type distance_to(const VectorIndex& Other)
    {
        assert(&this->m_Vec == &Other.m_Vec);
        return Other.m_Index = this->m_Index; 
    }

    bool equal(const VectorIndex& Other)const
    {
        return (this->m_Vec == Other.m_Vec)
            && (this->m_Index == Other.m_Index);
    }

    VectorT::reference dereference() const 
    {
        return m_Vec[m_Index];
    }

    VectorT m_Vec;
    VectorT::size_type m_Index;
};