Структура данных для хранения строк?

Question

Я ищу структуру данных для хранения строк. Мне нужна функция в интерфейсе, которая принимает строку в качестве единственного параметра и возвращает ссылку / итератор / указатель / дескриптор, который можно использовать для получения остальная часть времени жизни структуры данных. Установить членство, удаление записи и т. Д. Не требуется.

Меня больше беспокоит использование памяти, чем скорость.

Answer 1

Одна высокоэффективная структура данных для хранения строк - Trie . Это экономит память и время за счет сохранения строк с общими префиксами в одной и той же памяти.

Вы можете использовать в качестве указателя возвращенный последний маркер строки в Trie, который однозначно идентифицирует строку, и может использоваться для воссоздания строки путем перемещения Trie вверх.

Answer 2

Я думаю, что ключевым словом здесь является интернирование строк , где вы храните только одну копию каждой отдельной строки. В Java это выполняется с помощью String.intern():

String ref1 = "hello world".intern();
String ref2 = "HELLO WORLD".toLowerCase().intern();
assert ref1 == ref2;

Answer 3

Существует три способа хранения строк:

1. Фиксированная длина (структура типа массива)
2. Переменная длина, но максимальный размер фиксируется во время работы (структура типа указателя)
3. Структура связанного списка

Answer 4

Я думаю, что лучшей ставкой здесь будет ArrayList . У общих реализаций есть некоторые издержки от выделения дополнительного пространства в массиве для новых элементов, но если память является таким требованием, вы можете выделить вручную для каждого нового элемента. Это будет медленнее, но будет использовать только необходимую память для строки.