Прозрачные компараторы std::less/std::greater для std::basic_string

mrgordonfreman
mrgordonfreman

Рассмотрим пример (clang 4.0, libc++ из trunk)

std::map<std::string, int> m;
m["test"] = 1;
m.find("test"); // вызывается конструктор ключа, т.е. строки
std::string_view sv = "test";
m.find(sv); // не компилируется, у строки explicit конструктор по view

В C++14 в контейнеры std::map и std::set были добавлены функции вида

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

Они основываются на перегрузках оператора () у компаратора (который по умолчанию std::less) и не создают инстанс ключа. Но чтобы этот механизм заработал, компаратор должен обладать следующим свойством - выражение Compare::is_transparent должно быть корректным и обозначать тип (любой). Таким образом, библиотека предлагает написать свой компаратор и передать его через шаблонные параметры контейнера.

Тип std::basic_string наряду с целыми числами - основа любой программы на C++. Именно строки и числа чаще всего используются в качестве ключей в ассоциативных контейнерах. Но в текущей ситуации приходится постоянно помнить о том, что нужно прописать свой компаратор в очередной map или set (который все равно работает аналогично std::less). 

Предлагается передать эту ответственность стандартной библиотеке. Специализацию std::less для строки можно реализовать примерно так

namespace std
{

template<class CharT>
struct less<std::basic_string<
    CharT, std::char_traits<CharT>, std::allocator<CharT>>>
{
    using str_type = std::basic_string<
        CharT, std::char_traits<CharT>, std::allocator<CharT>>;
    
    using is_transparent = void; // Enable comparison with the view
    
    template<class T>
    bool operator ()(str_type const& lhs, T&& rhs) const {
        return lhs < rhs;
    }
    
    template<class T>
    bool operator ()(T&& lhs, str_type const& rhs,
        typename std::enable_if<!std::is_same_v<str_type,
            typename std::decay<T>::type>>::type* = nullptr) const {
        return lhs < rhs;
    }
};

}

Теперь со строками все будет работать как надо по умолчанию.

m.find("test"); // строка не создается
// std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >::operator()<char const (&) [5]>(...)
std::string_view sv = "test";
m.find(sv); // компилируется, строка не создается
// std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >::operator()<std::basic_string_view<char, std::char_traits<char> > const&>(...)
4
рейтинг
24 комментария
yndx-antoshkka
Так ведь уже с C++14 есть. Просто используйте обычные компараторы с <> :

std::map<std::string, int, std::less<>> super_fast;
yndx-antoshkka
mrgordonfreman
yndx-antoshkka,
Действительно, оно делает тоже самое и определяет is_transparent. Тогда вторая часть вопроса - имеет смысл сдедать такое поведение по умолчанию для строк?
mrgordonfreman
mrgordonfreman
yndx-antoshkka,
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

вместо
Compare = std::less<Key>
сделать что-то типа такого
Compare = typename std::default_less<Key>::type

<string> при включении будет добавлять свою специадизацию
mrgordonfreman
mrgordonfreman
yndx-antoshkka,
И еще связанный с этим вопрос - почему в unordered-контейнерах нет возможности выполнять поиск без создания инстанса ключа?
llvm.org/svn/llvm-project/libcxx/trunk/include/unordered_map
Тут вижу только такие варианты
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
mrgordonfreman
yndx-antoshkka
Мне бы хотелось иметь это поведение по умолчанию, но я не уверен в обратной совместимости. Unordered контейнеры надо допатчить, в них этого и правда не хватает.

Если готовы взяться за написание предложения - говорите, дам ссылки на похожие предложения и помогу советом.
yndx-antoshkka
mrgordonfreman
yndx-antoshkka,
Всегда готов!) Если не затруднит, то ссылки наверно будет лучше скинуть прямо на почту, чтобы тут в офтопик не уходить.
mrgordonfreman
yndx-antoshkka
mrgordonfreman, я не знаю вашей почты :)

Я посмотрел логи обсуждений. Если делать std::less<std::string> по умолчанию гетерогенным, то поломается пользовательский код: some_map.find({100, 'A'});

Фишка с std::default_less была рассмотрена и не прокатила, так как какую-то совместимость ломала open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0181r0.html

