Prévoir la taille d'une intersection de 2 sets

Version imprimable

12/03/2008, 12h01
tnarol

Prévoir la taille d'une intersection de 2 sets

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

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:

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

En fait, ceci serait plus propre :

Code:

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

Citation:
Envoyé par Sylvain Togni
En fait, ceci serait plus propre :
Code:

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:

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 ?

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

Voici mon code :
Code:

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 :

Citation:

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

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:

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

12/03/2008, 16h14
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 !
12/03/2008, 18h23
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.
12/03/2008, 20h00
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:

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

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

Code:

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

13/03/2008, 17h14
Sylvain Togni

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