Comment faire un algorithme standard split_if

Version imprimable

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:

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:

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:

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:

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é?

Bonjour,

Je te conseille de jeter un coup d’œil à l'article suivant, qui traite de cette problématique :
https://tcbrindle.github.io/posts/a-...on-tokenising/

Extrait :

Citation:

It’s long been a criticism of those coming to C++ from other languages that there is no split() function for strings in the standard library. The reason is that doing so in a generic way is pretty tricky. Let’s have a try at it now

L'auteur utilise une approche élégante à base de callback, qui permet de conserver un code ressemblant à la STL et surtout de laisser à l'appelant le choix dans le traitement des sous-séquences.

Pour ton pb ça donnerait (non testé) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 template <typename Iterator, typename T, typename Pred, typename BinaryOp> void split_if(Iterator first, Iterator last, Pred pred, BinaryOp callback) { do { auto split = std::find_if(first, last, [&](const auto& e) { return pred(*first, e); }); callback(first, split); first = split; } while (first != last); return; } std::vector<int> vec = { 1,1,1,2,3,3,4,4,5,5,5,5 }; using vit = std::vector<int>::iterator; std::vector<std::pair<vit, vit>> subs; split_if(vec.begin(), vec.end(), std::not_equal_to<>(), [&](vit b, vit e) { subs.push_back(std::make_pair(b, e)); });

Peut-être que l'erreur est de vouloir faire un algorithme ?

Code:

1
2
3
 
auto view = view::split_if(vec, pred);
std::vector<std::pair<vit, vit>> subs(view.begin(), view.end());

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <utility>
#include <iterator>
 
namespace views {
 
template<class RngCont>
class fw_range_iterator;
 
template<class ForwardIterator, class Pred, class Range = std::pair<ForwardIterator, ForwardIterator>>
struct basic_split_if
{
  using iterator = fw_range_iterator<basic_split_if>;
 
  friend iterator;
 
  using range_type = Range;
 
  basic_split_if(ForwardIterator first, ForwardIterator last, Pred pred)
  : first_(first)
  , last_(last)
  , cur_(first)
  , pred_(pred)
  {}
 
  iterator begin() {
    return iterator(*this);
  }
 
  iterator end() {
    return iterator(*this, 1);
  }
 
private:
  Range next() {
    first_ = cur_;
    while (cur_ != last_ && !pred_(*first_, *cur_)) {
      ++cur_;
    }
    return {first_, cur_};
  }
 
  ForwardIterator first_;
  ForwardIterator last_;
  ForwardIterator cur_;
  Pred pred_;
};
 
template<class RngCont>
struct fw_range_iterator
: std::iterator<std::input_iterator_tag, typename RngCont::range_type, void>
{
  using value_type = typename RngCont::range_type;
 
private:
  RngCont & c_;
  value_type r_;
 
  friend RngCont;
 
  fw_range_iterator(RngCont & c)
  : c_(c)
  , r_(c.next())
  {}
 
  fw_range_iterator(RngCont & c, int)
  : c_(c)
  {}
 
public:
  fw_range_iterator& operator++() {
    r_ = c_.next();
    return *this;
  }
 
  const value_type & operator*() const {
    return r_;
  }
 
  const value_type * operator->() const {
    return &r_;
  }
 
  bool operator==(fw_range_iterator const & other) const noexcept {
    return c_.first_ == other.c_.last_;
  }
 
  bool operator!=(fw_range_iterator const & other) const noexcept {
    return !operator==(other);
  }
};
 
template<class Cont, class Pred>
auto split_if(Cont & cont, Pred pred)
-> basic_split_if<decltype(cont.begin()), Pred>
{ return {cont.begin(), cont.end(), pred}; }
 
}
 
#include <vector>
#include <functional>
#include <iostream>
 
int main() {
  std::vector<int> vec = { 1,1,1,2,3,3,4,4,5,5,5,5 };
 
  for (auto && i : vec) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
 
  auto view = views::split_if(vec, std::not_equal_to<>());
  std::vector<decltype(view)::range_type> subs(view.begin(), view.end());
 
  for (auto && p : subs) {
    std::cout << '[' << p.first - vec.begin() << '-' << p.second - vec.begin() << "] ";
  }
}

