Действительно ли std::unordered_map::erase выполняет динамическое освобождение?

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

В частности, ко мне приходил разработчик и спрашивал о std::unordered_map. Нам разрешено быть не в реальном времени при запуске, поэтому он надеялся выполнить .reserve() во время запуска. Тем не менее, он обнаруживает, что во время выполнения он получает переполнение. Он использует операции поиска, вставки и удаления с помощью .erase().

Меня немного беспокоит то, что .reserve() фактически предотвращает более позднее выделение памяти во время выполнения (я действительно не понимаю объяснения того, что он делает с использованием кучи), но, в частности, .erase() я не вижу никаких гарантировать, что он не будет запрашивать динамическое освобождение кучи при вызове.

Итак, вопрос в том, каковы указанные взаимодействия с кучей (если они есть) для std::unordered_map::erase, и если он действительно освобождает память, есть ли какой-то трюк, который можно использовать, чтобы избежать их?

Я считаю, что это определено реализацией. Я бы проверил исходный код любой версии STL, которую вы используете, чтобы подтвердить ваши подозрения.

CoffeeTableEspresso 18.11.2022 21:33

@CoffeeTableEspresso - ИМХО, «определенная реализация» примерно эквивалентна «неопределенной», и это будет нормально в качестве ответа на вопрос, если это правда. Мы должны поддерживать программное обеспечение, которое мы поставляем, в течение десятилетий, поэтому то, что поставщик компилятора может сделать для нас не в реальном времени без предварительного уведомления, не является для нас хорошим решением, и я хотел бы знать, что это происходит.

T.E.D. 18.11.2022 21:36

@TED: «Однако мы работаем в жесткой среде реального времени». Тогда почему вы пытаетесь использовать контейнеры стандартной библиотеки? Они не созданы для таких вещей.

Nicol Bolas 18.11.2022 21:37

@NicolBolas - мы хорошо справляемся с простыми, такими как std::string, std::vector, std::map и т. д., с оговоркой, что они инициализируются при запуске (когда мы можем работать не в реальном времени), а затем только читать с тех пор (включая такие нюансы, как отказ от использования оператора массива на картах, если вы не уверены, что он там есть). Что касается того, что этот разработчик хочет сделать что-то настолько сложное, да, я разделяю ваши подозрения. Но мне задали вопрос, и я не знал наверняка, что это проблема, поэтому я спрашиваю.

T.E.D. 18.11.2022 21:42

Возможно, вы можете предоставить собственный распределитель.

apple apple 18.11.2022 21:45

@appleapple - Верно. У меня есть другие дела, так что это будет "нет" для бедного разработчика.

T.E.D. 18.11.2022 21:46

@ТЕД. В прошлый раз, когда я работал в среде «реального времени» (игры), мы использовали свои собственные пользовательские контейнеры вместо STL, потому что STL продолжала выделять время, которое нам не нравилось.

CoffeeTableEspresso 18.11.2022 22:03
"implementation defined" is roughly equivalent to "undefined" не совсем. Определяемое реализацией означает, что это задокументированное поведение для вашего компилятора и цепочки инструментов (не обязательно для точной целевой платформы или набора инструкций, которые определяются платформой). Неопределенное поведение вообще не документировано и может зависеть от обстоятельств или особенностей реализации, от порядка компиляции и т.д. Неопределенный является случайным, зависящим от факторов времени выполнения, которые также могут быть случайными.
Swift - Friday Pie 19.11.2022 12:10

@Swift-FridayPie - Вы упускаете мою мысль. Они эквивалентны мне, потому что мы должны поддерживать одно и то же программное обеспечение на протяжении десятилетий и использовать несколько компиляторов. Если это не определяется языком, я не могу рассчитывать на поведение, независимо от того, что в настоящее время делает компилятор du jour.

T.E.D. 20.11.2022 03:35

@ТЕД. Я знаю эту боль, да, я в такой же ситуации. После спуска есть определенный этап, когда это больше не вариант. Некоторые платформы имеют собственную реализацию доступа к памяти, поэтому даже самодельный контейнер может быть затронут.

