Bug dans un wrapper de la classe STL set

**sphere369** · 15/07/2009, 17h17

Bonjour,

J'essaye de compiler le code ci-dessous mais j'obtiens un message d'erreur également ci-dessous. D'avance merci pour votre aide.

Set.hpp :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#ifndef Set_HPP
#define Set_HPP
 
#include <set>
#include <list>
using namespace std;
 
template <class V> class SetThing {};
 
template <class V> class Set : public SetThing<V>
{
private:
		set<V> s;
 
public:
		// Iterator functions; Navigating in a set
		typedef typename set<V>::iterator iterator;
		typedef typename set<V>::const_iterator const_iterator;
 
public:
		// Constructors
		Set();						// Empty set
		Set(const set<V>& stlSet);	// Create a Set from STL set
		Set(const Set<V>& s2);		// Copy constructor
		// Construct a set from V that has STL-compatible iterators
		Set(const list<V>& con);	// From anm STL list
		Set<V> operator = (const Set<V>& s2);
		virtual ~Set();
 
		// Standard set operations from High School
		friend Set<V> Intersection(const Set<V>& s1, const Set<V>& s2);
		Set<V> operator ^ (const Set<V>& s2);	// Intersection
 
		friend Set<V> Union(const Set<V>& s1, const Set<V>& s2);
		Set<V> operator + (const Set<V>& s2);	// Union
 
		friend Set<V> Difference(const Set<V>& s1, const Set<V>& s2);
		Set<V> operator - (const Set<V>& s2);	// Difference
 
		friend Set<V> SymmetricDifference(const Set<V>& s1, const Set<V>& s2);
		Set<V> operator % (const Set<V>& s2);	// Symmetric Difference
 
		template <class V2> 
			Set<pair<V, V2> > operator * (const Set<V2>& s2)
			{ // Product Set(set of pairs)
					return CartesianProduct(s2);
			}
 
		template <class V2> 
			Set<pair<V, V2> > CartesianProduct(const Set<V2>& s2)
		{
 
				Set<pair<V, V2> > result;
 
				// Iterate from begin to end of first set
				// At each level create a pair with second element from s2
 
				set<V>::const_iterator iOuter;
				set<V2>::const_iterator iInner;
 
				for (iOuter = (*this).s.begin(); iOuter != (*this).s.end(); iOuter++)
				{
					for (iInner = s2.Begin(); iInner != s2.End(); iInner++)
					{
						result.Insert(pair<V,V2>(*iOuter, *iInner));
					}
 
				}
 
				return result;
			}
 
		iterator Begin();				// Return iterator at begin of set
		const_iterator Begin() const;	// Return const iterator at begin of set
		iterator End();					// Return iterator after end of set
		const_iterator End() const;		// Return const iterator after end of set
 
		// Operations on a single set
		long Size() const;				// Number of elements	
		void Insert(const V& v);		// Insert an element
		void Insert(const Set<V>& v);	// Insert another set
		void Remove(const V& v);		// Remove an element
		void Replace(const V& Old, const V& New);	// Replace old by new
		void Clear();					// Remove all elements
		bool Contains(const V& v) const;			// Is v in set?
		bool Empty() const;				// Contains no elements
 
		// Using 'clever' operators
		void operator + (const V& v);	// Insert an element
		void operator - (const V& v);	// Remove an element
 
		// Relations between sets (s1 == *this)
		bool Subset(const Set<V>& s2) const;	// s1 a subset of s2?
		bool Superset(const Set<V>& s2) const;	// s1 a superset of s2?
		bool Intersects(const Set<V>& s2) const;	// s1 and 22 have common elements?
 
 
};
 
#endif

Set.cpp :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
#ifndef Set_CPP
#define Set_CPP
 
#include <algorithm>
#include "Set.hpp"
 
 
// Constructors
template <class V>
Set<V>::Set()
{ // Empty set
 
	s = set<V>();
}
 
template <class V>
Set<V>::Set(const set<V>& stlSet)
{ // Empty set
 
	s = stlSet;
}
 
