container, iterator et filtres.

On connait tous les containers avec leurs iterators associés. Mais il n'y a pas de filtres applicables à ces iterators pour réduire leur portée à un sous-ensemble du container.

Prenons l'exemple d'un std::vector. Supposons qu'il soit trié, on peut alors faire un std::lower_bound dessus. On obtient en retour un iterator que l'on peut incrémenter, décrémenter, etc, mais c'est à nous de vérifier que l'iterator soit déréférençable et que son "contenu" soit valide en fonction de la clé passée en paramètre à std::lower_bound, et ainsi de suite pour les incrémentations successives que l'on ferait sur l'iterator.
Idéalement on devrait obtenir un sous ensemble du container initial filtré par la clé.

On pourrait avoir la même situation avec un std::vector non trié, une clé permettant de dire si un élément du container est valide ou non.

Au lieu d'une clé on pourrait utiliser comme filtre un autre vector, de booléens par exemple.

Un autre type de filtre sur un vector trié: ignorer les doublons.

En définitive, j'essaie de conceptualiser de manière générique la notion de filtre sur un container (à priori quelconque) afin de pouvoir l'utiliser aussi simplement que ceci:

Citation:

---

std::container c;
filtered_c=apply_filter(c, filter);
for(iterator it=filtered_c.begin();it!=filtered_c.end();++it)
{
}

---

La fonction apply_filter() serait une fonction template qui renverrait un pseudo container contenant les éléments filtrés du container passé en paramètre. Et, bien sûr, il n'est pas question d'en faire une copie, la complexité de apply_filter() doit être O(1).

Si vous avez des idées, merci.

Citation:

---

Envoyé par camboui

On connait tous les containers avec leurs iterators associés. Mais il n'y a pas de filtres applicables à ces iterators pour réduire leur portée à un sous-ensemble du container.

Prenons l'exemple d'un std::vector. Supposons qu'il soit trié, on peut alors faire un std::lower_bound dessus. On obtient en retour un iterator que l'on peut incrémenter, décrémenter, etc, mais c'est à nous de vérifier que l'iterator soit déréférençable et que son "contenu" soit valide en fonction de la clé passée en paramètre à std::lower_bound, et ainsi de suite pour les incrémentations successives que l'on ferait sur l'iterator.
Idéalement on devrait obtenir un sous ensemble du container initial filtré par la clé.

On pourrait avoir la même situation avec un std::vector non trié, une clé permettant de dire si un élément du container est valide ou non.

Au lieu d'une clé on pourrait utiliser comme filtre un autre vector, de booléens par exemple.

Un autre type de filtre sur un vector trié: ignorer les doublons.

En définitive, j'essaie de conceptualiser de manière générique la notion de filtre sur un container (à priori quelconque) afin de pouvoir l'utiliser aussi simplement que ceci:La fonction apply_filter() serait une fonction template qui renverrait un pseudo container contenant les éléments filtrés du container passé en paramètre. Et, bien sûr, il n'est pas question d'en faire une copie, la complexité de apply_filter() doit être O(1).

Si vous avez des idées, merci.

---

Peut-être comme ça?

Code:

---

1 2 3 4 5 6 7 8 9 10 11

