How can I do string interning in C or C++?

Question

Is there something like intern() method in C or C++ like there is in Java ? If there isn't, how can I carry out string interning in C or C++?

Align

Just code exactly what you want. – Morehouse

Suhail, have you looked on these questions: #1116540 , #4060911 ? – Chancey

@David Schwartz A caching like functionality. I want string interning – Align

Sounds like you're looking for boost::flyweight< std::string >, all identical strings will use the same memory. – Impunity

Is there something like intern() method in "C/C++"? No. There is no C/C++. QED. – Masry

@Impunity i think that is what is known as string interning ! I don't know of any library – Align

@R. Martinho Fernandes i asked in C AND C++ – Align

@SuhailGupta Well, those are two different questions. If you really care about the answer to both, you should make two posts. – Masry

Have a look at flyweight: boost.org/doc/libs/1_49_0/libs/flyweight/doc/index.html – Womera

@Shog9 did 'you' merge the questions ? If yes,then which answer should i accept. The one that answers the C query or C++ ? And you changed the meaning of my question. I had and instead of or – Align

@Subhail: you're either going to implement this in C or C++. So decide which, and then accept the corresponding answer. And no, I didn't close or merge this, just edited after the fact to allow answers on either language to suffice. – Ploch

Answer 1

boost::flyweight< std::string > seems to be exactly what you're looking for.

Impunity

Is there any other way. I am not aware of this library – Align

@Erick Robertson but is there any other way ? – Align

@SuhailGupta If I knew of another way, I would add another answer. – Fablan

If you can bare the interface typedef std::hash_set< std::string > StringCache; will net you a less fancy version of what you're looking for. C++ standard library is very bare bones compared to most other languages on its own. – Impunity

Note that boost::flyweight requires the objects to be immutable; this isn't the case of std::string. Things like [] are likely to cause problems (or not, depending on how the objects are later used). – Zenda

More precisely boost::flyweight makes the object immutable, [] won't cause problems because boost::flyweight< T > only ever exposes const T&. – Impunity

Answer 2

Is there something like intern() method in C like we have in Java ?

Not in the standard C library.

If there isn't, how to carry out string interning in C?

With great difficulty, I fear. The first problem is that "string" is not a well-defined thing in C. Instead you have char *, which might point at a zero-terminated string, or might just denote a character position. Then you've got the problem that some strings are embedded in other things ... or are stored on the stack. Both of which make interning impossible and/or meaningless. Then, there is the problem that C string literals are not guaranteed to be interned ... in the way that Java guarantees it. Finally, there is the problem that interning is a storage leak waiting to happen ... if the language is not garbage collected.

Having said that, the way to (attempt to) implement interning in C would be to create a hash table to hold the interned strings. You'd need to make it a precondition that you cannot intern a string unless it is either a literal or a string allocated in its own heap node. To address the storage leak issue, you'd need a per-string reference count to detect when an interned string can be discarded.

Roughneck

Answer 3

What would string interning mean in a language which has value semantics? Interning is a mechanism to force object identity for references to strings with value identity. It's relevant in languages which use reference semantics and use object identity as the default comparison function. C++ uses value semantics by default, and types like std::string don't have identity, so interning makes no sense.

Some implementations (e.g. g++) may use a form of reference semantics for the string data, behind the scenes. Such an implementation could offer some sort of interning of that data, as an extension. (G++ doesn't, as far as I know, but does automatically "intern" empty strings.)

Most other implementations don't even use reference semantics internally. How would you intern an implementation using the small string optimization (like MS)? Where the data is literally in the class in some cases, and there is no dynamically allocated memory.

Zenda