Il tuo manuale di C++ dovrebbe parlarne ...
1) In genere si sa quanto è grande, perchè durante la chiamata a malloc o a new si passa il numero di byte da allocare.
2) Sarebbe più corretto fare:
codice:
VERTEX *m_vertexs[256] = NULL;
int i = 0;

VERTEX *v = new VERTEX();
m_vertexs[i++] = v; //element 0
VERTEX *v = new VERTEX();
m_vertexs[i++] = v; //element 1

/*...codice...*/

delete m_vertexs[0];
delete m_vertexs[1];
o meglio: utilizzare una lista o un puntatore a puntatore.

Ti consiglio vivamente di leggerti un libro che ti spieghi bene i puntatori.
Io purtroppo non ne conosco, gli ho imparati con l'esperienza.
Forse il K&R ne parla bene, adesso non ricordo ...