[ptr_container] Any plans to add ptr_unordered_set/map?
Hi, An obvious question: Now we have unordered containers approved for 1.35, is the ptr_container library going to get the corresponding adapters as well for this release? I had a look in the svn trunk but only found disappointment... Ta Amit
Amit skrev:
Hi,
An obvious question: Now we have unordered containers approved for 1.35, is the ptr_container library going to get the corresponding adapters as well for this release? I had a look in the svn trunk but only found disappointment...
It is planned. Note, however, that boost::unordered_map/set was only resently reviewed and accepted, far too late to make ptr_unordered_map/set for 1.35. They are planned, and so is ptr_circular_buffer<T>. -Thorsten
On 27/01/2008, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Amit skrev:
An obvious question: Now we have unordered containers approved for 1.35, is the ptr_container library going to get the corresponding adapters as well for this release? I had a look in the svn trunk but only found disappointment...
It is planned. Note, however, that boost::unordered_map/set was only resently reviewed and accepted, far too late to make ptr_unordered_map/set for 1.35.
I should add that they were accepted too late to be included in 1.35. So if you're expecting them in the next release, you'll just find more disappointment. Sorry about that. Soon after the release, I'll upload a new version to the vault that you can add to 1.35, but it will be unofficial. Daniel
Daniel James <daniel_james <at> fmail.co.uk> writes:
I should add that they were accepted too late to be included in 1.35. So if you're expecting them in the next release, you'll just find more disappointment. Sorry about that.
I am using unordered_maps now, just added the the code posted for review to 1.34.1 branch. My app is heavily multithreaded (web server), has 2 huge unordered maps keyed on pair of pointers. Did a load test this morning, appears to work fine. I use Hsieh's hash function (http://www.azillionmonkeys.com/qed/hash.html). I'll upgrade to the SVN version if there have been any changes since the review. As an aside, my usage exposes a case where unordered lose miserably to ordered: I have a lexicon of words (wstring). Typically it has 20K entries (words in a given language, so well distributed), and is looked up often. Storing this as an unordered_map (with either boost:hash or Hsieh's hash) results in significantly lower lookup performance than in an ordered container. I am guessing this is because most of my lookups succeed. If set has N strings and looked up string has size s, lookup is O(log(N)(1 + sk)) character compares in an ordered set, where k is the proportion of strings with size=s; typically k << 1. While lookup in the hash set is O(C(1 + sj)) character compares + O(s) bit twiddles to calculate the hash, where C is the average chain length & j is the proprtion of strings in the right chain with size=s; j < 1. Since we intuitively expect k < j, and O(bit shift) > O(compare), ordered sets would win for lookups that succeed most of the time (unordered should be better if lookups failed most of the time, since it would reject without any comparisons). Just thought I'd share in case anyone is contemplating using unordered_sets for dictionaries :)
On 28/01/2008, Amit <contact.lipik@gmail.com> wrote:
As an aside, my usage exposes a case where unordered lose miserably to ordered:
I have a lexicon of words (wstring). Typically it has 20K entries (words in a given language, so well distributed), and is looked up often. Storing this as an unordered_map (with either boost:hash or Hsieh's hash) results in significantly lower lookup performance than in an ordered container.
[...]
Just thought I'd share in case anyone is contemplating using unordered_sets for dictionaries :)
Have you compared it to some sort of trie-based lookup? A TST patricia trie (I'm not sure if it's technically a patricia tree, but it's close enough) ought to have similar lookup speed properties, but slightly reduce the number of character comparisons. For that matter, has anyone written a generic container_map based on that kind of data structure? I don't think lookup on non-string container keys is frequent, but it could be a nice project. Goes off to contemplate how to make iterators work in that, ~ Scott
participants (4)
-
Amit -
Daniel James -
Scott McMurray -
Thorsten Ottosen