Structure de données pour stocker des chaînes de caractères?

Je suis à la recherche d'une structure de données pour stocker des chaînes de caractères. J'ai besoin d'une fonction dans l'interface qui prend une chaîne de caractères comme seul paramètre et renvoie une référence/itérateur/pointeur/poignée qui peut être utilisé pour récupérer la chaîne de caractères pour le reste de la durée de vie de la structure des données. L'appartenance, l'entrée de la suppression etc. n'est pas nécessaire.

Je suis de plus en plus concernés par l'utilisation de la mémoire que la vitesse.

Veuillez être plus précis. Quelle langue?
Nous avons besoin de plus d'informations pour vous aider... la plupart des langues déjà fournir structures de données pour la gestion des chaînes de manière efficace (par exemple, Java StringBuilder).
Je crois qu'il parle de stocker un ensemble de chaînes de caractères, pas un seul
Ah, que de sens maintenant =)

OriginalL'auteur Joe Gauterin | 2009-01-28

  1. 15

    Un très efficace structure de données pour stocker des chaînes de caractères est le Trie. Cela permet d'économiser de la mémoire et de temps en stocker des chaînes de caractères communs avec les préfixes à l'aide de la même mémoire.

    Structure de données pour stocker des chaînes de caractères?

    Vous pouvez utiliser comme pointeur retourné le marqueur final de la chaîne dans la Trie, qui identifie de manière unique la chaîne, et pourrait être utilisée pour recréer la chaîne en parcourant la Trie vers le haut.

    En fonction de la langue utilisée et la distribution de l'entrée, cela peut être inefficace: il y aura beaucoup de pointeurs de caractères uniques. Suffixe de la tente sont en O(n) la taille, mais GRAND. En java, chaque nœud aura un mutex et cond: VRAIMENT GRAND. Assurez-vous de mesurer la taille réelle, avant de se décider.
    Absolument de bons conseils. Notez que nous n'avons pas à discuter Suffixe tente en particulier, plutôt la trie général de la chaîne de stockage/de données de recherche de la structure. Une variante de la trie, qui traite un peu avec l'utilisation de la mémoire est l'Patricia Trie - qui évite le caractère unique des nœuds autant que possible.

    OriginalL'auteur Avi

  2. 3

    Je pense que le mot clé ici est chaîne de stage, où vous stockez une seule copie de chaque chaîne. En Java, ceci est accompli par String.stagiaire():

    String ref1 = "hello world".intern();
String ref2 = "HELLO WORLD".toLowerCase().intern();
assert ref1 == ref2;
    +1 pour intéressantes. Rapide google check montre similaire functionaliy .net. Chaîne de caractères.Stagiaire() de la classe statique.

    OriginalL'auteur Zach Scrivena

  3. 0

    Je pense que le meilleur choix ici serait un ArrayList. La commune implémentations ont une surcharge d'allouer de l'espace supplémentaire dans le tableau pour les nouveaux éléments, mais si la mémoire est d'une telle exigence, vous pouvez attribuer manuellement pour chaque nouvel élément. Il sera plus lent, mais seulement l'utilisation de la mémoire nécessaire pour la chaîne.

    OriginalL'auteur Gonzalo Quero

  4. 0

    Il y a trois façons de stocker des chaînes de caractères:

    1. De longueur fixe (de type matrice de structure)
    2. De longueur Variable, mais au maximum la taille est fixe pendant le temps de marche (type pointeur de structure)
    3. Liste liée à la structure

    OriginalL'auteur sangita bora