Остаётся только продумать тему, с unordered контейнерами и гетерогенными хешированиями. На эту тему уже писали пропозал, который решили рассматривать после C++14 и с тех пор всё заглохло open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3573.html Стоит попробовать написать человеку, и спросить как дела с этим предложением.
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, я всегда думал, что имя здесь соответствует почте на yandex.ru)
Выходит, что я заново изобрел колесо, все уже предлагали. Тогда про unordered контейнеры попробую разузнать. Спасибо за помощь!
Эти вопросы хотел еще на последней встрече РГ21 поднять в кулуарах, но как-то перескочили на проблемы mingw)
mrgordonfreman
mrgordonfreman
yndx-antoshkka, по документу open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3573.html
Автор на связь не выходит)

Мне этот пропозал не нравится
1) в гетерогенном хэше предлагают использовать std::decay<T> - это плохо, потому что для массивов произойдет array-to-pointer conversion и хэш будет вычисляться от T*
2) гетерогенность для lookup-функций создается добавлением хэша и компаратора в параметры шаблона самих функций - это плохо, как мы уже выяснили гетерогенность по умолчанию ломает совместимость и не честно по отношению к самому контейнеру с заранее определенным хэшем и компаратором

Я набросал вариант решения на примере unordered_set в libc++, вот тут патч можно посмотреть
github.com/compmaniak/libcxx/pull/1/files
Прогнал тесты, ничего не ломает, гетерогенность работает

Отличия от имеющегося пропозала
1) в гетерогенном хэше вместо std::decay<T> будет более безопасное std::remove_cv<std::remove_reference<T>>
2) если для контейнера хэш задан как std::hash<>, то по умолчанию компаратор тоже станет гетерогенным std::equal_to<>, и по аналогии с map/set через sfinae будут "включаться" гетерогенные lookup-функции
mrgordonfreman
yndx-antoshkka
mrgordonfreman, выглядит неплохо!

Добавьте несколько тестов на unordered_set<string> и string_view. Например:

std::unordered_set<std::string, std::hash<>> m = {
"Lorem", "ipsum", "dolor", "sit", "amet", "consectetur", "adipiscing", "elit"
};
std::string_view str_v = "amet";
assert(m.count(str_v) == 1);
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, готово, все ок
github.com/compmaniak/libcxx/pull/1/commits/389ba51ba5b376d26ff51c67cff6ec2fadce91f5
Успеем оформить proposal до встречи в Торонто?)
mrgordonfreman
yndx-antoshkka
mrgordonfreman, думаю успеем :)

Начинайте писать proposal. Как будет черновая версия - скидывайте ссылку, я подправлю. Ну и еще напишите о своей идее на std-proposals (а то вдруг кто-то делает точь в точь то же самое).
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, Черновая версия готова
compmaniak.github.io/proposals/Heterogeneous%20lookup%20in%20unordered%20containers.html

Вот сам репозиторий с исходником github.com/compmaniak/proposals

На std-proposals никто не отозвался, что делает то же самое
groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/RCmAwD9s5W8

Правда там указали, что поломается ABI в случае

template <class _Value, class _Hash = hash<_Value>,
class _Pred = typename _default_pred<_Value, _Hash>::type,
class _Alloc = allocator<_Value> >
class unordered_set

и сослались на пропозал open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0181r0.html
Не понятно в каком случае сломается, этот пропозал пережил одну правку
open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0181r1.html
и был отменен совсем недавно в Коне.

Поэтому пришлось это учесть и теперь придется записывать контейнер с явным указанием еще и гетерогенной функции сравнения

std::unordered_set<std::string, std::hash<>, std::equal_to<>> s = {"hello"};
s.find(std::string_view{"hello"});

Но лучше написать немного больше при объявлении, чем вовсе остаться без гетерогенного поиска)
mrgordonfreman
yndx-antoshkka
mrgordonfreman, получилось очень круто. Я в течение недели вышлю на почту указанную в proposal, несколько замечаний связанных с местными правилами и объясню дальнейшие шаги.

Натолкнулся на один очень важный момент: GCC и CLANG хешируют const char* = "Hello" не как строчку, а как void*, то есть просто хешируют адрес. Другими словами, вот этот пример выдаёт две разные строчки:

#include <unordered_map>
#include <iostream>

int main() {
const char* data = "Hello\0Hello";
std::cout << std::hash<const char*>()(data) << '\t' << data
<< '\n' << std::hash<const char*>()(data + 6) << '\t' << data + 6;
}


А это значит, что

std::set<std::string, std::less<>> s2 = {"hello"};
s2.find(std::string_view{"hello"}); // ok
s2.find("hello"); // не соберётся, т.к hash<const char[6]> не специализирован
const char* data = "Hello";
s2.find(data); // соберётся, но ничего не найдет