template <class V>
Set<V>::Set(const Set<V>& s2)
{ // Copy constructor
 
	s = set<V>(s2.s);
}
 
 
// Construct a set from V that has STL-compatible iterators
template <class V>
Set<V>::Set(const list<V>& con)
{ // From am STL container (list, vector)
 
	s = set<V>();
 
	// Create list iterator
	list<V>::const_iterator i;
 
	// Print every character in the list
	for (i = con.begin(); i != con.end(); ++i)
	{
			s.insert(*i);		// Will only be inserted once
	}
}
 
template <class V>
Set<V> Set<V>::operator = (const Set<V>& s2)
{
 
	if (this == &s2)
		return *this;
 
	s = s2.s;
 
	return *this;
}
 
template <class V>
Set<V>::~Set()
{
 
}
 
// Standard set operations from High School
template <class V>
Set<V> Intersection(const Set<V>& s1, const Set<V>& s2)
{
	set<V> myintersect;
	set<V>::iterator i = myintersect.begin();
	insert_iterator<set<V> > insertiter(myintersect, i);
	set_intersection(s1.s.begin(), s1.s.end(), s2.s.begin(), s2.s.end(), insertiter);
 
	return Set<V>(myintersect);
 
}
 
template <class V>
Set<V> Set<V>::operator ^ (const Set<V>& s2)
{ // Intersection
 
	return Intersection(*this, s2);
}
 
 
template <class V>
Set<V> Union(const Set<V>& s1, const Set<V>& s2)
{
	set<V> myunion;
	set<V>::iterator i = myunion.begin();
	insert_iterator<set<V> > insertiter(myunion, i);
	set_union(s1.s.begin(), s1.s.end(), s2.s.begin(), s2.s.end(), insertiter);
 
	return Set<V>(myunion);
 
}
 
 
template <class V>
Set<V> Set<V>::operator + (const Set<V>& s2)
{ // Union
 
	return Union(*this, s2);
 
}
 
 
template <class V>
Set<V> Difference(const Set<V>& s1, const Set<V>& s2)
{
	set<V> mydiff;
	set<V>::iterator i = mydiff.begin();
	insert_iterator<set<V> > insertiter(mydiff, i);
	set_difference(s1.s.begin(), s1.s.end(), s2.s.begin(), s2.s.end(), insertiter);
 
	return Set<V>(mydiff);
 
}
 
 
template <class V>
Set<V> Set<V>::operator - (const Set<V>& s2)
{ // Difference
 
	return Difference(*this, s2);
 
}
 
 
template <class V>
Set<V> SymmetricDifference(const Set<V>& s1, const Set<V>& s2)
{
	set<V> mysdiff;
	set<V>::iterator i = mysdiff.begin();
	insert_iterator<set<V> > insertiter(mysdiff, i);
	set_symmetric_difference(s1.s.begin(), s1.s.end(), s2.s.begin(), s2.s.end(), insertiter);
 
	return Set<V>(mysdiff);
}
 
template <class V>
Set<V> Set<V>::operator % (const Set<V>& s2)
{ // Symmetric Difference
 
	return SymmetricDifference(*this, s2);
 
}
 
 
template <class V> typename
Set<V>::iterator Set<V>::Begin()
{ // Return iterator at begin of set
 
	return s.begin();
}
 
template <class V> typename
Set<V>::const_iterator Set<V>::Begin() const
{ // Return const iterator at begin of set
 
	return s.begin();
 
}
 
template <class V> typename
Set<V>::iterator Set<V>::End()
{ // Return iterator after end of set
 
	return s.end();
 
}
 
template <class V> typename 
Set<V>::const_iterator Set<V>::End() const
{ // Return const iterator after end of set
 
	return s.end();
 
}
 
 
// Operations on a single set
template <class V>
long Set<V>::Size() const
{ // Number of elements	
 
	return s.size();
}
 
 
template <class V>
void Set<V>::Insert(const V& v)
{ // Insert an element
 
	s.insert(v);
}
 
