Hello.
Voilà, j’essaie de faire une méthode en c++ qui renverrait un tableau d’entier int[]
Seulement impossible de compiler. Quelle est la syntaxe correcte?
Voici la déclaration de la méthode dans le header:
int[] countmax(int vect[]);
/*
countmax returns mostfreq which contains the most frequent value in vect
(mostfreq[0]) and the number of occurences of this color (mostfreq[1])
If two values are as frequent as each other, the lowest is chosen
*/int *countmax(int vect[]);
ou
int *countmax(int *vect);
en allant plus loin, si tu pose la question c’est que tu n’as pas du voir les pointeur, attention a ne pas renvoyer l’adresse d’une variable locale d’une sous fonction (donc plus valide)
Ouep comme le dit Kzi, en C/C++ y’a pas moyen de passer un tableau par valeur. Fais bien gaffe à ce que tu fais, et assure-toi de bien comprendre ce qui se passe. A la limite, envisage la STL, c’est fait pour éviter ce genre de problèmes. Mais là aussi mieux vaut comprendre ce qu’on fait pour éviter les gros soucis de performance qui pourraient du coup apparaître.
je rejoins l’avis de me camarades precedent. Y’a pas mal des solutions pour résoudre ton problème (std::pair, passer le tableau résultat en paramètre…). Je te conseille l’approche suivante:
void countmax(int* inVect, int& outMostFreqValue, int& outRepeat);
Ca presente l’avantage de ne pas etre trop couteux (pas de copies inutiles), et tu as une déclaration de fonction bien claire peut éventuellement se passer de documentation…
Pour être un peu plus complet, ta fonction devra ressembler à
int* countmax(int vect[])
{
int *res = new int[2];
// code de la fonction
return res;
}
Et il ne faudra pas oublier de désallouer la mémoire dans le corps du programme.
c’est pour cela que, comme dit plus haut, il vaut mieux passer en paramètre le tableau résultat. En plus de gagner un peu en évitant une copie, tu peux te permettre d’avoir le tableau déclaré dans le corps du programme, ce qui évite une allocation dynamique couteuse en temps et source de fuites mémoires.
[quote=“Mizu, post:1, topic: 44687”]Hello.
Voilà, j’essaie de faire une méthode en c++ qui renverrait un tableau d’entier int[]
Seulement impossible de compiler. Quelle est la syntaxe correcte?
Voici la déclaration de la méthode dans le header:
int[] countmax(int vect[]);
/*
countmax returns mostfreq which contains the most frequent value in vect
(mostfreq[0]) and the number of occurences of this color (mostfreq[1])
If two values are as frequent as each other, the lowest is chosen
*/[/quote]
[code]std::pair<int, int> countmax(const std::vector &vecBlah)
{
std::vector<pair<int, int> > temp;
transform(vecBlah.begin(),
vecBlah.end(),
back_inserter(temp),
make_pair(_1, count(vecBlah.begin(), vecBlah.end(), _1));
return *max_element(temp.begin(), temp.end(), bind(pair<int, int>::right, _1) < bind(pair<int, int>::right, _2));
}[/code]
Ca compile sans doute pas mais tu as l’esprit C++ w4rl0rZ. Pourquoi se faire chier avec des int * en C++?
Mouais, perso je préfère largement la proposition de xmichelo. Avec des ref, on peut nommer les paramètres, et c’est bien plus lisible qu’un std::pair<int, int>. En plus de ça, plus je code et plus j’ai d’expérience, et plus j’ai appris à me méfier de tous les concepts avancés du C++. Alors c’est une question de goût c’est certain, et c’est surtout une question de domaine d’application, on a pas tous les mêmes contraintes. Mais moi mon grand principe c’est “keep it simple stupid” (KISS).
[code]void countmax(const std::vector & vec, int & max, int & count) {
max = elem.empty() ? 0 : elem[0];
count = 0;
for(int i = 0; i < elem.size(); ++i) {
if(elem[i] > max) {
max = elem[i];
count = 1;
} else {
if(elem[i] == max) ++count;
}
}
}[/code]
Ca n’utilise pas les algo de la STL, ça n’utilise pas d’itérateurs, ni de function binding, rien. Mais même un gars qui n’a jamais fait de C ou de C++ est capable de comprendre ce que ça fait et à quoi ça sert. J’insiste bien sur le fait que ton code soit irréprochable, Moloch. C’est aussi un code C++ fort élégant, et je comprends tout à fait que ce soit l’approche préférée pour certaines applications qui font des traitements lourds et complexes. Mais perso, et vu ce sur quoi je bosse, j’en suis revenu.
Ouais surtout que ca marche pas du tout mon truc impossible de faire une lambda… B) J’ai du me resoudre a ce truc moins w4rl0rd:
[code]class CountMaxFunctor
{
private:
vector m_v;
public:
CountMaxFunctor(const vector &v) : m_v(v) {}
public:
pair<int, int> operator ()(int i)
{
return make_pair(count(m_v.begin(), m_v.end(), i), i);
}
};
pair<int, int> countmax(const vector &vecBlah)
{
vector<pair<int, int> > temp;
CountMaxFunctor f(vecBlah);
transform(vecBlah.begin(),
vecBlah.end(),
back_inserter(temp),
f);
return *max_element(temp.begin(), temp.end());
}[/code]
Note, la comparaison par defaut de pair fait une comparaison first, puis second, d’ou l’ordre dans la paire. Enfin ca fait chier de faire un functor pour un truc aussi trivial, mais impossible malgre ma tentative de lambda:
[code]vector::const_iterator b = vecBlah.begin();
vector::const_iterator e = vecBlah.end();
transform(vecBlah.begin(),
vecBlah.end(),
back_inserter(temp),
bind(&make_pair<int, int>,
_1,
bind(&count<vector::const_iterator, int>, b, e, _1)()));[/code]
Passe pas… Probleme de passage de type rahhh. Je sens que je vais m’en retourner 10 fois dans mon sommeil.
Sinon je ne suis pas d’accord avec toi, en utilisant les algorithmes de la STL on arrive a detecter des la compilation des bugs sans compter que tu elimines tous les bugs potentiels du aux boucles mal faites, erreur d’etourderies (generalement detectees a la compilation), bozons fous, etc. Ca demande juste un petit temps d’adaptation. Regarde le code, pas de if, pas de for, pas de while, pas de new, pas de delete, bref tous les nids a bugs et buffer overflows, erreurs d’inatention, raus.
Apres ca depend du taff, de comment le code va vivre, les vaches, la formation de l’equipe, les motos toussa…
Non j’en démords pas, ton code fait deux copies complètes du tableau d’entiers, et plante sur la déréférenciation de l’iterateur de max_element si le tableau est vide. Sans compter le fait qu’il est deux fois plus long en termes de lignes de code (sans compter les lignes blanches), et qu’il a fallu trois tentatives pour l’écrire comparées à moins d’une minute pour ma part. Et au final quelqu’un qui n’a pas un niveau avancé en C++ ne sera pas capable de comprendre facilement de quoi il en retourne.
Pour les choses simples, la meilleure solution est la plus simple. Maintenant si on parlait d’un algo d’optimisation combinatoire à N dimensions, là effectivement vive l’abstraction. Mais ici, non. Et surtout que vue la question de Mizu, j’en déduis qu’il est encore en train de faire ses armes sur le langage, lui montrer ça comme étant la « bonne solution en C++ » c’est juste un truc pour le dégoûter à vie.
Comprenons-nous bien le C++ est mon language de prédilection. J’en écris 8 heures par jour pour le boulot, et 2-3 heures au soir pour le fun, sans compter les week-ends mais là c’est variable. J’ai écumé le code de la STL au point d’en récrire certaines parties en guise d’exercice pour être sûr de bien en comprendre le fonctionnement en détails, et j’ai une haute estime de la STL. Et j’adore aussi tout ce qui est programmation générique. Mais je suis réaliste, et je me rends compte que les solutions simples, même si moins élégantes pour certaines raisons (en partie théoriques), ont des avantages indéniables. Car le support des fonctions avancées du langage change d’un compilo à l’autre, que la généricité (dont on n’a pas si souvent besoin) vient souvent au prix d’une bonne couche de complexité, et surtout qu’en général on ne bosse pas qu’avec des gens qui ont une compréhension totale du langage. Et l’un des buts principaux de la programmation en équipe est d’écrire du code qui soit facilement compréhensible par les autres, et du coup facile à étendre et maintenir.
Ceci dit, j’encourage l’apprentissage et l’usage de ces fonctionnalités évoluées, mais dans les projets de petite ampleur, comme les projets personnels par exemple. Il n’y a rien de tel que d’acquérir par l’expérience une compréhension approfondie, pour réaliser pleinement les implications de tout ce qu’on fait, quel qu’en soit le niveau. Et pouvoir ensuite réfléchir la tête froide à associer le bon outil au bon usage. La STL, les templates, l’héritage, les interfaces, etc. là où c’est nécessaire, mais sans vouloir à tout prix en mettre partout par principe ou par désir d’impressionner.
On est tous passés (et perso je continue) par l’étape « when you got a hammer, everything looks like a nail ». Quand j’ai découvert la puissance des méchanismes d’héritage, j’ai conçu des applications dont la hiérarchie rendait minable celle de la monarchie française, quand j’ai découvert les templates j’avais plus un seul type natif dans mon code, etc. Puis j’ai réalisé les inconvénients de chaque approche, et maintenant je choisis pour chaque tâche l’outil que je vais utiliser en pesant le pour et le contre en connaissance de cause, j’imagine que c’est ce qu’on appelle l’expérience.
Oui c’est sans doute overkill pour un probleme de cette ampleur, mais la raison pour laquelle j’ai poste cette reponse (outre me la peter B) ) est tout simplement “en C++ on aurait plutot tendance a faire les choses ainsi, c’est ce vers quoi s’orienter tout en sachant que la route est longue”. Cela dit je suis un pietre pedagoge et j’en ai bien conscience.
Pour conclure ton code ne repond pas a la question posee puisque tu comptes le nombre d’occurence du maximum au lieu de retourner la valeur de l’occurence maximale. Si tu fais cette derniere chose, tu verras que le nombre de ligne de code sera superieur et que tu ne seras plus en O(n) avec un simple for (tu auras note que je suis en O(n*n), on peut sans doute faire mieux, j’ai d’ailleurs une idee pour retomber sur du O(n) avec un compromis temps memoire).
[code]vector v(10);
v[3] = 10;
int max = 0;
int count = 0;
// retourne max 10, count 1 au lieu de max 0 count 9
countmax(v, max, count);[/code]
Ou me tromperais-je?
Tiens oui, mon algo compte l’occurence du plus grand élément du tableau, j’ai lu l’énoncé trop rapidement B)
Allez, pour me faire pardonner :
[code]void countmax(const std::vector & elem, int & max, int & count) {
if(elem.empty()) {
max = 0;
count = 0;
return;
}
max = elem[0];
std::map<int, int> cmap;
for(int i = 0; i < elem.size(); ++i) {
++cmap[elem[i]];
}
for(int i = 0; i < elem.size(); ++i) {
if(cmap[elem[i]] > cmap[max]) max = elem[i];
}
count = cmap[max];
}[/code]
A vue de pif, c’est en O(2(n*log(m))), avec m le nombre d’éléments différents.
tsss on met pas de chiffres dans un ordre de grandeur … c est donc du O((n*log(m))) (en me basant sur le faites que dreamler a l ordre en question a peut etre juste)
Sinon c est plus un ordre de grandeur … mais un nombre d operation
Koubiak
Toi par contre, tu l’as pas B)
Bah je me souviens à l’univ on avait l’habitude de mettre les constantes quand elles étaient flagrantes. Mais je ne sais plus si on faisait ça par souci de précision, ou juste pour faire râler les mathématiciens qui allaient occuper le local après nous et se lamenter sur ce qui était inscrit au tableau B)
[code]pair<int, int> countmax_fast(const vector &vecBlah)
{
hash_map<int, pair<int, int> > mapFreqs;
pair<int, int> best;
for (vector<int>::const_iterator i = vecBlah.begin(); i != vecBlah.end(); i++)
{
mapFreqs[*i].second = *i;
mapFreqs[*i].first++;
if (mapFreqs[*i].first >= best.first)
best = mapFreqs[*i];
}
return best;
}[/code]
O(n) et STL über alles. B)
Ok, pwned B)
Mais tu avoueras que ta dernière proposition est bien plus simple que tes premières versions, et je la trouve 100% lisible, à part peut-être le fait que renvoyer un std::pair c’est pas parlant. Note que bon, dans ma solution on peut enlever le facteur 2 en groupant les deux boucles ça marche aussi (mais ça fait des assignements inutiles). Par contre, ok pour hash_map. Je ne sais pas pourquoi mais je pensais que c’était une extension pas très répandue, mais en fait y’a dans vc7 et vc8. Je devrais utiliser plus souvent.
Oui hash_map c’est über attention c’est dans stdext:: et ce n’est pas toujours plus intéressant qu’un map. hash_map est aussi présent dans g++. Faut savoir que sur les petites collections, le vector sera souvent le mieux car mine de rien l’insertion et le calcul du hash ça un coût. Ok dans le cas d’un int c’est peanut. Toute façon c’est un éternel débat et je suis incapable de donner une règle générale.
Quant au lisible pas lisible c’est très subjectif et une question d’habitude, au final faut commenter son code et expliquer ce qu’on fait. Parfois un bind c’est mieux qu’un functor parce que le bind c’est en place donc la lecture reste linéaire. Je travaille beaucoup et m’exerce beaucoup avec les bind donc j’ai tendance à en user et en abuser et quand je maîtriserai bien je l’utiliserai sans doute moins comme tu l’as dit mais je pense que c’est quand même un outil très très puissant.
Pour moi l’axe du futur c’est pouvoir détecter à la compilation un maximum d’erreur, une piste que la metaprogrammation offre.
Ca c’est sur, mais le futur tend aussi vers beaucoup de reflection.