Citation:

1 1 1 2 3 3 4 4 5 5 5 5
[0-3] [3-4] [4-6] [6-8] [8-12]

Edit: En fait, pourquoi Nested_container_type_t, plutôt que *out++ = {first, split}; ?

Merci pour vos très intéressantes réponses!

Citation:

Edit: En fait, pourquoi Nested_container_type_t, plutôt que *out++ = {first, split}; ?

Parce que je n'y avais pas pensé! en fait ça ouvre de nouveaux horizons: en particulier, plus vraiment besoin de créer une classe range spéciale comme tu le fais puisque (cf version 2 dans le code ci-dessous):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <vector> #include <algorithm> #include <iostream> 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); }); *out++ = {first, split}; // avec la modification suggérée first = split; } while (first != last); return std::forward<Pred>(pred); } int main() { using Vec = std::vector<int>; Vec vec = {1,1,1,1,2,2,3,4,4,4,5,5}; // version 1: vector<T> -> vector<vector<T>> std::vector<Vec> vv; split_if(std::begin(vec), std::end(vec), std::back_inserter(vv), [](auto&& a, auto&& b) { return a != b; }); for (const auto& v : vv) { for (auto i : v) std::cout << i << ' '; std::cout << std::endl; } /* 1 1 1 1 2 2 3 4 4 4 5 5 */ // version 2: vector<T> -> vector<Range<T>> using Iter = Vec::iterator; using Range = std::pair<Iter, Iter>; std::vector<Range> vr; split_if(std::begin(vec), std::end(vec), std::back_inserter(vr), [](auto&& a, auto&& b) { return a != b; }); for (const auto& r : vr) std::cout << std::distance(r.first, r.second) << " * " << *(r.first) << std::endl; /* 4 * 1 2 * 2 1 * 3 3 * 4 2 * 5 */ }
Naturellement cela fait deux sémantiques différentes puisqu'on a copie et possession d'un côté, référence via des itérateurs de l'autre.

Cependant, je reste un peu perplexe: quelle est la nature de { first, split } ? Au cours de mes essais de redécoupage, j'ai eu cette erreur: "operator= not implement for operands std::back_inserter<etca> and std::list_initializer<etcb>". Que peut-ce être alors?

Citation:

L'auteur utilise une approche élégante à base de callback, qui permet de conserver un code ressemblant à la STL et surtout de laisser à l'appelant le choix dans le traitement des sous-séquences.

En effet, c'est une approche très intéressante et très valable. J'ai essayé de l'intégrer comme surcharge à l'autre signature, qui a ses propres mérites, mais c'est assez difficile. Je pense qu'avec les concepts -qui devaient arriver dans le standard 2017 mais ont été repoussés au prochain- on pourrait arriver à quelque chose de joli et général. J'ai fait quelques tests rapides avec les concepts de gcc 6 mais je n'ai pas eu le temps de mener ça à bout.

@modérateur: je n'édite pas mon message précédent car celui-ci ne l'invalide pas tout à fait et est annoncé par le précédent.

@jo_link_noir, Arzar: voici une version qui me semble assez générique; elle est en revanche un peu en avance sur son temps :)
Je la présente dans l'ordre logique, mais pas de l'implémentation:

Code:

1
2
3
4
5
6
7
8
9
template <typename InputIt, typename OutputIt_or_Callable, typename Pred>
auto split_if(InputIt first, InputIt last, OutputIt_or_Callable out, Pred&& pred) {
  do {
    auto split = std::find_if(first, last, [first, &pred](auto&& e) { return pred(*first, e); });  
    call_or_assign(out, first, split); // mais on élimine quelques types de conteneur: std::array, par exemple
    first = split;
  } while (first != last);
  return std::forward<Pred>(pred);
}

Les changements sont donc le nom du deuxième paramètre template et l'introduction d'une fonction call_or_assign, qui est surchargée en fonction du concept auquel adhère l'argument out:

Code:

