This patch introduces a new comparator, namely `__lazy_synth_three_way`,
which tries to provide an efficient three way comparator for known types
and falls back to using the provided comparator if it doesn't know how
to do that. Currently, an efficient three way comparison is only
provided when using one of the `less` comparions object from the
standard library and `std::string`. This will be extended in future
patches.
```
------------------------------------------------------------------------------------------------------------------------------
Benchmark old new
------------------------------------------------------------------------------------------------------------------------------
std::map<std::string, int>::ctor(const&)/0 12.6 ns 12.6 ns
std::map<std::string, int>::ctor(const&)/32 858 ns 837 ns
std::map<std::string, int>::ctor(const&)/1024 46700 ns 46739 ns
std::map<std::string, int>::ctor(const&)/8192 458100 ns 449806 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/0 12.8 ns 12.7 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/32 1286 ns 1266 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/1024 93812 ns 84686 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/8192 1480346 ns 1385924 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/0 12.9 ns 12.8 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/32 1044 ns 1055 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/1024 63071 ns 62861 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/8192 595046 ns 590223 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/0 13.6 ns 13.6 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/32 880 ns 911 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/1024 48627 ns 47808 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/8192 458552 ns 454497 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/0 13.8 ns 13.6 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/32 864 ns 851 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/1024 49483 ns 49555 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/8192 456977 ns 457894 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/0 1.31 ns 1.31 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/32 425 ns 415 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/1024 14248 ns 14225 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/8192 136684 ns 133696 ns
std::map<std::string, int>::insert(value) (already present)/0 21.5 ns 16.2 ns
std::map<std::string, int>::insert(value) (already present)/32 22.7 ns 25.1 ns
std::map<std::string, int>::insert(value) (already present)/1024 54.5 ns 29.1 ns
std::map<std::string, int>::insert(value) (already present)/8192 78.4 ns 30.4 ns
std::map<std::string, int>::insert(value) (new value)/0 40.9 ns 39.0 ns
std::map<std::string, int>::insert(value) (new value)/32 58.3 ns 47.2 ns
std::map<std::string, int>::insert(value) (new value)/1024 120 ns 71.3 ns
std::map<std::string, int>::insert(value) (new value)/8192 157 ns 129 ns
std::map<std::string, int>::insert(hint, value) (good hint)/0 40.3 ns 40.7 ns
std::map<std::string, int>::insert(hint, value) (good hint)/32 48.0 ns 30.0 ns
std::map<std::string, int>::insert(hint, value) (good hint)/1024 107 ns 63.2 ns
std::map<std::string, int>::insert(hint, value) (good hint)/8192 132 ns 107 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/0 27.0 ns 40.9 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/32 68.3 ns 58.4 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/1024 125 ns 82.0 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/8192 155 ns 150 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/0 404 ns 405 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/32 2004 ns 1805 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/1024 102820 ns 76102 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/8192 1144590 ns 949266 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/0 408 ns 404 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/32 1592 ns 1377 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/1024 74847 ns 53921 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/8192 828505 ns 698716 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/0 407 ns 407 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/32 1584 ns 1557 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/1024 47157 ns 47443 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/8192 623887 ns 628385 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/0 405 ns 403 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/32 1478 ns 1510 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024 47852 ns 47835 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192 605311 ns 606951 ns
std::map<std::string, int>::erase(key) (existent)/0 129 ns 94.0 ns
std::map<std::string, int>::erase(key) (existent)/32 110 ns 106 ns
std::map<std::string, int>::erase(key) (existent)/1024 121 ns 128 ns
std::map<std::string, int>::erase(key) (existent)/8192 165 ns 66.9 ns
std::map<std::string, int>::erase(key) (non-existent)/0 0.269 ns 0.257 ns
std::map<std::string, int>::erase(key) (non-existent)/32 21.9 ns 11.3 ns
std::map<std::string, int>::erase(key) (non-existent)/1024 53.5 ns 25.4 ns
std::map<std::string, int>::erase(key) (non-existent)/8192 67.3 ns 31.9 ns
std::map<std::string, int>::erase(iterator)/0 46.3 ns 46.7 ns
std::map<std::string, int>::erase(iterator)/32 44.4 ns 41.8 ns
std::map<std::string, int>::erase(iterator)/1024 43.7 ns 46.4 ns
std::map<std::string, int>::erase(iterator)/8192 45.2 ns 44.1 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/0 407 ns 407 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/32 876 ns 906 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/1024 20880 ns 20444 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/8192 252881 ns 241583 ns
std::map<std::string, int>::clear()/0 407 ns 408 ns
std::map<std::string, int>::clear()/32 1252 ns 1323 ns
std::map<std::string, int>::clear()/1024 38488 ns 38017 ns
std::map<std::string, int>::clear()/8192 416492 ns 428534 ns
std::map<std::string, int>::find(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::find(key) (existent)/32 33.9 ns 15.3 ns
std::map<std::string, int>::find(key) (existent)/1024 43.0 ns 25.5 ns
std::map<std::string, int>::find(key) (existent)/8192 44.6 ns 29.3 ns
std::map<std::string, int>::find(key) (non-existent)/0 0.259 ns 0.257 ns
std::map<std::string, int>::find(key) (non-existent)/32 22.6 ns 11.4 ns
std::map<std::string, int>::find(key) (non-existent)/1024 48.6 ns 25.1 ns
std::map<std::string, int>::find(key) (non-existent)/8192 64.1 ns 31.1 ns
std::map<std::string, int>::count(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::count(key) (existent)/32 32.2 ns 17.3 ns
std::map<std::string, int>::count(key) (existent)/1024 42.4 ns 25.3 ns
std::map<std::string, int>::count(key) (existent)/8192 44.4 ns 31.6 ns
std::map<std::string, int>::count(key) (non-existent)/0 0.260 ns 0.259 ns
std::map<std::string, int>::count(key) (non-existent)/32 22.9 ns 11.3 ns
std::map<std::string, int>::count(key) (non-existent)/1024 49.8 ns 25.5 ns
std::map<std::string, int>::count(key) (non-existent)/8192 66.3 ns 31.9 ns
std::map<std::string, int>::contains(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::contains(key) (existent)/32 31.4 ns 18.0 ns
std::map<std::string, int>::contains(key) (existent)/1024 44.3 ns 26.5 ns
std::map<std::string, int>::contains(key) (existent)/8192 47.4 ns 30.2 ns
std::map<std::string, int>::contains(key) (non-existent)/0 0.452 ns 0.441 ns
std::map<std::string, int>::contains(key) (non-existent)/32 23.1 ns 11.5 ns
std::map<std::string, int>::contains(key) (non-existent)/1024 46.2 ns 26.3 ns
std::map<std::string, int>::contains(key) (non-existent)/8192 63.4 ns 31.4 ns
std::map<std::string, int>::lower_bound(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::lower_bound(key) (existent)/32 17.2 ns 19.0 ns
std::map<std::string, int>::lower_bound(key) (existent)/1024 27.1 ns 26.2 ns
std::map<std::string, int>::lower_bound(key) (existent)/8192 34.0 ns 36.0 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/0 0.259 ns 0.257 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/32 11.6 ns 11.5 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/1024 24.8 ns 25.6 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/8192 31.7 ns 31.6 ns
std::map<std::string, int>::upper_bound(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::upper_bound(key) (existent)/32 18.8 ns 19.7 ns
std::map<std::string, int>::upper_bound(key) (existent)/1024 25.3 ns 27.7 ns
std::map<std::string, int>::upper_bound(key) (existent)/8192 30.2 ns 29.9 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/0 0.260 ns 0.259 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/32 11.3 ns 12.0 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/1024 25.6 ns 25.9 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/8192 33.1 ns 34.2 ns
std::map<std::string, int>::equal_range(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::equal_range(key) (existent)/32 33.5 ns 15.8 ns
std::map<std::string, int>::equal_range(key) (existent)/1024 43.0 ns 25.1 ns
std::map<std::string, int>::equal_range(key) (existent)/8192 54.1 ns 30.7 ns
std::map<std::string, int>::equal_range(key) (non-existent)/0 0.265 ns 0.259 ns
std::map<std::string, int>::equal_range(key) (non-existent)/32 22.1 ns 12.1 ns
std::map<std::string, int>::equal_range(key) (non-existent)/1024 44.8 ns 24.4 ns
std::map<std::string, int>::equal_range(key) (non-existent)/8192 62.2 ns 40.1 ns
```
Fixes #66577