Petite expérience du matin (chagrin ?) : Comment faire un find sur un std::set
Revenons en arrière. Tout d'abord, qu'est-ce que std::string_view, et pourquoi voudrait-on l'utiliser pour faire un find ?
Vous avez peut-être remarqué que l'objet std::string est loin d'être gratuit. Non seulement les copies peuvent être chères (modulo COW et SSO, m'enfin bref), mais en plus le reste du monde conspire contre nous entre les chaînes codées en dur qui sont des const char *, et de nombreuses bibliothèques ne veulent pas en entendre parler. Voyez par exemple cette recherche dans un std::set : en passant un paramètre const char *, il se cache en fait la construction d'un objet std::string, et donc une allocation.
#include <set>
#include <string>
#include <iostream>
#include <stdlib.h>
int number_of_allocs = 0;
void* operator new(std::size_t size) {
++number_of_allocs;
void *p = malloc(size);
if(!p) throw std::bad_alloc();
return p;
}
void* operator new [](std::size_t size) {
++number_of_allocs;
void *p = malloc(size);
if(!p) throw std::bad_alloc();
return p;
}
void* operator new [](std::size_t size, const std::nothrow_t&) throw() {
++number_of_allocs;
return malloc(size);
}
void* operator new (std::size_t size, const std::nothrow_t&) throw() {
++number_of_allocs;
return malloc(size);
}
void operator delete(void* ptr) throw() { free(ptr); }
void operator delete (void* ptr, const std::nothrow_t&) throw() { free(ptr); }
void operator delete[](void* ptr) throw() { free(ptr); }
void operator delete[](void* ptr, const std::nothrow_t&) throw() { free(ptr); }
int main()
{
std::cout << number_of_allocs << std::endl;
std::set<std::string> str({"a", "b", "c"});
std::cout << number_of_allocs << std::endl;
// Longue chaine pour éviter le SSO
str.find("abceuhaoeuhaotuhaoutnohusaocamhamknomhucra,huh");
std::cout << number_of_allocs << std::endl;
return 0;
}
La punition est immédiate, le programme affiche 0, 3 et 4, parce que la chaîne dans le find a été convertie en std::string et a provoqué une allocation.
Si l'on s'amuse plutôt à passer un std::string_view, dans ce cas, le programme ne compile pas, car il n'y a pas de création implicite de std::string d'après une std::string_view.
str.find(std::string_view("abceuhaoeuhaotuhaoutnohusaocamhamknomhucra,huh"));
Entre en scène la nouvelle surcharge de la fonction find, datant du C++14, qui prend un paramètre template qui doit être comparable avec une clé "de manière transparente", sans conversion nécessaire. Ah ah! Pile ce qu'il nous faut. Il faut juste donner au std::set un comparateur transparent, comme std::less, et cela fonctionne.
[...]
int main()
{
std::cout << number_of_allocs << std::endl;
std::set<std::string, std::less<> > str({"a", "b", "c"});
std::cout << number_of_allocs << std::endl;
str.find(std::string_view("abceuhaoeuhaotuhaoutnohusaocamhamknomhucra,huh"));
std::cout << number_of_allocs << std::endl;
return 0;
}
Victoire, le programme affiche 0, 3, 3, et a donc économisé l'allocation ! Mieux encore, la version où l'on passe juste la chaîne en const char * a également économisé son allocation, le std::string_view n'étant là que pour empêcher la conversion implicite.
Première conclusion : ajoutez des std::less<> à vos std::set et std::map prenant des chaînes !
Deuxième conclusion : pensez à creer un comparateur manuel si vous faites ce genre de magie avec vos propres objets
Troisème conclusion : passez à C++20 pour faire la même chose avec std::unordered_set et std::unordered_map. Je vous en recauserai peut-être quand j'aurai mis à jour mon compilo.
Références:
https://en.cppreference.com/w/cpp/string/basic_string_view
https://en.cppreference.com/w/cpp/container/unordered_set/find
https://stackoverflow.com/questions/9927856/how-to-use-operator-new-to-count-number-of-times-of-dynamic-memory-allocation
https://stackoverflow.com/questions/35525777/use-of-string-view-for-map-lookup