template <class V>
void Set<V>::Insert(const Set<V>& mySet)
{ // Insert another set
 
	// Test this
	set<V>::iterator i = s.begin();
	insert_iterator<set<V> > insertiter(s, i);
	set_union(s.begin(), s.end(), mySet.s.begin(), mySet.s.end(), insertiter);
 
}
 
template <class V>
void Set<V>::Remove(const V& v)
{ // Remove an element
 
	s.erase(v);
}
 
template <class V>
void Set<V>::Replace(const V& Old, const V& New)
{ // Replace old by new
 
	s.erase(Old);
	s.insert(New);
}
 
template <class V>
void Set<V>::Clear()
{ // Remove all elements
 
	s.clear();
}
 
template <class V>
bool Set<V>::Contains(const V& v) const
{ // Is v in set?
 
 
	const_iterator it = s.find(v);
 
	if (it == s.end())
		return false;
 
	return true;
}
 
template <class V>
bool Set<V>::Empty() const
{ // Contains no elements
 
 
	return s.empty();
}
 
 
// Using 'clever' operators
template <class V>
void Set<V>::operator + (const V& v)
{ // Insert an element
 
	s.insert(v);
}
 
template <class V>
void Set<V>::operator - (const V& v)
{ // Remove an element
 
	s.remove(v);
}
 
 
// Relations between sets (s1 == *this)
template <class V>
bool Set<V>::Subset(const Set<V>& s2) const
{ // This a subset of s2?
 
	return includes(s2.s.begin(), s2.s.end(), (*this).s.begin(), (*this).s.end());
 
 
}
 
template <class V>
bool Set<V>::Superset(const Set<V>& s2) const
{ // this a superset of s2?
 
	return s2.Subset(*this);
 
}
 
template <class V>
bool Set<V>::Intersects(const Set<V>& s2) const
{ // s1 and s2 have common elements?
 
	if (Empty() == true || s2.Empty() == true)
		return false;
 
	set<V>::const_iterator iter;
 
	for (iter = s.begin(); iter != s.end(); iter++)
	{
		if (s2.Contains((*iter)) == true)
		{
			return true;
		}
	}
 
	return false;
}
 
#endif

Programme principale TestSetOperations2.cpp :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <string>
using namespace std;
 
#include "Set.cpp"   //Car utilisation de template
 
 
template <class T> void print(const Set<T>& l, const string& name)
{  // Print the contents of a Set. Notice the presence of a constant iterator.
 
	cout << endl << name << ", size of set is " << l.Size() << "\n[ ";
 
	set<T>::const_iterator i;
 
	for (i = l.Begin(); i != l.End(); ++i)
	{
			cout << *i << " ";
 
	}
 
	cout << "]\n";
}
 
template <class T> void printSet(const Set<pair<T, T> >& l, const string& name)
{  // Print the contents of a Set. Notice the presence of a constant iterator.
 
	cout << endl << name << ", size of set is " << l.Size() << "\n[ ";
 
	set<pair<T, T> >::const_iterator i;
 
	for (i = l.Begin(); i != l.End(); ++i)
	{
			cout << (*i).first << ", " << (*i).second << endl;
 
	}
 
	cout << "]\n";
}
 