std::collection c;   camboui::filtered_collection fc( c, filter );   for( camboui::filtered_collection::iterator it = fc.begin(); it != fc.end(); ++it ) { //... }

---

La paramètre filter est une fonction ou un "functor" (je connais pas le bon mot français) qui accepte une paramètre, un objet de la collection, et retourne un bool, true == oui, utilise cet objet, false == non, ne l'utilise pas.

Code:

---

1 2 3 4 5

bool only_odd_ints( int this_int ) { return (this_int % 2 == 1); }

---

La classe filtered_collection je laisse pour ceux qui lisent mon message... :mouarf:

Ou, plus simple:

Code:

---

1 2 3 4 5 6 7 8

std::collection c;   for( std::collection::iterator it = c.begin(); it != c.end(); ++it ) if( filter( *it ) ) { //... }

---

Tout le monde peut voir quel filter se trouve ici. Dans l'autre cas, il peut être caché plus facilement, et tu éviteras l'ajout de plus de templates. Les templates font plus de code compilé non-visible, et la compilation de beaucoup de code template va très lentement.

Ce n'est que mon avis... 8O

Merci pour ta réponse. Elle met bien en évidence toute la difficulté de la chose.

Ta dernière proposition est bien sûr ce que je souhaite éviter: parcourir tout le container. Les performances d'ordre O(n) quand on recherche un sous-ensemble du container par clé alors que le container est un vector trié, un set (ou map) ou une table hash (unordered_set), ne sont pas acceptables.

Le temps de compilation est secondaire. Le temps d'exécution prime. Et à terme j'espère gagner du temps de codage.

Ce que tu appeles "camboui::filtered_collection" est le noeud du problème, avec le paramètre "filter". Et sans doute plus encore l'iterator associé.

Voici un exemple de code que j'aimerais "simplifier et généraliser"

Citation:

---

LCode lc_tmp(...);
std::vector<LCode>::const_iterator lc_found=std::lower_bound(code_vect.begin(),code_vect.end(),lc_tmp);
while (lc_found!=code_vect.end() && !(lc_tmp<*lc_found))
{
...
++lc_found;
}

---

Je pense que tu devrais jeter un oeil à ceci:
http://boost-sandbox.sourceforge.net...html#id4604310
Ça devrait faire ton bonheur ;-)

Bonjour,
Effectivement Boost.Iterator a pensé à toi et te propose Boost.Filter Iterator.

Citation:

---

Envoyé par camboui

Merci pour ta réponse. Elle met bien en évidence toute la difficulté de la chose.

Ta dernière proposition est bien sûr ce que je souhaite éviter: parcourir tout le container. Les performances d'ordre O(n) quand on recherche un sous-ensemble du container par clé alors que le container est un vector trié, un set (ou map) ou une table hash (unordered_set), ne sont pas acceptables.

Le temps de compilation est secondaire. Le temps d'exécution prime. Et à terme j'espère gagner du temps de codage.

Ce que tu appeles "camboui::filtered_collection" est le noeud du problème, avec le paramètre "filter". Et sans doute plus encore l'iterator associé.

Voici un exemple de code que j'aimerais "simplifier et généraliser"

---

Hmm. Il y a deux types de filtres sur une collection:

* Selectionner une groupe contigue d'éléments
* Selectionner une groupe "aléatoire" d'éléments

Pour le deuxième cas, il faut toujours parcourir toutes les éléments. :(

Pour le premier cas, tu ne dois que trouver les deux bouts de la sous-collection, et les utiliser comme begin et end de l'iteration.

Merci. Tu mets le doigt sur le défi que je propose avec les mots justes :ccool:
boost.filter_iterator est bien joli, mais il ne propose qu'un enrobage du 2ème cas.
Et je vois un troisième cas possible, celui qui permet d'éviter les doublons.

Pour illustrer mon propos prenons la commande SQL suivante:

Code:

---

select [distinct] a,b,c from t where x,y,z

---

J'essaie dans une certaine mesure d'avoir une écriture simple comme celle de SQL avec comme input un container, et en output un sous-container du premier, peu importe le type filtre (SQL utilisera/créera des index si nécessaire).
La clause distinct de SQL gère l'unicité. La clause where gère les deux autres filtres de manière transparente.
Avec cette même écriture j'aimerais gérer les trois type de filtres, et même utiliser des filtres en cascade.

Par cascade t'entends subqueries? (en SQL j'entends).


edit : brrh des mots clefs SQL en minuscule :p

En quelque sorte.
Si je reprend mon exemple du premier post, on aurait quelque chose comme ceci:

Code:

---

1 2 3 4 5 6 7

std::container c; filtered_c1=apply_filter(c, filter1); filtered_c2=apply_filter(filtered_c1, filter2); filtered_c3=apply_filter(filtered_c2, filter3); for(iterator it=filtered_c3.begin();it!=filtered_c3.end();++it) { }

---

Le problème, c'est que tu as besoin d'une référence sur le conteneur dans ton itérateur (je ne vois pas comment faire autrement, y a peut-être une solution cela dit)

Mais sinon, ça ne me semble pas délirant quelque chose de ce genre (brut de fonderie et pas du tout testé, il y a probablement des erreurs dedans :) ) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

template<typename container> doublet_filtering_iterator operator++() { typename container::iterator; container::iterator it = m_it; container::iterator end = m_container.end(); ++m_it; while(m_it != end && *m_it == *it) ++m_it; return *this; }

---

(m_it est un itérateur standard, m_container une référence vers le conteneur). Il faut ensuite surcharger les autres opérateurs comme il se doit.

Pour pouvoir chaîner des itérateurs filtrants, j'imagine qu'on peut en faisant quelque chose de ce genre :

Code:

---

1 2	template<typename container, typename iterator> doublet_filtering_iterator operator++()

---

