Discussion :

[noussa_88]

salut,je voulais demander de l'aide concernant une fonction qui prend en argument un string et une liste de string et qui retourne un int qui représente la position du string dans la liste.(sachant que la chaine existe nécessairement dans la liste donc pas de besoin de vérifier sa présence ou pas)
bon j'ai écrit une fonction qui marche bien dans des cas et pas dans d'autres

Code :

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

1
2
3
4
5
6
7
8
9
 
occurence(list <string> listech,string  s)
  {  int a=0;
      list <string>::const_iterator i,j;
	  i=find(liste.begin(),liste.end(),s);
	  for(j=liste.begin();j!=i;++j)
		  ++a;
return a;
}

en utilisant le fonction comme suit occurence(liste,ch)
avec liste contient par exemple 4 chaines (dont ch) et ch est une variable string résultat d'une autre fonction, le résultat est toujours faux, il me retourne 4
si je lui donne directement un string ou bien une variable de type string juste initialisée avec une chaine,le résultat est juste!!!
je vois pas ou est le problème
s'il vous plait veuillez me répondre

[koala01]

Salut,

Tu devrais déjà prendre l'habitude de passer tes objet importants (en gros, tout ce qui n'est pas un type primitif) sous la forme de références à tes fonctions.

Si, de plus, l'argument d'une fonction n'a pas vocation à être modifié (ce qui est le cas aussi bien de ta std::string que de ta std::list), il faudrait le passer sous la forme d'une référence constante.

Cela t'évitera les copies inutiles, rendra le code plus rapide et permettra d'utiliser des variables temporaires anonynmes

Je ne serais pas étonné que le problème que tu rencontre soit lié à ce conseil, car 4 est la position, dans l'exemple que tu cites, de l'iterateur pointant sur end(), et que, lorsque tu écris un code proche de

Code :

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

int result = occurence(laliste,laFonctionQuiRenvoieUneChaine());

la valeur (de type std::string) de retour de laFonctionQuiRenvoieUneChaine est... une variable anonyme (il s'agit, réellement, d'une variable qui n'est créée et qui n'existe que pour l'appel de la fonction occurence, et au sujet de laquelle tu ne dispose d'aucun nom dans la fonction appelante pour y accéder).

De plus, tu fais, en quelque sorte, deux fois le travail en commençant par chercher la chaine dans ta liste avant de calculer la position de l'itérateur trouvé.

En effet, une liste est un conteneur à accès séquentiel, ce qui signifie que, si la chaine que tu recherche se trouve à la 110eme position, la fonction find devra de toutes manières passer par... les 109 positions précédentes...

(il en irait différemment si tu remplaçais ta liste par un tableau: l'accès aux élément d'un tableau étant aléatoire, la recherche peut être dichotomique )

Enfin, le résultat obtenu mets un autre problème en évidence: la valeur renvoyée si la chaine n'est pas trouvée varie en fonction du nombre d'éléments que contient ta liste et correspond au résultat du nombre renvoyé par la fonction size() de cette liste...

Cela signifie que, à l'heure actuelle, si tu veux t'assurer que tu as une valeur valide (qui correspond réellement à la position d'une chaine existante dans ta liste), tu devra recourir à un code proche de

Code :

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

1
2
3
4
5
6
7
8
9
int i = occurence(laliste, lachaine);
if(i == laliste.size())
{
    // la chaine ne se trouve pas dans la liste
}
else
{
    // la chaine se trouve dans la liste
}

Et là, pas de bol, il n'y a aucune assurance quant le fait que la fonction size() soit en mesure de renvoyer un résultat en temps constant...

Je veux dire par là qu'il n'est pas impossible que la fonction size de list soit implémentée sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
size_t list::size() const
{
    size_t ret = 0;
   const_iterator it = begin();
   while(it!=end())
   {
       ++it;
       ++ret;
   }
   return ret;
}

ce qui occasionne... un troisième parcours (intégral, cette fois-ci) de la liste

En prenant ces trois considérations en ligne de compte, tu pourrais avantageusement modifier ta fonction occurence en quelque chose proche de

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
/* fonction calculant la position d'une chaine donnée dans une liste
 * @ return : un entier représentant la position si la chaine est trouvée
               -1 si la valeur n'a pas été trouvée
 */
int occurence(std::list<std::string const & liste, std::string const & str)
{
    int cpt=0;
    std::list<std::string>::const_iterator it=liste.begin();
    /* nous parcourons toute la liste */
    while(it!=liste.end())
    {
        /*si la chaine représentée par l'itérateur est la chaine recherchée
         */
        if( (*it)==str)
        {
            /* il n'y a pas besoin d'aller plus loin. 
             * on renvoie la valeur du compteur
             */
            return ret;
        } 
        /* si on arrive ici, ce n'est pas le cas... 
         * on passe à l'itérateur suivant et on incrémente le compteur
         */
        ++it;
        ++cpt
    }
    /* si on arrive ici, c'est que la fin de la liste a été atteinte sans trouver
     * la chaine recherchée... 
     * nous renvoyons donc " -1 " pour l'indiquer explicitement
     */
    return -1;
}

De cette manière, la liste n'est parcourue qu'une seule fois, ce qui te permettra au moins de gagner un peu de performances (sans pour autant nuire au reste) si ta liste contient des milliers de chaines et que la chaine recherchée est la 95 432eme

Mais en plus, si tu n'es pas sur que la existe dans la liste, tu peux vérifier le fait à l'aide d'une valeur constante: -1, sous une forme proche de
int i = occurence(laFonctionQuiRenvoieUneListe(),
laFonctionQuiRenvoieUneChaine()); //ici, ca passe

Code :

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

1
2
3
4
5
6
7
8
if( i!= -1)
{
    // la chaine existe
}
else
{
    // la chaine n'existe pas
}

ce qui t'évite un appel à size() qui peut potentiellement... nécessiter un parcours supplémentaire et intégral de la chaine