Discussion :

[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:

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.

[cynique]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

Ou, plus simple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[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"

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;
}

[CedricMocquillon]

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

[3DArchi]

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

[cynique]

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.

[camboui]

Merci. Tu mets le doigt sur le défi que je propose avec les mots justes
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Goten]

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


edit : brrh des mots clefs SQL en minuscule :p

[CedricMocquillon]

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

En une:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;

[camboui]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Arzar]

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 ?

[CedricMocquillon]

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

[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...

[Arzar]

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 :

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.