Discussion :

[tnarol]

Salut,

Je veux l'utiliser pour faire l'intersection entre 2 std::set<std::string> dont les tailles sont par exemple 3 et 4. Ma question concerne l'iterateur de résultat qu'on donne en 5ème argument à la fonction.
J'ai créé un résultat std::set<std::string> result;
Dois-je redimensionner result en prévoyant une taille maximale de 3 ou bien je peux me contenter de donner result.begin() et il se débrouillera tout seul pour y insérer des éléments ?

Merci

[r0d]

Bonjour,

je ne suis pas trés à l'aise avec set_intersection, mais le code suivant pourra peut-être t'aider:

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
//je commence par remplir 2 sets s1 et s2
std::set<std::string> s1;
s1.insert("toto");
s1.insert("titi");
s1.insert("tata");
 
std::set<std::string> s2;
s2.insert("tutu");
s2.insert("toto");
s2.insert("titi");
s2.insert("tyty");
 
// je prépare s3 qui va récupérer le résultat le l'intersection.
std::set<std::string> s3;
// je copie le plus grand set (entre s1 et s2) dans s3
s3 = ( s1.size()>s2.size() ) ? s1 : s2;
// je remplis s3 de chaînes vide
std::fill(s3.begin(), s3.end(), "");
 
// j'applique set_intersection
std::set<std::string>::iterator it = std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin() );
 
//je "retaille" s3 de façon à ce que les éléments superflux soient supprimés
std::set<std::string>(s3.begin(), it ).swap(s3);

Pour répondre à ta question: oui, il faut pré-allouer le set dans lequel tu vas mettre le résultat.

[tnarol]

Merci, ça répond effectivement parfaitement à ma question.
En fait pour ce cas précis je me fous complètement de connaître l'intersection, tout ce qui m'intéresse c'est de savoir si elle est vide ou pas. C'est pourquoi je trouve assez rébarbatif de devoir faire autant de choses sur une variable que je n'utilise pas en fin de compte... Connaissez vous un façon aussi fiable mais plus directe d'obtenir l'info ?

[r0d]

Si j'ai bien compris, tu veux juste tester s'il existe au moins un élément commun entre deux conteneurs.
Si c'est le cas, je pense que le plus simple est d'utiliser la fonction find_first_of (déclarée, à l'instar de set_intersection, dans l'en-tête <algorithm>):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::set<std::string> s1;
std::set<std::string> s2;
 
//... remplissage de s1 et s2
 
std::set<std::string>::iterator it = std::find_first_of(s1.begin(), s1.end(), s2.begin(), s2.end() );
if (it==s1.end()) // si (it==s1.end()) cela signifie qu'aucun élément n'est commun à s1 et s2
{
//code
}
else // sinon cela signifie qu'il existe au moins 1 élément commun
{
//code
}

Hope it helps.

[tnarol]

Si j'ai bien compris, tu veux juste tester s'il existe au moins un élément commun entre deux conteneurs.

Oui c'est ça. Je suppose que la version find_first_of est plus efficace...

[r0d]

Beaucoup plus efficace en effet, et plus simple à écrire

[JolyLoic]

Sauf que find_first_of est de complexité O(n1*n2), alors qu'un set_intersection est de complexité O(n1+n2), donc à part si les deux set ont en général beaucoup d'éléments communs (dans ce cas, le find s'arrêtera vite), le set_intersection sera bien plus rapide.

Bien entendu, le plus rapide consisterait à faire une sorte de find_first_of utilisant le fait que les séquences sont triées, qui est une information très intéressante, probablement d'ailleurs en s'inspirant de l'algo de set_intersection et en ajoutant un court circuit dès qu'un élément commun est trouvé.

[r0d]

En effet. Je te remercie pour cette précision, et ça me donne un élément de réponse pour une question que je me pose depuis quelque temps: a quoi servent les algo set_intersection, set_difference, set_union, etc. ?

[HanLee]

En effet. Je te remercie pour cette précision, et ça me donne un élément de réponse pour une question que je me pose depuis quelque temps: a quoi servent les algo set_intersection, set_difference, set_union, etc. ?

Ben... en théorie des ensembles t'as jamais manipulé l'intersection, la différence et l'union de 2 ensembles ?

[r0d]

Si, mais ce que je veux dire, c'est que je trouve que ces fonctions sont tellement mal définies qu'elle sont inutilisables telles qu'elles. Ce topic en est un exemple parfait: on ne sait pas à l'avance combien d'éléments vont être communs à nos deux conteneurs. Donc si je devais faire une intersection entre deux set, je le ferais via un foncteur qui utilise un insert et qui serait appelé par une boucle for_each, plutôt que d'utiliser un set_intersection.

[HanLee]

Si, mais ce que je veux dire, c'est que je trouve que ces fonctions sont tellement mal définies qu'elle sont inutilisables telles qu'elles. Ce topic en est un exemple parfait: on ne sait pas à l'avance combien d'éléments vont être communs à nos deux conteneurs. Donc si je devais faire une intersection entre deux set, je le ferais via un foncteur qui utilise un insert et qui serait appelé par une boucle for_each, plutôt que d'utiliser un set_intersection.

En fait la bonne méthode c'est d'utiliser un insert_iterator construit à partir du std::set qui contiendra le résultat :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef std::set<std::string> string_set;
 
string_set E, F, G;
 
// code intense
 
std::set_intersection(E.begin(), E.end(),
                      F.begin(), F.end(),
                      std::inserter(G, G.begin()));
 
// Et voila, G = E <inter> F

[JolyLoic]

On peut aussi mettre le résultat dans un autre container, qui aura a priori moins d'overhead, comme par exemple un vector, avec un back_inserter.

Mais, la meilleure solution est sûrement un truc genre :

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
template<class It1, class It2>
bool intersects (It1 b1, It1 e1, It2 b2, It2 e2)
{
  while (b1 != e1 && b2 != e2)
  {
    if (*b1 < *b2)
    {
      ++b1;
    }
    else if (*b2 < *b1)
    {
      ++b2;
    }
    else 
    {
      return true;
    }
  }
  return false;
}

[Alp]

Oui, du moment que ce sont des sets, ça marche.

[JolyLoic]

Des set, ou des vecteurs triés, ou des listes triées, ou des deques triés, ou des userContainer triés...

[Alp]

Oui.
Mais par défaut c'est set.

A la limite, on peut à coups de traits optimiser l'intersection : si pas trié, on trie (selon le conteneur on trie différemment), puis on appelle ce code.

[koala01]

Salut,

Juste une petite remarque concernant une partie bien précise du code fournis au départ par r0d... que voici

Code :

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

1
2
// je copie le plus grand set (entre s1 et s2) dans s3
s3 = ( s1.size()>s2.size() ) ? s1 : s2;

Dans le sens où, au mieux, l'intersection ne contiendra que l'ensemble du plus petit set, je copierais plutôt le plus petit que le plus grand dans s3..

Le code deviendrait alors

Code :

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

1
2
// je copie le plus petit set (entre s1 et s2) dans s3
s3 = ( s1.size()>s2.size() ) ? s2 : s1;

à moins, bien sûr, que je n'ai loupé quelque chose sur le fonctionnement de set_intersection (ce qui est toujours possible )

[r0d]

non tu as raison. Mais de toutes façon, ce n'est pas la bonne façon de procéder