Что содержит параметр, присвоенный имени unordered_map<>?
Я просматривал отличную статью Марка Нельсона об алгоритме сжатия LZW и нашел в коде кое-что, с чем еще не сталкивался.
В коде он использовал unordered_map для хранения строк и их соответствующей частоты. Декларация карты была:
std::unordered_map<std::string, unsigned int> codes( (max_code * 11)/10 );
max_code хранит максимальное количество записей на карте, т.е. 32767. Код:
void compress( INPUT &input, OUTPUT &output, const unsigned int max_code = 32767 )
{
//code
}
Я не знаю, какой параметр имеет беззнаковое значение int, связанное с codes. Кроме того, может ли кто-нибудь просветить меня, почему значение max_code умножается на 11, а затем делится на 10?
Вот функция сжатия для справки:
template<class INPUT, class OUTPUT>
void compress( INPUT &input, OUTPUT &output, const unsigned int max_code = 32767 )
{
input_symbol_stream<INPUT> in( input );
output_code_stream<OUTPUT> out( output, max_code );
std::unordered_map<std::string, unsigned int> codes( (max_code * 11)/10 );
for ( unsigned int i = 0 ; i < 256 ; i++ )
codes[std::string(1,i)] = i;
unsigned int next_code = 257;
std::string current_string;
char c;
while ( in >> c ) {
current_string = current_string + c;
if ( codes.find(current_string) == codes.end() ) {
if ( next_code <= max_code )
codes[ current_string ] = next_code++;
current_string.erase(current_string.size()-1);
out << codes[current_string];
current_string = c;
}
}
if ( current_string.size() )
out << codes[current_string];
}
@Ranoiaetep Я не думаю, что ты получил мой вопрос. Если у меня есть map<string,int>m(1000) . Что такое 1000?
@mandybuot У тебя std::unordered_map, а не std::map. Целочисленный аргумент конструктора — это начальное количество сегментов для реализации хеш-таблицы, используемой std::unordered_map. Как говорится в комментарии выше, он должен быть порядка ожидаемого размера карты по соображениям производительности, чтобы избежать раннего перефразирования. Вернее, он должен быть немного больше, поэтому он умножается на 1,1. Это не скомпилируется для std::map.
Ответы 1
Шаблон типа std::unordered_map имеет ряд конструкторов , которые принимают size_type; обычно std::size_t, который является целым числом без знака. Это значение связано с семантикой или, скорее, типичной реализацией неупорядоченной карты в виде набора хэшей. Из ссылки выше:
explicit unordered_map(size_type bucket_count,
const Hash& hash = Hash(),
const key_equal& equal = key_equal(),
const Allocator& alloc = Allocator() );
- Создает пустой контейнер. Устанавливает для max_load_factor() значение 1,0. Для конструктора по умолчанию количество сегментов определяется реализацией.
...
Bucket_count — минимальное количество сегментов для использования при инициализации. Если он не указан, используется значение по умолчанию, определяемое реализацией.
Он служит индикатором того, сколько данных вы ожидаете от контейнера. Это, конечно, не будет идеальным из-за хеш-коллизий. Но это служит подсказкой для контейнера о том, сколько памяти нужно выделить, аналогично тому, что сделал бы std::vector::reserve().
Я предполагаю, что, выбрав немного больше, чем вам на самом деле нужно, здесь 1,1, вы с большей вероятностью избежите перераспределения на уровне корзины. 1.1 звучит для меня слишком консервативно, я мог бы выбрать 1.5 или выше. Но, возможно, были проведены эксперименты, чтобы определить, какой запас прочности использовать.
32767 - это максимальное значение для int16, что в основном является максимальным размером, который он хочет, чтобы словарь рос.