Bonjour.

Dans notre projet nous rencontrons un problème bien ennuyeux.
Pour faire simple, nous avons une classe 'BasePolynome' qui possède un attribut 'mon_polynome'. Cette classe possède trois opérateurs : +, - et *. Pour chacun de ces opérateurs nous rencontrons le même problème.

#include <map>
class BasePolynome
{
    public :
        BasePolynome& operator+=(const BasePolynome& poly);
    private :
        std::map<unsigned int, float> mon_polynome;
        unsigned int mon_degre_max;
};

Voici le code de l'opérateur += :

BasePolynome& BasePolynome::operator+=(const BasePolynome& poly)
{
    // Boucle sur les valeurs de poly, tant qu'on est pas à sa valeur max.
    for (unsigned int i = 0; i <= poly.mon_degre_max; ++i)
    {
        // Si l'indice n'existe pas dans this -> création.
        // Nous pourrions nous en passer, mais c'est plus sur ainsi.
        if (!ClefExiste(i)) // Fonction membre
            mon_polynome[i] = 0.f;
        // Addition.
        mon_polynome[i] += poly.mon_polynome.at(i);
    }
    // Adaptation du degré max de this.
    if (mon_degre_max < poly.mon_degre_max)
        mon_degre_max = poly.mon_degre_max;
    // Fini.
    return *this;
}

Premier constat : at n'existe pas sur tout les compilateurs. Petite recherche dans les doc : n'existe pas [officiellement]. Qu'en est-il? Pour la prochaine réforme, ou je ne sais quoi? [ Sous linux, avec g++ 4.2 et libc++6.4.2 ça compile. ].

Bon bref, nous changeons at pour l'opérateur []. Cette fois, problème à la compilation :

Citation : g++

BasePolynome.cpp: In member function «BasePolynome& BasePolynome::operator+=(const BasePolynome&)»:
BasePolynome.cpp:121: erreur: no match for «operator[]» in «poly->BasePolynome::mon_polynome[i]»
note: candidats sont: _Tp& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const _Key&) [with _Key = unsigned int, _Tp = float, _Compare = std::less<unsigned int>, _Alloc = std::allocator<std::pair<const unsigned int, float> >] <near match>

Si j'ai bien compris, c'est un problème de const . 'poly' étant une référence constante, impossible de faire de modification, et donc l'opérateur [] qui retourne une référence non constante ne peux pas être appelé.

Pourquoi l'opérateur [] de std::map n'est-il pas décliné en version constante comme l'est std::vector? C'est bien embêtant.

Alors nous sommes face à deux solutions :

• Enlever la constance de 'poly';
• Utiliser mutable sur 'mon_polynome'.

La première me semble pas bien du point de vue logique.
La deuxième me pose un problème : est-ce la bonne solution?


Quel est votre avis?

Merci d'avance [et merci à ceux qui ont tenu à la lecture ].
Hiura

En fait l'opérateur [] de map est techniquement inutile: il ne fait qu'appeler find et insert, du coup si tu fais m[k] et que la clé "k" n'existe pas dans "m", l'opérateur la créé, c'est pour çà qu'il n'est pas const.
Si tu veux faire avec const tu fais ainsi:

template<typename Key,typename Data,typename Compare,typename Alloc>
const Data& map_at(const std::map<Key,Data,Compare,Alloc>& map,const Key& key)
{
   std::map<Key,Data,Compare,Alloc>::const_iterator it=map.find(key);
   if(it==map.end())
      throw std::runtime_error("La clé n'existe pas pas");
   else
      return it.second;
}

(non testé)
La seule idée c'est de faire "find" au lieu de [].
Remarque: su tu est sûr que la clé existe, tu peux te contenter de faire:

// je met une macro mais en réalité il faudrait le refaire à la main à chaque fois car les macro c'est mal
#define map_at(map,key) \
   (map.find(key).second)

N'attaque pas directement ta map.
A la place, définis-toi un opérateur [] (dont tu auras besoin de toutes façons) qui réalises un std::map::find, et renvoie 0 si tu n'as pas trouver l'itérateur qui va bien.

