Quel conteneur choisir ?

On Jun 10, 5:26 pm, jeremie fouche <jfou...@voila.fr> wrote:

Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.

Premiere approche : std::map<Attribute::Name, Attribute> Pour
assurer l'unicité d'un attribut donnée, c'est nickel, mais il
sont forcement rangé dans l'ordre alphabetique.

Deuxieme approche : std::list<Attribute>
Pour l'ordre, c'est nickel, par contre, pour assurer l'unicité d'un
Attribute, il faut se taper a chaque ajout une recherche dans la list
afin de verifier qu'un Attribute ayant le même Name n'existe pas. BOF a ussi.
D'ailleurs, je ne sais pas trop si vector<> et list<> ici ne sont pas
équivalent ?

La première question est : combien de paires
attributes-valeurs ? Jusqu'à quelque dizaines, j'utiliserais un
std::vector< AttributeValuePair >, sans plus de soucis. Quand le
compte commencent à dépasser les centaines de milliers,
j'adopterais sans doute quelque chose de plus compliquées, dès
le départ. Entre les deux, je commencerais probablement avec la
solution std::vector, mais je ferais particulièrement attention
de bien l'encapsuler, de façon à pouvoir le changer par la
suite, si ça s'avérait nécessaire.

Troisieme approche : Un joyeu combiné des 2 solutions précedentes :
- std::map<Attribute::Name, Attribute>
- std::list< std::map<Attribute::Name, Attribute>::const_iterator >
ou std::list< std::map<Attribute::Name*>

J'ai pas testé, mais je pense que cela fonctionne. Ca me parrait juste
un poil lourd pour ce que je veux faire, non ?

Tu veux dire quelque chose du genre :

std::map< Attribute, Value >elems ;
std::vector< std::map< Attribute, Value >::iterator >
order ;

Ça dépend. Tant qu'on n'en a pas besoin, je l'éviterais. C'est
toujours plus difficile de maintenir deux collections en sync
que de n'en avoir qu'une.

Quatrieme approche : std::map<Attribute::Name, Attribute, ????>
Rajouter un predicat qui n'est pas std::less<std::string> (par defaut),
mais un autre qui ne change pas l'ordre d'insertion dans la map. C'est
possible ca ?

Non. Il faut une deuxième map. C'est le rôle de order, ci
dessus.

Mais comme j'ai dit au départ, std::find sur un std::vector est
largement suffisant pour plusieurs dizaines d'attributes.

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
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

Bonjour

Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.

[...]

Des idées ?

Peut-être que boost::multi_index peut t'aider. Autrement, dans
boost::iterator il y a un permutation_iterator qui pourrait aider à
implémenter ta troisième approche.

--
Loïc

On 11 juin, 00:29, Loïc Joly <loic.actarus.j...@numericable.fr> wrote:

jeremie fouche a écrit :> Bonjour

Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.

Pour un problème équivalent, j'avais choisi une map string / index et
un vector d'attributs:
// take ownership
+ bool addAttribute(const std::string& name, Attribute* value);
+ Attribute* getAttributeByName(const std::string& name) const;
+ Attribute* getAttributeById(uint32 id) const;
+ uint32 getAttributeId(const std::string& name) const;
+ uint32 getAttributeCount()const;
- std::map<std::string, uint32> m_index
- un std::vector<Attribute*> m_attributes


cella te permets:
- un couts mémoire / cpu plus faible que si tu utillisais une liste
(on passe souvent plus de temps à consulter la liste d'attribut plutôt
que d'ajouter ou d'enlever des attributs)
- un accès via des chaines relativement rapide (recherche dans map +
indirection tableau)
- une serialization / introspection relativement simple (boucle sur le
vector)
- des mini-optimisation possibles (un seul recheche dans la map par
appel) ({ static uint32 id = m_index.find("MaxX")->second;
m_attributes[id]->set(42); })

Je t'invite à allez voire boost:any qui permet une implementation
simple de ta classe Attribute

On Jun 10, 5:26 pm, jeremie fouche <jfou...@voila.fr> wrote:

Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.

La première question est : combien de paires
attributes-valeurs ? Jusqu'à quelque dizaines, j'utiliserais un
std::vector< AttributeValuePair >, sans plus de soucis.

C'est le cas. Je vais donc poursuivre dans cette direction.