int main()
{
	Set<int> first;				// Default constructor
 
	// Only unique (new elements) added
	first.Insert(1);
	first.Insert(2);
	first.Insert(3);
	print (first, "First set");
 
	Set<char> s1;
	s1.Insert('A');
	s1.Insert('B');
	s1.Insert('C');
	s1.Insert('D');
	s1.Insert('F');
	print (s1, "s1");
 
	Set<char> s2;
	s2.Insert('0');
	s2.Insert('A');
	s2.Insert('B');
	s2.Insert('C');
	s2.Insert('D');
	//s2.Insert('E');
	s2+'E';
	s2.Insert('H');
	s2.Replace('H', 'G');
	print (s2, "s2");
	s2.Remove('G');
	print (s2, "s2");
 
	Set<char> ws;		// Work space
 
	ws = s1 + s2;
	print(ws, "Union");
 
	ws = s1 ^ s2;
	print(ws, "Intersection");
 
	ws = s1 - s2;
	print(ws, "Difference s1 - s2");
 
	ws = s2 - s1;
	print(ws, "Difference s2 - s1");
 
 
	ws = s1 % s2;
	print(ws, "Symmetric Difference");
 
	// Subset/superset stuff
	Set<char> s3;
	s3.Insert('A');
	s3.Insert('B');
	s3.Insert('C');
	s3.Insert('D');
 
	if (s3.Subset(s1) == true)
		cout << "Yes, is subset OK\n";
	else
		cout << "Bah1\n";
 
	if (s1.Superset(s3) == true)
		cout << "Yes, is superset OK\n";
	else
		cout << "Bah1\n";
 
	if (s1.Intersects(s3) == true)
		cout << "Yes, we have intersection OK\n";
	else
		cout << "Bah1\n";
 
	Set<char> s4;
	if (s1.Intersects(s4) == false)
		cout << "Yes, we have NO intersection OK\n";
	else
		cout << "Bah1\n";
 
	s4.Insert('A');
	if (s1.Intersects(s4) == true)
		cout << "Yes, we have intersection OK\n";
	else
		cout << "Bah1\n";
 
	// Sets from lists
	list<char> myList;
	myList.push_back('A');
	myList.push_back('B');
	myList.push_back('C');
	myList.push_back('C');
	myList.push_back('C');
	myList.push_back('D');
	myList.push_back('D');
	myList.push_back('D');
	myList.push_back('D');
	myList.push_back('A');
	myList.push_back('A');
	myList.push_back('A');
	myList.push_back('A');
	myList.push_back('A');
 
	Set<char> s5(myList);
	print(s5, "Filtered set");
 
 
	if (s5.Contains('A') == true)
		cout << "OK, contains A\n";
	else 
		cout << "Bah\n";
 
	if (s5.Contains('Z') == false)
		cout << "OK, contains NOT Z\n";
	else 
		cout << "Bah\n";
 
	// Cartesian product
	Set<int> s11;
	s11.Insert(2);
	s11.Insert(3);
 
	Set<int> s12;
	s12.Insert(8);
	s12.Insert(9);
 
	Set<pair <int, int> > S = s11.CartesianProduct(s12);
	printSet(S, "Pr");
 
	Set<pair <int, int> > S2 = s12.CartesianProduct(s11);
	printSet(S2, "Pr");
 
	return 0;
}

Message d'erreur :

Code :

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

1
2
3
4
5
1>TestSetOperations2.obj : error LNK2019: symbole externe non résolu "class Set<char> __cdecl Intersection(class Set<char> const &,class Set<char> const &)" (?Intersection@@YA?AV?$Set@D@@ABV1@0@Z) référencé dans la fonction "public: class Set<char> __thiscall Set<char>::operator^(class Set<char> const &)" (??T?$Set@D@@QAE?AV0@ABV0@@Z)
1>TestSetOperations2.obj : error LNK2019: symbole externe non résolu "class Set<char> __cdecl Union(class Set<char> const &,class Set<char> const &)" (?Union@@YA?AV?$Set@D@@ABV1@0@Z) référencé dans la fonction "public: class Set<char> __thiscall Set<char>::operator+(class Set<char> const &)" (??H?$Set@D@@QAE?AV0@ABV0@@Z)
1>TestSetOperations2.obj : error LNK2019: symbole externe non résolu "class Set<char> __cdecl Difference(class Set<char> const &,class Set<char> const &)" (?Difference@@YA?AV?$Set@D@@ABV1@0@Z) référencé dans la fonction "public: class Set<char> __thiscall Set<char>::operator-(class Set<char> const &)" (??G?$Set@D@@QAE?AV0@ABV0@@Z)
1>TestSetOperations2.obj : error LNK2019: symbole externe non résolu "class Set<char> __cdecl SymmetricDifference(class Set<char> const &,class Set<char> const &)" (?SymmetricDifference@@YA?AV?$Set@D@@ABV1@0@Z) référencé dans la fonction "public: class Set<char> __thiscall Set<char>::operator%(class Set<char> const &)" (??L?$Set@D@@QAE?AV0@ABV0@@Z)
1>C:\sphere369\DistanceLearning\Code\Part2_Data_Structures_Templates_And_Patterns\Debug\Chap12_SetOperations2_DEB.exe : fatal error LNK1120: 4 externes non résolus

