Discussion :

[Krustig]

Après s'être inspiré d'un ancien post sur le forum developpez.com j'ai tenté d'utiliser find_if.

Mais j'ai quelques soucis...

Voici ce que je veux faire :

Detecter un noeud dans une liste d'ojbet "Emprunteur" grâce à un ID stocké dans cette objet.

Voici mon "code" :

Code :

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

1
2
3
4
5
6
7
void HashT::remove(string itsPrenom, string itsNom) // Suppression d'une adhérent par nom et prenom
{
	list<Emprunteur>::iterator empIterator;
	int id = HashFX(itsNom + itsPrenom);
	empIterator = find_if(EmprunteurList.begin(), EmprunteurList.end(), MaClassEgal(id));
 
}

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
#pragma once
#include "Emprunteur.h"
 
struct MaClassEgal
{
    MaClassEgal(int n)
	{
		nb = n;
	}
 
    bool operator ()(const Emprunteur& m) const
    {
		return m.GetId() == nb;
    }
 
private :
 
    int nb;
};

Merci pour votre aide

[Sylvain Togni]

Ça a l'air correct, quel est le problème ?

[Krustig]

La voici : error C2275: 'EmprunteurList'*: utilisation non conforme de ce type comme expression

Voici la définition dans le .h

Code :

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

1
2
3
4
5
6
7
8
9
10
 
typedef list<Emprunteur> EmprunteurList;
 
....
 
 
private:
	EmprunteurList **mTab;
	unsigned int mTabSize;
	unsigned int mnElement

Je ne pense pas que ca vient de là étant donné que j'arrive à ajouter des éléments dans la liste... donc dans le tableau de pointeur sur liste Emprunteur (pfiou:p)

[Laurent Gomila]

Code :

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

EmprunteurList.begin(), EmprunteurList.end()

EmprunteurList est un type, pas une variable.

A part ça, un list<>** ... c'est vraiment nécessaire ?

[Krustig]

Si ca ne tenait qu'a moi : non !
Je dois réaliser une table de hachage externe donc je vais devoir stocker les informations dans une liste chainée à l'indice du tableau modulo ma taille utile.

Sinon tout fonctionne très bien maintenant !
Merci pour votre aide !

PS : je suis ouvert à toutes critiques de mon code, donc n'hésitez pas s'il existe une meilleur solution que <> ** ! Comprendre ses erreurs c'est apprendre

[Krustig]

Cela dit, j'ai encore une question au sujet du find_if !
Comment savoir s'il a vraiment trouvé la valeur recherchée ?
Car find_if return last s'il n'a rien trouvé mais si je n'ai qu'un element dans ma liste : first = last, donc je risque d'avoir des erreurs....

[Sylvain Togni]

Non, find_if renvoi end() s'il n'a rien trouvé, c'est à dire un itérateur pointant après le dernier élément.

[poukill]

EmprunteurList est un type, pas une variable.

Laurent a trouvé ton problème !

[Krustig]

to the first element in the range for which the application of pred to it does not return false (zero).
If pred is false for all elements, the function returns last. www.cplusplus.com

Tu en es sur pour le end ?

[Invité]

je ne réponds pas vraiment a la question, mais pour ta table de hachage, as tu songé a utiliser le conteneur std::map<> ?

[Krustig]

je ne réponds pas vraiment a la question, mais pour ta table de hachage, as tu songé a utiliser le conteneur std::map<> ?

Non ! Car je ne connais pas très bien le conteneur std::map et il me semble que je ne peux faire du hachage extern avec. (Contrainte de mon projet...)

Je me trompe ?

[Invité]

Non ! Car je ne connais pas très bien le conteneur std::map et il me semble que je ne peux faire du hachage extern avec. (Contrainte de mon projet...)

qu'est ce qu'un hachage extern exactement ?

pour ce qui est du map, c'est un tableau associatif (qui prend des pairs de valeurs, dont une clé (unique dans tout le tableau) et une valeur associée).

[Krustig]

qu'est ce qu'un hachage extern exactement ?

C'est que si ta une collision tu la traites de cette facon :

SI f(clé) donne un indice "occupé" alors stocker la clé et son information dans une liste linéaire "accrochée" à la case d'indice i.

[Invité]

C'est que si ta une collision tu la traites de cette facon [...]

euh, collision... moi perdu !
collision de quoi ? si on essaye d'écrire dans une clé qui existe déja ?

en tout cas, dans ce que tu dis, je ne vois aucune contre indication a l'utilisation du map, quitte meme à faire un truc du genre :

Code :

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

std::map<MonTypeCle, std::vector<MonTypeDesValeurs> >

[Krustig]

euh, collision... moi perdu !
collision de quoi ? si on essaye d'écrire dans une clé qui existe déja ?

Exemple :
tu as 100 valeurs à stocker dans un tableau de taille utile égale à 10.

Toutes tes clees seront différentes si ta fonction de hachage est bonne. Mais comme tu as un tableau de taille utile 10 et non de 100, tu prends la valeur de ta clé et tu la fais modulo 10 pour pouvoir stocker ta valeur dans ton tableau. ( Collision possible )

Tu aura ainsi l'indice du tableau où est stockée ta valeur !
Il te suffit juste de parcourir la liste et tu retrouves ta valeur stockée dans ta table de hachage grâce à ta clée

[Médinoc]

Une table de hachage gère typiquement les collisions de hachage avec des listes (généralement des listes chaînées).
Cela est indépendant du fait d'exiger ou non l'unicité de la clé. Mais si les collisions sont gérés et que l'unicité de la clé est demandée, les listes peuvent (ou non) être triées pour faciliter la recherche d'une clé existante dedans.

Sinon, une std::map est triée, elle utilise donc généralement un arbre plutôt qu'une table de hachage.


Cette dualité (hash_map<> contre map<>) se retrouve aussi dans java (HashMap contre TreeMap) et .Net (Dictionary<> contre SortedDictionary<>).



Dans l'idéal, un template de table de hachage devrait permettre de spécifier le type de liste à utiliser pour les collisions (ou bien, les interdire carrément) : typiquement std::list, std::vector, ou std::set.

[Krustig]

Merci pour cette réponse qui a le mérite d'être très claire