C++: unordered_map с композитным ключом

template< class K > iterator find( const K& x );
	(3) 	(since C++20)

https://en.cppreference.com/w/cpp/container/unordered_map/find

Там в конце как раз есть пример с поиском string_view в мапе из string-ов:

   // C++20 demo: Heterogeneous lookup for unordered containers (transparent hashing)
   std::unordered_map<std::string, size_t, string_hash, std::equal_to<>> map{ {"one"s, 1} };
   std::cout << std::boolalpha
       << (map.find("one")   != map.end()) << '\n'
       << (map.find("one"s)  != map.end()) << '\n'
       << (map.find("one"sv) != map.end()) << '\n';

Без итоговых замеров производительности все эти потуги — потуги

Вы эту лишнюю копию не заметите (на перф статистике). Забейте.

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

А еще у ТС может не быть С++20, тогда он все делает правильно. Так как строка является ключом, она все равно иммутабельная – можно создавать ее как unique_ptr<char[]> и делать try_emplace(string_view{ ptr.get(), len }, ..., std::move(ptr)), вьюха не инвалидируется.

Строчки «маленькие» или большие? Если маленькие, то действительно копирование будет очень быстрым. Если большие, то не следует их в ключ сувать. Можно ключ сделать типом pair<size_t, int>, где size_t будет хэшем строки. Саму строку можно положить в MyStruct.

Строчки «маленькие» или большие?

Правильный вопрос (кроме шуток). Дайте мне пару дней. Пообщаюсь с коллегой который по совместительству member WG21, я уверен - в последних стандартах extra copy можно избежать (мы с ним это в какой-то момент обсуждали).

Копировать строки не так дешево. Точнее, копировать дешево, а аллоцировать место под копию – нет, не говоря уже о фрагментации и заведомой избыточности этой операции. Зачем делать что-то, если с равными усилиями этого можно не делать?

rupert справедливо заметил выше: для маленьких строк аллокация не происходит. Это оптимизация называемая SSO (short string optimization). Для обычных компов это:

32 bit - 10 символов 64 bit - 22 символа.

И да, обязательно меряться. Без измерений эти измышления не стОят ничего.

https://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc

Для обычных компов это:

32 bit - 10 символов 64 bit - 22 символа.

Нет.

Пороги для SSO: в MSVC STL и GNU libstdc++ это 15 символов для 64 bit и я не помню сколько для 32 bit(7?).

22 символа это только в LLVM libc++…

Да, поэтому я и уточнил про аллокацию – избегаемую при использовании SSO. По поводу максимальных размеров fsb4000 уже поправил, но в любом случае – это немного, и при использовании сколь-нибудь длинных строк аллоцировать придется.

По-моему, очень просто создавать дешёвый ключ без переаллокаций со строкой внутри без всяких вью:

struct MyStruct {};

thread_local tuple<string, MyStruct> key;
auto &crt_key(auto &str) {
	std::get<0>(key) = str;
	std::get<1>(key) = {};
	return key;
}

int main() {
	crt_key("dkjf");
}

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

А почему мимо? Можно ведь сделать хэшер, который будет принимать как tuple с string, так и tuple с string_view.

если нужны только insert и find проще всего сразу считать хэш кортежа, и использовать его как ключ неупорядоченной мапы

std::unordered_map<hash, MyStruct>

Коллизии в этом семестре ещё не проходили?

здравствуй мой ироничный друг

конечно, неизбежно появляется вероятность коллизии, но в зависимости задачи, объема данных, и реализации хэша она может быть пренебрежимо мала.

Так можно же комбинировать хэши элементов из кортежа https://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unordered-map-unordered-set

К чему ты это скинул?

требуется тапл в качестве ключа использовать, так что это по большей части мимо

Проще всего будет добавить операторы сравнения с легковесной структуркой

У ТСа unordered_map, так что просто оператором сравнения не обойдёшься. Шаблонный template <typename K> find(const K&) доступен только тогда, когда используется прозрачный хэш и компаратор — а это ровно то о чём я пишу.

Там описывается, как правильно комбинировать хэши элементов кортежа для получения общего хэша с хорошими свойствами (т.е. более менее равномерно распределенного).

Ну круто. Коллизии куда-то денутся от этого?

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

Короче, ты за надежду на удачу+закат Солнца вручную, вместо того, чтобы взять бустовый unordered_map, если уж C++20 недоступен, и обеспечить heterogeneous lookup.

Ты нормальный? Какая удача? Я тебе про прогнозируемое время возникновения коллизий за счет равномерно распределенных значений хэшей. Какая удача? Какое солнце?

