Discussion :

[marcelin88]

Bonsoir,

1) Je dois créer un petit programme gérant une population: sont stockées l'adresse, le nom et l'argent de chaque personne.
On accède aux données via le nom de la personne et son adresse. Il ne peut pas y avoir deux personnes avec le même nom à la même adresse.

Code :

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

1
2
3
4
5
struct Node {
string name;
string addr;
int money;
};

La mémoire et le temps d’exécution sont limités, quelle structure de donné me conseillez vous d'utiliser? Un tas? Un AVL?

2) Dans un second temps je devrais gérer les données de manière différente: en plus d’accéder aux données via le nom de la personne et son adresse, je devrais aussi être capable d'y accéder avec une autre variable (unique): aussi un string.


J'ai pensé à faire deux arbres: l'un trié en fonction des noms, et l'autre trié en fonction de la variable unique.

Code :

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

1
2
3
4
5
6
struct Node {
string name;
string addr;
string id; //variable unique
int money;
};

Je ne vois pas comment procéder autrement.

[Iradrille]

Hello,

Pourquoi pas des map / unordered_map ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Person {
   const std::string name;
   const std::string addr;
   const std::string id;
   int money;
};
 
// possède les données, un bon allocateur peut faire gagner pas mal de perf lors de l'ajout / suppression de données.
std::list<Person> data; 
 
// 2 maps qui permettent d'accéder rapidement aux données
std:: /* unordered_ */ map<std::pair<std::string, std::string>, Person*> byNameAddr;
std:: /* unordered_ */ map<std::string, Person*> byId;

edit : ou des std:: /* unordered_ */ set<Person *>, avec les bonnes fonctions de comparaisons / hash à la place des map. Çà marche aussi.

[marcelin88]

Merci de vos réponses
Malheureusement je n'ai droit qu'a certains headers. J'ai oublié de la dire, désolé.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
#include <cstdio> 
#include <cstdlib>
#include <cmath> 
#include <cstring> 
#include <iostream> 
#include <iomanip> 
#include <string> 
#include <vector> 
#include <algorithm>

C'est vrai que des maps et des sets auraient bien aidé!
Que pensez vous?

[Iradrille]

Malheureusement je n'ai droit qu'a certains headers.

Pourquoi ? C'est un exo ? Développement embarqué et tu bosses avec une fraction du C++ ?

Si c'est un exo, tu peux t'en sortir avec un vector, mais les recherches en O(n) dedans ça va pas être la joie.
Sinon je te conseille d'implémenter les types que tu as besoin : (unordered) map ou set.

Tu n'es pas obligé de faire ça à la main : récupère une implémentation complète de la STL et ajoute les fichiers dont tu as besoin à ton projet.

[marcelin88]

C'est un exo pour apprendre le c++
Une solution lineaire n'est pas envisageable en raison du temps limité d 'execution.

Dans ce cas je vais utiliser des arbres en codant les ibsertions et suppressions?

[Trademark]

Pour le premier exercice, tu peux coder un arbre ou une table de hashage suivant ce que tu connais le mieux. Pour le deuxième exo, tu auras effectivement besoin de maintenir plusieurs structures de données en parallèle mais trouve un moyen pour ne pas dupliquer les données :-)

[robinsondesbois]

Je pense qu'avec un vector de nom et un vector d'indice tu peut t'en sortir.
Tu stock en triant en fonction des nom ton vector. Dans un autre vector tu stocke l'indice des lettres de l'alphabet. Pour accéder à tes données tu n'a plus qu'à faire une recherche dichotomique dans le sous vector correspondant à la lettre de l'alphabet.

[marcelin88]

Finalement j'ai opté pour l'option de la fonction de hachage pour accéder aux données (DJB).

En revanche je ne comprends pas très bien comment faire un tableau de pointeurs pour ne pas utiliser beaucoup de mémoire.

J'utilise ce code là, mes fonctions d'insertion, de suppression et de modification marchent.

Code :

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

1
2
3
4
5
6
7
 struct node{
     string name;
     string addr;
     int in,exp;
   };
 
   vector<node> liste;

[Médinoc]

En fait, il faut savoir s'il y a beaucoup de modifications de la collection par rapport à ses lectures.

• Si les contraintes mémoire sont les plus importantes et les modifications rare, un simple tableau trié peut faire l'affaire (et s'il faut plusieurs "clés", utiliser des tableaux de pointeurs pour les clés secondaires).
• Si les modifications sont nombreuses et la mémoire pas trop limitée, un arbre sera plus recommandé que le tableau.
• Si l'on n'a pas besoin d'ordre, une table de hachage a du bon, mais ne pas oublier que derrière chaque case de la table se trouve encore une collection à gérer (dans les exercices d'école c'est souvent une liste chaînée non-triée, mais rien n'empêche de faire une table de hachage avec un arbre dans chaque tiroir...