Discussion :

[bill86]

Bonjour,

J'aimerais faire une comparaison entre deux vecteurs de classe A et je cherche à utiliser des fonctions prédéfinies pour gagner du temps. J'ai cherché dans la FAQ et sur le net et je me suis tombé sur le site de microsoft :
http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx

La méthode utilisée est intéressante, mais je veux bien utiliser une fonction prédéfinie de la bibliothèque STL par exemple.

Aviez vous une idée? ou dois je créer moi même un opérateur comme celui dans l'exemple précédent?


Merci d'avance.

[Jean-Marc.Bourguet]

Je comprends pas la question, tu pointes vers une page donnant un exemple d'utilisation d'une fonction de la SL.

[Nogane]

Bonjour,
Je ne crois pas que cet opérateur(== sur des vector) existe dans la STL, mais il est facile a faire. Sinon, il y as bien la fonction std::equal:

template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2 );

Elle est juste plus lourde syntaxiquement.

[Jean-Marc.Bourguet]

Je ne crois pas que cet opérateur(== sur des vector) existe dans la STL,

Il existe. De meme qu'operator!=, operator<, operator<=, operator>= operator>=.

[bill86]

Rebonjour,

Je reformule la question, y'a pas une autre solution, meilleure que celle citée permettant de faire une comparaison entre deux vecteurs d'objets (même si la comparaison se fait selon l'ordre lexicographique et que dans mon cas les vecteurs contiennent des objets non triés, mais bon je vais me débrouiller...).

Merci pour vos réponses.

[koala01]

Salut,

Il n'y a rien à faire, il n'est possible de comparer deux contenants qu'en... comparant leur contenu...

Comment voudrais tu faire autrement ?

Maintenant, il est différentes possibilités pour s'assurer que la comparaison entre deux objets soit "cohérente", et donc que la comparaison de deux conteneurs soit, elle aussi cohérente en fonction des objets qu'ils contiennent

[bill86]

Merci koala01, maintenant espérons que C++ soit gentil avec mes 200 000 vecteurs et le nombre de comparaisons engendré (soit une complexité de l'ordre de 200 000 au carée )...

Encore merci pour vos réponses.

[koala01]

C'est pour cela que la comparaison de conteneur s'effectue normalement sur des éléments triés, de manière à ce qu'elle puisse "se contenter" d'une comparaison dont la complexité est maximum de N

[bill86]

Absolument koala01, mais dans mon cas il n'est pas question de trier les éléments, déjà je cherche encore des optimisations dans mon programme...

[3DArchi]

Selon tes données et leur disparité, peut-être peux-tu te contenter d'un hash sur ton vecteur et tester l'inégalité (modulo collision) entre les 2 hashs pour en déduire qu'ils sont différents.

[bill86]

@3DArchi: mais quelle très bonne idée!
merci beaucoup, je vais essayer de faire ça

Merci encore!

[JolyLoic]

Attention, j'ai l'impression qu'il y a confusion entre deux notions distinctes :
- Comparer si des vecteurs sont égaux (mêmes éléments, dans le même ordre) : C'est ce que fait l'opérateur ==, en O(N)
- Comparer si des vecteurs contiennent les mêmes éléments, sans considération d'ordre : C'est ce que fait is_permutation pour des compilateurs récents. Sa complexité est en O(N²) dans le cas pire.

[bill86]

@JolyLoic : C'est la deuxième notion.
-"Comparer si des vecteurs contiennent les mêmes éléments, sans considération d'ordre" (et si on pourrait savoir si les éléments de l'un sont inclus dans l'autre ou pas ça sera génial).
Vous avez une idée?

J'ai cherché sur le net la fonction "is_permutation" j'ai pas trouvé des choses intéressantes.

Merci.

[Flob90]

is_permutation n'est pas encore sur tout les compilo (section 25.2.12 de la norme sinon).

Mais si tes élément appartiennent à un ensemble ordonné (strictement), copier puis trier les deux conteneurs et les comparer sera plus efficase il me semble (quasi-linéaire contre quadratique pour is_permuation)

[bill86]

Mes éléments n'appartiennent pas à un ensemble ordonné. En fait ce que je cherche à trouver c'est de savoir si un vecteur de string est inclus dans un autre vecteur de string ou pas (ou mm égal), c'est tout, sachant que les éléments string du vecteur ne sont pas ordonnée.

[Flob90]

(L'ensemble des chaines de caractères est ordonné, donc si tes éléments appartiennent à un ensemble ordonné)

Si tu ne te préoccupe pas des doublons tu peus utiliser un tri, unique puis set_difference, ca te donnera une complexité quasi-linéaire.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
bool is_include(std::vector<std::string> v1, std::vector<std::string> v2)
{
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	std::vector<std::string>::const_iterator i1 = unique(v1.begin(), v1.end());
	std::vector<std::string>::const_iterator i2 = unique(v2.begin(), v2.end());
	std::vector<std::string> r;
	return ( set_difference(v1.cbegin(), i1, v2.cbegin(), i2, r.begin()) == r.cbegin() );
}

Et après tu peus faire mieux en prenant en entrée des ranges et en jouant avec la classe de trait des itérateurs.

[bill86]

Juste la dernière instruction, j'ai compris comment ça se fait?

[bill86]

ReBonjour,

Je me suis trouvé dans l'obligation de trier les éléments du vecteur, j'ai pas trouvé une autre alternative. J'ai désormais deux vecteurs de string triés.
Cependant j'ai pas trouvé un algorithme ou une méthode efficace dans la bibliothèque STL répondant à mon besoin :

=> Fusionner les deux vecteurs si le nombre d'éléments en commun dépasse un nombre donnée.
Donc j'ai besoin de :
-Trouver le nombre d'éléments en commun
-L'indice du premier élément en commun dans le 1er vecteur
-L'indice du premier élément en commun dans le 2e vecteur
-Fusionner les deux vecteurs.

Merci d'avance.

[bill86]

Pour la fusion j'ai trouvé la fonction set_union :
http://www.cplusplus.com/reference/algorithm/set_union/
Je vais l'adapter pour les vecteurs de string...

[Flob90]

Tu as essayé de comprendre le code que j'ai donné en utilisant une doc de la bibliothèque standard ? (ou la norme ?)

Il y a trois étaqpes :
- Je trie les deux tableaux
- J'enlève les doublons dans chaques tableaux
- J'effectue la différence entre le premier est le second, ie je fait un nouveau tableaux dans lequel il n'y aura que les chaines de charactère du premier tableaux qui ne sont pas dans le second

Si ce nouveau tableau est vide alors le premier est inclu dans le second (démonstration mathématique assez rapide).