std::vector< std::pair<std::string, Attribute> >
ou le first est le nom de l'attribut.
J'ai un peu l'impression de refaire une std::map avec clef/valeur. Mais
j'ai bien compris la différence.
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espace
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?

Mais comme j'ai dit au départ, std::find sur un std::vector est
largement suffisant pour plusieurs dizaines d'attributes.

Je pense que std::find n'est pas ce que je recherche, il me faut un
std::find_if, car c'est uniquement sur le nom de l'attribut que je veux
l'unicité.

En somme, il faut que je me fasse une fonction qui permette l'ajout de
l'attribut :

typedef std::vector< std::pair<std::string, Attribute> > TAttributes;

TAttributes m_attributes;

class PredFindAttribByName
{
private:
std::string m_sName;

public:
PredFindAttribByName(const std::string& sName)
: m_sName(sName) { }

bool operator()(const TAttributes::value_type& val)
{
return val.first == m_sName;
}
};

bool add(const Attribute& rcAttribute)
{
bool bAdded = false;
TAttributes::const_iterator iterFound;
iterFound = std::find_if( m_attributes.begin()
, m_attributes.end()
, PredFindAttribByName(rcAttribute.GetName())
);
if (iterFound == m_attributes.end())
{
TAttributes::value_type val = std::make_pair( rcAttribute.GetName()
, rcAttribute
);
m_attributes.push_back(val);
bAdded = true;
}
return bAdded;
}

Tu voyais quelquechose comme ca ?
Il y a mieux, peut etre ?
Merci beaucoup pour tes remarques
--
Jérémie

On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche <jfouche@voila.fr>:

Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espace
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?

Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un
tableau quelque part dans un programme, j'utilise vector<>, sauf si
j'ai de bonnes raisons de penser qu'il ne convient pas.

Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.

vector<> est très rapide pour l'accès aléatoire, mais très lent pour
l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très
lent" -- il faut un sacré paquet d'éléments pour que ça se voit.

list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais
permet une insertion rapide d'un élément n'importe où.

deque<> est un peu au milieu. Il ménage la chèvre et le chou, et est à
préférer si tu as besoin d'insérer (ou supprimer) des éléments au
début et à la fin. Bizarrement, alors qu'il semble fournir le meilleur
des deux mondes, il est assez peu utilisé.

On Jun 11, 7:56 pm, jeremie fouche <jfou...@voila.fr> wrote:

On Jun 10, 5:26 pm, jeremie fouche <jfou...@voila.fr> wrote:

Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.

La première question est : combien de paires
attributes-valeurs ? Jusqu'à quelque dizaines, j'utiliserais un
std::vector< AttributeValuePair >, sans plus de soucis.

C'est le cas. Je vais donc poursuivre dans cette direction.

std::vector< std::pair<std::string, Attribute> >
ou le first est le nom de l'attribut.
J'ai un peu l'impression de refaire une std::map avec clef/valeur. Mais
j'ai bien compris la différence.

Pour info, je ne crois pas avoir déjà utilisé std::vector, car je s uis
un addepte de std::map ou std::list.

Intéressant. Je ne me rappelle pas d'avoir déjà utilisé
std::list.

