récupération de l'intersection d'une liste.

Version imprimable

21/10/2010, 21h33
deubelte

récupération de l'intersection d'une liste.

Bonjour

J'aimerais vous soumettre un petit pb simple.

J'ai une liste de devises, sous forme de string:

liste1={"EUR", "JPY", "GBP", "USD", "NOK", "XXX"}

j'ai une autre liste de couples:

{("EUR", "EIBEUR"); ("EUR", EOIEUR"); ("EUR", "LIBEUR"); ("GPB", "LIBGBP"); ("ZZZ"; "LIBZZZ");}
Je pense représenter cela par des paires.

Maintenant, je voudrais récupérer dans la liste uniquement les couples dont le premier élément fait partie de la liste1.
Bien évidemment, je peux faire un truc bourrain. Mais je voudrais savoir s'il existe dans la STL, boost, un moyen pour récupérer l'intersection de deux listes.
Attention, il ne s'agit pas de récupérer la liste, mais uniquement la liste dont les premier termes de chaque pairs se trouvent dans la liste1.

Ainsi, avec mon exemple, on aurait:

{("EUR", "EIBEUR"); ("EUR", EOIEUR"); ("EUR", "LIBEUR"); ("GPB", "LIBGBP")}

car la devise ZZZ n'est pas présente dans la liste 1.

je vous remercie
21/10/2010, 21h43
NoIdea

Un iterateur devrait être tout aussi efficace que ce que boost implémente : tu es obligé de parcourir toute ta liste. Il doit bien avoir un truc a base de foncteur qui pourrait marcher mais l'algo fait maison marchera mieux et sera plus simple.
21/10/2010, 22h28
deubelte

Tu veux dire que ca pourrais aller plus vite si je refaisais moi-même l'algorithme?
je peux réinventer la roue?

Bonjour,

Il y aurait peut-etre une solution avec set_intersection(). Mais il y a plusieurs problemes:
1 - un probleme technique: il faut trouver un moyen pour permettre le cast implicite d'un pair<string,string> (ou une structure fait maison) en string (en l'occurrence la premiere string de la paire)
2 - un probleme de design: il faut utiliser des set, avec toutes les contraintes que cela comporte.

L'idee serait un code qui ressemblerait a ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <string>
#include <set>
#include <iostream>
#include <iterator>
 
using namespace std;
 
 
struct str_pair
{
    str_pair( const string & first, const string & second ) : first_( first ), second_( second ) {} 
    bool operator < ( const str_pair & other ) const { return ( first_ < other.first_ ); }
    string first_, second_;
};
 
ostream& operator << ( ostream & ostr, const str_pair & pair_in )
{
    ostr << pair_in.first_ << "/" << pair_in.second_;
    return ostr;
}
 
bool MyComp( const string & left, const str_pair & right )
{
    return ( left == right.first_ );
}
 
 
int main(int argc, char* argv[])
{
    set<string> v1;
    set<str_pair> v2;
    v1.insert("EUR");
    v1.insert("JPY");
    v1.insert("GBP");
    v1.insert("USD");
    v1.insert("NOK");
    v1.insert("XXX");
 
    v2.insert(str_pair("EUR", "EIBEUR"));
    v2.insert(str_pair("EUR", "EOIEUR"));
    v2.insert(str_pair("EUR", "LIBEUR"));
    v2.insert(str_pair("GPB", "LIBGBP"));
    v2.insert(str_pair("ZZZ", "LIBZZZ"));
 
    cout << "v1:" << endl;
    copy( v1.begin(), v1.end(), ostream_iterator<string>(std::cout, " - "));
 
    cout << endl << "v2:" << endl;
    copy( v2.begin(), v2.end(), ostream_iterator<str_pair>(std::cout, " - "));
    cout << endl << endl;
 
    set<str_pair> v3;
    set_intersection( v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3), MyComp );
    cout << "v3:" << endl;
    copy( v3.begin(), v3.end(), ostream_iterator<str_pair>(std::cout, " - "));
 
    cin.get();
    return 0;
}

code qui ne compile pas a cause du probleme 1.

Moi, j'ai fait cela:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std::set<std::string> aList;
aList.insert("USD");
aList.insert("GBP");
aList.insert("NOK");
aList.insert("EUR");
aList.insert("XXX");
 
 
std::set<std::string> alist2;
alist2.insert("EIBEUR");alist2.insert("OISEUR");alist2.insert("LIBEUR");alist2.insert("LIBGBP");
alist2.insert("LIBZZZ");alist2.insert("LIBNOK");
 
std::set<std::string> alist3;
 
std::set<std::string>::const_iterator it=alist2.begin();
for(;it!=alist2.end();++it){
	std::string ffs=it->substr(3,3);
 
	if(aList.find(it->substr(3,3))!=aList.end())  alist3.insert(*it);
}

Toutes les idées de correction sont les bienvenues

22/10/2010, 11h28
deubelte
code qui ne compile pas a cause du probleme 1.

Je voulais savoir en fait s'il existe un truc qui permet d'appliquer une procédure, une fonction, à une liste d'éléments.
apply_proc(aList, aFunction);

et qui renvoie bien sur une liste d'éléments qui ont été passés dans la aFunction

Je pensais à faire un truc comme ca:

En utilisant la fonction substr() et l'algorithm transform.
Mais il faut définir une userdefined function, qui prend un string, et qui renvoie un string modifié par substr().
Code:

1 2 3 std::string (*MyFunc)(std::string)=std::string::substr(); std::transform(aList.begin(),aList.end(),aList3,);
merci
22/10/2010, 11h49
el_socio

Je ne comprends pas bien ou tu veux en venir,
mais, si ca peut aider:
la fonction transform prends une fonction (ou un foncteur) en 4eme parametre:
http://r0d.developpez.com/articles/a...tl-fr/#LII-B-3

Pour appliquer une fonction a un conteneur, tu peut utiliser for_each (le troisieme parametre est la fonction, ou le foncteur. Dans ton cas, je pense que l' utilisation d' un foncteur serait mieux, car tu peux stocker, dans ce foncteur, le resultat de la sequence). Voir http://r0d.developpez.com/articles/a...tl-fr/#LII-A-1

merci pour la référence,
ca aide.

Donc, voila ou j'en suis:
Définition de la fonction user:
Code:

1 2 3 4 const std::string MyFunc(std::string mastring){ return mastring.substr(3,3); }
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 std::set<std::string> aList; aList.insert("USD"); aList.insert("GBP"); aList.insert("NOK"); aList.insert("EUR"); aList.insert("XXX"); std::set<std::string> alist2; alist2.insert("EIBEUR");alist2.insert("OISEUR");alist2.insert("LIBEUR");alist2.insert("LIBGBP"); alist2.insert("LIBZZZ");alist2.insert("LIBNOK"); std::set<std::string> aList3; std::transform(aList.begin(),aList.end(),aList3.begin(),MyFunc);
mais snif, quand je compile, j'obtiens comme erreur:

Error 1 error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>' (or there is no acceptable conversion)

22/10/2010, 12h13
el_socio

Je ne sais pas. Chez moi ton code compile (mais plante).
Le truc c'est que visiblement, le probleme a change depuis le premier message, alors je suis un peu perdu.

Au cas ou, j'avais trouve une solution au probleme tel qui est pose dans le premier message:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator> // juste pour le ostream_iterator, pour l'affichage
#include <vector>
 
using namespace std;
 
 
struct str_pair // pourrait etre une std::pair<string,string>
{
    str_pair( const string & first, const string & second ) : first_( first ), second_( second ) {} 
    string first_, second_;
};
 
// juste pour l'affichage
ostream& operator << ( ostream & ostr, const str_pair & pair_in )
{
    ostr << pair_in.first_ << "/" << pair_in.second_;
    return ostr;
}
 
struct Construct // foncteur pour construire le resultat
{
    Construct( const vector<string> & vref, vector<str_pair> & result ) : vref_( vref ), result_( result ) {}
 
    void operator () ( const str_pair & sp )
    {
        if ( find( vref_.begin(), vref_.end(), sp.first_ ) != vref_.end() )
            result_.push_back( sp );
    }
 
    const vector<str_pair> & GetResult() const { return result_; }
 
private:
    vector<str_pair> & result_;
    const vector<string> & vref_;
};
 
int main(int argc, char* argv[])
{
    vector<string> v1;
    v1.push_back("EUR");
    v1.push_back("JPY");
    v1.push_back("GBP");
    v1.push_back("USD");
    v1.push_back("NOK");
    v1.push_back("XXX");
 
    vector<str_pair> v2;
    v2.push_back(str_pair("EUR", "EIBEUR"));
    v2.push_back(str_pair("EUR", "EOIEUR"));
    v2.push_back(str_pair("EUR", "LIBEUR"));
    v2.push_back(str_pair("GPB", "LIBGBP"));
    v2.push_back(str_pair("ZZZ", "LIBZZZ"));
 
    // affichage v1
    cout << "v1:" << endl;
    copy( v1.begin(), v1.end(), ostream_iterator<string>(std::cout, " - "));
 
    // affichage v2
    cout << endl << "v2:" << endl;
    copy( v2.begin(), v2.end(), ostream_iterator<str_pair>(std::cout, " - "));
    cout << endl << endl;
 
    // construction resultat
    vector<str_pair> v3;
    for_each( v2.begin(), v2.end(), Construct( v1, v3 ) );
 
    // affichage resultat
    cout << "v3:" << endl;
    copy( v3.begin(), v3.end(), ostream_iterator<str_pair>(std::cout, " - "));
 
    cin.get();
    return 0;
}

23/10/2010, 11h24
zul

Le plus simple je pense est d'utiliser std::remove_if avec le prédicat qui va bien (first is not in list1).