Mais ... quitte à utiliser une structure comme une std::map, je tenterais plutôt de réaliser un parcours concurrent, via itérateurs, sur les deux tables. Histoire de faire du O(n) plutôt que du O(ln n).

PS: La table est déjà capable de te fournir le degre max.

Merci de vos réponses si rapide.

J'ai donc écrit l'opérateur []. Est-il bon? [ Histoire de pas partir à côté . ]

/*!
* \brief Opérateur d'accès aux valeurs de \b mon_polynome.
  \warning Cette fonction ne vérifie pas si la clef existe. Utilisez
        \b BasePolynome::ClefExiste pour le savoir. Si une clef qui
        n'existe pas est donnée alors \b 0 est retourné.
* \param clef : le degré cherché.
* \return La valeur correspondant à \b clef, ou \b 0.
* \note Cette fonction est constante.
*/

float BasePolynome::operator[](const unsigned int clef) const
{
    typedef std::map<unsigned int, float>::const_iterator cit;
    // Recherche de la clef.
    const cit it = mon_polynome.find(clef);
    // Elle existe.
    if (it != mon_polynome.end())
        // Retour de la valeur assossiée.
        return it->second;
    // C'est pas le cas.
    else
        // Valeur par défaut.
        return 0.f;
}

Si la fonction est constante c'est voulu : nous ne voulons pas que l'objet soit modifié par cette fonction.

Et la nouvelle version de l'opérateur += :

BasePolynome& BasePolynome::operator+=(const BasePolynome& poly)
{
    // Boucle sur les valeurs de poly, tant qu'on est pas à sa valeur max.
    for (unsigned int i = 0; i <= poly.mon_degre_max; ++i)
    {
        // Si l'indice n'existe pas dans poly -> prochaine itération.
        if (!poly.ClefExiste(i))
            continue;
        // Si l'indice n'existe pas dans this -> création.
        // Nous pourrions nous en passer, mais c'est plus sur ainsi.
        if (!ClefExiste(i))
            mon_polynome[i] = 0.f;
        // Addition.
        mon_polynome[i] += poly[i];
    }
    // Adaptation du degré max de this.
    if (mon_degre_max < poly.mon_degre_max)
        mon_degre_max = poly.mon_degre_max;
    // Fini.
    return *this;
}

Citation : lmghs

Mais ... quitte à utiliser une structure comme une std::map, je tenterais plutôt de réaliser un parcours concurrent, via itérateurs, sur les deux tables. Histoire de faire du O(n) plutôt que du O(ln n).

Nous ne maitrisons pas encore tout à fait cet aspect du C++, et nous sommes limité dans le temps. P-ê changerons-nous notre code après coup. Mais merci du conseil.

Citation : lmghs

PS: La table est déjà capable de te fournir le degré max.

Je n'ai pas trouvé. Quelle est cette fonction? map::upper_bound ne retourne pas le plus élevé, je devrais donc faire une sorte de boucle. C'est pas moins efficace?

juste pour info, il y a une discussion semblable sur op[] de std::map sur fclc++, je ne l'ai pas lu en entier mais il me semble que la solution touvé est la meme qu'ici

http://groups.google.com/group/fr.comp.lang.c++/browse_thread/thread/1a42a68691c1a6c5#

Pourquoi représenter un polynome sous la forme d'une std::map ?

Un "simple" vector ne serait-il pas adapté ? Dans le sens où vous n'avaz pas besoin de clés autres que des int, non ?

upper_bound , lower_bound et equal_range sont des fonctions de recherche.

Le dernier exposant, tu l'obtiens avec rbegin()->first si non vide.

S'il y a beaucoup de GROS trous, une map peut être mieux qu'un vecteur, sinon, cela ne vaut pas le coup

Hum, je ne vois pas pourquoi rbegin()->first donnerait le plus élvé puisque "map" ne fournie aucune garantie sur l'ordre de parcours des itérateurs, il se pourrait(bien que dans la pratique, l'implémentation sous forme d'arbre donne cette propriété) que rbegin()->first renvoie le plus petit ou même n'importe lequel. Tout du moins, la doc de la STL de SGI ne spécifie rien là dessus.

set et map sont des conteneurs triés. Sans cette propriété, tu pers l'accès en O(ln n)

