Quelle structure utiliser pour ce modèle? vecteur, liste chainée ou autres?

Bonsoir,

J'ai un programme très compliqué à implémenter et j'ai quelques soucis dans le choix des structures à utiliser. Le modèle que j'aimerai avoir consiste en une liste de, à peu près 200 000 nœuds (objets) contenant chacun d'autres structures, avec éventuellement des transitions entre ces différents nœuds.

La question que je me pose est : quelle structure utiliser pour modéliser les noeuds et les transitions, pour ne pas tomber dans un problème de débordement mémoire?
est-ce un vecteur? une liste chaînées? ou autres?

D'après ce que j'ai lu, un vecteur peut contenir plus que 200 000 noeuds, mais est ce qu'il peut stocker ces noeuds sachant que chacun peut contenir plusieurs objets (deux ou 3 vecteurs, des entiers,, et des structures de données). Une caractéristique intéressante qui me laisse favoriser les vecteurs est leur facilité de gestion des items (accès, suppression, ajout, parcourt...) et aussi sa façon d'allocation des noeuds (non contiguë, à la différence des tableaux).

Une dernière question, est ce que JAVA pourrait faire l'affaire pour ce modèle. JAVA offre des méthodes prédéfinies pour la gestion des chaînes de caractère et j'en ai besoin ici...


Merci d'avance.

Hello,
De manière générale, pour un conteneur ayant un grand nombre d'éléments et dont la taille varie peu, je te conseille le vecteur (std::vector) (qui stocke les éléments de manière contiguë puisqu'il s'agit en fait d'un tableau dynamique avec quelques fonctionnalités en plus).
Par contre, si tu vas passer ton temps à insérer des éléments, mieux vaut se tourner vers la std::list qui est faite pour ca.
Pour plus de détaille sur le choix du conteneur en fonction de la situation, la FAC est là.

ReBonsoir,

@vikki : Merci pour votre réponse et merci beaucoup pour le lien vers la FAQ, un article très intéressant!!
Je crois que je vais utiliser la structure std:vector, elle me permettrais d'accèder, parcourir et maj facilement les noeuds...

Pour les chaînes de caractères, j'ai un fichier texte, et je vais à chaque fois extraire une suite de chaînes de caractères (après un pré-traitement, des espaces...). Y'a pas une fonction prédéfinie pour manipuler tous ça très vite... (comme la fct StringTokenizer en JAVA)


Merci encore.

Pour la manipulation du contenu d'un fichier la FAQ est encore est toujours là ;).
Pour une manipulation assez poussée des chaines de caractères, c'est plus tendu en se limitant au standard. Mais boost.tokenizer s'en charge.

Merci beaucoup vikki...

je crois que maintenant, je devrait me mettre au travail, j'ai plus de temps à perdre, le modèle est très compliqué, et y'aura bcp de structure et de calcul, j'espère que C++ soit gentil :)
Si j'aurai des problèmes je te contacterais vikki ;)
Peut être que je mettrais le code sur internet, bien qu'il s'agit d'un travail de recherche :D