Ответ 1

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

Ответ 2

Короткий ответ: да, это возможно, но это не тривиально. Вам необходимо определить пользовательский распределитель для вашей карты. Основная идея заключается в том, что ваш пользовательский распределитель выделит один блок памяти для карты. Поскольку для карты требуются новые узлы, распределитель просто назначит им адреса в предварительно выделенном блоке. Что-то вроде этого:

std::map<KeyType, ValueType, std::less<KeyType>, MyAllocator> myMap;

myMap.get_allocator().reserve( nodeSize * numberOfNodes );

Есть ряд проблем, с которыми вам придется иметь дело.

Во-первых, вы не знаете размер каждой карты node или количество распределений, которые карта будет выполнять. Это внутренние детали реализации. Вы можете поэкспериментировать, но вы не можете предположить, что результаты будут выполняться в разных компиляторах (или даже в будущих версиях одного и того же компилятора). Поэтому вам не стоит беспокоиться о распределении "фиксированной" карты размера. Скорее, ваша цель должна заключаться в сокращении количества ассигнований, требуемых для нескольких.

Во-вторых, эта стратегия становится довольно сложной, если вы хотите поддерживать удаление.

В-третьих, не забывайте проблемы с выравниванием памяти. Указатели, которые возвращает ваш распределитель, должны быть правильно выровнены для различных типов объектов, которые будет хранить память.

Все, что было сказано, прежде чем пытаться это сделать, убедитесь, что это необходимо. Распределение памяти может быть очень дорогостоящим, но вы все равно не должны предполагать, что это проблема для вашей программы. Мера, чтобы узнать. Вы также должны рассмотреть альтернативные стратегии, которые естественным образом позволяют предусмотреть выделение. Например, отсортированный список или std:: unordered_map.

Ответ 3

Не уверен, что это ответит на ваш вопрос, но Boost.Container имеет flat_map, в котором вы можете зарезервировать место. По сути, вы можете видеть это как отсортированный вектор пар (ключ, значение). Совет: если вы также знаете, что ваш вход отсортирован, вы можете использовать вставку с подсказкой для максимальной производительности.

Ответ 4

Вы говорите о block allocators. Но его трудно реализовать. Мера, прежде чем думать о таких трудных вещах. Во всяком случае Boost содержит некоторые статьи о реализации блока-распределителя. Или используйте уже реализованную предварительно выделенную карту Stree

Ответ 5

На этот вопрос уже есть несколько хороших ответов, но они упускают некоторые основные моменты.

Инициализируйте карту напрямую

Карта заранее знает размер, если инициализируется напрямую с помощью итераторов:

auto mymap = std::map(it_begin, it_end);

Это лучший способ избежать проблемы. Если вы не осведомлены о реализации, карта может узнать размер заранее от итераторов, и вы переместили проблему в реализацию std::, чтобы беспокоиться о ней.

Вместо этого используйте insert с итераторами, то есть:

mymap.insert(it_begin, it_end);

см.: https://en.cppreference.com/w/cpp/container/map/insert

Остерегайтесь преждевременной оптимизации

но я чувствую, что трачу некоторое вычислительное время.

Это звучит очень похоже на преждевременную оптимизацию (то есть вы не знаете, где находится узкое место - вы догадываетесь или видите проблему, которая на самом деле не одна). Вместо этого сначала измерьте, а затем проведите оптимизацию - повторите, если необходимо.

Распределение памяти уже может быть оптимизировано, в значительной степени

Прокатить свой собственный блок распределения для карты может быть почти бесполезным. В современной системе (к ней я включаю OS/аппаратные средства и уровень языка c++) распределение памяти уже очень хорошо оптимизировано для общего случая, и вы могли бы ожидать незначительного улучшения или вообще не улучшать его, если бы использовали свой собственный распределитель блоков. Даже если вы проявите большую осторожность и поместите карту в один непрерывный массив - хотя это и само по себе улучшение - вы все равно можете столкнуться с проблемой, заключающейся в том, что в конце элементы могут быть расположены в массиве случайным образом (например, порядок вставки) и все равно быть менее дружественным к кешу (это очень зависит от вашего фактического варианта использования - я предполагаю, что набор данных очень большой).

Использовать другой контейнер или стороннюю карту

Если вы все еще сталкиваетесь с этой проблемой - возможно, лучше всего использовать другой контейнер (например, отсортированный std::vector - используйте std::lower_bound для поиска) или использовать стороннюю карту, оптимизированную для использования вами карты. Хороший пример - flat_map из boost - посмотрите этот ответ.

Заключение

1. Пусть std::map беспокоится об этой проблеме.
2. Когда производительность является основной проблемой: используйте структуру данных (возможно, стороннюю), которая лучше всего подходит для того, как используются ваши данные (случайные вставки или массовые вставки/в основном итерация или в основном поиск/и т.д.). Затем вам нужно профилировать и собирать показатели производительности для сравнения.