Et puis SGI spécifie très bien que map modélise un UniqueSortedAssociativeContainer, qui est un raffinement de SortedAssociativeContainer, chez lesquels: "their elements are always sorted in ascending order by key." Chose encore plus détaillée dans les invariants plus bas.

Citation : Nanoc

Pourquoi représenter un polynome sous la forme d'une std::map ?

Un "simple" vector ne serait-il pas adapté ? Dans le sens où vous n'avaz pas besoin de clés autres que des int, non ?

C'était notre ancienne idée. Si on a opté pour une std::map c'est principalement pour avoir des trous [ ne pas représenter tous les degrés ] . Et p-ê que dans un futur lointain on permettra l'utilisation de degré fractionnel. Sait-on jamais.

Citation : lmghs

upper_bound , lower_bound et equal_range sont des fonctions de recherche.

Le dernier exposant, tu l'obtiens avec rbegin()->first si non vide.

Donc comme la map est triée on peut prendre le dernier élément comme la clef la plus élevée. C'est bon à savoir. Merci.
Mais tu dis "si non vide". Qu'entends-tu par là?

Citation : Chlab_lak

juste pour info, il y a une discussion semblable sur op[] de std::map sur fclc++, je ne l'ai pas lu en entier mais il me semble que la solution touvé est la meme qu'ici

http://groups.google.com/group/fr.comp.lang.c++/browse_thread/thread/1a42a68691c1a6c5#

Je n'ai pas tout lu, mais il propose de faire un peu la même chose : créer une classe "redéfinissant" [ ce n'est pas le bon terme, mais je trouve pas... ] std::map. Un peu la même chose que lmghs l'a proposé.

A part ça, mon code est-il correcte?

Ok, j'avais pas pensé à l'optimisation qui pouvait découler de la suppression des "trous".

Concernant le code, ne devrais tu pas retourner une référence constante et faire une deuxième version non-constante retournant cette fois un référence (non-constante) ?
C'est en tout cas comme ça que sont implémentés ces opérateurs le plus souvent.

En fait, si je n'ai pas retourné une référence /non/constante, c'est par ce que la modification par ce bié(ortho?) ne doit pas être permise [notre programme n'est pas très "conventionnel", on fait qqch d'un peu particulier ; du moins, pour l'instant cette utilisation nous suffit (à débatre?)].


Question optimisation, une référence constante est-elle mieux qu'un float?

const float& BasePolynome::operator[](const unsigned int clef) const;
// Ou
float BasePolynome::operator[](const unsigned int clef) const;
// ?

Merci de votre aide.

"biais."

std::vector renvoie une référence constante, car il donne accès à sa représentation interne : buffer d'éléments contigus ; cela permet aussi d'accéder directement à une entité stockée.
Or tu stockes avant tout des valeurs (non contigües) et pas des entités. Du coup, leur donner un accès serait, je pense, mal venu.

D'accord. Donc plutôt float que const float& , isn't it?

Ici je pense oui.
Certains préfèrent carrément renvoyer des "const float". Cf discussion sur GOTW normalement. Bien qu'abusant des const, j'avoue que ne pousse pas encore le vice jusque là.

Renvoyer un const peut-il poser problème dans certain cas? [ Je n'ai pas vraiment d'exemple en tête, mais si je reçois un type constant d'une fonction, si je veux la modifier en local, pour ne sais-je quelle raison, il n'y aura pas de problème de const-pas const? ]

Cela peut poser problème dans des cas où l'on ne fait probablement pas un truc que l'on devrait faire. D'où l'intérêt de la chose.

http://www.gotw.ca/gotw/006.htm

J'ai trouvé la réponse :

Citation : au point 5

(It should not return 'const int' in this case, though, since the int is already an rvalue and to put in 'const' can interfere with template instantiation and is confusing, misleading, and probably fattening.)

Merci pour le lien, très intéressant.

Je crois que cette fois c'est bon, encore merci à tous!

Petit Edit :
-> Grâce à std::map::rbegin()->first un problème inconnu à été résolu! [enfin, ça à permis que je trouve l'erreur ]
Alors encore merci!