{"id":2911,"date":"2021-01-11T10:29:00","date_gmt":"2021-01-11T01:29:00","guid":{"rendered":"http:\/\/43.203.250.216\/?p=2911"},"modified":"2021-01-10T22:31:14","modified_gmt":"2021-01-10T13:31:14","slug":"%ec%97%b0%ea%b4%80-%ec%bb%a8%ed%85%8c%ec%9d%b4%eb%84%88%ec%97%90-find_if%eb%a5%bc-%ec%93%b4%eb%8b%a4%ea%b5%ac%ec%9a%94","status":"publish","type":"post","link":"https:\/\/litcoder.com\/?p=2911","title":{"rendered":"\uc5f0\uad00 \ucee8\ud14c\uc774\ub108\uc5d0 find_if()\ub97c \uc4f4\ub2e4\uad6c\uc694?"},"content":{"rendered":"\n<p>\uc5f0\uad00 \ucee8\ud14c\uc774\ub108\ub294 \ub370\uc774\ud130\ub97c \ucd94\uac00 \ud560 \ub54c \ub0b4\ubd80\uc5d0 hash table\uc774\ub098 tree \uad6c\uc870\ub97c \uc720\uc9c0\ud574\uc11c \ub9ce\uc740 \uc6d0\uc18c\uac00 \uc0bd\uc785 \ub418\ub354\ub77c\ub3c4  \uc6d0\ud558\ub294 \uac12\uc744 \ube60\ub978 \uc18d\ub3c4\ub85c \uac80\uc0c9 \ud558\ub294\uac83\uc774 \uac00\ub2a5\ud558\ub3c4\ub85d \ud574\uc900\ub2e4.<\/p>\n\n\n\n<p>\uc5b4\ub5a4 key\uac00 \uc8fc\uc5b4 \uc84c\uc744 \ub54c \uc774\uac83\uc774 \uc815\ud655\ud788 \uc6d0\ud558\ub294 \uac12\uc774 \uc544\ub2c8 \ub354 \ub77c\ub3c4 \ud2b9\uc815\ud55c \ubc94\uc704\uc5d0 \ub4e4\uba74 \ud574\ub2f9 Block\uc744 \ubc18\ud658\ud558\ub294 \ucf54\ub529\uc744 \ud558\uace0 \uc788\uc5c8\ub294\ub370, \uc0dd\uac01\ubcf4\ub2e4 map\uc774\ub098 set \uac19\uc740 \uc5f0\uad00 \ucee8\ud14c\uc774\ub108\uc5d0 find_if()\ub85c \uc870\uac74\uc744 \uc8fc\ub294 \ucf54\ub4dc \ub808\ud37c\ub7f0\uc2a4\ub4e4\uc774 \ub9ce\uc558\ub2e4. \uc608\ub97c \ub4e4\uba74 \ub2e4\uc74c\uacfc \uac19\uc774 \uc8fc\uc5b4\uc9c4 set\uc5d0 \ub300\ud574 find_if()\ub85c \ubaa8\ub4e0 \uc6d0\uc18c\ub4e4\uc744 \ub3cc\uba74\uc11c \uc8fc\uc5b4\uc9c4 key\uac00 \ub4e4\uc5b4 \uac08 \uc218 \uc788\ub294 Block \ucc3e\ub294 \uac83\uacfc \uac19\uc740 \uacbd\uc6b0\uc774\ub2e4.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"eclipse\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">find_if(\n  s.begin(), s.end(),\n  [findKey](const Block* el) {\n    return findKey >= el->blkBase \\\n      &amp;&amp; findKey &lt; (el->blkBase + el->blkSize); });<\/pre>\n\n\n\n<p>\uc8fc\uc5b4\uc9c4 \uc6d0\uc18c\uc758 \uc218\uac00 \uc5bc\ub9c8 \uc5c6\ub2e4\uba74 \uc774\ub7f0 \uc885\ub958\uc758 \ucf54\ub4dc\uac00 \ubcc4 \ubb34\ub9ac\uac00 \uc5c6\uaca0\uc9c0\ub9cc, \uc6d0\uc18c\uc758 \uc218\uac00 \ub9ce\uc544\uc9c0\uba74 \ub450\ub4dc\ub7ec\uc9c0\ub294 \uc131\ub2a5 \ucc28\uc774\ub97c \ubcf4\uc778\ub2e4. \ub2e4\uc74c\uc740 \uc774\uc640 \uac19\uc774 find_if()\ub85c \ubaa8\ub4e0 \uc6d0\uc18c\ub4e4\uc744 \ubc29\ubb38\ud574 \uac00\uba70 range\uc5d0 \uc18d\ud558\ub294\uc9c0 \uac80\uc0ac\ud558\ub294 \ucf54\ub4dc\ub97c vector, map, set\uc5d0 \ub300\ud574\uc11c 10\ub9cc\uac1c\uc758 \uc6d0\uc18c\ub85c \ub3cc\ub9b0 \uac83\uc778\ub370, \uc624\ud788\ub824 vector\uc5d0 \ube44\ud574 map\uacfc set\uc774 \uac01\uac01 4\ubc30\uc5d0\uc11c 6\ubc30 \uc815\ub3c4\uc758 \ub290\ub9b0 \uac80\uc0c9 \uc131\ub2a5\uc744 \ubcf4\uc5ec \uc900\ub2e4.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"raw\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">[Vector]\n100000 items pushed to vector.\nInsertion: 13ms\nSearching: 28879ms\n\n[Map]\n100000 items pushed to map.\nInsertion: 63ms\nSearching: 120259ms\n\n[Set]\n100000 items pushed to set.\nInsertion: 60ms\nSearching: 193998ms\n<\/pre>\n\n\n\n<p>\uc5f0\uad00 \ucee8\ud14c\uc774\ub108 \ub4e4\uc740 \uc6d0\uc18c\ub97c \ucd94\uac00\ud560 \ub54c \ud6a8\uc728\uc801\uc778 \uac80\uc0c9\uc744 \uc704\ud55c \ubd80\uac00\uc801\uc778 \ub3d9\uc791\uc744 \uc218\ud589\ud574\uc57c \ud558\ubbc0\ub85c insertion\uc5d0 \uc2dc\uac04\uc774 \uc870\uae08 \ub354 \uac78\ub9ac\ub294 \uac74 \uadf8\ub807\ub2e4 \uccd0\ub3c4, \uc6d0\uc18c\uc758 \uc218\uc5d0 \ub530\ub77c \uc120\ud615\uc801\uc73c\ub85c \uac80\uc0c9 \uc2dc\uac04\uc774 \uc99d\uac00\ud558\ub294 vector\uc5d0 \ube44\ud574 4\ubc30\uc5d0\uc11c 6\ubc30 \uc815\ub3c4\uc758 \uac80\uc0c9 \uc2dc\uac04\uc774 \ub354 \ub4dc\ub294 \uacb0\uacfc\ub294 \uc5f0\uad00 \ucee8\ud14c\uc774\ub108\uc5d0 \ub300\ud574 find_if()\ub97c \ub4e4\uc774 \ub300\ub294 \uc790\uccb4\uac00 \ud604\uba85\ud55c \uc0dd\uac01\uc778\uac00 \ud558\ub294 \uc758\uad6c\uc2ec\uc774 \ub4e4\uac8c \ud55c\ub2e4. \uc989, find_if()\ub97c \uc0ac\uc6a9\ud558\uba74 \uc8fc\uc5b4\uc9c4 \ucee8\ud14c\uc774\ub108\uc758 \uad6c\uc870\uc5d0 \ub9de\uac8c \ud6a8\uc728\uc801\uc73c\ub85c iteration\uc744 \ud574 \uc8fc\uace0 <strong>\uadf8\ub7f0\uac70 \uc5c6\ub2e4<\/strong>. \uc801\uc5b4\ub3c4 g++(v7.5.0)\uc5d0\uc11c\ub294.<\/p>\n\n\n\n<p>\uadf8\ub807\ub2e4\uba74 \uc774 \uacbd\uc6b0 \ucc98\ub7fc, C++\uc5d0\uc11c \ud2b9\uc815\ud55c \uac12\uc774 \uc544\ub2c8\ub77c \uc8fc\uc5b4\uc9c4 \ud0a4\uac00 \ubc94\uc704\uc5d0 \ub4dc\ub294\uc9c0 \uac80\uc0ac\ud558\uace0 \uc2f6\uc740 \uacbd\uc6b0\ub294 \uc5b4\ub5bb\uac8c \ud574\uc57c \ud560\uae4c? Java\uc758 Navigatable* \ub9cc\ud07c\uc740 \uc138\ubd80\uc801\uc774\uc9c4 \uc54a\uc9c0\ub9cc C++\uc758 map\uacfc set \ubaa8\ub450 \uc8fc\uc5b4\uc9c4 key\uc5d0\uc11c \uac00\uc7a5 \uac00\uae4c\uc6b4 \uac12\uc744 \ubc18\ud658\ud558\ub294 <a href=\"https:\/\/www.cplusplus.com\/reference\/set\/set\/lower_bound\/\" data-type=\"URL\" data-id=\"https:\/\/www.cplusplus.com\/reference\/set\/set\/lower_bound\/\">lower_bound()<\/a> \/ <a href=\"https:\/\/www.cplusplus.com\/reference\/set\/set\/upper_bound\/\" data-type=\"URL\" data-id=\"https:\/\/www.cplusplus.com\/reference\/set\/set\/upper_bound\/\">upper_bound()<\/a>\ub97c \uc81c\uacf5\ud55c\ub2e4. \uc774\ub97c \uc774\uc6a9\ud574\uc11c \ub2e4\uc74c\uacfc \uac19\uc774 \ubc18\ud658\ub41c \uac1d\uccb4\uc5d0 \ub300\ud574\uc11c\ub9cc \ucd94\uac00\ub85c \uac80\uc0ac\ub97c \ud574\uc11c \ubc94\uc704\uc5d0 \ub4dc\ub294\uc9c0 \ud655\uc778\ud558\uba74 \ubcf4\ub2e4 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"eclipse\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">auto re = s.lower_bound(&amp;findBlk);\nauto el = *re;\nif (re != s.end()\n    &amp;&amp; (findKey >= el->blkBase &amp;&amp; findKey &lt; (el->blkBase + el->blkSize))) {\n}<\/pre>\n\n\n\n<p>\uc774\ub807\uac8c find_if()\ub85c \ubaa8\ub4e0 \uc6d0\uc18c\ub4e4\uc744 \ubc29\ubb38\ud558\ub294 \uac83\uc774 \uc544\ub2cc, lower_bound()\ub85c \ubc18\ud658 \ubc1b\uc740 \uacb0\uacfc\ub9cc \uac80\uc0ac\ud558\ub294 \ubc29\ubc95\uc73c\ub85c \uc704\uc640 \uac19\uc740 10\ub9cc\uac1c\uc758 \uc6d0\uc18c\uc5d0 \ub300\ud574 \ub3cc\ub824\ubcf4\uba74 \uae30\ub300\ud588\ub358 \ubc14\uc640 \uac19\uc774 vector\ubcf4\ub2e4 \ud6e8\uc52c \uc88b\uc740 \uc5f0\uad00 \ucee8\ud14c\uc774\ub108\uc758 \uac80\uc0c9 \uc18d\ub3c4\ub97c \ubcfc \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"raw\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">[Vector]\n100000 items pushed to vector.\nInsertion: 13ms\nSearching: 29765ms\n\n[Map]\n100000 items pushed to map.\nInsertion: 62ms\nSearching: 35ms\n\n[Set]\n100000 items pushed to set.\nInsertion: 62ms\nSearching: 36ms\n<\/pre>\n\n\n\n<p>\uc2dc\ud5d8\uc5d0 \uc0ac\uc6a9\ud55c \uc804\uccb4 \ucf54\ub4dc\ub294 GitHub Gist\uc5d0 \ubd99\uc5ec\ub454\ub2e4.<\/p>\n\n\n<script src=\"https:\/\/gist.github.com\/51d7b547b5e1f660802006bb5f7d61e9.js\"><\/script>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uc5f0\uad00 \ucee8\ud14c\uc774\ub108\ub294 \ub370\uc774\ud130\ub97c \ucd94\uac00 \ud560 \ub54c \ub0b4\ubd80\uc5d0 hash table\uc774\ub098 tree \uad6c\uc870\ub97c \uc720\uc9c0\ud574\uc11c \ub9ce\uc740 \uc6d0\uc18c\uac00 \uc0bd\uc785 \ub418\ub354\ub77c\ub3c4 \uc6d0\ud558\ub294 \uac12\uc744 \ube60\ub978 \uc18d\ub3c4\ub85c \uac80\uc0c9 \ud558\ub294\uac83\uc774 \uac00\ub2a5\ud558\ub3c4\ub85d \ud574\uc900\ub2e4. \uc5b4\ub5a4 key\uac00 \uc8fc\uc5b4 \uc84c\uc744 \ub54c \uc774\uac83\uc774 \uc815\ud655\ud788 \uc6d0\ud558\ub294 \uac12\uc774 \uc544\ub2c8 \ub354 \ub77c\ub3c4 \ud2b9\uc815\ud55c \ubc94\uc704\uc5d0 \ub4e4\uba74 \ud574\ub2f9 Block\uc744 \ubc18\ud658\ud558\ub294 \ucf54\ub529\uc744 \ud558\uace0 \uc788\uc5c8\ub294\ub370, \uc0dd\uac01\ubcf4\ub2e4 map\uc774\ub098 set \uac19\uc740 \uc5f0\uad00 \ucee8\ud14c\uc774\ub108\uc5d0 find_if()\ub85c \uc870\uac74\uc744 \uc8fc\ub294 \ucf54\ub4dc [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[247,263,262,261,260,264,265],"class_list":["post-2911","post","type-post","status-publish","format-standard","hentry","category-programming","tag-c","tag-set","tag-unordered_map","tag-vector","tag-260","tag-264","tag-265"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/2911","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2911"}],"version-history":[{"count":27,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/2911\/revisions"}],"predecessor-version":[{"id":2938,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/2911\/revisions\/2938"}],"wp:attachment":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2911"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2911"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}