Operation sur duplicates dans un vecteur, solution elegante ?

John Deuf wrote:

J'ai un vecteur d'objets (grosso-modo un string et un int
comme membres). Je voudrais que les objets identiques (string
identiques) dans mon vecteur ne fassent plus qu'un en
s'additionnant (ajout des int).

Y-t-il une solution elegante avec les algorithmes de la STL ou
boost ? J'ai vu qu'on pouvait faire un srd::sort() puis
std::unique(), mais ca ne fait que les supprimer.

Bien entendu, j'ai surcharge les operateurs == et += de mon
objet.

Je sais que tu n'est pas un débuttant, mais est-ce que tu as
considéré la possibilité d'utiliser un std::map< std::string,
int >, avec :
myMap[ obj->text ] += obj->value ;
il me semble que ça résoud le problème d'office.

Si par la suite, tu as vraiment besoin d'un vecteur de tes
objets, donne le un constructeur :
Object::Object(
std::vector< std::string, int >::value_type const& ) ;
et alors :
std::vector< Object > v( myMap.begin(), myMap.end() ) ;
doit faire l'affaire.

--
James Kanze mailto: james.kanze@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

James Kanze :

Je sais que tu n'est pas un débuttant

Oh si je le suis ;-)

mais est-ce que tu as
considéré la possibilité d'utiliser un std::map< std::string,
int >, avec :
myMap[ obj->text ] += obj->value ;
il me semble que ça résoud le problème d'office.

Mais ca ne casse pas l'encapsulation cette methode ?
Ou je devrais alors ecrire des getters, je n'ai pas trop envie que l'on
puisse acceder aux donnees directement.

Et en realite, dans l'objet que j'utilise la donnee est un peu plus
complexe qu'un int, c'est est un vector de double de taille variable.

J'ai deja implemente la chose avec des boucles, mais je me demandais s'il
on pouvais ecrire quelque chose de plus elegant, du genre :

do_on_duplicates( v.begin(), v.end(), plus<Object>());

Mais apparament, pas assez de personnes ne sont tombees sur le probleme
avant moi pour ecrire l'algorithme :-)

--
John Deuf

John Deuf wrote:

James Kanze :

mais est-ce que tu as
considéré la possibilité d'utiliser un std::map< std::string,
int >, avec :
myMap[ obj->text ] += obj->value ;
il me semble que ça résoud le problème d'office.

Mais ca ne casse pas l'encapsulation cette methode ?

Quelle méthode ?

Tout ce que tu avais décrit, c'est une structure de données -- le
cible,
en somme. J'ai voulu suggérer une façon possible d'y arriver. Ne
sachant
pas plus sur le contexte, c'est difficile à savoir s'il convient ou
non.

Si pour une raison ou une autre, tu l'estîmes préférable de
maintenir le
vector, quelque chose du genre :

pos = std::find( v.begin(), v.end(), obj ) ;
if ( pos == v.enc() ) {
v.push_back( obj ) ;
} else {
*pos += obj ;
}

ferait l'affaire. Si le vecteur devient assez gros pour que la
recherche
linéaire devient trop couteuse, on remplace find par lower_bound, et
on
fait l'insertion au bon endroit pour garder le vector trié.

Ou je devrais alors ecrire des getters, je n'ai pas trop envie que
l'on puisse acceder aux donnees directement.

Et en realite, dans l'objet que j'utilise la donnee est un peu plus
complexe qu'un int, c'est est un vector de double de taille variable.

J'ai deja implemente la chose avec des boucles, mais je me demandais
s'il on pouvais ecrire quelque chose de plus elegant, du genre :

do_on_duplicates( v.begin(), v.end(), plus<Object>());

Mais apparament, pas assez de personnes ne sont tombees sur le
probleme avant moi pour ecrire l'algorithme :-)

D'abord, avec les informations que j'ai sous la main, je ne suis pas
sûr
d'avoir bien compris le problème. Si l'idée, c'est de faire
l'opération
d'un coup, après que tous les éléments sont créés une première
fois,
j'aurais tendance à utiliser un std::set intermédiaire. Pour le
générer,
on a le choix entre une boucle explicite avec un opérateur comme
ci-dessous ou d'écrire une variante sur insertion iterator et
d'utiliser
std::copy. boost::function_output_iterator semble tout à fait indiqué
dans le deuxième case :