avec m_it du type itérateur. Par contre, la syntaxe doit être assez immonde :

Code:

---

doublet_filtering_iterator<std::vector, even_filtering_operator<std::vector,std::vector::iterator> > it(coll.begin());

---

par exemple :). En jouant avec les différents constructeurs, on doit pouvoir arriver plus ou moins à ce que tu veux pouvoir écrire.

C'est censé enlever les doublons se trouvant à la suite ?
Tu peux faire ça avec un filtre adjacent avec boost.range_ex (qui bien sûr, dispose aussi de filtre unaire)

Voilà, après de bonnes vacances, un peu de réflexion et quelques heures passées à découvrir boost, voici un petit code facile:

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

typedef std::less<int> the_predicate;   void f1(std::vector<int> & v,int to_be_found) { the_predicate p; std::vector<int>::const_iterator it_found=std::lower_bound(v.begin(), v.end(), to_be_found, p);   for (; it_found!=v.end() && !p(to_be_found,*it_found); ++it_found) std::cout << *it_found << ' '; std::cout << std::endl; }   int main() { std::vector<int> vi; vi.push_back(1); vi.push_back(2); vi.push_back(3); vi.push_back(4); vi.push_back(5); vi.push_back(5); vi.push_back(5); vi.push_back(5); vi.push_back(7); vi.push_back(8); vi.push_back(9); vi.push_back(12); vi.push_back(13); vi.push_back(14); vi.push_back(14); vi.push_back(15); vi.push_back(16); std::sort(vi.begin(),vi.end(),the_predicate());   int i=5;   f1(vi,i);   return 0; }

---

C'est un code simple et efficace. Il s'agit, vous l'aurez compris, d'extraire tous les éléments d'un vector correspondant à un critère donné via une recherche dichotomique. J'ai appelé le critère "the_predicate", il est classique puisqu'il s'agit de l'operator<() abondamment utilisé dans la stl.
Je l'ai cependant expressément nommé pour qu'on le voit bien ;)

J'utilise souvent lower_bound() suivi d'une boucle for(), mais l'écriture du gardien de la boucle est parfois un peu fastidieuse et le code est spécifique à ce cas de figure.

J'ai donc quand même essayé de voir ce que je pouvais tirer de boost::filter_iterator et voici le résultat après avoir remplacé le code de f1():

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void f1(std::vector<int> & v,int to_be_found) { the_predicate p; std::unary_negate<std::binder1st<the_predicate> > not_less_int(std::binder1st<the_predicate>(p, to_be_found)); boost::filter_iterator<std::unary_negate<std::binder1st<the_predicate> >, std::vector<int>::iterator> filtered_begin( not_less_int, std::lower_bound(v.begin(), v.end(), to_be_found, p), v.end()); boost::filter_iterator<std::unary_negate<std::binder1st<the_predicate> >, std::vector<int>::iterator> filtered_end( not_less_int, v.end(), v.end()); boost::filter_iterator<std::unary_negate<std::binder1st<the_predicate> >, std::vector<int>::iterator> filtered_it(filtered_begin);   for (; filtered_it!=filtered_end; ++filtered_it) std::cout << *filtered_it << ' '; std::cout << std::endl; }

---

C'est intellectuellement très riche, le gardien de la boucle for() est simplifé (filtered_it!=filtered_end) et il y aurait moyen de mettre plusieurs filtres en cascade.

Mais... :aie:

J'aurais bien sur pu faire un typedef de cette chose std::unary_negate<std::binder1st<the_predicate>> pour un peu alléger l'écriture, mais ça n'en reste pas moins un peu lourdingue je trouve. Quelqu'un pour me contredire ?

Ce code pourrait faire cinq lignes courtes et expressives sans problème.
Qu'est-ce que censé faire la fonction f1 exactement ?

Citation:

---

Envoyé par loufoque

Ce code pourrait faire cinq lignes courtes et expressives sans problème.

---

Tu pourrais nous montrer stp ?
Personnellement il ma fallu un bon moment pour trouver comment transformer le prédicat the_predicate servant à trier le vector afin de pouvoir l'utiliser avec filter_iterator.
Je l'ai appelé la chose std::unary_negate<std::binder1st<the_predicate>> (;))
S'il y a plus simple je suis preneur (en réutilisant le prédicat ayant servi au tri du vector, il n'y a pas de raison d'en pondre un autre).

Citation:

---

Envoyé par loufoque

Qu'est-ce que censé faire la fonction f1 exactement ?

---