**3DArchi** · 16/07/2009, 09h38

Salut,
Je ne suis pas sur de voir l'intérêt d'une telle classe qui m'a l'air de réécrire des algos existants de la STL pour manipuler les set.
Ceci dit, une petite lecture de la FAQ t'apportera la réponse à ton problème très classique avec les templates : Pourquoi mes templates ne sont-ils pas reconnus à l'édition des liens ?

**Arzar** · 16/07/2009, 12h33

Si je me souviens bien, il y a une salop- difficulté du langage (une de plus

) entre les classes templates et les fonctions templates amies...

Il me semble qu'il faut rajouter des template<typename V> devant chaque fonction friend:

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
 
// Standard set operations from High School
template <typename V>
friend Set<V> Intersection(const Set<V>& s1, const Set<V>& s2);
Set<V> operator ^ (const Set<V>& s2);	// Intersection
 
template <typename V>
friend Set<V> Union(const Set<V>& s1, const Set<V>& s2);
Set<V> operator + (const Set<V>& s2);	// Union
 
template <typename V>
friend Set<V> Difference(const Set<V>& s1, const Set<V>& s2);
Set<V> operator - (const Set<V>& s2);	// Difference
 
template <typename V>
friend Set<V> SymmetricDifference(const Set<V>& s1, const Set<V>& s2);
Set<V> operator % (const Set<V>& s2);	// Symmetric Difference

**sphere369** · 16/07/2009, 18h49

Bonjour,

Les fichiers .tpp ne semblent être reconnus par mon compilateur.
Je vais essayer la proposition de Arzar.

Merci pour votre aide.

**Goten** · 16/07/2009, 19h14

Envoyé par Arzar

Si je me souviens bien, il y a une salop- difficulté du langage (une de plus

) entre les classes templates et les fonctions templates amies...

Il me semble qu'il faut rajouter des template<typename V> devant chaque fonction friend:

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
 
// Standard set operations from High School
template <typename V>
friend Set<V> Intersection(const Set<V>& s1, const Set<V>& s2);
Set<V> operator ^ (const Set<V>& s2);	// Intersection
 
template <typename V>
friend Set<V> Union(const Set<V>& s1, const Set<V>& s2);
Set<V> operator + (const Set<V>& s2);	// Union
 
template <typename V>
friend Set<V> Difference(const Set<V>& s1, const Set<V>& s2);
Set<V> operator - (const Set<V>& s2);	// Difference
 
template <typename V>
friend Set<V> SymmetricDifference(const Set<V>& s1, const Set<V>& s2);
Set<V> operator % (const Set<V>& s2);	// Symmetric Difference

Jean-marc Bourguet à poster du code récapitulant et expliquant la situation à ce sujet y'a un petit moment, il me semble. Je vais essayer de retrouver ça.

**sphere369** · 17/07/2009, 15h13

Je ne sais pas trop si cela vient de l'utilisation de class a la place de typename mais normalement cela est équivalent.
Je ne suis pas sorti de l'auberge...

Je mets cela sur ma "TO DO list"....car la il y a urgence (préparation pour entretiens...).

**3DArchi** · 17/07/2009, 15h18

Envoyé par Goten

Jean marc bourguet à poster du code récapitulant et expliquant la situation à ce sujet y'a un petit moment, il me semble. Je vais essayer de retrouver ça.

Tu pensais à ça ?

Bug dans un wrapper de la classe STL set

C++

Discussions similaires

Partager

Partager