The system I'm thinking of using is one that has a std::vector<PathData> that I allocate say 20 elements.
A unit can then requests a path , in doing so it recieves a ticketID that it later uses to poll the path manager for its path.
This ticketID is the array index of the fixed size vector container of paths, each path has a reference count of how many units
are following it. When this count is 0 we can reuse that element. The down side is I have to always search for a empty element
and also do it for evey path request could be heaps due to its a RTS game.
I've created a class PathManager, while doing so I keep saying to my self that there must be a neater way to go about this, and
this leads me to this post. If anyone has any ideas I would love to here them thanks Dan.

//here is my path manager class its only a prototype
[source]
//------------------------------------------------------------------------------------
//this class we fill in when we create a new path
//we keep the start and end cell pointers as reference and a list of path points
//keeps track of how many units are usint this path we can remove them when where done
//can only use a path when valid is true
//------------------------------------------------------------------------------------
class PathData
{
public:
DWORD NumberInuse;//how many units are following this path we remove paths after not in use
std::list<D3DXVECTOR3> path;
cCell *StartCell;
cCell *EndCell;

bool Valid;//if false the path is not yet built
PathData(void)
{
StartCell = NULL;
EndCell = NULL;
Valid = false;//when the path is created true
NumberInuse = 0;
}//end ctor
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
~PathData(void)
{
}//end dctor
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////

void AddUser(void){NumberInuse++;}
void RemoveUser(void){NumberInuse--; if(NumberInuse < 0) NumberInuse = 0;}

};//end class PathData
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////




//-----------------------------------------------------------------------------------------
//this class will hold and create paths a path is a PathData we will
//hold a vector of these and the ticket will be the index to the vector of paths
//if the distance from the start and end cells are with in some range of any paths in the list
//it will use that path and not create a new path this way we dont create multiple paths with a group
//selection say
//the size needs to be set so we can find empty slots based on the valid array index
//this way we dont remove elements we reuse them, if there is now room it will try to free
//up a slot first
//the ticket number will not change due to removale
//-----------------------------------------------------------------------------------------
class cRTSPathManager
{
private:
//private members
std::vector<PathData> PathList;//holds created paths the indext(ticket) comes from this lists size

public:
//PUBLIC FUNCTIONS
//-----------------------------------------------------------------------------
//how many path we want to create
//-----------------------------------------------------------------------------
cRTSPathManager(UINT numberpaths);
~cRTSPathManager(void);

//----------------------------------------------------------------------------
//call this to summit a path request it will return a ticket number used to
//Identifie the path, because the path may not be ready straght away
//samepathdistance is used to see is a path is allready created or near the location
//returns -1 on errors
//-----------------------------------------------------------------------------
UINT PathRequest(cCell *StartCell, cCell *EndCell, float samepathdistance);


//------------------------------------------------------------------------------------
//you need to call this when a unit leaves the path to remove its reference
//------------------------------------------------------------------------------------
void RemoveRequest(UINT ticketid);

};//end class cRTSPathManager
/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////


//-----------------------------------------------------------------------------
//how many path we want to create
//-----------------------------------------------------------------------------
cRTSPathManager::cRTSPathManager(UINT numberpaths)
{
PathList.resize(numberpaths, PathData());
}//end destructor
////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////



//----------------------------------------------------------------------------------------------
//
//-----------------------------------------------------------------------------------------------
cRTSPathManager::~cRTSPathManager(void)
{
}//end destructor
////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////





//----------------------------------------------------------------------------
//call this to summit a path request it will return a ticket number used to
//Identifie the path, because the path may not be ready straight away
//samepathdistance is used to see is a path is allready created or near the location
//returns -1 on errors
//-----------------------------------------------------------------------------
UINT cRTSPathManager::PathRequest(cCell *StartCell, cCell *EndCell, float samepathdistance)
{
UINT index = -1;
bool startnodesame = false;
bool endnodesame = false;
//we need to see if there is a path near our start and end
for(UINT ctr =0; ctr < PathList.size(); ctr++)
{
//check distance from the current path cell with the new request to see if we can use this path
//check start cell range
D3DXVECTOR3 t = PathList[ctr].StartCell->Centre - StartCell->Centre;
float dist = D3DXVec3LengthSq(&t);
if(dist <= samepathdistance)
{
//we can use the start
startnodesame = true;
}
//check the end cell
t = PathList[ctr].EndCell->Centre - EndCell->Centre;
dist = D3DXVec3LengthSq(&t);
if(dist <= samepathdistance)
{
//we can use the start
endnodesame = true;
}

//if end node same and start node same is true then we can use this path
if(endnodesame && startnodesame)
{
PathList[ctr].AddUser();
return ctr;//this is our slot
}//end using this path
}//end for all paths memorey slots
///////////////////////////////////////////////////////////////////////

//if we get to here there is no path we can use so we need to find a empty slot
for(UINT ctr =0; ctr < PathList.size(); ctr++)
{
if(PathList[ctr].NumberInuse <= 0)
{
//here is our slot
PathList[ctr].AddUser();
PathList[ctr].path.clear();
PathList[ctr].StartCell = StartCell;
PathList[ctr].EndCell = EndCell;
PathList[ctr].Valid = false;
//create a path here
return ctr;
}
}//end
//if we are here we have a problem we need to free some slots up
for(UINT ctr =0; ctr < PathList.size(); ctr++)
{
if(PathList[ctr].NumberInuse <= 0)
{
//here is our slot
PathList[ctr].Valid = false;
PathList[ctr].path.clear();
PathList[ctr].StartCell = StartCell;
PathList[ctr].EndCell = EndCell;
//we freed this slot add the request
PathList[ctr].AddUser();
//create the path here
return ctr;//this is the next fee slot
}
}//end
//now if we get here we are done for
return index;//error -1

}//end PathRequest
////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////





//------------------------------------------------------------------------------------
//you need to call this when a unit leaves the path to remove its reference
//------------------------------------------------------------------------------------
void cRTSPathManager::RemoveRequest(UINT ticketid)
{
UINT Error = -1;
if(Error == ticketid)
return;//not valid
if(ticketid > PathList.size())
return;//error
//ok its valid
PathList[ticketid].RemoveUser();
}//end RemoveRequest
////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////

[/source]

Why use a fixed-length array and manage what's being used yourself? You are effectively implementing a poor man's allocator. Try using shared pointers instead (for the reference count), and let the usual allocator do the work for you.