Гарантируется ли что map рассматривает возможность наличия в ней нескольких

Question

pro.cxx

Андрей Руссков

Гарантируется ли что map рассматривает возможность наличия в ней нескольких

ключей типа Key, эквивалентных некоторому значению типа T?

#c++ #embedded #programming #russian

0

02.02.2021

16 ответов

23 просмотра

Dmitry Sokolov

Глянул libcxx, для transparent разруливается на equal_range unique/multi. Но там не чистый lower/upper, там спуск, если попали на равный, то lower/upper от него, т.к. обе границы на ветке. В libstc++ так же, но unique похоже не выделен, просто общий код для map/multimap. А вот для transparent там всё странно, один спуск и поиск конца итерацией...

0

02.02.2021

Dmitry Sokolov

Посмотрел в msvc, общий код для map/multimap, key_type/transparent. Т.е. тоже допускает множественность. Хотя формально не сказано, получается таки имплементации учитывают что порядок может быть слабее чем key_compare, в libcxx так прям явно: https://github.com/llvm-mirror/libcxx/blob/master/include/map#L1452 Ну и как раз за счёт того что для key_type выделена _unique версия получается разница: https://godbolt.org/z/sT8c1f

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Посмотрел в msvc, общий код для map/multimap, key_...

В стандарте написано четко, что надо вернуть пару из lower/upper bound.

0

03.02.2021

Dmitry Sokolov

Constantine Drozdov
В стандарте написано четко, что надо вернуть пару ...

Ну если компаратор транзитивный, так оно и есть. И если он транзитивный, то для map он не может вернуть более одного элемента (если сравнение по key_type).

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Ну если компаратор транзитивный, так оно и есть. И...

Аргумент для equal_range transparent не компаратор, а специальный

0

03.02.2021

Dmitry Sokolov

Constantine Drozdov
Аргумент для equal_range transparent не компаратор...

Там отдельные имплементации ж в любом случае, по произвольному ключу запрещено для не transparent. Ну и в libcxx соптимизировали по ключу для map.

0

03.02.2021

Dmitry Sokolov

Constantine Drozdov
Аргумент для equal_range transparent не компаратор...

Так то можно например написать transparent comparator для пар который заодно сможет сравнивать по first. И через equal_range(FirstType) получать диапазоны с одинаковым key.first.

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Так то можно например написать transparent compara...

Я понимаю, да

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Так то можно например написать transparent compara...

Можно еще в этом случае компаратор, выдающий нетранзитивное равенство, использовать :)

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Так то можно например написать transparent compara...

есть такая известная в узких кругах штука max(lhs.second, lhs.first + rhs.second) <=> max(rhs.second, rhs.first + lhs.second)

0

03.02.2021

Dmitry Sokolov

Constantine Drozdov
Можно еще в этом случае компаратор, выдающий нетра...

Ну и вот поиск upper_bound итерацией это мне кажется баг: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407 Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.

0

03.02.2021

Constantine Drozdov

Dmitry Sokolov
Ну и вот поиск upper_bound итерацией это мне кажет...

хм... а это не сломается уже на нормальном запросе transparent компаратора для мультимапы из одинаковых элементов?

0

03.02.2021

Dmitry Sokolov

Constantine Drozdov
хм... а это не сломается уже на нормальном запросе...

Не, там по сравнениям то смысл тот же самый что и в upper_bound.

0

03.02.2021