{"id":218,"date":"2019-01-05T11:22:57","date_gmt":"2019-01-05T03:22:57","guid":{"rendered":"https:\/\/www.caiqinyi.cn\/?p=218"},"modified":"2021-04-24T16:46:30","modified_gmt":"2021-04-24T08:46:30","slug":"some_useful_functions_in_stl","status":"publish","type":"post","link":"https:\/\/www.caiqinyi.cn\/index.php\/2019\/01\/05\/some_useful_functions_in_stl\/","title":{"rendered":"STL\u4e2d\u4e00\u4e9b\u5b9e\u7528\u7684\u5c0f\u6280\u5de7(\u6301\u7eed\u66f4\u65b0)"},"content":{"rendered":"

\u6709\u4e00\u4e9b\u7a0b\u5e8f, \u867d\u7136\u5199\u8d77\u6765\u4e0d\u96be, \u4f46\u662f\u53ef\u80fd\u6bd4\u8f83\u9ebb\u70e6\u6216\u5bb9\u6613\u51fa\u9519, \u8fd9\u65f6\u5c31\u53ef\u4ee5\u7528C++\u51fd\u6570\u5e93\u91cc\u81ea\u5e26\u7684\u4e00\u4e9b\u5b9e\u7528\u7684\u51fd\u6570. \u8fd9\u91cc\u53ea\u8bb0\u5f55\u4e00\u4e9b\u4e0d\u592a\u5e38\u89c1\u53ef\u80fd\u4f1a\u7528\u4e0a\u7684\u51fd\u6570. \u4ee5\u540e\u53ef\u80fd\u4f1a\u7ee7\u7eed\u66f4\u65b0~<\/p>\n


\n1. __gcd(x, y).
\n\u6c42\u4e24\u4e2a\u6570\u7684\u6700\u5927\u516c\u7ea6\u6570, \u5728algorithm\u5e93\u4e2d.<\/p>\n

2. unique(a + 1, a + n + 1) .
\n\u53bb\u91cd\u51fd\u6570. \u8ddfsort\u7684\u7528\u6cd5\u4e00\u6837. \u4e0d\u8fc7\u8fd4\u56de\u7684\u503c\u662f\u6700\u540e\u4e00\u4e2a\u6570\u7684\u5730\u5740, \u6240\u4ee5\u8981\u5f97\u5230\u65b0\u7684\u6570\u7ec4\u957f\u5ea6\u5e94\u8be5\u8fd9\u4e48\u5199: new_n = unique(a + 1, a + n + 1) – a – 1.<\/p>\n

3. lower_bound(a + 1, a + n + 1, x); upper_bound(a + 1, a + n + 1, x).
\nlower_bound\u662f\u67e5\u627e\u6570\u7ec4\u4e2d\u7b2c\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8ex\u7684\u6570, \u8fd4\u56de\u8be5\u5730\u5740, \u540c\u7406\u4e5f\u662fpos = lower_bound(a + 1, a + n + 1, x) – a. upper\\_bound\u662f\u67e5\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8ex\u7684\u6570, \u7528\u6cd5\u548clower_bound\u4e00\u6837. \u590d\u6742\u5ea6\u662f\u4e8c\u5206\u7684\u590d\u6742\u5ea6, O(logn), (\u5176\u5b9e\u5c31\u662f\u4ee3\u66ff\u4e86\u624b\u5199\u4e8c\u5206)<\/p>\n

4. fill(a + 1, a + n + 1, x).
\n\u5c06\u6570\u7ec4a\u4e2d\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u90fd\u8d4b\u6210x, \u8ddfmemset\u7684\u533a\u522b\u662f, memset\u662f\u4e00\u4e2a\u5b57\u8282\u4e00\u4e2a\u5b57\u8282\u8d4b\u503c, fill\u662f\u4e00\u4e2a\u5143\u7d20\u4e00\u4e2a\u5143\u7d20\u8d4b\u503c!(\u7701\u6389\u4e00\u5c42for\u2026\u2026)<\/p>\n

5. next_permutation(a, a + n).
\n\u8be5\u51fd\u6570\u5305\u542b\u5728\u5934\u6587\u4ef6algorithm\u91cc\u9762, \u5b83\u6309\u7167\u5b57\u5178\u5e8f\u4ea7\u751f\u6392\u5217, \u5e76\u4e14\u662f\u4ece\u6570\u7ec4\u4e2d\u5f53\u524d\u7684\u5b57\u5178\u5e8f\u5f00\u59cb\u4f9d\u6b21\u589e\u5927\u76f4\u81f3\u5230\u6700\u5927\u5b57\u5178\u5e8f. \u8bb0\u5f97\u4f7f\u7528\u524d\u9700\u8981\u5bf9\u5bb9\u5668\u8fdb\u884c\u6392\u5e8f, \u5426\u5219\u5f97\u5230\u7684\u6392\u5217\u96c6\u5408\u5143\u7d20\u4e00\u822c\u4f1a\u504f\u5c11.<\/p>\n

6. \u5982\u4f55\u5224\u65ad\u4e00\u4e2a\u6570\u662f2\u7684\u5e42?
\n1\u4e2a\u6570\u4e58\u4ee52\u5c31\u662f\u5c06\u8be5\u6570\u5de6\u79fb1\u4f4d, \u800c2\u76840\u6b21\u5e42\u4e3a1, \u6240\u4ee52\u7684n\u6b21\u5e42\u5c31\u662f\u5c061\u5de6\u79fbn\u4f4d, \u8fd9\u6837\u6211\u4eec\u77e5\u9053\u5982\u679c\u4e00\u4e2a\u6570n\u662f2\u7684\u5e42, \u5219\u5176\u53ea\u6709\u9996\u4f4d\u4e3a1, \u5176\u540e\u82e5\u5e72\u4e2a0, \u5fc5\u7136\u6709n&(n – 1)=0. (\u5728\u6c421\u4e2a\u6570\u7684\u4e8c\u8fdb\u5236\u8868\u793a\u4e2d1\u7684\u4e2a\u6570\u7684\u65f6\u5019\u8bf4\u8fc7, n&(n-1)\u53bb\u6389n\u7684\u6700\u540e\u4e00\u4e2a1). \u56e0\u6b64, \u5224\u65ad\u4e00\u4e2a\u6570n\u662f\u5426\u4e3a2\u7684\u5e42, \u53ea\u9700\u8981\u5224\u65adn&(n-1)\u662f\u5426\u4e3a0\u5373\u53ef. (\u8c28\u8bb0, \u6b64\u5904\u7684\u5224\u65ad\u5e94\u5199\u4e3aif((n&n-1)==0), \u56e0\u4e3a==\u7684\u4f18\u5148\u7ea7\u662f\u8981\u6bd4&\u7684\u4f18\u5148\u7ea7\u8981\u9ad8\u7684)<\/p>\n

7. \u5982\u4f55\u5224\u65ad\u662f2\u7684\u591a\u5c11\u6b21\u65b9\u5462? (\u5373\u63a2\u8ba8\u5e95\u6570\u4e3a2\u7684\u5bf9\u6570\u51fd\u6570\u7684\u5b9e\u73b0)<\/p>\n

\r\nint log2(int value)   \/\/\u9012\u5f52\u5224\u65ad\u4e00\u4e2a\u6570\u662f2\u7684\u591a\u5c11\u6b21\u65b9\r\n{\r\n if (value == 1)\r\n  return 0;\r\n else\r\n  return 1+log2(value>>1);\r\n}\r\n<\/pre>\n
8.\u6c42\u4e24\u4e2a\u96c6\u5408\u7684\u4ea4\u96c6
\n\u4f7f\u7528set_intersection:<\/p>\n
\r\nvector<int> y;\r\nset_intersection(begin(s1), end(s1),\r\n        begin(s2), end(s2), back_inserter(y));\r\n<\/pre>\n
\u8fd9\u91cc\u4f7f\u7528\u4e86back_inserter\u4e0d\u5f97\u4e0d\u8bf4\u662f\u975e\u5e38\u5999\u4e86. \u53e6\u5916, s1, s2\u4e00\u822c\u90fd\u662f\u4e00\u4e2aset\u800c\u975evector, \u56e0\u4e3a\u8be5\u51fd\u6570\u8981\u6c42s1, s2\u662f\u6709\u5e8f\u7684(\u8ddfunique\u4e00\u6837\u7684\u8981\u6c42).<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6709\u4e00\u4e9b\u7a0b\u5e8f, \u867d\u7136\u5199\u8d77\u6765\u4e0d\u96be, \u4f46\u662f\u53ef\u80fd\u6bd4\u8f83\u9ebb\u70e6\u6216\u5bb9\u6613\u51fa\u9519, \u8fd9\u65f6\u5c31\u53ef\u4ee5\u7528C++\u51fd\u6570\u5e93\u91cc\u81ea\u5e26\u7684\u4e00\u4e9b\u5b9e\u7528\u7684\u51fd\u6570. … \u7ee7\u7eed\u9605\u8bfbSTL\u4e2d\u4e00\u4e9b\u5b9e\u7528\u7684\u5c0f\u6280\u5de7(\u6301\u7eed\u66f4\u65b0)<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"_links":{"self":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/218"}],"collection":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/comments?post=218"}],"version-history":[{"count":28,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/218\/revisions"}],"predecessor-version":[{"id":222,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/218\/revisions\/222"}],"wp:attachment":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/media?parent=218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/categories?post=218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/tags?post=218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}