Интересно, какой гений придумал что std::set и std::multiset удовлетворяют AssociativeContainer?...

Во всех остальных известных мне языках, "ассоциативный" означает именно мапу, т.е. один объект ассоциируется с другим https://en.wikipedia.org/wiki/Associative_array

Ну а в плюсах queue через deque, но queue же не удовлетворяет требованиям на deque

Это намёк, что set это map на unit_type

add a pair to the collection; remove a pair from the collection; modify an existing pair; lookup a value associated with a particular key set<pair<T1, T2>> всё это вполне может (надо только аккуратно посмотреть, что нужная гетерогенная операция будет)

как-то не очень по табличке сходится, у вектора тяжеловато с contains() за логарифм

Отсортируем!

тогда с insert сложновато будет

ну зависит от размера (количества элементов) даже поиск перебором по НЕ сортированному вектору может быть быстрее поиска по дереву : Big O не всегда отражает реальную скорость

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

Да но иногда это очень важно. Для таких случаев они и есть как я понимаю.

Мне кажется, что это просто ошибка проектирования зари STL, когда cache friendly было не так важно

Почему ошибка-то? Вам дают возможность делать и так и так. Это преимущество а не ошибка.

Потому что в другую сторону можно обеспечить пользовательским кодом. Это лишняя гарантия.

Не надо решать за людей какие гарантии им лишние. Вам лишняя, кому-то другому в самый раз =)

А если эта гарантия вам не нужна (99% случаев), то у вас нет подходящего решения, только очень медленное

В смысле нет? Если не нужна то есть перечисленные выше аналоги.

Представьте, что в std будет добавлен именованный shared_mutex и не будет всех остальных примитивов синхронизации

Но это явно не тот случай. Добавили же и вектор и обычный map.

Но не добавили быстрый map, который именно что отображает элементы.

Поясните? Типа бустового flat_map?

Ну посмотрите сравнение производительности unordered_map<int, int> и хеш-таблиц открытой адресации

Плохой пример, было бы норм если бы shared_mutex написали нормально

А как они в бусте называются? Если их нет в бусте то напишите, предложите в стандартную библиотеку, прославьтесь =)

https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ как будто все об этом не знают)

Вот более актуальные бенчмарки, там цифры поинтереснее https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/

а почему пики и падения есть? с чем связано падение сложности после пика?

Ага, почти 10 уже)

Modify не получится так как константой является вся пара, а не только первая компонента.

через extract там можно всё modify нынче

я не разбирал графики настолько детально, но полагаю, что там реаллокация и прыгающий load_factor

Посмотрел. Насколько я понимаю обгон делается не отказом от гарантий по итераторам а просто более эффективными алгоритмами. То есть проектирование правильное, критикуется конкретно реализация в libstdc++.

Это построение в принципе не работает для неперемещаемых ключей

Отказом в том числе - flat_map нереализуема без такового

Нет же, там одна большая аллокация памяти в хешмапе

Не очень ясно зачем в бенчмарках emilib1 или ska, да и думаю некоторые другие, они вроде бажные. Вообще мне кажется практически всегда достаточно absl. Кст если говорить о мапах, то по-моему довольно прикольная штука: https://github.com/serge-sans-paille/frozen

Да, у автора есть вывод в конце, что хорошая дефолтная мапа — absl Ну и с тех пор ещё два года прошло

У открытой адресации есть небольшой изъян, worse case. Который не предугадать. И этот товарищ сделал вид что его обошёл. Чутка покукушил и в rehash. Что приведёт к жору памяти в неприятных случаях.

В смысле worst case? Хеш плохой? И там робингудят

Ну нужно хеш получше подобрать, чем id

В chaining схеме надо просто пройти по коллизиям. В open addressing надо использовать алгоритм обхода который в худшем случае для любой из схем будет O(n). И одна косвенная адресация, ну какой 10-кратный рост? Разве что в искусственных int-int мапах

ты не веришь, что vector<T> может быть быстрее list<T> в 10 раз в качестве стека?) хуже O(n) не может быть, и там никогда не будет O(n), потому что робин гуд, говорю

Я не верю что в качественном hashmap одна лишняя косвенная адресация делает 10x

Почему одна-то? Цепочки непустые обычно, да и unordered_map трогает память неаккуратно в целом

для начала давай заметим, что в любом односвязном списке O(N) указателей имеет значение nullptr :)

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

так что в качестве априорного оверхеда за корзиночно-списочной схемы будет размер_буфера*sizeof(указателя) мусора в кэше просто так

но на самом деле худшее, что можно сделать кэшу, это написать a[i][j] для int** а, потому что нужно два раза подряд вычитать память и спекуляция вряд ли справится с таким; именно таким занимается списковая хешмапа

Для того чтобы обеспечить минимальное количество коллизий нужно табличку то с запасом держать, так что sizeof value тоже даст о себе знать, причём намного раньше

Ну так и куча мелких аллокаций тоже не бесплатная в плане оверхеда

в открытой накладные расходы 1 бит за ячейку для элемента, а не 8 байт

Соотноси 8/sizeof value

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

В этом сравнении некорректность, потому что ты считаешь бесплатным аллокатор для элементов списка

Неее, а если sizeof например килобайт. Зачем мне платить за такую таблицу?

Ну это же вырожденный случай, положите в таблицу указатели

Я же тебе выше предложил способ переделать открытую адресацию в то, что кажется тебе быстрее :)

Ну давай за быстродействие, chaining = одна косвенная адресация в лучшем случае + проход по списку коллизий. Open addressing для второго варианта вообще не гарантирует же толком ничего даже если коллизий мало.

Да ровно такая же гарантия, потому что open addressing имеет меньше накладных расходов и при том же memory usage будет работать на меньшем load factor

Заметь, я экономлю один указатель на элемент в варианте unique_ptr внутри open addressing, мне этого хватит, чтобы load factor из 0.5 сделать 0.33

Chaining легко работает при load factor близких к единице. Open addressing при этом начнет конечно жутко лажать

Близкий к 1 load factor означает ожидаемое количество проверок порядка 2 и соответствует load factor 0.5 для open addressing по расходу памяти)

В случае открытой контроль sizeof value и запоминание хеша отдаются на откуп пользователю