Recherche dans un vector

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à tous,

J'ai un petit problème d'algo en C++ et préférerais éviter d'utiliser une boucle en utilisant une solution de la STL, si tant est qu'elle existe.

Voici la situation: j'ai un vector<string> et un objet de type Molecule:

1
2
3
4
5
6
7
8
class Molecule
{
public:
    bool match(string pattern);
};

Molecule mol;
vector<string> patterns;

J'aimerais savoir si Molecule::match(…) renvoie true pour au moins un des patterns. J'ai pensé à any_of de C++11 mais je ne sais pas si c'est possible:

1
any_of(patterns.begin(), patterns.end(), [](Molecule mol){/* ??? */})

Une idée? Merci d'avance! :)

Par respect pour les visiteurs de Zeste de Savoir, je m'engage à ne jamais effacer ce message.

+0 -0

Salut,

Tant qu'on ne sait pas comment est codé “match”, il n'y a aucune optimisation possible. Que tu utilises une fonction de la STL ou une simple boucle, les performances seront les mêmes (à une microseconde près). Je te conseille donc de choisir la solution la plus simple et la plus lisible (au niveau du code), et donc de faire une bonne vieille boucle. Pas besoin de sortir l'artillerie lourde quand on peut s'en passer. ;)

Happy coding

(EDIT : erreur de markdown corrigée)

Édité par GuilOooo

Canis Lupus pour vous servir

+0 -0

Cette réponse a aidé l'auteur du sujet

Ceci devrait marcher

1
2
3
4
5
6
7
8
Molecule mol;
vector<string> patterns;
//fill patterns
any_of(patterns.begin(), patterns.end(), 
                         [&mol](string pattern){  
                             return mol.match(pattern);
                         }
       );

GuilOooo >> toujours choisir la STL quand tu le peux. Utiliser un algo de la STL te garantie une semantique claire sur l'intention première. Je vois le code, je sais ce qu'il va faire.

Avec une boucle je suis oblige d'analyser la boucle, vérifier qu'il y pas d'effet de bords,… Tu vas p-e avoir un boulet qui lorsqu'il reprendra ton code, se mettra à faire n'importe quoi ou à recoder l'existant.

Bref utiliser la STL, c'est s'assurer que son code est le plus futur-proof possible

Édité par Davidbrcz

+0 -0

GuilOooo >> toujours choisir la STL quand tu le peux. Utiliser un algo de la STL te garantie une semantique claire sur l'intention première. Je vois le code, je sais ce qu'il va faire.

Avec une boucle je suis oblige d'analyser la boucle, vérifier qu'il y pas d'effet de bords,… Tu vas p-e avoir un boulet qui lorsqu'il reprendra ton code, se mettra à faire n'importe quoi ou à recoder l'existant.

Bref utiliser la STL, c'est s'assurer que son code est le plus futur-proof possible

Davidbrcz

OK. Par pure curiosité, si j'ai besoin d'un algorithme simple du même style qui ne soit pas dans la STL (au hasard, le k-ième plus grand élément d'un tableau, ou un truc du genre), devrais-je également recoder un petit combinateur dans le même style ?

Canis Lupus pour vous servir

+0 -0

OK. Par pure curiosité, si j'ai besoin d'un algorithme simple du même style qui ne soit pas dans la STL (au hasard, le k-ième plus grand élément d'un tableau, ou un truc du genre), devrais-je également recoder un petit combinateur dans le même style ?

Idéalement oui. Surtout que souvent ca consiste juste a mettre une boucle dans une fonction template. Pas de quoi casser 3 pattes a un canard.

Sinon pour ton exemple, un sort reverse order + unique et accès au k-eme et c'est plie =). 4 lignes de code, pas une boucle manuelle et tu peux même mentalement voir l’évolution du vecteur ligne par ligne (après, c'est p-e pas le plus efficacement algorithmiquement parlant ^^)

Édité par Davidbrcz

+0 -0
Auteur du sujet

Merci beaucoup Davidbrcz, c'est exactement ce qu'il me fallait! Bizarre la syntaxe, je vais essayer de lire ça pour mieux comprendre.

Tant qu'on ne sait pas comment est codé “match”, il n'y a aucune optimisation possible.

GuilOooo

En fait l'optimisation n'était pas mon soucis. Le code est plus compliqué que ce que je vous ai dit et je me serais retrouvé avec un enchevêtrement de boucles un peu tordu.

Merci à vous. :)

Par respect pour les visiteurs de Zeste de Savoir, je m'engage à ne jamais effacer ce message.

+0 -0