Ты не следишь, на что я отвечал? Вот, шизик предлагает хранить хэши, т.е. вычислять их самому. Это называется «закат Солнца вручную», см. например https://dic.academic.ru/dic.nsf/proverbs/22889/Закат.

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

Твои ответы выглядят как то, что ты поддерживаешь шизика.

Да. Но ты на мое сообщение, где я привел ссылку, ответил, что мол коллизии никуда не денутся.

Некоторое время назад в каждом фреймверке была своя реализация COW-строк. Посмотри, может и у тебя есть, их и используй.

Ну а иначе находи правильный метод вставки через string_view и енкапсулируй его вместе с коллекцией. Всё равно показывать наружу этот unordered_map опасно.

эка тебя порвало )

Да. Но ты на мое сообщение, где я привел ссылку, ответил, что мол коллизии никуда не денутся.

И? Ты с этим не согласен или что?

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

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

Я же пишу, что коллизии - это обязательный спутник хэш таблиц.

Чел… вроде из моего изначального сообящения ясно что я на это намекаю. К чему ты пишешь пространные простыни об этом? У тебя приступ резонёрства?

парадокс дней рождения учит нас, что для получения 50% вероятности коллизии на 128-битных хэшах нам нужно их 2^64 штук. это в свою очередь означает, что для возникновения коллизии нужно хэшировать приблизительно 6 млрд. строк в секунду на протяжении 100 лет.

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

все эти твои рассуждения о «надеждах на удачу» из серии анекдотов про блондинку - «шансы 50%, или встречу или не встречу».

что для получения 50% вероятности коллизии на 128-битных хэшах

Я Вам завидую - у Вас видимо 2^128 x sizeof() памяти имеется? В реальности при заполнении таблички в 50-75% даже при «хорошем» хеше можно запросто поиметь buckets с 5-6 элементами.

Спасибо, это помогло, только пришлось писать свой хешер (с флагом прозрачности и двумя перегрузками под tuple с string_view и под tuple с string), а не использовать универсальный из https://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unorde....

Вы путаете «коллизию» таблицы (т.е. взятые для индексации бакетов несколько бит из хэша) и коллизию хэша. На первый взгляд идея заменить в ключе строку на хэш без учёта коллизий кажется идиотской, но это пока у вас в качестве хэша какой-нибудь CRC32. Если у вас 16 байт (как в MD5), у вас система будет настолько же защищённой от коллизий как edonkey. Если 20 байт (как в SHA1), то настолько же защищённой как git.

• в кишках unordered_map пространство значений хэш функции проецируется на маленькую (в сравнении с пространством хэшей) табличку, в связи с чем вероятность коллизий возрастает на порядки. и эти коллизии unordered_map умело (или не очень) разруливает, и нас это совершенно не интересует.

• а интересует нас вот что. поступило предложение считать хэш для кортежа отдельно, и его же использовать как ключ для unordered_map. и вот в этом месте возник вопрос о коллизиях, ибо некоторые из нас опасаются что hash(«kokoko», 1) и hash(«дщдщдщ», 2) совпадут, и хрен тогда наш фокус удался.

• посчитаем что мы имеем для хэша удобного размера size_t. на максимально распространенных платформах size_t это 64 бита. т.е наш предел, выше которого вероятность коллизии существенна, это 2^32=4294967295 хэшей. в переводе на русский это 4294967295*(sizeof(size_t) + sizeof(YourVeryOwnDataType)), что в первом очень скромном приближении ~64 гигабайт памяти в пределах одной вычислительной сессии(это если ваша YourVeryOwnDataType занимает всего 8 байт) что какгбэ овердохера и «Я Вам завидую» (тм)

• исходя из типичных 50-100к записей на хэштаблицу в пределах вычислительной сессии вероятность коллизии пренебрежимо мала.

• и зойчем все это? во-первых размер ключа всего 8 байт, что играет даже для сравнительно небольших кортежей в варианте ТС, где строка + инт, и во-вторых хэш можно считать в любой удобный момент времени и хоть вприсядку. никаких неудобств, с которыми столкнулся ТС просто нет.

• бонус - при размере хэша size_t, чтобы не хэшировать захешированное, можно хэш-функцию определить как

// custom specialization of std::hash can be injected in namespace std
template<>
struct std::hash<std::size_t>
{
    std::size_t operator()(std::size_t s) const noexcept
    {
        return s;
    }
};

сказке конецЪ.

Ну ок.

сказке конецЪ.

Действительно - сказка. Как Вы ловко сползли с 64 бит на 32 в своих оценках требуемой памяти, а за попытки специализировать std::hash<std::size_t> вообще расстреливать на месте надо. «Он не ведал что творил», (c) мой.

Вы путаете «коллизию» таблицы (т.е. взятые для индексации бакетов несколько бит из хэша) и коллизию хэша.

