Am I missing something or is Boost: String dictionary?
One of the libraries I work with (libXML2) has a very useful concept called a string dictionary, and I am surprised this doesn't appear to be in either STL or Boost. Am I missing something, or is Boost missing something? The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry). The dictionary entries contain a copy of the string. Entries may be compared for equality/inequality in O(1) time. The lifespan of the strings in the entry is managed by the entry. This really simplifies writing parsers and the like, and is such a useful concept that I'm really surprised not to see it in STL or Boost.
Hi,
The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry). [...]
Maybe I misunderstood the concept. I think you are looking for std::setstd::string. Christof -- okunah gmbh Software nach Maß Zugspitzstraße 211 86165 Augsburg Geschäftsführer Christof Donat cd@okunah.de www.okunah.de Registergericht Augsburg Augsburg HRB 21896 UStID: DE 248 815 055
On Monday 06 May 2013 17:35:56 Christof Donat wrote:
Hi,
The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry).
[...]
Maybe I misunderstood the concept. I think you are looking for std::setstd::string.
...or std::map/std::unordered_map, perhaps.
Maybe I misunderstood the concept. I think you are looking for std::setstd::string.
Thanks all, that answered my question - it was me who was missing something. Thanks.
On May 6, 2013, at 8:26 AM, david.hagood@gmail.com wrote:
One of the libraries I work with (libXML2) has a very useful concept called a string dictionary, and I am surprised this doesn't appear to be in either STL or Boost. Am I missing something, or is Boost missing something?
The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry).
The dictionary entries contain a copy of the string. Entries may be compared for equality/inequality in O(1) time. The lifespan of the strings in the entry is managed by the entry.
Except for the O(1) part, this sounds to me like a:
std::map
On Mon May 6 18:26:46 2013, david.hagood@gmail.com wrote: [...]
The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry).
The dictionary entries contain a copy of the string. Entries may be compared for equality/inequality in O(1) time. The lifespan of the strings in the entry is managed by the entry.
What you described seems to be [string interning](http://en.wikipedia.org/wiki/String_interning), and it can be done simply as unordered_set<string> interned; const string *intern(const string &s) { return &*interned.insert(s).first; } assert(intern("abc") == intern("abc")); assert(intern("abc") != intern("xyz")); Cheers, Yakov
On Mon, May 6, 2013 at 11:26 AM,
One of the libraries I work with (libXML2) has a very useful concept called a string dictionary, and I am surprised this doesn't appear to be in either STL or Boost. Am I missing something, or is Boost missing something?
The basic idea is: Given you have a string and an instance of a dictionary, you can: 1) check if the string is already in the dictionary. 2) Add the string to the dictionary and return the dictionary entry (if the string is already present, return existing entry).
The dictionary entries contain a copy of the string. Entries may be compared for equality/inequality in O(1) time. The lifespan of the strings in the entry is managed by the entry.
This really simplifies writing parsers and the like, and is such a useful concept that I'm really surprised not to see it in STL or Boost.
Look at Boost.Flyweight. There is even an example for strings. -- François Duranleau
participants (6)
-
Andrey Semashev -
Christof Donat -
david.hagood＠gmail.com -
Francois Duranleau -
Marshall Clow -
Yakov Galka