La bibliothèque standard est construite autour de quelques principes qui doivent permettre de maximiser à la fois sa généricité et sa performance; parmi les plus importants figure la distinction entre les conteneurs et les algorithmes, les itérateurs faisant l'interface entre les deux. Il me semble néanmoins que ce principe conduit à une impasse dans le cas d'un algorithme, pourtant courant, destiné à diviser une séquence en plusieurs sous-séquences selon un certain critère. D'ailleurs, il n'existe pas d'algorithme standard permettant de faire cela.
Voici une version de l'algorithme qui n'est que partiellement générique, puisqu'elle impose le type du conteneur de sortie:
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 template <typename Iterator, typename T, typename Pred> auto split_if(Iterator first, Iterator last, std::vector<std::vector<T>>& cont, Pred&& pred) { do { auto split = std::find_if(first, last, [first, &pred](auto&& e) { return pred(*first, e); }); cont.emplace_back(first, split); first = split; } while (first != last); return std::forward<Pred>(pred); }
Une signature qui ressemble aux algorithmes de la STL serait plutôt (avec la définition):
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 template <typename InputIt, typename OutputIt, typename Pred> auto split_if(InputIt first, InputIt last, OutputIt out, Pred&& pred) { do { auto split = std::find_if(first, last, [first, &pred](auto&& e) { return pred(*first, e); }); using Inner_cont = Nested_container_type_t<OutputIt>; // voir ci-dessous le rôle de Nested_container_type_t *out++ = Inner_cont(first, split); // mais on élimine quelques types de conteneur: std::array, par exemple first = split; } while (first != last); return std::forward<Pred>(pred); }
Nested_container_type_t est déjà un indice des contorsions nécessaires: un output_iterator qui n'est pas en même temps forward_iterator a le type void comme value_type. Pour retrouver le type de conteneur à créer et assigner à l'OutIt dans la fonction, il faut donc prévoir deux cas: l'habituel, où le conteneur sera déduit de Iterator::value_type, et celui de l'output_iterator pur pour lequel il faut passer par le conteneur qui le paramètre (la signature d'un std::back_insert_iterator par exemple, est template <Container> std::back_insert_iterator<Container>):
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 #include <iterator> template <typename Iterator, bool> struct Nested_container_type { using type = typename std::iterator_traits<Iterator>::value_type; }; template <template <typename> typename Iterator, typename Container> struct Nested_container_type<Iterator<Container>, false> { using type = typename Container::value_type; }; template <typename Iterator> using Nested_container_type_t = typename Nested_container_type<Iterator, !std::is_same< typename std::iterator_traits<Iterator>::value_type, void >::value>::type;
La dernière solution que je vois est d'utiliser directement dans le code (c'est-à-dire sans créer un nouvel algorithme) un algorithme de la bibliothèque standard -mais dont ne peut pas dire qu'il est véritablement prévu à cet effet:
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 std::vector<int> vec = {1,1,1,2,3,3,4,4,5,5,5,5}; auto splitted = std::accumulate(first, last, std::vector<std::vector<int>>(), [](auto&& cont, auto i) { if (!cont.empty() && cont.back().back() == i) cont.back().emplace_back(i); else cont.emplace_back(1, i); return std::move(cont); // la "move semantic" devrait rendre la chose suffisamment rapide });
Il existe également d'autres sémantiques: je pense aux iterateurs group_by_iterator de cpp_itertools, qui sont une "traduction" de Python, mais elles ne permettent pas forcément de faire tout ce qu'on peut faire avec un conteneur de conteneurs, comme une opération de tri.
Moralité, je me retrouve avec uniquement des solutions insatisfaisantes:
- soit écrire autant d'algorithmes que de combinaisons de conteneurs (pourquoi écrire un algorithme alors) ou me restreindre à un seul type de conteneurs
- soit faire des contorsions pour créer un algorithme dans le style STL mais avec des limitations cachées dont l'irrespect serait difficile à détecter par des assertions statiques
- soit utiliser std::accumulate mais d'une façon qui annule un des plus grands avantages d'un algorithme nommé: rendre apparent le sens de ce qu'on est en train de faire
Je ne parle même pas des performances, certainement variables mais que je n'ai pas mesurées.
Donc, enfin, ma question: comment traitez-vous le problème de votre côté? Une piste à laquelle je n'aurais pas pensé?
Partager