С этим надо что-то порешать, с подобными недочётами proposal в стандарт не примут.
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, Чтобы работал следующий код

std::unordered_set<std::string, std::hash<>, std::equal_to<>> s = {"hello"};
s.find("hello");

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

1) Ввести новый трейт is_character<T>, который для типов char, char16_t, char32_t, wchar_t будет выдавать true. Сейчас появился тип std::byte, т.е. С++17 разделяет понятия байта и текстового символа. Поэтому такой трейт будет вполне уместным.

2) Определить специализации std::hash для типов T[N] и T(&)[N], для которых is_character_v<T> будет true. Хэш вычислять с помощью string_view (и поставлять в том же заголовочном файле).

Вот пример реализации с тестами
github.com/compmaniak/libcxx/commit/e9690312003b2aef0f53eb98f768a7cdfd8889a6

А со следующим кодом

std::unordered_set<std::string, std::hash<>, std::equal_to<>> s = {"hello"};
const char *data = "hello";
s.find(data);

можно ничего не делать) Объяснение может быть таким:

1) Сломается совместимость, нельзя внезапно взять и вычислять хэш по-другому.
2) Нельзя гарантировать однозначное вычисление хэша во всех единицах трансляции.
unit1.cpp
---------------------
#include <functional>
const char* s = "hello";
std::hash<>{}(s); // будет вычислен как T*

unit2.cpp
---------------------
#include <functional>
#include <string>
const char* s = "hello";
std::hash<>{}(s); // будет вычислен как std::string_view{s}

3) Гетерогенный поиск в контейнерах выключен по умолчанию. Его включение - это сознательное действие разработчика. Точно такие же проблемы с непредсказуемым поведением мы можем получить с гетерогенным поиском по std::map/std::set, когда ADL сыграет с нами злую шутку.

Еще я думал над идеей что-то типа hash_proxy<T>, который будет выдавать тип, через который гетерогенный хэш считать. Но это мне кажется хуже, чем первый вариант, потому что придем к противоречию
const char* s = "hello";
assert( std::hash<const char*>{}(s) != std::hash<>{}(s) );
А это уже серьезный аргумент против.

Выходит, что const char* - это обуза со временем С. Но не отказываться же из-за этого от всех плюсов гетерогенного поиска?)
mrgordonfreman
yndx-antoshkka
mrgordonfreman, хм...
А что получится, если к вашему предложению (тому, которое до предложения с is_character) добавить, что hash<string> должен выглядеть вот так:

template <class Char, class Trait, class A> struct hash<std::basic_string<Char, Trait, A>> {
size_t operator()(std::basic_string_view<Char, Trait> t) const noexcept {
return hash<std::basic_string_view<Char, Trait>>{}(t);
}
};

+ is_transparent брать из компаратора + убрать специализацию struct hash<void>?

Тогда все примеры будут работать:
std::unordered_set<std::string, std::hash<std::string>, std::equal_to<>> s2 = {"hello"};
s2.find(std::string_view{"hello"}); // ok
s2.find("hello"); //ok
const char* data = "Hello";
s2.find(data); // ok

Но я не уверен, что будет работать
s2.find({"Hello word", 5}); // ??? а это наc вообще должно волновать при std:;equal_to<> ???
yndx-antoshkka
yndx-antoshkka
mrgordonfreman, минутку! Мне не удалось найти пример, где std::less<> ведёт себя иначе чем std::less<std::string>:

#include <set>
#include <string>
#include <cassert>

int main() {
std::set<std::string, std::less<>> s {
"Hello", "dudde", "Woopsie", {5, 'Q'}
};

assert( s.count("Hello") );
assert( s.count(std::string{"Hello"}) );
assert( s.count({"Hello Word", 5}) );
assert( s.count({5, 'Q'}) );
}

А это значит что можно получить ОГРОМНЫЙ плюс:
* берём ваш proposal, убираем специализацию std::hash<void>, берём is_transparent из комапартора
* все компараторы специализируем для std::basic_string<Char, Trait, A>, говорим что они гетерогенные, принимают параметр std::basic_string_view<Char, Trait>
* PROFIT: из коробки ВСЕ ассоциативные контейнеры с std::string начинают работать во много раз быстрее
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, отличная идея! Опробовал, все функционирует.
Предлагаю тогда разбить работу на части
1) гетерогенный поиск в unordered контейнере + hash<string> через string_view
2) специализация всех компараторов для строки
Я буду дожимать первую часть.
Для второй части наверно лучше будет отдельный пропозал делать - меняет поведение по умолчанию имеющегося кода, вдруг ABI где отъедет. Смешивать в один документ сложновато будет, и выше вероятность, что комитет зарубит сразу 2 фичи)
mrgordonfreman
mrgordonfreman
yndx-antoshkka, а можно как-нибудь узнать, почему отклонили это предложение open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0181r1.html ?
Я нашел только итоги голосования, на форуме про сломанное ABI говорили. Но вот как именно такая небольшая правка могла повлиять, не понятно.
Вполне может быть, что со специализацией компараторов для std::string такие же проблемы будут.
mrgordonfreman
mrgordonfreman
yndx-antoshkka, с вычислением хэша строки через string_view проблема нашлась