1
2
3
4
5
6
7
8
template <typename It>
void call_or_assign(Iterator out, It first, It last) {
    out++ = { first, last };
}
template <typename It>
void call_or_assign(Callable call_back, It first, It last) {
    call_back(first, last);
}

Voilà la définition des concepts utilisés (c'est vraiment incroyable, ces concepts, quel dommage qu'il faille attendre si longtemps!):

Code:

1
2
3
4
template <typename T>
    concept bool Iterator = requires (T t) { *t; t++; };
template <typename T>
    concept bool Callable = !Iterator<T>; // ok peut mieux faire

PS: pour tester les concepts de gcc 6 sans avoir à faire une build à la main, vous pouvez utiliser ce petit site: http://melpon.org/wandbox/

Voici enfin le code de test:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int main() {
 
    using Vec = std::vector<int>;
    Vec vec = {1,1,1,1,2,2,3,4,4,4,5,5};
 
    // version 1: vector<T> -> vector<vector<T>>
    std::vector<Vec> vv;
    split_if(std::begin(vec), std::end(vec), std::back_inserter(vv), [](auto&& a, auto&& b) { return a != b; });
 
    for (const auto& v : vv) {
        for (auto i : v) std::cout << i << ' ';
        std::cout << std::endl;
    }
 
/* output:
1 1 1 1 
2 2 
3 
4 4 4 
5 5
*/
 
    // version 2: vector<T> -> vector<Range<T>>
    using Iter = Vec::iterator;
    using Range = std::pair<Iter, Iter>;
    std::vector<Range> vr;
    split_if(std::begin(vec), std::end(vec), std::back_inserter(vr), [](auto&& a, auto&& b) { return a != b; });
 
    for (const auto& r : vr) 
        std::cout << std::distance(r.first, r.second) << " * " << *(r.first) << std::endl;
 
/*output
4 * 1
2 * 2
1 * 3
3 * 4
2 * 5
*/
 
    // version 3: vector<T> -> Closure
    std::vector<Vec> result;
    auto call_back = [&result](auto&& first, auto&& last) {
        result.emplace_back(first, last);
    };
    split_if(std::begin(vec), std::end(vec), call_back, [](auto&& a, auto&& b) { return a != b; });
 
    for (const auto& v : result) {
        for (auto i : v) std::cout << i << ' ';
        std::cout << std::endl;
    }
 
/* output:
1 1 1 1 
2 2 
3 
4 4 4 
5 5
*/
 
}

EDIT: à la réflexion, il serait plus lisible de faire deux signatures:

Code:

1
2
3
4
template <typename InputIt, typename OutputIt, typename Pred>
  auto split_if(InputIt first, InputIt last, OutputIt out, Pred&& pred); // 1
template <typename InputIt, typename Callable, typename Pred>
  auto split_if(InputIt first, InputIt last, Callable call_back, Pred&& pred); // 2

renvoyant à une fonction d'implémentation commune.

08/03/2016, 14h48
jo_link_noir

Le range à un avantage, il ne crée pas de conteneur intermédiaire et reste utilisable dans une boucle. C'est plus performant si les valeurs récupérées sont jetables. C'est dommage que l'iterateur de début et l'itérateur de fin doivent être du même type, cela complexifie le code. En c++17, ce n'est plus le cas dans les range for-loop mais je n'ai pas vu de changement au niveau des fonctions prenant une paire d'itérateur (algorithme, constructeur de conteneur, etc). C'est dommage, parce que faire std::vector (make_split_if_iterator (begin(s), end(s), pred), end(s));, serait vachement fun. Même si je préfère rangev3 (c++20 du coup ?).

Citation:

Envoyé par stendhal666

Cependant, je reste un peu perplexe: quelle est la nature de { first, split } ?

Celle définie par l'appeler. C'est un appel de constructeur pour T dans l'expression 'operator=(T)'. Les règles changent en présence de template pour operator= (il n'en faut pas) ou si T prend un std::initializer_list (le comportement peu surprendre).
list initialization.
08/03/2016, 15h38
stendhal666
Citation:

