From 21d68ac5605f12ffea3f05ad677c717577f767ee Mon Sep 17 00:00:00 2001 From: Dmitry Ilvokhin Date: Sun, 2 Jul 2023 13:08:36 +0100 Subject: Add a post about libstdc++ `std::unordered_map` Detailed description of libstdc++ `std::unordered_map` implementation with URLs to source code and some explanations. --- .../libstdc++-hashtable-linked-list.excalidraw | 854 +++++++++++++++++++++ 1 file changed, 854 insertions(+) create mode 100644 posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw (limited to 'posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw') diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw new file mode 100644 index 0000000..ef8e75d --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw @@ -0,0 +1,854 @@ +{ + "type": "excalidraw", + "version": 2, + "source": "https://excalidraw.com", + "elements": [ + { + "type": "text", + "version": 1626, + "versionNonce": 1706265386, + "isDeleted": false, + "id": "4GJnTRmGDjxnh7FpQtrfd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 122.24743607838934, + "y": 176.4669361343948, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 171.1999969482422, + "height": 25, + "seed": 337238766, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683476589551, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "_M_before_begin", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "_M_before_begin", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1417, + "versionNonce": 1215560554, + "isDeleted": false, + "id": "ONtMFi-HJ3osgmAjkuWYs", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 457.1824678776138, + "y": 352, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 1474, + "versionNonce": 804585002, + "isDeleted": false, + "id": "1_dSNhOetsCgtYQ_s51Hx", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 745.4324678776138, + "y": 353.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1539, + "versionNonce": 1076509354, + "isDeleted": false, + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 493.68246787761376, + "y": 381.5474028211833, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 242.18516432344842, + "height": 86.70204311252468, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475915878, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "ytCfont2iIzHFS7wJr_ci", + "focus": 0.7382390820646367, + "gap": 5.071058646631116 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 123.00000000000006, + 86.70204311252468 + ], + [ + 242.18516432344842, + 2.8683393657897227 + ] + ] + }, + { + "type": "rectangle", + "version": 1625, + "versionNonce": 1678337846, + "isDeleted": false, + "id": "w9t6oond8UfIrkxQyMmM9", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1028.9324678776138, + "y": 352.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 88.00000000000001, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475821296, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1534, + "versionNonce": 1481153526, + "isDeleted": false, + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 779.544342931109, + "y": 381.9584128865794, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 238.8360551730816, + "height": 90, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475923593, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "yC_IWudaRTFJLHBBgwK5a", + "focus": 0.7042011222257625, + "gap": 5.551683800279079 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 97, + 90 + ], + [ + 238.8360551730816, + 3.019680509788941 + ] + ] + }, + { + "type": "rectangle", + "version": 1747, + "versionNonce": 1618607926, + "isDeleted": false, + "id": "-0i159PySDfAXjLw46YGi", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 156.06309756145015, + "y": 349.9287298531372, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86.00000000000011, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683475798995, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2411, + "versionNonce": 2073114410, + "isDeleted": false, + "id": "fDGakrHl2y_N1MGaVmSvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 149.55583348503265, + "y": 349.0113367602938, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686747, + "height": 59.9098051159695, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "KzlOPbqaLCtoJknIGsvAx", + "type": "arrow" + } + ], + "updated": 1683475798995, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2166, + "versionNonce": 1890994346, + "isDeleted": false, + "id": "xUttQCOY2JjRwO4r_Zfvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 149.9763864410761, + "y": 216.9223249044295, + "strokeColor": "#000000", + "backgroundColor": "#fa5252", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "MdHItGBZlhFM9xb42IRYD" + ], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683476607406, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 3450, + "versionNonce": 891088694, + "isDeleted": false, + "id": "KzlOPbqaLCtoJknIGsvAx", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 183.45423218312015, + "y": 248.8931101602777, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 50.77176430550634, + "height": 128.70967935539264, + "seed": 908754930, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475906708, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "fDGakrHl2y_N1MGaVmSvh", + "focus": -1.0228716005205234, + "gap": 6.979300727704427 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + -50.77176430550634, + 50.356889839722356 + ], + [ + -40.870485401541345, + 128.70967935539264 + ] + ] + }, + { + "type": "arrow", + "version": 1487, + "versionNonce": 798940935, + "isDeleted": false, + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 191.15146049489215, + "y": 380.25000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 258.3568841683801, + "height": 97.77140805893004, + "seed": 623910702, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683476888670, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "IaZmTKFovKV0N4MauTSwd", + "focus": 0.7648622002620978, + "gap": 4.473432544181321 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 118.5862401199837, + 96 + ], + [ + 258.3568841683801, + -1.7714080589300352 + ] + ] + }, + { + "type": "text", + "version": 428, + "versionNonce": 427228074, + "isDeleted": false, + "id": "0KVHqF3l1lAQG2TIieqkX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1039.6824678776138, + "y": 365.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 902878830, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 2442, + "versionNonce": 440888310, + "isDeleted": false, + "id": "ytCfont2iIzHFS7wJr_ci", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 740.9763337932766, + "y": 351.47723960906353, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "type": "arrow" + }, + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2346, + "versionNonce": 546491593, + "isDeleted": false, + "id": "IaZmTKFovKV0N4MauTSwd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 453.9763337932766, + "y": 349.2211091186287, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + }, + { + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "type": "arrow" + } + ], + "updated": 1683476884986, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2469, + "versionNonce": 1229762102, + "isDeleted": false, + "id": "yC_IWudaRTFJLHBBgwK5a", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 1023.9763337932764, + "y": 351.4772396090636, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475827842, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 454, + "versionNonce": 1548922102, + "isDeleted": false, + "id": "56jgqKlVGVs597B3fb6m0", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 248.68246787761382, + "y": 353.25000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 952556575, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "QDts3yqcBiUgXuxA-E-oX" + }, + { + "id": "KzlOPbqaLCtoJknIGsvAx", + "type": "arrow" + } + ], + "updated": 1683475798996, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 389, + "versionNonce": 1228096874, + "isDeleted": false, + "id": "QDts3yqcBiUgXuxA-E-oX", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 278.61580222819975, + "y": 365.75000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 72.13333129882812, + "height": 25, + "seed": 1458566161, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475798996, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<19, 19>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "56jgqKlVGVs597B3fb6m0", + "originalText": "<19, 19>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 527, + "versionNonce": 1974966570, + "isDeleted": false, + "id": "buSUoavgf_Af8aPtc-gV1", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 549.6824678776138, + "y": 355.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 910572241, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "5gBibH2KPwn5So0ObiuvP" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 473, + "versionNonce": 369714806, + "isDeleted": false, + "id": "5gBibH2KPwn5So0ObiuvP", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 570.7824663517349, + "y": 367.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 89.80000305175781, + "height": 25, + "seed": 674805937, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<36, 36>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "buSUoavgf_Af8aPtc-gV1", + "originalText": "<36, 36>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 575, + "versionNonce": 914285546, + "isDeleted": false, + "id": "hS7RxZYjoxvAh-xcMcXWw", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 839.6824678776138, + "y": 355.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 71562353, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "hTRSWa0vCqDIfHrhRjJ5A" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 529, + "versionNonce": 541140918, + "isDeleted": false, + "id": "hTRSWa0vCqDIfHrhRjJ5A", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 860.6158022281998, + "y": 368, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 90.13333129882812, + "height": 25, + "seed": 227425873, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<25, 25>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "hS7RxZYjoxvAh-xcMcXWw", + "originalText": "<25, 25>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 552, + "versionNonce": 1569642154, + "isDeleted": false, + "id": "rBoiVjSuf474Tru-eeXE3", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1122.6824678776138, + "y": 354.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 1471038015, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "MDQWBmmGzdijwd6PvQ1HW" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 514, + "versionNonce": 678346998, + "isDeleted": false, + "id": "MDQWBmmGzdijwd6PvQ1HW", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1151.9824671146744, + "y": 367, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 73.4000015258789, + "height": 25, + "seed": 977904223, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<14, 14>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "rBoiVjSuf474Tru-eeXE3", + "originalText": "<14, 14>", + "lineHeight": 1.25, + "baseline": 18 + } + ], + "appState": { + "gridSize": null, + "viewBackgroundColor": "#ffffff" + }, + "files": {} +} \ No newline at end of file -- cgit v1.2.3-70-g09d2