Есть довольно много вариантов для вас, желательно из STL. Используйте класс для хранения одной строки в объекте класса или в строке, если вы не хотите создавать объекты, если строки достаточно велики и вам не нужен доступ ко всем возвращенным строкам.
1) Использовать вектор - использовать умные указатели (shared_ptr) для создания объектов класса и помещать их в вектор. Из-за копирования, используемого в векторе, я бы использовал shared_ptr. Сортируй позже
2) Используйте карту / набор - Создание и вставка элементов могут быть дорогостоящими, если вы ищете более быстрые вставки. Посмотри, может быть, быстрее.
3) Хэш-карта - вставка и поиск времени лучше, чем карта / набор.