Не компилируется следующий код

template <class Char, class Trait, class A> struct hash<std::basic_string<Char, Trait, A>> {
size_t operator()(std::basic_string_view<Char, Trait> t) const noexcept {
return hash<std::basic_string_view<Char, Trait>>{}(t);
}
};

template <class To>
struct ConvertibleToSimple {
operator To() const { return To{}; }
};
using T = std::string;
typename std::result_of<std::hash<T>(ConvertibleToSimple<T>&)>::type r{};

Примерно такой код в тестах libcxx для проверки требований к функции хэша
mrgordonfreman
yndx-antoshkka
mrgordonfreman, долго и мучительно пытался обойти подобную проблему, в итоге ничего хорошего не вышло. Получилось нечто, что на некоторых граничных условиях в огромных количествах генерирует временные строки.

> 2) специализация всех компараторов для строки
Та же проблема - множество временных объектов строки в граничных случаях.

Похоже что стоит ограничиться гетерогенным поиском только когда пользователь это явно запросил.
yndx-antoshkka
yndx-antoshkka
mrgordonfreman, немного поэкспериментировал с производительностью. Современные компиляторы убирают создание временного объекта ключа. Получается что разницы в производительности между set<string>{}.find("qwe") и set<string, less<>>{}.find("qwe") - нет никакой.

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

struct person; // can not be constructed from string!
bool operator==(const person& p, const std::string& name);
bool operator==(const std::string& name, const person& p);

Идею с гетерогенными компараторами по умолчанию для string - выкидываю на свалку, прироста скорости она не даёт.

Идея с гетерогенными unordered контейнерами - жжот, расширяет применимость контейнеров. Постараюсь в ближайшее время сделать pull request с правками.
yndx-antoshkka
mrgordonfreman
yndx-antoshkka, будем что-либо делать со следующим кейсом?

std::unordered_set<std::string, std::hash<>, std::equal<>> s2 = {"hello"};
s2.find(std::string_view{"hello"}); // ok
s2.find("hello"); // не соберётся, т.к hash<const char[6]> не специализирован
const char* data = "Hello";
s2.find(data); // соберётся, но ничего не найдет

Сейчас пропозал не решает это, предоставляет только прозрачный хэш и необходимые функции.
У меня появилась еще мысль добавить в string_view конструктор по массиву символов

template<class Ch, class Traits = std::char_traits<Ch>>
class basic_string_view {
template<size_t N>
basic_string_view(Ch const (&a)[N]) {
auto pos = Traits::find(a, N, Ch('\0')); // ищем нул-символ
if (pos == nullptr)
создаем по строке (a, a + N);
else
создаем по строке (a, --pos);
}
};

Совместимо с созданием по C-строке + можно будет безопасно создавать вью на массивы без нул-символа. Тогда хэши массивов можно будет красиво выразить через string_view.
mrgordonfreman
yndx-antoshkka
mrgordonfreman, basic_string_view трогать не стоит. Такой конструктор не очень красивый: поведение зависит от рантайма + пользователю очень легко случайно сконвертировать массив без '\0' к указателю и получить segmentation fault.

С кейсом делать ничего не надо и добавлять специализацию std::hash<> тоже не надо. Стоит сделать чтобы контейнер становился "гетерогенным" из-за компаратора, а не функции хеширования. Функцию хеширования пользователь должен передать/сделать сам.

Таким образом мы получим гетерогенные контейнеры, но не придётся мучаться c std::hash и супер различными несовместимыми его имплементациями.

Тогда проблемный пример будет выглядеть как std::unordered_set<std::string, users_hash, std::equal<>> и решение по хешированию ляжет на плечи пользователя. Решить за пользователя мы не можем эту проблему - нет подхода который везде хорошо работает и не ломает пользовательский код.
yndx-antoshkka
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).