Аналог std::map с минимальным расходом памяти

338

01 мая 2017, 03:20

Существует ли аналог std::map с оптимизацией по используемой памяти?

Проблема в том, что std::map в gcc 6.3 имеет размер в 48 байт, и получается большой перерасход памяти на каждый элемент.

Answer 1

В этом мире за все приходится если не платить - то потом расплачиваться...

В map плата взимается не только за скорость, но и универсальность. Если у вас, например, много поисков, а вставка элементов разовая - то можно взять вектор, отсортировать, и потом искать с тем же O(log N), но без лишней траты памяти. Или разработать идеальную хеш-функцию и искать и вовсе за O(1). Словом, знание конкретной задачи может подсказать другие решения.

Но если вам нужно постоянно вставлять, удалять, искать - то бесплатно это не достичь. Либо ценой памяти, либо ценой снижения скорости каких-то операций, либо... Либо все вместе.

Словом, как в том слогане - "Пишем программы быстро, качественно, дешево. Ваше дело - выбрать два нужные критерия из трех..."