Действительно ли std::unordered_map::erase выполняет динамическое освобождение?
Нетрудно найти информацию о поведении больших операций контейнера stl во времени. Однако мы работаем в жесткой среде реального времени, и у меня гораздо больше проблем с поиском информации об их поведении при использовании памяти кучи.
В частности, ко мне приходил разработчик и спрашивал о std::unordered_map. Нам разрешено быть не в реальном времени при запуске, поэтому он надеялся выполнить .reserve() во время запуска. Тем не менее, он обнаруживает, что во время выполнения он получает переполнение. Он использует операции поиска, вставки и удаления с помощью .erase().
Меня немного беспокоит то, что .reserve() фактически предотвращает более позднее выделение памяти во время выполнения (я действительно не понимаю объяснения того, что он делает с использованием кучи), но, в частности, .erase() я не вижу никаких гарантировать, что он не будет запрашивать динамическое освобождение кучи при вызове.
Итак, вопрос в том, каковы указанные взаимодействия с кучей (если они есть) для std::unordered_map::erase, и если он действительно освобождает память, есть ли какой-то трюк, который можно использовать, чтобы избежать их?
@CoffeeTableEspresso - ИМХО, «определенная реализация» примерно эквивалентна «неопределенной», и это будет нормально в качестве ответа на вопрос, если это правда. Мы должны поддерживать программное обеспечение, которое мы поставляем, в течение десятилетий, поэтому то, что поставщик компилятора может сделать для нас не в реальном времени без предварительного уведомления, не является для нас хорошим решением, и я хотел бы знать, что это происходит.
@TED: «Однако мы работаем в жесткой среде реального времени». Тогда почему вы пытаетесь использовать контейнеры стандартной библиотеки? Они не созданы для таких вещей.
@NicolBolas - мы хорошо справляемся с простыми, такими как std::string, std::vector, std::map и т. д., с оговоркой, что они инициализируются при запуске (когда мы можем работать не в реальном времени), а затем только читать с тех пор (включая такие нюансы, как отказ от использования оператора массива на картах, если вы не уверены, что он там есть). Что касается того, что этот разработчик хочет сделать что-то настолько сложное, да, я разделяю ваши подозрения. Но мне задали вопрос, и я не знал наверняка, что это проблема, поэтому я спрашиваю.
Возможно, вы можете предоставить собственный распределитель.
@appleapple - Верно. У меня есть другие дела, так что это будет "нет" для бедного разработчика.
@ТЕД. В прошлый раз, когда я работал в среде «реального времени» (игры), мы использовали свои собственные пользовательские контейнеры вместо STL, потому что STL продолжала выделять время, которое нам не нравилось.
"implementation defined" is roughly equivalent to "undefined" не совсем. Определяемое реализацией означает, что это задокументированное поведение для вашего компилятора и цепочки инструментов (не обязательно для точной целевой платформы или набора инструкций, которые определяются платформой). Неопределенное поведение вообще не документировано и может зависеть от обстоятельств или особенностей реализации, от порядка компиляции и т.д. Неопределенный является случайным, зависящим от факторов времени выполнения, которые также могут быть случайными.
@Swift-FridayPie - Вы упускаете мою мысль. Они эквивалентны мне, потому что мы должны поддерживать одно и то же программное обеспечение на протяжении десятилетий и использовать несколько компиляторов. Если это не определяется языком, я не могу рассчитывать на поведение, независимо от того, что в настоящее время делает компилятор du jour.
@ТЕД. Я знаю эту боль, да, я в такой же ситуации. После спуска есть определенный этап, когда это больше не вариант. Некоторые платформы имеют собственную реализацию доступа к памяти, поэтому даже самодельный контейнер может быть затронут.
Ответы 2
Стандарт не определяет шаблоны размещения контейнеров как таковые. Они фактически получены из правил аннулирования итератора/ссылки. Например, vector::insert делает недействительными все ссылки только в том случае, если количество вставленных элементов приводит к тому, что размер контейнера превышает его вместимость. Это означает, что произошло перераспределение.
Напротив, единственные операции над unordered_map, которые делают ссылки недействительными, — это те, которые фактически удаляют этот конкретный элемент. Даже перефразирование (которое, вероятно, выделяет память) не делает ссылки недействительными (поэтому reserve ничего не меняет).
Это означает, что каждый элемент должен храниться отдельно от самой хеш-таблицы. Это отдельные узлы (поэтому у него есть интерфейс извлечения node_type), и они должны иметь возможность выделяться и освобождаться по отдельности.
Поэтому разумно предположить, что каждая вставка или стирание представляет по крайней мере одно выделение/освобождение.
Если вы согласны с тем, что узлы продолжают потреблять память даже после того, как они были удалены из контейнера, вы можете довольно легко написать класс Allocator, который в основном превращает освобождение в NOP.
Довольно много систем реального времени в основном выделяют всю память, которую они собираются использовать, заранее, а затем, когда они заканчивают инициализацию, они не выделяют и не освобождают память. Это позволит вам сделать почти то же самое с unordered_map.
Тем не менее, я несколько скептически отношусь к преимуществам в этом случае. Основная сила unordered_map — поддержка вставки и удаления, которые обычно выполняются быстро. Если вы не собираетесь выполнять вставку во время выполнения, велика вероятность, что это не особенно хороший выбор.
Если это коллекция, которая в основном заполняется во время инициализации, а затем используется в основном как есть, с несколькими элементами, которые «удаляются», но больше не вставляются после завершения инициализации, вам, вероятно, будет лучше с простым отсортированным массивом и поиск с интерполяцией (или, если данные распределены чрезвычайно непредсказуемо, может быть бинарный поиск, но поиск с интерполяцией обычно лучше). В этом случае я бы обрабатывал удаление, просто добавляя логическое значение к каждому элементу, указывающее, является ли этот элемент действительным или нет. Сотрите, установив для этого значения значение false. Если вы найдете такое значение во время поиска, вы его просто проигнорируете.
Как правило, мы согласны использовать дополнительную память в обмен на то, что не делаем распределения во время выполнения. Однако, когда наше приложение закрывается, ему необходимо освободить/освободить все свои ресурсы, а у нас нет ОС с тяжелыми процессами, которая бы это обеспечивала, поэтому это должен делать код. Таким образом, мы не можем просто полностью потерять контроль над тем, что выделено.
Кроме того, я как бы спрашиваю о нестандартном поведении здесь. Я, конечно, мог бы сам состряпать распределитель в реальном времени. Кучи реального времени существуют. Тем не менее, я не собираюсь брать на себя дополнительную работу по кодированию, просто отвечаю на вопрос разработчика.
Я думаю, что ваш последний абзац имеет на это право. Основная проблема разработчиков заключается в том, что «ключ», по которому они хотят искать, представляет собой 16-битное целое число, и они не хотят просто выделять огромный разреженный массив. Поэтому они хотели, чтобы хешированный поиск происходил.
@TED: Для 16-битных целых чисел в качестве ключей я бы, по крайней мере, подумал о том, чтобы разбить их на два байта и использовать двухуровневую таблицу, как я описал в старом ответе.
Я считаю, что это определено реализацией. Я бы проверил исходный код любой версии STL, которую вы используете, чтобы подтвердить ваши подозрения.