Я то как раз не путаю. В контексте unordered_map коллизии самого хеша не так интересны как коллизии проекции (об этом уже упоминали).

Если у вас 16 байт (как в MD5), у вас система будет настолько же защищённой от коллизий как edonkey. Если 20 байт (как в SHA1)

Спешу напомнить что даже последние Xeon’ы поддерживают 46bit physical and 48bit virtual address space, десктопные процы и того меньше. Какие нафиг 16-20 байт??

Как Вы ловко сползли с 64 бит на 32 в своих оценках требуемой памяти

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

размер же «требуемой памяти» приблизительно равен N * (sizeof(key_t) + sizeof(value_t)) где N число записей, тчк. сколько записей изволите - столько и памяти, прямо пропорционально, сожрете.

Я то как раз не путаю. В контексте unordered_map коллизии самого хеша не так интересны как коллизии проекции

путаешь. нам пофиг на unordered_map и коллизии проекции. мы не о них говорим.

в тексте вообще нет оценок количества «требуемой памяти»

Спешу напомнить (процитировать):

посчитаем что мы имеем для хэша удобного размера size_t. на максимально распространенных платформах size_t это 64 бита. т.е наш предел, выше которого вероятность коллизии существенна, это 2^32=4294967295 хэшей. в переводе на русский это 4294967295*(sizeof(size_t) + sizeof(YourVeryOwnDataType)), что в первом очень скромном приближении ~64 гигабайт памяти

путаешь. нам пофиг на unordered_map и коллизии проекции. мы не о них говорим.

Перечитайте оригинальный пост ТС пожалуйста. Как я понимаю он говорил о hash tables (particularly about std::unordered_map), и об extra copies озабочен был. Я, кстати, пообщался с нашими «гуру в стандартах», но я не уверен что это всё ещё актуально (учитывая направление в котором дискуссия завернулась).

Спешу напомнить (процитировать)

и где там про «требуемую память»? там про «предел, выше которого вероятность коллизии существенна». и достигать этого предела как раз таки совсем не требуется.

Перечитайте оригинальный пост ТС пожалуйста

а мы давно ответвились и дискуссия развернулась не вокруг проблем ТС, а вокруг одного из способов их решения.

а мы давно ответвились и дискуссия развернулась не вокруг проблем ТС, а вокруг одного из способов их решения.

В упор не вижу связи между тем что ТС спрашивал, и текущим направлением дискуссии.

если обобщить - ТС боролся с ключом в виде кортежа и с побочными эффектами его использования, разными способами.

вот тут C++: unordered_map с композитным ключом (комментарий) был предложен радикальный способ - использование в качестве ключа хэш кортежа, а не сам кортеж, что на корню решает проблемы, упомянутые ТС. однако возникли сомнения в том, что это решение взлетит, по причине вероятных коллизий. вокруг рассуждений об их вероятности и шла оставшаяся часть дискуссии. в основном.

если обобщить - ТС боролся с ключом в виде кортежа и с побочными эффектами его использования, разными способами

Неправда. ТС интересовало что именно делать с extra copies. Обобщенно - мы имеем дело с Key and KeyView. Если ТС интересно продолжать дискуссию в этом ключе - I’m at his service.

Я то как раз не путаю. В контексте unordered_map коллизии самого хеша не так интересны как коллизии проекции (об этом уже упоминали).

Спешу напомнить что даже последние Xeon’ы поддерживают 46bit physical and 48bit virtual address space, десктопные процы и того меньше. Какие нафиг 16-20 байт??

Видимо всё-таки путаете.

Речь идёт о замене std::unordered_map<std::tuple<std::string, int>, MyStruct> на std::unordered_map<hash_t, MyStruct>. Никто не предлагает 2^128 бакетов, пускай анордеред_мап рулит бакетами как хочет, главное что для создания ключа выбирается вместо дорогой (из-за аллока) операции копирования строки или опасной операции запихивания стрингвью берётся относительно быстрая и 100% безопасная операция хэширования.

главное что для создания ключа выбирается вместо дорогой (из-за аллока)

A наши спецы про transparent hash говорили. Завезли в 20ых плюсах.

вроде туплы из буста умееют делать это без своих костылей

Не, не умеют, зато в бусте есть hash_combine, чтобы переложить геморр на кого-нибудь другого

using mykey_t = tuple<string, int>;
struct My_hash {
	size_t operator()(const mykey_t &k)const {
		std::size_t seed = 0;
		boost::hash_combine(seed, get<0>(k));
		boost::hash_combine(seed, get<1>(k));
		return seed;
	}
};
using map_t = unordered_map<mykey_t, int, My_hash>;