Comment obtenir la bonne valeur par défaut?
Salut à tous!
Je suis à court d'idée sur un petit problème qui s'est posé quand j'ai tenté d'implémenter un petit exercice du Stroustrup.
Très brièvement, sans utiliser les conteneurs, j'essaie d'implémenter une classe qui représenterait des ensembles d'entiers (distincts les uns des autres, un ensemble ne peut pas contenir deux fois le même int (en valeur bien entendu))
Code:
1
2
3
4
5
6
|
Class IntSet
{
size_t t;
int* p;
}; |
La représentation de mon ensemble serait donc très simple, un pointeur vers un tableau d'entiers, et la taille de ce tableau.
J'ai donc différents constructeurs
Code:
1
2
3
4
|
IntSet() : p(0), sz(0) {}
IntSet(int);
IntSet(const int&, size_t); |
On pourrait en imaginer un tas d'autres, notamment à partir d'un autre tableau d'entiers.
J'ai également des fonctions membres basiques, comme ajouter un entier, en retirer un, ...
Maintenant je souhaite implémenter une fonction assistante qui puisse faire l'intersection de 2 ensembles qui aurait le prototype suivant :
Code:
1
2
|
IntSet inter(const IntSet& is1, const IntSet& is2); |
Dans le corps de cette fonction, je comptais donc commencer par créer un tableau d'entiers ti de la taille donnée par la plus petite des tailles des 2 ensembles et avec une valeur par défaut (exemple : max qu'un int puisse être). Puis bêtement parcourir mes ensembles pour remplir ti avec les valeurs communes et ensuite construire mon ensemble IntSet à retourner en supprimant les valeurs par défaut. Mais la valeur par défaut pourrait très bien faire partie des 2 ensembles et donc je la supprimerai aussi.
Evidemment, il y a bien des moyens pour implémenter cette fonction autrement mais ce n'est pas ce qui m'intéresse ici. Je souhaite réellement savoir s'il y a des moyens de contourner ces valeurs par défaut qui peuvent faire partie de l'ensemble. Y-a-t il une astuce?
En effet, avec mon implémentation, lorsque j'ajoute un entier à un ensemble, je joue avec les allocations dynamiques, donc beaucoup d'opérations lourdes pour n'ajouter qu'un élement:
Pour donner une idée : (isIn(int a) étant une fonction membre renvoyant true si l'entier a se trouve déja dans l'ensemble)
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
IntSet& IntSet::addInt(int a){
if(!isIn(a)){
if(p){
int* temp = new int[++sz];
for(unsigned int i=0; i<sz-1; ++i)
temp[i] = p[i];
temp[sz-1] = a;
delete[] p;
p = temp;
}
else {
p = new int[1];
p[0] = a;
++sz;
}
}
return *this;
} |
Quoiqu'il en soit il serait intéressant de se retrouver avec une fonction 'reserve' à la façon std::vector qui me permettrait de préallouer de l'espace mémoire sans pour autant être gêné par une valeur par défaut.
Dois-je fixer la valeur par défaut au minimum ou au maximum qu'un int de l'implémentation puisse prendre et limiter l'intervalle de valeurs de l'ensemble au conséquence?
Comment s'y prend vector<int> ?
Merci :)
P.S. : je précise que je ne veux pas d'une solution où un tri réglerait le problème.
