I am making a downloading program that shows the user a list of their queued downloads. At the moment I am using

using std::vector;

class download; //defined elsewhere for simplicity here it doesn't matter what it contains

vector<download*> vDownloads;

vDownloads.push_back(blah1);
vDownloads.push_back(blah2);
vDownloads.push_back(blah3);

The problem is that when a download finishes I want to delete it. AFAIK vector likes to keep the elements in consecutive order in the ram, so if I delete the first one, blah2 will go to where blah1 was, blah3 goes to where blah2 was, ... blahN goes to where blahN-1 was. So my implementation is great in its simplicity, but if the downloads are small then there could be 30-40 finishing a second and if there are 5000 downloads then it could drain performance. I think I have made it better by using pointers, but it still seems like a bad way to do it.

So I have been thinking about other implementations. The obvious is a linked list.

class download
{
public:
&tab;download * next;
&tab;...
};

download * head;

This way works nicely, but the problem then is looking for a record (by index say) within it. So I got this idea that I could use a binary tree to sort them by index. Searching for a record within it would be much quicker (I think that is the idea) and like the linked list deleting a record just affects between 1 and 3 other records, not N-1.

class download
{
public:
&tab;download * left;
&tab;download * right;
&tab;...
};

download * head;

So what do you reckon? Is there an even better way to do this that I haven't thought of? I think the biggest problem here is memory management, moving as little as possible.