Отсортированные строки

Условие

Реализуйте класс, поддерживающий набор строк в отсортированном порядке. Класс должен содержать два публичных метода:

class SortedString {
 public:
    void AddString(const std::string& s);
    std::vector<std::string> GetSortedString() const;
};

Добавление строки должно выполняться за логарифмическое время по числу строк, а передача вектора строк - за линейное.

Ограничения

• Строки содержат только буквы латинского алфавита и цифры
• Длина строки от 1 до 15
• Количество строк от 0 до 500000
• Максимальное время на добавление всех строк и последующий вызов GetSortedString: 2 секунды

Как тестировать локально

Собрать программу с помощью cmake и запустить ctest:

mkdir build; cd build
cmake ..; cmake --build .
ctest -V