Discussion :

[tnarol]

Salut,

J'aimerais savoir s'il existe une méthode permettant de connaitre la taille de l'intersection de 2 sets qui soit plus rapide que celle consistant à calculer le set intersecté (avec set_intersection) puis à mesurer sa taille.

Merci

[Sylvain Togni]

Tu peux par exemple utiliser la fonction set_intersection en lui passant un itérateur de sortie spécial, qui ne copiera pas les éléments, mais se contentera de les compter. Quelque chose comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
struct CountIt : std::iterator<std::output_iterator_tag, T>
{
  int n;
 
  CountIt() : n(0) {}
 
  CountIt& operator*() {return *this;}
  CountIt& operator=(T const&) {++n; return *this;}
  CountIt& operator++() {return *this;}
  CountIt& operator++(int) {return *this;}
};

[Sylvain Togni]

En fait, ceci serait plus propre :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
struct CountIt : std::iterator<std::output_iterator_tag, T>
{
  int n;
  T t;
 
  CountIt() : n(0) {}
 
  T& operator*() {++n; return t;}
  CountIt& operator++() {return *this;}
  CountIt& operator++(int) {return *this;}
};

[tnarol]

En fait, ceci serait plus propre :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
struct CountIt : std::iterator<std::output_iterator_tag, T>
{
  int n;
  T t;
 
  CountIt() : n(0) {}
 
  T& operator*() {++n; return t;}
  CountIt& operator++() {return *this;}
  CountIt& operator++(int) {return *this;}
};

Super, je sais pas si ça marche mais c'est vraiment élégant, je vais essayer ça, je suppose que je récupère la valeur désirée simplement de la manière suivante :

Code :

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

1
2
3
4
 
CountIt iter;
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), iter);
int tailleIntersection = iter.n;

N'est ce pas ?

[tnarol]

Bon évidemment ça ne marche pas du premier coup... et je n'ai pas la moindre idée de pourquoi.

Voici mon code :

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
 
template<typename T>
struct countIt : iterator<output_iterator_tag, T>
{
	int n;
	T t;
 
	countIt() : n(0) {}
 
	//int getSize() { return n; }
	T& operator*() {++n; return t;}
	countIt& operator++() {return *this;}
	countIt& operator++(int) {return *this;}
};
 
 
 
size_t utils::intersectionSize(const set<unsigned int>& set1, const set<unsigned int>& set2)
{
	countIt< set<unsigned int> > iter;
	set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), iter);
	return iter.n;
}

Et voici l'erreur de compilation :

1>utils.cpp
1>c:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3527) : warning C4996: 'std::_Set_intersection' was declared deprecated
1> c:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3512) : see declaration of 'std::_Set_intersection'
1> Message: 'You have used a std:: construct that is not safe. See documentation on how to use the Safe Standard C++ Library'
1> .\utils.cpp(23) : see reference to function template instantiation '_OutIt std::set_intersection<std::_Tree<_Traits>::const_iterator,std::_Tree<_Traits>::const_iterator,countIt<T>>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt)' being compiled
1> with
1> [
1> _OutIt=countIt<std::set<unsigned int>>,
1> _Traits=std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>,
1> T=std::set<unsigned int>,
1> _InIt1=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator,
1> _InIt2=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator
1> ]
1>c:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3504) : error C2679: binary '=' : no operator found which takes a right-hand operand of type 'const unsigned int' (or there is no acceptable conversion)
1> c:\Program Files\Microsoft Visual Studio 8\VC\include\set(153): could be 'std::set<_Kty> &std::set<_Kty>::operator =(const std::set<_Kty> &)'
1> with
1> [
1> _Kty=unsigned int
1> ]
1> while trying to match the argument list '(std::set<_Kty>, const unsigned int)'
1> with
1> [
1> _Kty=unsigned int
1> ]
1> c:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3515) : see reference to function template instantiation '_OutIt std::_Set_intersection<std::_Tree<_Traits>::const_iterator,std::_Tree<_Traits>::const_iterator,_OutIt>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,std::_Range_checked_iterator_tag)' being compiled
1> with
1> [
1> _OutIt=countIt<std::set<unsigned int>>,
1> _Traits=std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>,
1> _InIt1=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator,
1> _InIt2=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator
1> ]
1> c:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3527) : see reference to function template instantiation '_OutIt std::_Set_intersection<std::_Tree<_Traits>::const_iterator,std::_Tree<_Traits>::const_iterator,_OutIt>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,std::_Unchecked_iterator_tag)' being compiled
1> with
1> [
1> _OutIt=countIt<std::set<unsigned int>>,
1> _Traits=std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>,
1> _InIt1=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator,
1> _InIt2=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator
1> ]
1> .\utils.cpp(23) : see reference to function template instantiation '_OutIt std::set_intersection<std::_Tree<_Traits>::const_iterator,std::_Tree<_Traits>::const_iterator,countIt<T>>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt)' being compiled
1> with
1> [
1> _OutIt=countIt<std::set<unsigned int>>,
1> _Traits=std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>,
1> T=std::set<unsigned int>,
1> _InIt1=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator,
1> _InIt2=std::_Tree<std::_Tset_traits<unsigned int,std::less<unsigned int>,std::allocator<unsigned int>,false>>::const_iterator
1> ]

[Sylvain Togni]

Il y a deux problèmes :
- le paramètre template T doit être unsigned int, pas set<unsigned int>
- les itérateurs sont passés par copie dans la fonction set_itersection, ce qui fait qu'il faut récupérer la valeur de retour

Code :

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

1
2
3
4
size_t utils::intersectionSize(const set<unsigned int>& set1, const set<unsigned int>& set2)
{
	return set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), countIt< unsigned int >()).n;
}