c++ - Does unordered_map iterator/reference invalidation allow for cuckoo, hopscotch, and robin hood hashing? -


i'm trying figure out if it's possible build conformant, efficient implementation of modern c++'s std::unordered_map using techniques cuckoo hashing, hopscotch hashing, , robin hood hashing allow compact tables, high load factors, , maintain high performance. what's special these techniques involve potentially moving elements around make room others, rather chaining, or probing until open slot found (as in linear or quadratic probing) or.

from insert http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/

  1. iterator validity on cases, iterators in container remain valid after insertion. exception being when growth of container forces rehash. in case, iterators in container invalidated.

  2. a rehash forced if new container size after insertion operation increase above capacity threshold (calculated container's bucket_count multiplied max_load_factor).

  3. references elements in unordered_map container remain valid in cases, after rehash.

and erase http://www.cplusplus.com/reference/unordered_map/unordered_map/erase/

  1. only iterators , references elements removed invalidated.

  2. the rest unaffected.

  3. [c++14 only] relative order of iteration of elements not removed operation preserved.

the requirement other references remain valid in both operations seem require probing scheme involving evictions work on table structure allocated nodes separate array , pointed @ them instead. perhaps implementation keep separate array of elements entries in table index into, avoid dynamic allocation, still adds indirection. there more efficient way address requirement?

the requirement element references remain valid across insert after rehash seems imply either dynamic node allocation or above indirection array required chaining or non-moving open addressing design. right?

in general, requirement placed on unordered_map standard enforce indirection or other sort of inefficiency in hash table implementation?


-

Comments

Post a Comment

Popular posts from this blog

PySide and Qt Properties: Connecting signals from Python to QML -

i trying run simple pyside appliccation design made in qml. call function in qml python in separated thread. i have following qml view: import qt 4.7 rectangle { visible: true width: 100; height: 100 color: "lightgrey" text { id: datestr objectname: "datestr" x: 10 y: 10 text: "init text" font.pixelsize: 12 function updatedata(text) { datestr.text = qstr(text) console.log("you said: " + text) } } } here application: some imports.... #!/usr/bin/python import sys import time pyside import qtdeclarative, qtcore pyside.qtgui import qapplication pyside.qtdeclarative import qdeclarativeview the qthread worker.... #worker thread class worker(qtcore.qthread): updateprogress = qtcore.signal(int) def __init__(self, child): qtcore.qthread.__init__(self) self.child = child def run(self):
Read more

c# - DevExpress.Wpf.Grid.InfiniteGridSizeException was unhandled -

Image
when using devexpress, see error: devexpress.wpf.grid.infinitegridsizeexception unhandled message="by default, infinite grid height not allowed since grid rows rendered , hence grid work slowly. fix issue, should place grid container give finite height grid, or should manually specify grid's height or maxheight. note can avoid exception setting gridcontrol.allowinfinitegridsize static property true, in case grid run slowly." the problem dxgrid has infinite height. to fix, set height non-infinite. snoop absolutely invaluable this: if "height" xaml element infinite (i.e. 0 or nan ), can set using one of following: option 1: height="{binding path=actualheight, relativesource={relativesource mode=findancestor, ancestortype=uielement}}" option 2: verticalalignment="stretch" option 3: height="auto" hint: use verticalalignment="stretch" if child of grid <rowdefinition height=
Read more

scala - 'wrong top statement declaration' when using slick in IntelliJ -

Image
i'm porting project scala 2.9 2.10, therefore have use slick instead of scalaquery. i'm using slick 2.1.0 since supports ms access. according this tutorial , upgrade guide changed robs object class , added val robs : why error message wrong top statement declaration , how rid of it? edit: i'm new scala... according this question seems can't put val outside of methods or classes, right? code above directly in packge. right approach slick then? should move code in class or trait? according this changed val robs = tablequery[robs] to object robs extends tablequery(new robs(_)) {} . no warnings or errors anymore. :)
Read more