Какой stl контейнер лучше всего подходит для данной задачи?
У вас описание классической очереди. Попробуйте queue
Так как объекты большие, оверхед списка будет незаметен. Ваше решение достаточно эффективно. Можете, как Дмитрий Ковальский предлагает, использовать адаптер queue (возможно со списком в качестве контейнера если хочется)