Se il problema è la memoria, userei una lista, che occupa il minimo di memoria possibile.
Se il problema è il tempo di accesso allora la lista è fuori discussione, decisamente meglio il vector.
Comunque, come ti ha già detto MItaly sopra di me, un vector è quasi sicuramente la soluzione che cerchi, a condizione che ti ricordi di usare reserve().