Boost или stl api для хеширования массива строк в виде строки => индекс-массива

Question

Я ищу повышение или STL API, который имитирует этот:

https://mxr.mozilla.org/mozilla-central/source/xpcom/ds/nsStaticNameTable.h

Короче говоря, чтобы улучшить производительность поиска, он создает карту (хеш) из массива строк (char*), в котором ключами являются индексы массива.

Я знаю, что это легко реализовать поверх других API.

Answer 1

Прежде всего, вы отметили, что текущая реализация является особенно медленной? Вы должны всегда тестировать, прежде чем пытаться оптимизировать.

Во всяком случае, казалось бы, что boost::bimap<> это то, что вы просили. Затем вы просто заменяете массив на boost::bimap и составьте свои собственные индексы на лету.

Answer 2

Учитывая массив const char*как это принято nsStaticCaseInsensitiveNameTable::Init функция, вы можете инициализировать std::unordered_map<>:

std::unordered_map<const char*, int, my_equal_to<const char*>> string_to_index;
for (int i = 0; i < count; ++i)
    string_to_index[aNames[i]] = i;

К сожалению, функция хеширования по умолчанию - std::hash() - воля имеет const char* адреса, а не указанные текстовые данные ASCIIZ, так что вам придется написать свои собственные или скопировать. Там один называетсяmy_equal_to"отредактирован в вопрос на C++ unordered_map с ключом * в качестве ключа

Единственная разница здесь в том, что std::unordered_mapэквиваленты "Lookup"(вы могли бы использовать operator[] если бы вы знали, что строка появится где-то, иначе лучше использовать find) не чувствительны к регистру, поэтому вам нужно позвонить to_lower() Функция обработки строк в вашем ключе, если вы не уверены, что это уже строчный символ. (Обратите внимание, что согласно nsStaticCastInsensitiveNameTable документация заголовка, строки, которые его просят сохранить, должны быть строчными в качестве предварительного условия использования). Если придется позвонить каким-то образом to_lower() функция беспокоит вас, вы могли бы тривиально обернуть unordered_map в вашем собственном классе, который называется to_lower() перед пересылкой в ​​функции поиска.