En général, on dit que std::vector, c'est la collection par
défaut. Mais je dis bien « on » : je l'ai entendu souvent, je
ne sais pas de qui, ni réelement pourquoi (sinon que
std::vector, c'est bien la collection la plus simple).

Faut il que je reserve de l'espace pour ce conteneur ?

Non.

Est il aussi souple que std::list ?

Souple dans quel sens ? Il a l'avantage d'avoir un itérateur
aléatoire. Il supporte à peu près toutes les actions de
std::list, mais les performances de différentes actions varient.

Par rapport à std::list, il a le désavantage que des insertions
et des suppressions peuvent invalider les itérateurs. Vue la
façon dont je me sers des collections et des itérateurs, ça a
peut d'importance, mais pour d'autres, ça pourrait être un
critère important.

Pourquoi std::vector plutot que std::list ?

Habite, peut-être. Comme j'ai dit, pour moi, c'est le défaut.

Mais comme j'ai dit au départ, std::find sur un std::vector est
largement suffisant pour plusieurs dizaines d'attributes.

Je pense que std::find n'est pas ce que je recherche, il me faut un
std::find_if, car c'est uniquement sur le nom de l'attribut que je veux
l'unicité.

Oui. J'ai une tendance à dire « find » pour englober les deux.
C'est certainement find_if qu'il te faut.

En somme, il faut que je me fasse une fonction qui permette l'ajout de
l'attribut :

typedef std::vector< std::pair<std::string, Attribute> > TAttributes;

TAttributes m_attributes;

class PredFindAttribByName
{
private:
std::string m_sName;

public:
PredFindAttribByName(const std::string& sName)
: m_sName(sName) { }

bool operator()(const TAttributes::value_type& val)
{
return val.first == m_sName;
}
};

bool add(const Attribute& rcAttribute)
{
bool bAdded = false;
TAttributes::const_iterator iterFound;
iterFound = std::find_if( m_attributes.begin()
, m_attributes.end()
, PredFindAttribByName(rcAttribute.GetName())
);
if (iterFound == m_attributes.end())
{
TAttributes::value_type val = std::make_pair( rcAttribute.GetName()
, rcAttribute
);
m_attributes.push_back(val);
bAdded = true;
}
return bAdded;
}

Tu voyais quelquechose comme ca ?

Tout à fait. Dans la pratique, il me faut prèsque toujours une
fonction « contains() », qui fait le début de ta fonction, et
que j'utilise ici, mais c'est la seule différence. Ça donne
quelque chose comme :

La plupart de temps, à la place de std::pair, j'utilise une
petite classe à moi. Avec les noms d'éléments un peu plus
parlant que « first » et « second », et des classes
fonctionnelles embriquées avec les Match, c-à-d MatchName,
MatchValue, etc. (ce qui permet des recherches sur de multiples
critères).

Il y a mieux, peut etre ?

Il y a toujours mieux:-). En général, dès qu'on finit un bout de
code, on se rend compte d'une façon bien meilleur de le faire.
Mais tant que tu ne dépasses pas quelque dizaines d'entrées,
c'est certainement la solution la plus simple et la plus facile
à comprendre.

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
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

On Jun 11, 9:20 pm, Fabien LE LEZ <grams...@gramster.com> wrote:

On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche <jfou...@voila.fr>:

Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espace
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?

Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un
tableau quelque part dans un programme, j'utilise vector<>, sauf si
j'ai de bonnes raisons de penser qu'il ne convient pas.

Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.

vector<> est très rapide pour l'accès aléatoire, mais très lent p our
l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très
lent" -- il faut un sacré paquet d'éléments pour que ça se voit.

Ou des éléments dont la copie est très chère.

list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais
permet une insertion rapide d'un élément n'importe où.

Ou que tu as besoins de garder des itérateurs, ou des pointeurs
ou des références à des éléments, tout en insérant ou en
enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des
autres collections, que ses itérateurs ne sont que
bi-directionnels, et non aléatoire. Elle a l'avantage, en
révanche, qu'ils restent valides tant que l'élément reste dans
la collection.

Quand tu as vraiment beaucoup d'éléments (des centaines de
milliers, voire plus), ou que tu fais des insertions et des
suppressions en pagaille, elle a aussi le désavantage de
fragmenter la mémoire et d'avoir une très mauvaise localisation.

deque<> est un peu au milieu. Il ménage la chèvre et le chou, et est à
préférer si tu as besoin d'insérer (ou supprimer) des éléments au
début et à la fin. Bizarrement, alors qu'il semble fournir le meilleur
des deux mondes, il est assez peu utilisé.

D'après ce que j'ai compris, il y a eu une erreur dans les
premières versions qui faisaient qu'elle était affreusement
lente. Dans la pratique, je m'en sers assez souvent, chaque fois
que j'ai besoin d'une queue, en fait. (Pour des piles et des
tableaux, je me sers de std::vector.)

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
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

On Jun 11, 2:41 pm, Vianney Lançon <Vianney.Lan...@gmail.com> wrote:

[...]

Je t'invite à allez voire boost:any qui permet une implementation
simple de ta classe Attribute

