Всегда ли карта и набор выделяют 1 предмет за раз? - PullRequest
0 голосов
/ 18 января 2019

Я реализую распределитель для std::map и std::set в C ++ 14. Распределитель должен предоставить функцию pointer allocate(size_type n), которая одновременно выделяет пространство для n элементов.

После некоторых тестов я видел, что std::map и std::set всегда делают allocate(1) на моей платформе, я не видел ни одного n > 1. Это имеет смысл для меня, если я думаю о представлении внутреннего дерева.

Стандарт гарантирует такое поведение? Или я могу безопасно доверять n == 1 всегда на какой-то конкретной платформе?

1 Ответ

0 голосов
/ 18 января 2019

Гарантирует ли стандарт такое поведение?

Нет. Стандарт не гарантирует этого.

Или я могу безопасно доверять == 1 всегда на какой-то конкретной платформе?

Количество выделений при вводе ограничено сложностью методов контейнеров. Например, для std::map::insert стандарт указывает (из cppreference , только первые 3 перегрузки, вставляя один элемент):

1-3) Логарифмический размер контейнера, O (log (size ())).

Тогда разработчики могут свободно выбирать реализацию, которая удовлетворяет этой спецификации. Часть log(size()) состоит в том, что вам нужно найти место, куда вставить и выделить место для фиксированного числа элементов, это просто постоянный вклад в сложность. Реализация может выбрать выделение пространства для двух элементов при каждом втором вызове. 2 так же постоянна, как и 1. Однако не должно быть слишком сложно найти случаи, когда распределение 1 более эффективно, чем распределение 2 в абсолютном выражении. Более того, std::map и std::set не требуются для хранения своих элементов в непрерывной памяти.

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

allocate(n) - это не то же самое, что allocate(1) n раз.

A::allocate(n) должен возвращать один указатель, поэтому нетрудно выделить несмежную память. Однако не требуется, чтобы этот указатель был T*. Вместо этого A::allocate(n) возвращает A::pointer. Это может быть любой тип, если он удовлетворяет NullablePointer, LegacyRandomAccessIterator и LegacyContiguousIterator.

cppreference упоминает boost :: interprocess :: offset_ptr в качестве примера распределения сегментированной памяти. Возможно, вы захотите взглянуть на это. Вот полная цитата:

Необычные указатели

Когда указатель типа элемента не является необработанным указателем, это обычно упоминается как «причудливый указатель». Такие указатели были введены для поддерживают сегментированные архитектуры памяти и используются сегодня для доступа объекты размещены в адресных пространствах, которые отличаются от однородных виртуальное адресное пространство, к которому обращаются необработанные указатели. Пример причудливый указатель - это независимый от адреса адресный указатель boost :: interprocess :: offset_ptr, что позволяет выделить основанные на узлах структуры данных, такие как std :: set в разделяемой памяти и файлы, отображаемые в память, сопоставленные по разным адресам в каждом процессе. Необычные указатели могут использоваться независимо от распределителя, который предоставил их через шаблон класса std :: pointer_traits.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...