C'est un appel de constructeur pour T dans l'expression 'operator=(T)'. Les règles changent en présence de template pour operator= (il n'en faut pas) ou si T prend un std::initializer_list (le comportement peu surprendre).

En effet... c'est un de ces côtés obscurs de la syntaxe du C++: il faut être bien à jour pour distinguer les accolades d'initialisation du genre int x{0}, celles de la list_initalization (ou bien sont-ce les mêmes), celles d'une std::initializer_list, et celles (mais sont-elles bien différentes?) pour l'initialisation membre à membre d'une struct. Merci en tout cas.

Citation:

Le range à un avantage, il ne crée pas de conteneur intermédiaire et reste utilisable dans une boucle. C'est plus performant si les valeurs récupérées sont jetables. C'est dommage que l'iterateur de début et l'itérateur de fin doivent être du même type, cela complexifie le code. En c++17, ce n'est plus le cas dans les range for-loop mais je n'ai pas vu de changement au niveau des fonctions prenant une paire d'itérateur (algorithme, constructeur de conteneur, etc). C'est dommage, parce que faire std::vector (make_split_if_iterator (begin(s), end(s), pred), end(s));, serait vachement fun. Même si je préfère rangev3 (c++20 du coup ?).

Oui C++20 (en fait il paraît que la cible pour le cycle serait de deux ans pour l'avenir, donc peut-être C++19) mais disponible en TS pour le prochain opus. A priori la bibliothèque de Niebler (celui qui a soumis la chose au comité standard) contient aussi les algorithmes standard adaptés pour des types différents itérateur/sentinelle.
Je suis d'accord, je ne fais qu'à moitié le pas vers l'après-prochain standard ;) mais bon les concepts sont dans gcc 6, pas les ranges.
En revanche ce qui ne me convient pas pour cet usage précis dans la sémantique de range, c'est que si je veux créer un vector<vector<T>> à partir du split_range, je dois faire une boucle:
Code:

1 2 3 4 std::vector<vector<int>> vv; for (auto p : subs) { vv.emplace_back(p.first, p.second); }
Et c'est une étape nécessaire dès que j'ai besoin d'un random_iterator, comme pour un tri. Donc je dirais qu'un algorithme split_if a sa place également pour ce genre d'usages.

Citation:

En effet... c'est un de ces côtés obscurs de la syntaxe du C++: il faut être bien à jour pour distinguer les accolades d'initialisation [1] du genre int x{0}, celles de la list_initalization [2] (ou bien sont-ce les mêmes), celles d'une std::initializer_list [3], et celles (mais sont-elles bien différentes?) pour l'initialisation membre à membre [4] d'une struct. Merci en tout cas.

Il me semble qu'il n'y a pas de différence entre 1, 2 et 4 (même si le nom est différent pour l'initialisation membre à membre). Par contre, pour 3 (std::initializer_list), il y a une subtilité qui fait que les constructeurs avec initializer_list sont prioritaires et les autres ignorés. Sauf en 14 où le compilateur va les essayer si ceux avec initializer_list échoues.

Citation:

En revanche ce qui ne me convient pas pour cet usage précis dans la sémantique de range, c'est que si je veux créer un vector<vector<T>> à partir du split_range, je dois faire une boucle:

Mauvais langue :p
Code:

1 2 3 4 5 6 7 8 template<class Rng, class Cont, class Pred> auto split_if2(Cont & cont, Pred pred) -> basic_split_if<decltype(cont.begin()), Pred, Rng> { return {cont.begin(), cont.end(), pred}; } using range_type = std::vector<int>; auto view = views::split_if2<range_type>(vec, std::not_equal_to<>()); std::vector<range_type> subs(view.begin(), view.end());

08/03/2016, 17h45
stendhal666

Citation:

Mauvais langue :p

ok je me rends :)

En fait je me suis posé la question de split_if en donnant quelques exercices à un débutant (écrire split_if ne fait pas partie de l'exercice of course). L'idée de mon tuto/exercices est de montrer tout ce qu'on peut faire avec les algorithmes standard. Mais split_if résiste, alors... Cependant introduire les ranges qui sont reportées à 2019 dans un tuto pour débutant ce serait du vice.