Je ne crois pas. D'après ce que j'ai compris, sa classe
Attribute, c'est ce que qu'on appelle habituellement une
« attribute-value pair », un identificateur (souvent, mais pas
nécessairement, une chaîne de caractères) et une valeur, qui
selon l'application aurait toujours le même type, ou un dans un
petit ensemble de types. Si on voulait se restreindre à Boost et
la bibliothèque standard, ça serait un std::pair< boost::any,
boost::any > dans le cas le plus général, mais en général, on
veut pas être aussi général, on veut des noms plus parlant que
« first » et « second », et surtout, on veut une
vérification statique des types, autant que se peut. Aussi,
selon les utilisations, on peut ne pas vouloir supporter la
modification de l'attribute identificateur en dehors d'une
affectation complète. Ce qui amène à quelque chose du genre :

class AttributeValuePair
{
public:
explicit AttributeValuePair(
std::string const& attr,
ValueType const& value )
: myAttr( attr )
, myValue( value )
{
}

std::string const& attribute() const
{
return myAttr ;
}

ValueType const& value() const
{
return myValue ;
}

void value( ValueType const& newValue )
{
myValue = newValue ;
}

class MatchAttr
{
public:
explicit MatchAttr(
std::string const& name )
: myName( name )
{
}

bool operator()(
AttributeValuePair const& avPair )
const
{
return myName == avPair.attribute() ;
}

private:
std::string myName ;
} ;

// ...

private
std::string myAttr ;
ValueType myValue ;
} ;

Selon le cas, ValueType peut être aussi simple qu'un int, ou
aussi complex qu'un Boost::variant. (Voir plus : dans mon
application actuelle, ValueType supporte aussi une certaine
nombre de conversions ; on peut utiliser un ValueType de double
où il en faut une de type chaîne, par exemple.)

(En passant, je crains qu'on reconnaît ici ma prédilection pour
des logiciels de reseau. L'AttributeValuePair, c'est pris
directement de ASN.1, et donc de SNMP, LDAP, etc.)

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
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

Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé
que cela soit contraignant pour des grandes listes dans la phase de test
et de validation.

Elle est sensée être O(1)...

--
Loïc

On Jun 11, 9:20 pm, Fabien LE LEZ <grams...@gramster.com> wrote:

On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche <jfou...@voila.fr>:

Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espace
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?

Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un
tableau quelque part dans un programme, j'utilise vector<>, sauf si
j'ai de bonnes raisons de penser qu'il ne convient pas.

Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.

vector<> est très rapide pour l'accès aléatoire, mais très lent pour
l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très
lent" -- il faut un sacré paquet d'éléments pour que ça se voit.

Ou des éléments dont la copie est très chère.

Mais seulement au moment ou la mémoire de travail de l'objet est
étendue. Dans le cas où cela pose problème et où c'est possible,
reserve() peut faire passer la pillule.

list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais
permet une insertion rapide d'un élément n'importe où.

Ou que tu as besoins de garder des itérateurs, ou des pointeurs
ou des références à des éléments, tout en insérant ou en
enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des
autres collections, que ses itérateurs ne sont que
bi-directionnels, et non aléatoire. Elle a l'avantage, en
révanche, qu'ils restent valides tant que l'élément reste dans
la collection.

Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé
que cela soit contraignant pour des grandes listes dans la phase de test
et de validation.

Quand tu as vraiment beaucoup d'éléments (des centaines de
milliers, voire plus), ou que tu fais des insertions et des
suppressions en pagaille, elle a aussi le désavantage de
fragmenter la mémoire et d'avoir une très mauvaise localisation.

deque<> est un peu au milieu. Il ménage la chèvre et le chou, et est à
préférer si tu as besoin d'insérer (ou supprimer) des éléments au
début et à la fin. Bizarrement, alors qu'il semble fournir le meilleur
des deux mondes, il est assez peu utilisé.

Je n'ai pour ainsi dire jamais eu besoin d'insérer et de supprimer des
deux cotés d'un container. vector, queue et list suffisent souvent faire
une lifo ou une fifo.

D'après ce que j'ai compris, il y a eu une erreur dans les
premières versions qui faisaient qu'elle était affreusement
lente. Dans la pratique, je m'en sers assez souvent, chaque fois
que j'ai besoin d'une queue, en fait. (Pour des piles et des
tableaux, je me sers de std::vector.)

Pourquoi pas queue tout simplement ?
Le seul reproche que je lui trouve c'est de ne pas fournir d'iterator
(ou au moins de const_iterator) ce qui serait pratique pour les traces.


Michael