Discussion :

[Xtrem_Voyageur]

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 :

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

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 :

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

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 :

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

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 :

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
 
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.

[Flob90]

Je pense que ta solution à base de valeur par défaut est assez lourde. Tu pourrais prendre une variable de type size_t qui te donne la taille utile de la zone allouée, et une la taille totale.

[Xtrem_Voyageur]

Hum, je n'y avais absolument pas pensé. C'est pourtant très simple!
2 tailles et tout est réglé. C'est comme cela qu'est implémenté std::vector?

[Flob90]

La norme ne dit pas comment doit être implémenté la bibliothèque standard, elle définie juste les interfaces. Cependant ca doit être ca de manière plus ou moins déguiser le plus souvent (je laisse les gens qui se sont déjà plongé dans l'implémentation des conteneurs te répondre plus précisement sur ce point ).

[Arzar]

Tout à fait, la norme ne fait qu'énumérer un ensemble d'interface et de contraintes. Elle ne fixe en aucun cas les détails d'implémentation.
Maintenant, les contraintes sont telles qu'à ma connaissance, en pratique, la totalité des bibliothèques standards finissent par implémenter std::vector sous la forme de trois pointeurs:

T* first; // pointer to beginning of array
T* last; // pointer to current end of sequence (size)
T* end; // pointer to end of array (capacity)

Xtrem_Voyageur, c'est donc en effet équivalent à ta solution un pointeur + deux tailles.
(Je suspecte la solution à trois pointeurs d'être un peu plus simple à coder)

[Xtrem_Voyageur]

Merci à tous les 2.
J'en ai également profité pour pondre un petit bout de code de façon à voir comment évoluait la capacité d'un vector au fur et à mesure qu'on le remplissait.
Et ça n'est pas linéaire. Ca ressemble à du logarithmique à partir d'un certain rang... mais je ne m'avance pas.
Nb d'éléments / Capacité
0 / 0
1 / 1
2 / 2
3 / 3
4 / 4
5 / 6
6-9 / 9
10-13 /13
14-19 / 19
20-28 / 28
29-42 /42
43-63 / 63

En tout cas, Merci

[Flob90]

C'est pas spécifier par la norme comment ca doit être augmenté à chaque fois. Cependant la norme fixe une chose, insertion à la fin en temps amortie constant, il faudrait faire un calcul de complexité pour savoir comment effectuer les réallocations.