Data structure for storing strings?

Question

I'm looking for a data structure to store strings in. I require a function in the interface that takes a string as its only parameter and returns a reference/iterator/pointer/handle that can be used to retrieve the string for the rest of the lifetime of the data structure. Set membership, entry deletion etc. is not required.

I'm more concerned with memory usage than speed.

Answer 1

One highly efficient data structure for storing strings is the Trie. This saves both memory and time by storing strings with common prefixes using the same memory.

You could use as the pointer returned the final marker of the string in the Trie, which uniquely identifies the string, and could be used to recreate the string by traversing the Trie upwards.