Je l'ai expliqué (et c'est assez facile à voir je pense): extraire d'un vector trié les éléments correspondant à une clé (ici je me contente de faire un std::cout).
Ces éléments forment un sous-container du container d'origine. Si j'ai bien compris l'usage de filter_iterator, il aide à déterminer les bornes [begin,end[ du sous-container en obtenant deux iterators utilisables dans "l'esprit" de la stl.

EDIT:
Je viens de trouver un sérieux problème de performance avec filter_iterator. En cause le troisième paramètre de l'intantiation de filtered_begin et filtered_end: v.end(). Il faudrait le remplacer par la borne supérieure du sous-container recherché, mais on ne la connait pas à priori... A moins de faire un upper_bound().
Je me demande si c'est bien filter_iterator qu'il faut utiliser dans mon exemple de vector trié, j'ai des doutes. Un autre iterator plus adapté ?

Citation:

---

Je l'ai expliqué (et c'est assez facile à voir je pense): extraire d'un vector trié les éléments correspondant à une clé

---

Pour ça, il suffit de faire std::equal_range.

Tu n'as jamais voulu filtrer, tu veux juste extraire un sous-intervalle de ta séquence.

Citation:

---

Ce code pourrait faire cinq lignes courtes et expressives sans problème.

---

En une:

Code:

---

1 2 3 4 5

void f1(vector<int> & v,int to_be_found) { for_each(equal_range(v, to_be_found, the_predicate()), cout << _1 << ' '); }

---

avec :

Code:

---

1 2 3 4 5 6 7 8 9

#include <boost/lambda/lambda.hpp> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/algorithm/equal_range.hpp>     using namespace std; using namespace boost; using namespace boost::lambda;

---

Mwouais...

Je n'aime pas trop equal_range() parce qu'il fait 2 recherches binaires (lower_bound() et upper_bound()) et c'est à priori ce que je cherche à éviter, une devrait suffire.

Et puis:

Code:

---

1 2	#include <boost/range/algorithm/for_each.hpp> #include <boost/range/algorithm/equal_range.hpp>

---

N'existent pas dans les headers de boost. Mais ceci existe:

Code:

---

1 2	#include <boost/foreach.hpp> #include <boost/range.hpp>

---

T'as quelle version de boost ? (j'ai 1.37 et 1.40)
Mais c'est pas grave, les versions de la STL suffisent à priori.

Citation:

---

Envoyé par camboui

Mwouais...

Je n'aime pas trop equal_range() parce qu'il fait 2 recherches binaires (lower_bound() et upper_bound())...

---

T'es sûr !?

Il me semblait avoir lu quelque part qu'equal_range avait été ajouté à la STL précisement pour avoir une méthode permettant de trouver les bornes efficacement - en une passe - et justement pour éviter que les developpeurs soient tentés d'utiliser des méthodes en deux passes désastreuses comme un lower_bound + upper_bound.

Quel serait l'intéret d'equal_range sinon ?

C'est du boost sandbox : http://boost-sandbox.sourceforge.net...tml/index.html mais il me semble qu'elle a été acceptée, y'a plus qu'à attendre qu'elle soit intégrée à une prochaine version de boost

Edit: il semblerait que maintenant tout soit dans un seul fichier algorithm.hpp: https://svn.boost.org/svn/boost/sand.../algorithm.hpp

Une seule recherche binaire te permettra de trouver une seule de tes deux bornes; après tu es obligé d'itérer tant que ton prédicat reste vrai. Au niveau complexité, soit tu assures 2*log(n)+1 soit tu fais log(n)+x*O(comparaison) avec x au plus égal à n. Après c'est à toi de voir en fonction de la complexité de ton prédicat et du nombre d'éléments à trouver...

Citation:

---

Envoyé par CedricMocquillon

Une seule recherche binaire te permettra de trouver une seule de tes deux bornes; après tu es obligé d'itérer tant que ton prédicat reste vrai. Au niveau complexité, soit tu assures 2*log(n)+1 soit tu fais log(n)+x*O(comparaison) avec x au plus égal à n. Après c'est à toi de voir en fonction de la complexité de ton prédicat et du nombre d'éléments à trouver...

---

Ouaip, effectivement j'ai parlé trop vite. La norme dit :

Citation:

---

Returns : make_pair(lower_bound(first, last, value),
upper_bound(first, last, value))

Complexity: At most 2 * log(last - first) + 1 comparisons.

---

equal_range permet donc surtout d'avoir une écriture plus agréable, mais ne devrait pas être fondamentalement plus efficace qu'un lower + upper.