Sinon pour ton exemple, un sort reverse order + unique et accès au k-eme et c'est plie =). […] (après, c'est p-e pas le plus efficacement algorithmiquement parlant ^^)

Davidbrcz

Nous sommes d'accord, c'était juste le premier exemple qui m'est passé par la tête. :)

@mathiasmch : c'est la fonction anonyme qui te perturbe, j'imagine ?

L'idée (grossièrement) est de définir une fonction sans lui donner de nom, puis de passer immédiatement cette fonction en paramètre à any_of. Sans fonction anonyme, on aurait écrit (corrigez-moi si je me trompe) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Molecule mol;

bool fonction(string pattern)
{
    return mol.match(pattern);
}

int main(void)
{
    vector<string> patterns;
    any_of(patterns.begin(), patterns.end(), fonction);

    return 0;
}

L'utilisation d'une fonction anonyme évite de lui donner un nom (ce qui est inutile étant donné qu'on ne s'en sert qu'une seule fois) et évite de rendre mol globale, ce qui est indésirable (voire impossible dans des situations plus complexes).

Canis Lupus pour vous servir

+0 -0
Auteur du sujet

Merci, oui j'ai eu croisé quelques lambdas mais j'ai encore beaucoup à apprendre à leur sujet…

En fait, il semblerait qu'une lambda puisse faire le même travail qu'un foncteur, je me trompe?

Edit: Par exemple, récemment j'avais fait:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
struct FormulaFunctor
{
    string operator()(Molecule mol)
    {
        return mol.formula();
    }
};

vector<Molecule> mols = ...;
vector<string> formulas = ...;

transform(mols.begin(), mols.end(), formulas.begin(), FormulaFunctor());

Je pourrais remplacer le foncteur par une lambda ?

1
2
3
4
vector<Molecule> mols = ...;
vector<string> formulas(mols.size(), "");

transform(mols.begin(), mols.end(), formulas.begin(), [](Molecule mol){return mol.formula();})

Je n'ai malheureusement pas de quoi tester sous la main…

Édité par mathiasm

Par respect pour les visiteurs de Zeste de Savoir, je m'engage à ne jamais effacer ce message.

+0 -0

Cette réponse a aidé l'auteur du sujet

Effectivement, il y a quasi-équivalence entre lambda et foncteurs. "Quasi" car les lambda pré-C++14 ne peuvent pas être polymorphiques.
Sinon, les lambdas sont ce qui rend les algorithmes standards de base (for-each, copy_if, …) enfin utilisables.

OK. Par pure curiosité, si j'ai besoin d'un algorithme simple du même style qui ne soit pas dans la STL (au hasard, le k-ième plus grand élément d'un tableau, ou un truc du genre), devrais-je également recoder un petit combinateur dans le même style ?

GuilOooo

std::nth_element() est déjà la réponse à ta question.

+1 -0
Banni

1
2
3
4
5
6
vector<string> patterns;
any_of(patterns.begin(), patterns.end(), 
                         [&mol](string pattern){  
                             return mol.match(pattern);
                         }
       );

Devoir écrire 6 lignes pour faire un truc aussi trivial, rajouter les bornes à la main, expliciter les variables capturées etc. ça n'est pas seulement peu lisible, c'est aussi extrêmement rébarbatif à écrire.

+1 -0

Et la version huile de coude ? N'est-elle pas rébarbative à écrire ?

(ce qui me fait penser qu'il doit y avoir moyen de définir des snippets de la forme

1
2
3
4
begin(trucs), end(trucs), 
[placeholder](auto const& truc_sans_s_et_avec_politique_de_nommage_des_paramètres_ou_placeholder) {
     placeholder;
}

hum....)

Édité par lmghs

+0 -0

Enfin utilisable, mais toujours avec une syntaxe de merde. On a rarement vu un langage aussi biscornu que C++…

puffy-freshy

On peut débattre de la syntaxe du C++ sur ce forum, mais ça aurait été plus sympa de le faire dans un topic à part et de faire un message un peu plus mesuré. Merci d'y penser la prochaine fois. :)

Canis Lupus pour vous servir

+1 -0
Auteur du sujet

Effectivement, il y a quasi-équivalence entre lambda et foncteurs. "Quasi" car les lambda pré-C++14 ne peuvent pas être polymorphiques.

lmghs

Ah et bien coïncidence, je viens de tomber sur ça dans les notes de version de GCC 4.9.1: "G++ supports C++1y generic (polymorphic) lambdas. " !

Par respect pour les visiteurs de Zeste de Savoir, je m'engage à ne jamais effacer ce message.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte