IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

container, iterator et filtres.


Sujet :

C++

  1. #1
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut 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:
    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.

  2. #2
    Membre régulier Avatar de cynique
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    60
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 60
    Points : 72
    Points
    72
    Par défaut
    Citation Envoyé par camboui Voir le message
    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...

  3. #3
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    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;
    }

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Points : 345
    Points
    345
    Par défaut
    Je pense que tu devrais jeter un oeil à ceci:
    http://boost-sandbox.sourceforge.net...html#id4604310
    Ça devrait faire ton bonheur ;-)

  5. #5
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Points : 13 017
    Points
    13 017
    Par défaut
    Bonjour,
    Effectivement Boost.Iterator a pensé à toi et te propose Boost.Filter Iterator.

  6. #6
    Membre régulier Avatar de cynique
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    60
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 60
    Points : 72
    Points
    72
    Par défaut
    Citation Envoyé par camboui Voir le message
    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.

  7. #7
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    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.

  8. #8
    Membre chevronné
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Points : 2 205
    Points
    2 205
    Par défaut
    Par cascade t'entends subqueries? (en SQL j'entends).


    edit : brrh des mots clefs SQL en minuscule :p
    "Hardcoded types are to generic code what magic constants are to regular code." --A. Alexandrescu

  9. #9
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    En quelque sorte.
    Si je reprend mon exemple du premier post, on aurait quelque chose comme ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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)
    {
    }

  10. #10
    Membre émérite
    Avatar de white_tentacle
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    1 505
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 1 505
    Points : 2 799
    Points
    2 799
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  11. #11
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    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)
    Boost ftw

  12. #12
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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...

    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 ?

  13. #13
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    Ce code pourrait faire cinq lignes courtes et expressives sans problème.
    Qu'est-ce que censé faire la fonction f1 exactement ?
    Boost ftw

  14. #14
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    Citation Envoyé par loufoque Voir le message
    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 Voir le message
    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é ?

  15. #15
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    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.
    Boost ftw

  16. #16
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Points : 345
    Points
    345
    Par défaut
    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;

  17. #17
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    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.

  18. #18
    Membre émérite

    Inscrit en
    Mai 2008
    Messages
    1 014
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 1 014
    Points : 2 252
    Points
    2 252
    Par défaut
    Citation Envoyé par camboui Voir le message
    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 ?

  19. #19
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Points : 345
    Points
    345
    Par défaut
    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

  20. #20
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 301
    Points : 345
    Points
    345
    Par défaut
    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...

Discussions similaires

  1. Réponses: 8
    Dernier message: 13/10/2010, 13h33
  2. SAM et container et Filtre
    Par spopoff dans le forum Glassfish et Payara
    Réponses: 1
    Dernier message: 05/11/2009, 18h41
  3. [Débutant] Résultat filtré avec CONTAINS ?
    Par mimicracra dans le forum Oracle
    Réponses: 17
    Dernier message: 17/07/2006, 16h11
  4. Filtre passe Bande
    Par Mau dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 28/06/2002, 18h03
  5. Probleme de filtre dans bdd
    Par scorpiwolf dans le forum C++Builder
    Réponses: 2
    Dernier message: 04/06/2002, 11h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo