В классе 2 основных метода:

1. Сохранение связки имя->ip
2. Получение ip по имени

Код запускаемого приложения является тестом функционала класса.

Допускается считать, что ip - строковое значение.

class DNSCache
{
public:
    void update(const std::string& name, const std::string& ip) = 0;
    std::string resolve(const std::string& name) const = 0;
};

Дополнительно:

1. Реализовать возможность создания класса DNS-кэш только в одном экземпляре на процесс
2. Количество сохраняемых элементов в кэше лимитировано при его создании. В случае вставки нового элемента в уже полностью заполненный кэш необходимо освободить для него места за счет самого старого элемента кэша.
3. Обеспечить корректную работу кэша в многопоточной среде. Адаптировать код запускаемого приложения под многопоточную.
4. Подсчитать сложность методов вставки в кэш и извлечения из кэша
5. Реализовать класс наиболее оптимально по сложности вставки/извлечения и объему хранения.

Допускается использовать последние стандарты C++. Исполняемые файл должен собираться и запускаться в Linux среде.

Поскольку для вставки и извлечения используется unodrered_map, сложность вставки и извлечения пропорциональна O(logN). Присутствует определённый оверхэд по памяти. Помимо неизбежного хранения указателей на поддеревья и хэшей ключей в unordered_map, также используется очередь итераторов для удаления. Этого можно избежать, реализовав специальный аллокатор, который будет циклически выделять участки памяти из заранее выделенного массива фиксированного размера с автоматической чисткой "лишних" данных, но это приведёт к излишнему усложнению кода, возможным проблемам с кроссплатформенностью, а также увеличенному времени удаления элемента, т.к. придётся выполнять поиск элемента, которому принадлежит удаляемый участок памяти. Альтернативно, можно реализовать с нуля бинарное дерево поиска (например, красно-чёрное дерево) с учётом такой аллокации. В тестовом примере можно обратить внимание на наличие некоторого количества ошибок в выводе. Это связано с тем, что адрес успевает стать "самым старым" и удалиться до того как проверка до него дойдёт. Разумеется, чем ближе число параллельных потоков к ограничению размера кэша, тем реже эта ошибка проявляется, полностью исчезая если потоков меньше чем размер кэша.

g++ -pthread -std=c++17 main.cpp -o main