class Updater
{
public:
Updater( std::set< C, COrder >& target )
: myTarget( &target )
{
}
void operator()( C const& obj ) const
{
const_cast< C& >((*myTarget->insert( obj.asIndex()
).first)) += obj ;
}
private:
std::set< C, COrder >*
myTarget ;
} ;

void
fixup( std::vector< C >& v )
{
std::set< C, COrder >
tmp ;
std::copy( v.begin(), v.end(),
boost::make_function_output_iterator( Updater( tmp ) )
) ;
std::vector< C > result( tmp.begin(), tmp.end() ) ;
v.swap( result ) ;
}

Dans l'ensemble, je préfèrerais bien utiliser un std::map, et éviter
le
const_cast. Dans ce cas-là, il faudrait bien exposer la partie de
l'objet qui sert de clé, au moins que fixup n'en soit membre. Même
avec
std::set, ci-dessus, il faut bien prévoir la fonction membre
asIndex(),
qui renvoie un objet avec la même chaîne, mais avec la valeur de
l'int
0. Avec map, on a simplement un std::map< C::IndexType, C >, et
l'opérateur dans Updater devient « (*myTarget)[ obj.index() ] += obj
».
En fin de compte, si tu veux gérer une identité selon une clé, il
faut
bien que le code externe le sache.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

En fin de compte, si tu veux gérer une identité selon une clé, il
faut bien que le code externe le sache.

Non, je ne veux pas gérer une identité selon une clé, je veux
additionner les objets identiques dans un container.
Et pour ça, que l'objet aient les opérateurs == et += doit suffire
(et c'est le cas de mon objet).

J'ai décris mon objet à titre indicatif (et ça t'a fait pensé a une
structure de données) mais finalement ce n'est pas utile et ça
pourrait être n'importe quoi (des string par exemple).

Ta solution est certainement plus acceptable niveau performance voire
modélisation, mais actuellement mon objet existe déjà et je ne veux
pas casser l'encapsulation.

Apparament, il n'y a pas d'algorithme dejà fait pour ça, il faudrait
donc que je m'y atèle... J'ai trouvé sur le web un article de Torjo
sur l'écriture d'un stable_unique(). Il ne reste peut-être pas
beaucoup de travail pour le généraliser à d'autres opérations que
la suppression.

John Deuf wrote:

En fin de compte, si tu veux gérer une identité selon une
clé, il faut bien que le code externe le sache.

Non, je ne veux pas gérer une identité selon une clé, je veux
additionner les objets identiques dans un container. Et pour
ça, que l'objet aient les opérateurs == et += doit suffire (et
c'est le cas de mon objet).

Ça dépend. Si le seul opérateur de comparaison est ==, la seule
solution pour la récherche est une récherche linéaire
(std::find).

Intuitivement, je le trouve un peu bizarre que l'opérateur +=
n'influce pas sur l'opérateur ==.

J'ai décris mon objet à titre indicatif (et ça t'a fait pensé
a une structure de données) mais finalement ce n'est pas utile
et ça pourrait être n'importe quoi (des string par exemple).

Ça, je l'avais compris.

Ta solution est certainement plus acceptable niveau
performance voire modélisation, mais actuellement mon objet
existe déjà et je ne veux pas casser l'encapsulation.

Apparament, il n'y a pas d'algorithme dejà fait pour ça,

En tant que tel, non. En révanche, il existe des algorithmes qui
puissent en être adaptés.

il faudrait donc que je m'y atèle... J'ai trouvé sur le web un
article de Torjo sur l'écriture d'un stable_unique(). Il ne
reste peut-être pas beaucoup de travail pour le généraliser à
d'autres opérations que la suppression.

Je ne connais pas l'article de Torjo, mais std::unique ne ferait
ton affaire que si le vecteur est trié (ce qui impose une
rélation d'ordre).

Si le nombre d'éléments n'est pas trop grand (ce qui vaut mieux,
si tu utilises une récherche linèaire), je pencherais toujours
vers une solution avec std::copy vers un temporaire, avec un
function_output_iterator de Boost, puis un swap. La seule chose
qui change par rapport à ma suggestion avec std::set, c'est dans
Updater::operator()(), tu utilises le code que j'avais donné
pour la gestion du vector au fil de l'eau, c-à-d :

pos = std::find( v.begin(), v.end(), obj ) ;
if ( pos == v.enc() ) {
v.push_back( obj ) ;
} else {
*pos += obj ;
}

Note bien, cependant, que toute algorithme à base de la récherche
linéaire sera quadratique, et donc ne conviendra que pour des
ensembles assez petits.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34