Is random access and push_back without invalidating the elements possible in C++?

Question

Basically I need to be able to use operations like push_back() + random access a list like std::vector is able to do, while also keeping its pointer validity, like std::list does. Is this possible?

I was working with pointers pointing to various elements inside the list, and while std::vector provides random access to elements, everything invalidates upon push_back().

Answer 1

Perhaps you have heard of a data structure like a hash-linked list? This data structure is an extension of the linked list, which maintains an additional array on top of the normal linked list, the number of elements of this array is the same as the number of elements of the linked list, except that its elements are pointers to the corresponding linked list elements. The advantage of this data structure is that it allows for random access and makes use of fragmented memory. But this seems to be some deviation from your problem description? I'm not sure if this would meet your needs..

Code just like this(I'm very sorry, I had very little time to write the answer so I didn't really compile and run it, maybe the code is still buggy, hahaha):

#include <list>
#include <vector>

templete<typename T>
class CHashList
{
public:
  std::list<T> m_data;
  std::vector<T*> m_pointer;
public:
  void push_back(T newData)
  {
    m_data.push_back(newData);
    m_pointer.push_back(&m_data.back());
  }
  T& operation[](int i)
  {
    return *m_pointer[i];
  }
  // other operations...
};

Hope it can help you.

Answer 2

Boost's stable_vector gives a ready solution for what you ask.

From its documentation:

Like vector, iterators are random access. stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a stable_vector remain valid as long as the element is not erased.