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;
}

[Olistan]

Petites questions d'un débutant qui essaye de comprendre cette approche élégante:
- Pourquoi c'est la définition de l'opérateur * qui incrémente la variable ?
- Quel est le rôle exact de l'opérateur ++ ? J'aurais pensé bêtement que c'est pour déplacer l'itérateur mais il retourne un pointeur this ? Et pourquoi le définir en left-value et right-value ?

Merci !

[tnarol]

Super ça marche ! Merci beaucoup.
J'ai une autre question du même style, cette fois sur les unions...
Je commence un nouveau thread.

[groscask]

Justement : ici, la surcharge de l'opérateur ++ permet à l'algo de la STL de faire ces appels. Mais nous, on se fiche de changer d'éléments, vu que le seul véritable but est de compter

Ensuite, lorsque tu utilises des itérateurs avec la STL, tu les 'déréférences', à la manière des pointeurs en C :

Code :

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

1
2
for (std::vector<int>::iterator i = vec.begin(); i != vec.end(); ++i)
    (*i) = ...;

Or, au sein même de la STL, lorsque tu utilises un iterateur perso, elle va appeler cet operateur * comme toi tu l'aurais fait.
Ici, cela permet donc de compter le nombre d'éléments. Et pour répondre aux critères d'un itérateur de... sortie, elle doit renvoyer une valeur. (complètement factice ici).

[yan]

Bonjour,
voici modifier pour ne pas appliquer l'operateur= qui peut être long

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
template<typename T>
struct countIt : iterator<output_iterator_tag, T>
{
    template<typename T2>
    struct no_egale
    {
        no_egale<T2> & operator=(const T2 &)
        {
            return*this;
        }
    };
	int n;
	no_egale<T> t;
 
	countIt() : n(0) {}
 
	//int getSize() { return n; }
	no_egale<T>& operator*() {++n; return t;}
	countIt& operator++() {return *this;}
	countIt& operator++(int) {return *this;}
};

[Sylvain Togni]

À noter que boost semble avoir un tel itérateur : boost::counting_iterator.