Swift - Friday Pie 21.11.2022 17:00
Как настроить Tailwind CSS с React.js и Next.js?
Как настроить Tailwind CSS с React.js и Next.js?
Tailwind CSS - единственный фреймворк, который, как я убедился, масштабируется в больших командах. Он легко настраивается, адаптируется к любому...
LeetCode запись решения 2536. Увеличение подматриц на единицу
LeetCode запись решения 2536. Увеличение подматриц на единицу
Увеличение подматриц на единицу - LeetCode
Переключение светлых/темных тем
Переключение светлых/темных тем
В Microsoft Training - Guided Project - Build a simple website with web pages, CSS files and JavaScript files, мы объясняем, как CSS можно...
Отношения "многие ко многим" в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel могут быть немного сложными, но с помощью Eloquent ORM и его моделей мы можем сделать это с легкостью. В этой...
В PHP
В PHP
В большой кодовой базе с множеством различных компонентов классы, функции и константы могут иметь одинаковые имена. Это может привести к путанице и...
Карта дорог Беладжар PHP Laravel
Карта дорог Беладжар PHP Laravel
Laravel - это PHP-фреймворк, разработанный для облегчения разработки веб-приложений. Laravel предоставляет различные функции, упрощающие разработку...
1
10
70
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Стандарт не определяет шаблоны размещения контейнеров как таковые. Они фактически получены из правил аннулирования итератора/ссылки. Например, vector::insert делает недействительными все ссылки только в том случае, если количество вставленных элементов приводит к тому, что размер контейнера превышает его вместимость. Это означает, что произошло перераспределение.

Напротив, единственные операции над unordered_map, которые делают ссылки недействительными, — это те, которые фактически удаляют этот конкретный элемент. Даже перефразирование (которое, вероятно, выделяет память) не делает ссылки недействительными (поэтому reserve ничего не меняет).

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

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

Если вы согласны с тем, что узлы продолжают потреблять память даже после того, как они были удалены из контейнера, вы можете довольно легко написать класс Allocator, который в основном превращает освобождение в NOP.

Довольно много систем реального времени в основном выделяют всю память, которую они собираются использовать, заранее, а затем, когда они заканчивают инициализацию, они не выделяют и не освобождают память. Это позволит вам сделать почти то же самое с unordered_map.

Тем не менее, я несколько скептически отношусь к преимуществам в этом случае. Основная сила unordered_map — поддержка вставки и удаления, которые обычно выполняются быстро. Если вы не собираетесь выполнять вставку во время выполнения, велика вероятность, что это не особенно хороший выбор.

Если это коллекция, которая в основном заполняется во время инициализации, а затем используется в основном как есть, с несколькими элементами, которые «удаляются», но больше не вставляются после завершения инициализации, вам, вероятно, будет лучше с простым отсортированным массивом и поиск с интерполяцией (или, если данные распределены чрезвычайно непредсказуемо, может быть бинарный поиск, но поиск с интерполяцией обычно лучше). В этом случае я бы обрабатывал удаление, просто добавляя логическое значение к каждому элементу, указывающее, является ли этот элемент действительным или нет. Сотрите, установив для этого значения значение false. Если вы найдете такое значение во время поиска, вы его просто проигнорируете.

Как правило, мы согласны использовать дополнительную память в обмен на то, что не делаем распределения во время выполнения. Однако, когда наше приложение закрывается, ему необходимо освободить/освободить все свои ресурсы, а у нас нет ОС с тяжелыми процессами, которая бы это обеспечивала, поэтому это должен делать код. Таким образом, мы не можем просто полностью потерять контроль над тем, что выделено.

T.E.D. 18.11.2022 22:11

Кроме того, я как бы спрашиваю о нестандартном поведении здесь. Я, конечно, мог бы сам состряпать распределитель в реальном времени. Кучи реального времени существуют. Тем не менее, я не собираюсь брать на себя дополнительную работу по кодированию, просто отвечаю на вопрос разработчика.

T.E.D. 18.11.2022 22:14

Я думаю, что ваш последний абзац имеет на это право. Основная проблема разработчиков заключается в том, что «ключ», по которому они хотят искать, представляет собой 16-битное целое число, и они не хотят просто выделять огромный разреженный массив. Поэтому они хотели, чтобы хешированный поиск происходил.

T.E.D. 18.11.2022 22:16

@TED: Для 16-битных целых чисел в качестве ключей я бы, по крайней мере, подумал о том, чтобы разбить их на два байта и использовать двухуровневую таблицу, как я описал в старом ответе.

Jerry Coffin 18.11.2022 22:45

Другие вопросы по теме