I strongly recommend rethinking using a bare vector.
My reason for that is that you need to guarantee that that the memory of the vector is never reallocated. Note that you also should in any case make sure that your vector is made sure to allocate all required memory from the start, either by initializing with empty elements or by using std::vector::reserve.
Otherwise, if you have a pointer already set and then change the capacity of the vector, the pointer becomes invalid, a good setup if you want undefined behaviour.
Therefore I strongly advise you to use a wrapper class around your vector, which makes sure no capacity change is ever called.
Now, if you do that, the thing is, why do you use actual pointers?
Consider using data of type std::vector<std::pair<T, size_t> >, with the second entry actually storing the position within the vector, rather than an actual pointer:
template<class T>
class PointingVector
{
public:
PointingVector(const std::vector<T>& vec);
private:
std::vector<std::pair<T, size_t> > data;
};
template<class T>
PointingVector<T>::PointingVector(const std::vector<T>& vec)
{
for (int i=0; i<vec.size()-1; i++)
{
data.push_back(std::make_pair(vec[i], i+1));
}
data.push_back(std::make_pair(vec.back(), 0)); // assuming that the last points to the first
}
After that, make sure that every additional method you add leaves the pointing consistent. Like should you write something similar to erase, make sure that all pairs are updated accordingly.
And the analogy to dereferencing is trivial:
template<class T>
std::pair<T, size_t>& PointingVector<T>::get(size_t index)
{
return data[index];
}
The important thing about my solution is that you can exclude possible bugs in regard to dangling pointers. Those are really bad, especially since they might not cause an error in test executions, given the nature of undefined behaviour. Worst thing in my solution is that the indices are wrong after calling a method that has a bug.
And if you want to introduce anything that changes the capacity of the vector, no problem, no need to redo any pointers. Just make sure the indices are changed accordingly. If you did this with pointers, your first step would probably be to create a list of indices anyway, so why not work with one directly.
Plus, as this solution has no (visible) pointers at all, you don't need to do any memory management.
Another solution: Ditch std::pair and define your own type:
template<class T>
struct Node
{
T data;
Node* next; // or a smart pointer type
Node(const T& data, Node* next) : data(data), next(next) {}
};
Then build up your vector like this:
template<class T>
std::vector<Node<T>*> createPointingVector(const std::vector<T>& vec)
{
std::vector<Node<T>*> new_vec;
for (int i=0; i<vec.size(); i++)
{
new_vec.push_back(new Node<T>(vec[i], nullptr));
}
for (int i=0; i<vec.size()-1; i++)
{
new_vec[i]->next = new_vec[i+1];
}
new_vec[vec.size()-1]->next = new_vec[0];
return new_vec;
}
Note that without smart pointers, you need to do memory management. I'd consider making next a weak_ptr<Node>, and have the vector be over shared_ptr<Node>. That way, the memory is automatically deallocated as soon as the vector gets deleted (assuming you have no other pointers active).
