Array of pointers data structure Does this data structure make sense? It's essentially a vector of pointers, intended to point to larger objects. In effect, it gives the benefit of a linked list, with an \$O(1)\$ lookup at the cost of maintaining an array of pointers to each element. 

What edge cases am I missing, and what's the formal name of this data structure? (What's the standard data structure used in such situations?) 

#include&lt;iostream&gt;
#include&lt;vector&gt;
using namespace std;
template &lt;class T&gt;
class pointerArray
{

    vector&lt;void*&gt; addresses;
    public:
    pointerArray(int initialSize=100)
    {
        addresses.resize(initialSize);
    }
    ~pointerArray()
    {
        for(unsigned int i=0;i&lt;addresses.size();i++)
        {
            if(addresses[i]!=0)
            {
                delete (T*)addresses[i];
            }
        }
    }
    T&amp; operator[](unsigned int pos)
    {
        if(pos &gt;= addresses.capacity())
        {
            addresses.resize(pos*2);
        }
        if(addresses[pos] == 0)
        {
            T* ptr = new T;
            addresses[pos] = ptr;
        }
        return *(T*)(addresses[pos]);

    }
};


int main()
{
    pointerArray&lt;string&gt; pa(100);
    for(int i=0;i&lt;10000;i++)
    {
        pa[i]="Hello World This Is a Very Long String";
    }
    for(int i=0;i&lt;10000;i++)
    {
        cout&lt;&lt;pa[i]&lt;&lt;endl;
    }
}
I don't think that this data structure has any special name(vector of pointers sounds reasonable). 

Now about the code itself: 


I do not see any reason to use void* pointers here and cast them explicitly every time you access an element. You can just use vector&lt;T*&gt; addresses and get rid of all casts. You can also use smart pointers(unique_ptr looks like a good choice here). Here is my version of this class:

template&lt;class T&gt;
class PointerArray {
public:
    PointerArray(size_t initialSize = 100): array(initialSize) {}

    T&amp; operator[](size_t pos) {
        if (pos &gt;= array.size()) {
            size_t newSize = std::max(pos + 1, 2 * pos);
            array.resize(newSize);
        }
        if (!array[pos]) {
            array[pos] = std::unique_ptr&lt;T&gt;(new T()); // or std::make_unique in C++14
        } 
        return *array[pos];
    }

private:
    std::vector&lt;std::unique_ptr&lt;T&gt;&gt; array;
};


There no need for a custom destructor anymore(unique_ptr handles it).
Note that I have added this line: int newSize = std::max(pos + 1, 2 * pos);. Why is it necessary? We need it when the initialSize is 0 and so is pos. 
In this line: if(pos &gt;= addresses.capacity()), you should be comparing pos to the vector's size, not capacity(because it is an undefined behavior to access elements of the vector beyond size). 
More general notes: 


using namespace std; is a bad practice. There is no need to pollute global namespace. 
Binary operators are usually surrounded with whitespaces. It is also conventional to have an empty line between different functions to improve readability. 

And the last one: do have good reasons to use this data structure? In my opinion, as long as a simple std::vector&lt;T&gt; works fine, there is no need to invent any new data structures.