Recherche dans un vector

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!

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)

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 ?

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 ^^)

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

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.

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

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…

Pour tester une syntaxe (C++ ou autre), n'hésite pas à utiliser un IDE en ligne, ça peut être pratique (par exemple http://ideone.com/ ou http://coliru.stacked-crooked.com/ ) Pour ton code, oui, c'est équivalent, avec l’instanciation d'un objet en moins (je ne sais pas si le compilateur supprime ce surcoût)

Merci beaucoup pour toutes ces précisions.

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

Faut savoir sauter des lignes, aérer son code tout ça. Les one-liner, c'est rigolo, mais ce n'est pas lisible. Quelque soit le langage.

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.

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

un troll. Le premier du forum, non ? Tu veux un trophée ?

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.

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