2

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

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

1
  • 1
    Аналог есть, не столь быстрый, да. Это массив ключ-значение. Всего 16 байт на элемент, если ключ и значение - указатели, для amd64. Это, кстати, не смешно. Все зависит от задачи. Поиск по значению (в вашем случае это ключ) в упорядоченном массиве имеет такую же логарифмическую сложность, как и поиск в map.
    – user239133
    Commented 28 апр. 2017 в 21:45

1 ответ 1

5

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

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

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

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

3
  • 1
    Добавлю, что идеальная хеш-функция — это не сарказм, а реально существующий термин. Commented 29 апр. 2017 в 6:48
  • @Arhad Ну, я именно это и имел в виду :)
    – Harry
    Commented 29 апр. 2017 в 7:51
  • 2
    мы-то знаем; а те, для кого такое понятие в новинку, попросту не поймут. Вот и пояснил. Commented 29 апр. 2017 в 7:54

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.