Discussion :

[befalimpertinent]

Bonjour,
J'aimerais créer une fonction template prenant un iterator de début et un iterator de fin. Jusqu'a la rien de bien compliqué mais j'aimerais aussi pouvoir fournir en paramètre des pointeurs représentant un tableau.

Je m'explique:

Code :

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

1
2
3
4
5
6
 
template<typename iter> bool find(iter beg,iter end,int value)
{
//doit pouvoir fonctionner sur les vector entier, les set, ...
return true;
}

Code :

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

1
2
3
 
vector<int> tab1;
bool b1=find(tab1.begin(),tab1.end(),5);

Mais j'aimerais également pouvoir faire:

Code :

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

1
2
3
 
int tab2[]={2,3,4};
bool b2=find(tab2,tab2+3,5); //ne marche évidement pas: iter is anbiguous

Comme cela ce fait avec les fonctions sort, random_suffle et autre de la STL.

A moins que je me plante et qu'il y ait plusieurs définition de std::sort (1 pour les std containers et 1 pour les tableaux) sinon quelque chose m'échappe.

[loufoque]

ne marche évidement pas: iter is anbiguous

C'est parfaitement correct, je ne comprends pas en quoi le fait que ça ne marche pas soit évident... Tu as du te planter ailleurs.
Par exemple, c'est bien entendu pas

Code :

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

template<iter>

mais

Code :

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

template<typename iter>

et tu as aussi d'autres coquilles dans ton code.

Sinon, cette fonctionnalité existe déjà en standard : std::find...

[befalimpertinent]

Tu as raison l'erreur venait d'ailleurs (problème à la déclaration de la fonction qui causait le "iter is anbiguous") ça semble correct maintenant. J'ai édité le premier post pour corriger les coquilles (qui n'étaient pas dans mon code initial).

Pour le std::find, je connais, dans mon cas il s'agit d'un find un peu particulier que je n'ai pas détaillé. En fait je sais que ce que je reçoit est trié donc je fais un find optimisé par dichotomie.

Merci

[Altess]

befalimpertinent > Donc le code de ton premier post est correct ?

[Goten]

Oui modulo les coquilles qu'il a corrigé le code est valide.

[Arzar]

Pour le std::find, je connais, dans mon cas il s'agit d'un find un peu particulier que je n'ai pas détaillé. En fait je sais que ce que je reçoit est trié donc je fais un find optimisé par dichotomie.

Un std::binary_search, donc.

[Floréal]

pourrais tu nous montrer l'implémentation de ta fonction?
Sinon oui binary_search fait déjà une recherche dichotomique, mais alors ton tableau devra être déjà ordonné (je ne sais pas si c'est le cas).

[befalimpertinent]

Je ne l'ai pas encore vraiment tester et il est probable que j'ai quelques erreurs au niveau des +1, -1 sur les iterateurs

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
template<typename iter>
inline
iter find_opt(value v,const iter &begin,const iter &end)
{	
 
  iter mediane=begin;
  iter deb=begin,fin=end;
  while(deb != fin)
  {
    mediane = begin+(fin-deb)/2;
    if(*mediane == v) return mediane;
    else if(*mediane < v) deb = mediane+1;
    else if(*mediane > v) fin = mediane-1;
  }
  return end;
}

Je ne connait pas std::binary_search, je regarde la doc pour voir si ça peut aller.

[befalimpertinent]

Bien que corrigé, je ne parviens pas à trouver d'explications sur mon premier problème. L'erreur était la suivante : le passage par référence des paramètres de find provoque le "template parameter 'iter' is ambiguous". Si je passe par valeur pas de problème.
EMC sous Visual2005:

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
#if AVEC_REF
template<typename iter>
bool find_opt(const iter &beg,const iter &end,int value)
  {
    return true;
  }
#else
template<typename iter>
bool find_opt(const iter beg,const iter end,int value)
  {
    return true;
  }
#endif
void main()
{
vector<int> tab1;
bool b1=find_opt(tab1.begin(),tab1.end(),5);//ne provoque jamais de message d'erreur
 
int tab2[]={2,3,4};
bool b2=find_opt(tab2,tab2+3,5);//provoquera le message 
//error C2782: 'bool find_opt(const iter &,const iter &,int)' : template parameter 'iter' is ambiguous
//si AVEC_REF est activé
}

[Arzar]

Je ne comprends pas trop non plus le message "template parameter 'iter' is ambiguous", par contre je me souviens avoir lu plusieurs fois que les itérateurs de la STL sont conçus pour être passé par valeur, doit bien y avoir une raison

Sinon, ton code pour la recherche dichotomique est effectivement équivalent à celui de la STL (les erreurs en moins...). La fonction binary_find n'est pas directement présente mais on peut très facilement la reproduire grâce à std::lower_bound :

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
 
template<typename ForwardIterator, typename T>
ForwardIterator
binary_find(ForwardIterator first, ForwardIterator last, const T& value)
{
ForwardIterator it = lower_bound(first, last, value);
return (it == last || value < *it) ? last : it;
}
 
template<typename ForwardIterator, typename T, typename Compare>
ForwardIterator
binary_find(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
ForwardIterator it = lower_bound(first, last, value, comp);
return (it == last || value < *it) ? last : it;
}

La conteneur doit être trié au préalable et les items doivent être comparable par l'opérateur <.