{"id":987,"date":"2026-01-14T17:57:52","date_gmt":"2026-01-14T09:57:52","guid":{"rendered":"https:\/\/www.coni.top\/blog\/?p=987"},"modified":"2026-03-03T23:29:03","modified_gmt":"2026-03-03T15:29:03","slug":"c-slt%e5%b8%b8%e7%94%a8%e5%ae%b9%e5%99%a8%e6%93%8d%e4%bd%9c","status":"publish","type":"post","link":"https:\/\/www.coni.top\/blog\/?p=987","title":{"rendered":"C++ SLT\u5e38\u7528\u5bb9\u5668"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">\u5bb9\u5668\u5927\u7c7b<\/h3>\n\n\n\n<ul>\n<li><strong>\u987a\u5e8f\u5bb9\u5668<\/strong>\uff1a<code>vector \/ deque \/ list \/ array<\/code>\n<ul>\n<li>\u6309\u201c\u4f4d\u7f6e\/\u987a\u5e8f\u201d\u5b58\u6570\u636e<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u5173\u8054\u5bb9\u5668\uff08\u6709\u5e8f\uff09<\/strong>\uff1a<code>map \/ set \/ multimap \/ multiset<\/code>\n<ul>\n<li>\u6309\u201ckey\/\u503c\u7684\u6392\u5e8f\u89c4\u5219\u201d\u5b58\uff0c\u5e95\u5c42\u6811\u7ed3\u6784\uff0c<code>O(logN)<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u65e0\u5e8f\u5bb9\u5668\uff08\u54c8\u5e0c\uff09<\/strong>\uff1a<code>unordered_map \/ unordered_set<\/code>\n<ul>\n<li>\u5e73\u5747 <code>O(1)<\/code>\uff0c\u4e0d\u6392\u5e8f<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u5bb9\u5668\u9002\u914d\u5668<\/strong>\uff1a<code>stack \/ queue \/ priority_queue<\/code>\n<ul>\n<li>\u201c\u63a5\u53e3\u53d7\u9650\u201d\u7684\u5c01\u88c5\uff08\u4e0d\u652f\u6301\u904d\u5386\uff09<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\u5171\u540c\u63a5\u53e3\uff08\u5927\u591a\u6570\u90fd\u6709\uff09<\/h3>\n\n\n\n<ul>\n<li><code>size() \/ empty() \/ clear()<\/code><\/li>\n\n\n\n<li><code>begin() \/ end()<\/code> \u7528\u4e8e\u904d\u5386<\/li>\n\n\n\n<li><code>insert \/ erase<\/code>\uff08\u4e0d\u540c\u5bb9\u5668\u7ec6\u8282\u4e0d\u540c\uff09<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">1) <code><strong>std::vector&lt;T&gt;<\/strong><\/code>\uff08\u52a8\u6001\u6570\u7ec4\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;vector&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li><strong>\u8fde\u7eed\u5185\u5b58<\/strong>\uff08cache \u53cb\u597d\uff0c\u904d\u5386\/\u62f7\u8d1d\u5feb\uff09<\/li>\n\n\n\n<li>\u652f\u6301 <strong>\u968f\u673a\u8bbf\u95ee<\/strong>\uff1a<code>v[i]<\/code>\u3001<code>v.at(i)<\/code><\/li>\n\n\n\n<li><strong>\u5c3e\u90e8\u63d2\u5165\u5feb<\/strong>\uff1a<code>push_back<\/code> \u5747\u644a O(1)<\/li>\n\n\n\n<li><strong>\u4e2d\u95f4\u63d2\u5165\/\u5220\u9664\u6162<\/strong>\uff1aO(N)\uff08\u9700\u8981\u79fb\u52a8\u5143\u7d20\uff09<\/li>\n\n\n\n<li>\u81ea\u52a8\u6269\u5bb9\uff1b\u6269\u5bb9\u65f6\u8fed\u4ee3\u5668\/\u5f15\u7528\/<code>data()<\/code> \u53ef\u80fd\u5931\u6548<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\"> \u521d\u59cb\u5316<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>std::vector&lt;int&gt; v;                 \/\/ \u7a7a<br>std::vector&lt;int&gt; v2(5);             \/\/ 5\u4e2a0<br>std::vector&lt;double&gt; v3(6, 0.0);     \/\/ 6\u4e2a0.0<br>std::vector&lt;int&gt; v4 = {1,2,3};      \/\/ \u5217\u8868\u521d\u59cb\u5316<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\uff08\u8bfb\/\u5199\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>v&#91;i];            \/\/ \u4e0d\u505a\u8d8a\u754c\u68c0\u67e5\uff08\u8d8a\u754c=\u672a\u5b9a\u4e49\u884c\u4e3a\uff09\nv.at(i);         \/\/ \u5e26\u8fb9\u754c\u68c0\u67e5\uff0c\u8d8a\u754c\u629b std::out_of_range\nv.front();       \/\/ \u7b2c\u4e00\u4e2a\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09\nv.back();        \/\/ \u6700\u540e\u4e00\u4e2a\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09\nv.data();        \/\/ \u6307\u5411\u5e95\u5c42\u8fde\u7eed\u5185\u5b58\u7684\u6307\u9488\uff08\u4f20 C \u63a5\u53e3\u5e38\u7528\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u63d2\u5165 \/ \u5220\u9664<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>v.push_back(x);                              \/\/ \u672b\u5c3e\u8ffd\u52a0\nv.pop_back();                                \/\/ \u5220\u9664\u672b\u5c3e\n\nv.insert(v.begin() + pos, x);                \/\/ \u4e2d\u95f4\u63d2\u5165\uff08O(N)\uff09\nv.erase(v.begin() + pos);                    \/\/ \u5220\u9664\u5355\u4e2a\u4f4d\u7f6e\uff08O(N)\uff09\nv.erase(v.begin() + l, v.begin() + r);       \/\/ \u5220\u9664\u533a\u95f4 &#91;l, r)\nv.clear();                                   \/\/ \u6e05\u7a7a\u6240\u6709\u5143\u7d20\uff08\u5bb9\u91cf\u4e0d\u53d8\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u8d4b\u503c \/ \u91cd\u7f6e<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>v.assign(6, 0.0);                            \/\/ \u76f4\u63a5\u91cd\u7f6e\u4e3a 6 \u4e2a 0.0\nv.resize(10);                                \/\/ \u6539\u957f\u5ea6\uff08\u6269\u5c55\u8865\u9ed8\u8ba4\u503c T()\uff09\nv.resize(10, 3.14);                          \/\/ \u6269\u5c55\u7528 3.14 \u586b\u5145<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5bb9\u91cf\u7ba1\u7406<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>v.size();                                    \/\/ \u5f53\u524d\u5143\u7d20\u4e2a\u6570\nv.capacity();                                \/\/ \u5f53\u524d\u5bb9\u91cf\uff08\u4e0d\u5c0f\u4e8e size\uff09\nv.reserve(100);                              \/\/ \u9884\u7559\u5bb9\u91cf\uff08\u907f\u514d\u591a\u6b21\u6269\u5bb9\uff09\nv.shrink_to_fit();                           \/\/ \u8bf7\u6c42\u6536\u7f29\u5bb9\u91cf\uff08\u975e\u5f3a\u5236\uff09\nv.empty();                                   \/\/ \u662f\u5426\u4e3a\u7a7a<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08C++11\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (const auto&amp; x : v) { \/* \u53ea\u8bfb\u904d\u5386 *\/ }\nfor (auto&amp; x : v) { \/* \u53ef\u4fee\u6539\u904d\u5386 *\/ }\n\nfor (auto it = v.begin(); it != v.end(); ++it) {\n    \/\/ *it \u8bbf\u95ee\n}<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5178\u578b\u7528\u4f8b\uff1a\u4ece\u6570\u7ec4\u6784\u9020 vector \/ \u8ffd\u52a0\u6570\u7ec4\u5185\u5bb9<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>double a[6] = {0,0,0,0,0,0};<br>std::vector&lt;double&gt; v(a, a+6); \/\/ \u6784\u9020<br><br>\/\/ \u8ffd\u52a0\u63d2\u5165\u6570\u7ec4\u5230vector\u672b\u5c3e<br>v.insert(v.end(), a, a+6);<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751\uff1a\u4e0b\u6807\u8d4b\u503c\u524d\u5fc5\u987b\u6709\u7a7a\u95f4<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>std::vector&lt;double&gt; v;<br>v[0] = 1.0; \/\/ \u00d7 \u8d8a\u754c\uff08\u672a\u5b9a\u4e49\u884c\u4e3a\uff09<br><br>v.resize(6);<br>v[0] = 1.0; \/\/ <\/code>\u221a<\/pre>\n\n\n\n<h5 class=\"wp-block-heading\"> \u8fed\u4ee3\u5668\/\u6307\u9488\u5931\u6548\u89c4\u5219\uff08\u91cd\u70b9\uff09<\/h5>\n\n\n\n<ul>\n<li><code>push_back<\/code> \u53ef\u80fd\u89e6\u53d1\u6269\u5bb9 \u21d2 <strong>\u6240\u6709\u8fed\u4ee3\u5668\u3001\u5f15\u7528\u3001data() \u6307\u9488\u90fd\u53ef\u80fd\u5931\u6548<\/strong><\/li>\n\n\n\n<li><code>erase\/insert<\/code> \u5728 <code>vector<\/code> \u4e2d\u901a\u5e38\u4f1a\u4f7f\u63d2\u5165\u70b9\u4e4b\u540e\u7684\u8fed\u4ee3\u5668\u5931\u6548<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">2) <code>std::array&lt;T, N&gt;<\/code>\uff08\u56fa\u5b9a\u957f\u5ea6\u6570\u7ec4\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;array&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li><strong>\u957f\u5ea6\u5728\u7f16\u8bd1\u671f\u56fa\u5b9a<\/strong>\uff08<code>N<\/code> \u662f\u6a21\u677f\u53c2\u6570\uff09<\/li>\n\n\n\n<li><strong>\u8fde\u7eed\u5185\u5b58<\/strong>\uff08\u4e0e C \u6570\u7ec4\u5e03\u5c40\u4e00\u81f4\uff0ccache \u53cb\u597d\uff09<\/li>\n\n\n\n<li><strong>\u65e0\u52a8\u6001\u5206\u914d<\/strong>\uff08\u901a\u5e38\u5728\u6808\u4e0a\u6216\u4f5c\u4e3a\u5bf9\u8c61\u6210\u5458\uff09<\/li>\n\n\n\n<li>\u652f\u6301 <strong>\u968f\u673a\u8bbf\u95ee<\/strong>\uff1a<code>a[i]<\/code>\u3001<code>a.at(i)<\/code><\/li>\n\n\n\n<li>\u53ef\u4e0e STL \u7b97\u6cd5\u914d\u5408\u4f7f\u7528\uff08\u6709 <code>begin\/end<\/code>\uff09<\/li>\n\n\n\n<li><strong>\u4e0d\u80fd\u6539\u53d8\u957f\u5ea6<\/strong>\uff08\u6ca1\u6709 <code>push_back \/ resize<\/code>\uff09<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11 \u9700\u8981\u53cc\u82b1\u62ec\u53f7\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\">std::array&lt;int, 5&gt; a1 = {{1, 2, 3, 4, 5}};<br>std::array&lt;double, 6&gt; a2 = {{0, 0, 0, 0, 0, 0}};<br>std::array&lt;int, 3&gt; a3 = {{}};              \/\/ \u5168\u90e8\u521d\u59cb\u5316\u4e3a 0<\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\uff08\u8bfb \/ \u5199\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>a&#91;i];            \/\/ \u4e0d\u505a\u8d8a\u754c\u68c0\u67e5\uff08\u8d8a\u754c=\u672a\u5b9a\u4e49\u884c\u4e3a\uff09\na.at(i);         \/\/ \u5e26\u8fb9\u754c\u68c0\u67e5\uff0c\u8d8a\u754c\u629b std::out_of_range\na.front();       \/\/ \u7b2c\u4e00\u4e2a\u5143\u7d20\na.back();        \/\/ \u6700\u540e\u4e00\u4e2a\u5143\u7d20\na.data();        \/\/ \u6307\u5411\u5e95\u5c42\u8fde\u7eed\u5185\u5b58\u7684\u6307\u9488\uff08T*\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5bb9\u91cf\u76f8\u5173<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>a.size();        \/\/ \u8fd4\u56de N\na.empty();       \/\/ C++11 \u4e2d\u6c38\u8fdc\u662f false\uff08N &gt; 0 \u65f6\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u586b\u5145 \/ \u8d4b\u503c<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>a.fill(0);       \/\/ \u6240\u6709\u5143\u7d20\u8d4b\u4e3a\u540c\u4e00\u4e2a\u503c\n\n#include &lt;algorithm&gt;\nstd::fill(a.begin(), a.end(), 1.0);<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (const auto&amp; x : a) { \/* \u53ea\u8bfb *\/ }\nfor (auto&amp; x : a) { \/* \u53ef\u4fee\u6539 *\/ }\n\nfor (auto it = a.begin(); it != a.end(); ++it) {\n    \/\/ *it\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u4ea4\u6362<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::array&lt;int, 3&gt; x = {{1,2,3}};\nstd::array&lt;int, 3&gt; y = {{4,5,6}};\nx.swap(y);               \/\/ O(N)<\/code><\/pre>\n\n\n\n<ul>\n<li>\u4e0e C \u6570\u7ec4 \/ vector \u7684\u4e92\u64cd\u4f5c<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/C \u6570\u7ec4 \u2192 std::array\ndouble c&#91;6] = {1,2,3,4,5,6};\nstd::array&lt;double, 6&gt; a;\nstd::copy(c, c + 6, a.begin());\n\n\/\/std::array \u2192 std::vector\n#include &lt;vector&gt;\nstd::vector&lt;double&gt; v(a.begin(), a.end());\n\n\/\/\u4f5c\u4e3a\u201c\u6570\u7ec4\u6307\u9488\u201d\u4f7f\u7528\nvoid foo(const double* p, int n);\nfoo(a.data(), static_cast&lt;int&gt;(a.size()));<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u7528\u9014\u5efa\u8bae<\/h5>\n\n\n\n<ul>\n<li>\u957f\u5ea6\u56fa\u5b9a\uff08\u6bd4\u5982 6 \u4e2a double\uff09\u66f4\u63a8\u8350 <code>array&lt;double,6&gt;<\/code> \u800c\u4e0d\u662f <code>vector&lt;double&gt;<\/code>\n<ul>\n<li>\u66f4\u5feb\u3001\u66f4\u7701\u5185\u5b58\u3001\u8bed\u4e49\u660e\u786e<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">3) <code>std::pair&lt;A,B&gt;<\/code>\uff08\u4e8c\u5143\u7ec4\/ \u952e\u503c\u5bf9\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;utility&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u7528\u6765\u5b58\u50a8 <strong>\u4e24\u4e2a\u76f8\u5173\u7684\u503c<\/strong>\uff1a<code>first<\/code> \u548c <code>second<\/code><\/li>\n\n\n\n<li>\u4e24\u4e2a\u7c7b\u578b\u53ef\u4ee5\u4e0d\u540c\uff1a<code>std::pair&lt;A,B&gt;<\/code><\/li>\n\n\n\n<li><code>std::map<\/code> \u7684\u5143\u7d20\u7c7b\u578b\u5c31\u662f <code>std::pair&lt;const K, V&gt;<\/code><\/li>\n\n\n\n<li>\u5e38\u7528\u4e8e\uff1a\n<ul>\n<li>\u8fd4\u56de\u4e24\u4e2a\u7ed3\u679c\uff08\u51fd\u6570\u8fd4\u56de\u503c\uff09<\/li>\n\n\n\n<li>\u5b58\u952e\u503c\u5bf9\uff08map\/set \u63d2\u5165\u8fd4\u56de\u503c\uff09<\/li>\n\n\n\n<li>\u628a\u4e24\u4e2a\u5b57\u6bb5\u4e34\u65f6\u6253\u5305\u4f20\u9012\/\u5b58\u50a8<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u6210\u5458<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code>pair.first   \/\/ \u7b2c\u4e00\u4e2a\u5143\u7d20\npair.second  \/\/ \u7b2c\u4e8c\u4e2a\u5143\u7d20<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u521b\u5efa \/ \u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<p>1\uff09\u76f4\u63a5\u6784\u9020<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>std::pair&lt;int, double&gt; p(1, 3.14);<\/code><\/pre>\n\n\n\n<p>2\uff09\u7528 <code>std::make_pair<\/code>\uff08\u81ea\u52a8\u63a8\u5bfc\u7c7b\u578b\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>auto p2 = std::make_pair(2, 2.71);<\/code><\/pre>\n\n\n\n<p>3\uff09\u5217\u8868\u521d\u59cb\u5316\uff08C++11\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>std::pair&lt;int, std::string&gt; p3 = {1, \"one\"};\n\n\/\/ \u6ce8\u610f\uff1amake_pair(\"one\") \u91cc\u5b57\u7b26\u4e32\u5b57\u9762\u91cf\u7c7b\u578b\u662f const char*\uff0c\u5982\u679c\u4f60\u60f3\u8981 std::string\uff0c\u53ef\u4ee5\u663e\u5f0f\u5199\uff1a\nstd::pair&lt;int, std::string&gt; p = std::make_pair(1, std::string(\"one\"));<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u8bbf\u95ee \/ \u4fee\u6539<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code>int a = p.first;\ndouble b = p.second;\n\np.first = 10;\np.second = 0.5;<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u51fd\u6570\u8fd4\u56de\u4e24\u4e2a\u503c<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;utility&gt;\n\nstd::pair&lt;bool, int&gt; parse() {\n    \/\/ \u6210\u529f\u4e0e\u7ed3\u679c\u4e00\u8d77\u8fd4\u56de\n    return std::make_pair(true, 42);\n}\n\nint main() {\n    std::pair&lt;bool, int&gt; r = parse();\n    if (r.first) {\n        int value = r.second;\n    }\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u4e0e <code>std::map<\/code> \u914d\u5408\uff1a<code>insert<\/code> \u7684\u8fd4\u56de\u503c<\/li>\n<\/ul>\n\n\n\n<p><code>map.insert(...)<\/code> \u8fd4\u56de <code>std::pair&lt;iterator, bool&gt;<\/code>\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;map&gt;\n#include &lt;utility&gt;\n\nstd::map&lt;int, int&gt; m;\nstd::pair&lt;std::map&lt;int,int&gt;::iterator, bool&gt; ret =\n    m.insert(std::make_pair(1, 100));\n\nif (ret.second) {\n    \/\/ \u63d2\u5165\u6210\u529f\n    \/\/ ret.first \u6307\u5411\u65b0\u63d2\u5165\u7684\u5143\u7d20\n} else {\n    \/\/ \u63d2\u5165\u5931\u8d25\uff08key \u5df2\u5b58\u5728\uff09\n    \/\/ ret.first \u6307\u5411\u5df2\u6709\u5143\u7d20\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u4e0e <code>std::set<\/code> \u914d\u5408\uff1a<code>insert<\/code> \u7684\u8fd4\u56de\u503c<\/li>\n<\/ul>\n\n\n\n<p><code>set.insert(x)<\/code> \u8fd4\u56de <code>pair&lt;iterator, bool&gt;<\/code>\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;set&gt;\n#include &lt;utility&gt;\n\nstd::set&lt;int&gt; s;\nauto ret = s.insert(3);\n\nif (!ret.second) {\n    \/\/ 3 \u5df2\u5b58\u5728\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u6bd4\u8f83\uff08pair \u652f\u6301\u6bd4\u8f83\u8fd0\u7b97\uff09<\/li>\n<\/ul>\n\n\n\n<p><code>pair<\/code> \u9ed8\u8ba4\u662f <strong>\u5b57\u5178\u5e8f\u6bd4\u8f83<\/strong>\uff1a<\/p>\n\n\n\n<ul>\n<li>\u5148\u6bd4\u8f83 <code>first<\/code><\/li>\n\n\n\n<li><code>first<\/code> \u76f8\u7b49\u518d\u6bd4\u8f83 <code>second<\/code><\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::pair&lt;int,int&gt; a = {1, 5};\nstd::pair&lt;int,int&gt; b = {2, 0};\n\nbool x = (a &lt; b); \/\/ true\uff0c\u56e0\u4e3a 1 &lt; 2<\/code><\/pre>\n\n\n\n<ul>\n<li>\u4ea4\u6362<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::pair&lt;int,int&gt; a = {1, 2};\nstd::pair&lt;int,int&gt; b = {3, 4};\na.swap(b); \/\/ \u6216 std::swap(a,b)<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><strong><code>pair<\/code> \u4e0d\u662f\u5bb9\u5668<\/strong>\uff1a\u53ea\u80fd\u5b58 2 \u4e2a\u503c\uff0c\u6ca1\u6709 <code>size()\/begin()\/end()<\/code><\/li>\n\n\n\n<li><strong>\u7c7b\u578b\u63a8\u5bfc\u5c0f\u5fc3\u5b57\u7b26\u4e32\u5b57\u9762\u91cf<\/strong>\uff1a<code>make_pair(1, \"one\")<\/code> \u7684\u7b2c\u4e8c\u4e2a\u662f <code>const char*<\/code><\/li>\n\n\n\n<li><code>map<\/code> \u5143\u7d20\u662f <code>pair&lt;const K, V&gt;<\/code>\uff1a<code>it-&gt;first<\/code> \u662f <code>const<\/code>\uff0c\u4e0d\u80fd\u6539 key<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">4) <code>std::map&lt;K,V&gt;<\/code>\uff08\u6709\u5e8f\u952e\u503c\u8868\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;map&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u5b58\u50a8 <strong>\u952e\u503c\u5bf9<\/strong>\uff1a<code>(key, value)<\/code><\/li>\n\n\n\n<li><strong>key \u552f\u4e00<\/strong>\uff08\u540c\u4e00\u4e2a key \u53ea\u80fd\u51fa\u73b0\u4e00\u6b21\uff09<\/li>\n\n\n\n<li>\u6309 key <strong>\u81ea\u52a8\u6392\u5e8f<\/strong>\uff08\u9ed8\u8ba4\u5347\u5e8f\uff0c\u6bd4\u8f83\u5668\u9ed8\u8ba4 <code>std::less&lt;K&gt;<\/code>\uff09<\/li>\n\n\n\n<li>\u5e95\u5c42\u4e00\u822c\u662f <strong>\u7ea2\u9ed1\u6811<\/strong>\uff08\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\uff09<\/li>\n\n\n\n<li>\u5e38\u89c1\u64cd\u4f5c\u590d\u6742\u5ea6\uff1a\u67e5\u627e\/\u63d2\u5165\/\u5220\u9664 <strong>O(log N)<\/strong><\/li>\n\n\n\n<li>\u904d\u5386\u65f6\u4f1a\u6309 key \u6709\u5e8f\u8f93\u51fa<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\">std::map&lt;int, int&gt; m1; \/\/ \u7a7a<br><br>std::map&lt;int, std::string&gt; m2 = {<br>    {1, \"one\"},<br>    {2, \"two\"}<br>};<br><br>\/\/ value \u662f vector \u7684\u4f8b\u5b50<br>std::map&lt;int, std::vector&lt;double&gt;&gt; m3;<br>m3[1] = std::vector&lt;double&gt;(6, 0.0);<\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u67e5\u8be2 \/ \u5224\u65ad\u662f\u5426\u5b58\u5728\uff08\u4e0d\u4f1a\u63d2\u5165\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::map&lt;int,int&gt; m;\n\n\/\/ find\uff1a\u627e\u5230\u8fd4\u56de\u8fed\u4ee3\u5668\uff0c\u5426\u5219\u8fd4\u56de end()\nstd::map&lt;int,int&gt;::iterator it = m.find(10);\nif (it != m.end()) {\n    int key = it-&gt;first;\n    int val = it-&gt;second;\n}\n\n\/\/ count\uff1amap \u4e2d\u53ea\u53ef\u80fd\u662f 0 \u6216 1\nif (m.count(10) != 0) { \/* \u5b58\u5728 *\/ }<\/code><\/pre>\n\n\n\n<ul>\n<li>\u8bbf\u95ee \/ \u4fee\u6539 value\uff08\u5b58\u5728\u5219\u6539\uff0c\u4e0d\u5b58\u5728\u5219\u63d2\u5165\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>m&#91;10] = 5;          \/\/ \u82e5 key=10 \u4e0d\u5b58\u5728\uff0c\u4f1a\u63d2\u5165 {10, 0} \u518d\u8d4b\u503c\u4e3a 5\nint x = m&#91;10];      \/\/ \u82e5 key=10 \u4e0d\u5b58\u5728\uff0c\u4f1a\u63d2\u5165 {10, 0} \u5e76\u8fd4\u56de 0\n\n\/\/ \u91cd\u8981\u5751\uff1aoperator&#91;] \u4f1a\u201c\u65e0\u610f\u63d2\u5165\u201d\u3002\n\u5982\u679c\u4f60\u5e0c\u671b key \u4e0d\u5b58\u5728\u5c31\u62a5\u9519\/\u4e0d\u63d2\u5165\uff0c\u7528 find \u6216 at\uff08\u4f46 at \u662f C++11 \u6709\u7684\uff0c\u4f1a\u629b\u5f02\u5e38\uff09\uff1a\n\/\/ C++11: at \u4e0d\u4f1a\u63d2\u5165\uff0c\u4f46 key \u4e0d\u5b58\u5728\u4f1a\u629b std::out_of_range\nint v = m.at(10);<\/code><\/pre>\n\n\n\n<ul>\n<li>\u63d2\u5165\uff08\u4e0d\u4f1a\u8986\u76d6\u5df2\u6709 key\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ insert \u8fd4\u56de pair&lt;iterator, bool&gt;\nstd::pair&lt;std::map&lt;int,int&gt;::iterator, bool&gt; r = m.insert(std::make_pair(1, 100));\nif (r.second) {\n    \/\/ \u63d2\u5165\u6210\u529f\n} else {\n    \/\/ key \u5df2\u5b58\u5728\uff0c\u672a\u63d2\u5165\uff0cr.first \u6307\u5411\u5df2\u6709\u5143\u7d20\n}\n\n\/\/ C++11\nm.insert(std::pair&lt;int,int&gt;(2, 200));\nm.insert(std::make_pair(3, 300));\n\n\u5982\u679c\u8981\u201c\u5b58\u5728\u5c31\u6539\uff0c\u4e0d\u5b58\u5728\u5c31\u63d2\u201d\uff0c\u6700\u7b80\u5355\uff1am&#91;key] = value;\n\u5982\u679c\u8981\u201c\u53ea\u63d2\u4e0d\u8986\u76d6\u201d\uff0c\u7528 insert<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5220\u9664<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>m.erase(10);             \/\/ \u6309 key \u5220\u9664\uff08\u8fd4\u56de\u5220\u9664\u4e2a\u6570\uff1a0 \u6216 1\uff09\nm.erase(it);             \/\/ \u6309\u8fed\u4ee3\u5668\u5220\u9664\nm.erase(m.begin(), m.end()); \/\/ \u5220\u9664\u4e00\u4e2a\u8303\u56f4\uff08\u6e05\u7a7a\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>m.clear();<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08C++11\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (std::map&lt;int,int&gt;::const_iterator it = m.begin(); it != m.end(); ++it) {\n    int k = it-&gt;first;\n    int v = it-&gt;second;\n}\n\n\/\/ C++11 range-for\nfor (const auto&amp; kv : m) {\n    int k = kv.first;\n    int v = kv.second;\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u8303\u56f4\u67e5\u8be2\uff08\u6709\u5e8f map \u7684\u4f18\u52bf\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/map \u6709\u5e8f\uff0c\u6240\u4ee5\u53ef\u4ee5\u505a\u201c\u627e\u7b2c\u4e00\u4e2a &gt;= key\u201d\u7684\u67e5\u8be2\u7b49\uff1a\nstd::map&lt;int,int&gt;::iterator it1 = m.lower_bound(10); \/\/ \u7b2c\u4e00\u4e2a key &gt;= 10\nstd::map&lt;int,int&gt;::iterator it2 = m.upper_bound(10); \/\/ \u7b2c\u4e00\u4e2a key &gt; 10\n\n\/\/ \u7b49\u4e8e key \u7684\u8303\u56f4\uff08map \u8981\u4e48 0 \u4e2a\u8981\u4e48 1 \u4e2a\uff09\nstd::pair&lt;std::map&lt;int,int&gt;::iterator, std::map&lt;int,int&gt;::iterator&gt; rg = m.equal_range(10);\n\n\/\/\u5178\u578b\u7528\u6cd5\uff1a\u904d\u5386\u533a\u95f4 &#91;L, R) \u7684 key\nfor (auto it = m.lower_bound(L); it != m.lower_bound(R); ++it) {\n    \/\/ it-&gt;first in &#91;L, R)\n}<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ul>\n<li><strong><code>m[key]<\/code> \u4f1a\u63d2\u5165\u9ed8\u8ba4\u503c<\/strong>\uff1a\u53ea\u67e5\u5b58\u5728\u6027\u4e0d\u8981\u7528\u5b83<\/li>\n\n\n\n<li><code>insert<\/code><strong>\u4e0d\u4f1a\u8986\u76d6<\/strong>\uff1akey \u5df2\u5b58\u5728\u65f6\u63d2\u5165\u5931\u8d25<\/li>\n\n\n\n<li>key \u662f <code>const<\/code>\uff1a<code>it-&gt;first<\/code> \u4e0d\u80fd\u6539\uff08\u7f16\u8bd1\u671f\u9650\u5236\uff09<\/li>\n\n\n\n<li>\u904d\u5386\u65f6\u6309 key \u6392\u5e8f\uff0c\u4e0d\u662f\u63d2\u5165\u987a\u5e8f<\/li>\n\n\n\n<li><code>find<\/code> \u662f O(logN)\uff0c\u4e0d\u662f O(1)\uff08\u56e0\u4e3a\u6811\u7ed3\u6784\uff09<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">5) <code>std::set&lt;T&gt;<\/code>\uff08\u6709\u5e8f\u96c6\u5408\uff0c\u5143\u7d20\u552f\u4e00\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;set&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u5b58\u50a8 <strong>\u5143\u7d20\uff08value\uff09<\/strong>\uff0c\u6bcf\u4e2a\u5143\u7d20 <strong>\u552f\u4e00<\/strong>\uff08\u4e0d\u5141\u8bb8\u91cd\u590d\uff09<\/li>\n\n\n\n<li>\u5143\u7d20\u4f1a\u6309\u6bd4\u8f83\u89c4\u5219 <strong>\u81ea\u52a8\u6392\u5e8f<\/strong>\uff08\u9ed8\u8ba4\u5347\u5e8f\uff0c\u6bd4\u8f83\u5668\u9ed8\u8ba4 <code>std::less&lt;T&gt;<\/code>\uff09<\/li>\n\n\n\n<li>\u5e95\u5c42\u4e00\u822c\u662f <strong>\u7ea2\u9ed1\u6811<\/strong>\uff08\u5e73\u8861\u4e8c\u53c9\u641c\u7d22\u6811\uff09<\/li>\n\n\n\n<li>\u67e5\u627e\/\u63d2\u5165\/\u5220\u9664\u590d\u6742\u5ea6\uff1a<strong>O(log N)<\/strong><\/li>\n\n\n\n<li>\u9002\u5408\uff1a\u53bb\u91cd + \u6709\u5e8f\u8f93\u51fa\u3001\u5feb\u901f\u5224\u65ad\u5143\u7d20\u662f\u5426\u5b58\u5728<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code>std::set&lt;int&gt; s1;                 \/\/ \u7a7a\nstd::set&lt;int&gt; s2 = {3, 1, 2, 2};   \/\/ \u53bb\u91cd\u540e\u4e3a {1,2,3}\n\n\u6307\u5b9a\u6392\u5e8f\u89c4\u5219\uff08\u964d\u5e8f\uff09\uff1a\n\n#include &lt;functional&gt;\nstd::set&lt;int, std::greater&lt;int&gt; &gt; s3 = {1,2,3}; \/\/ {3,2,1}<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u67e5\u8be2 \/ \u5224\u65ad\u662f\u5426\u5b58\u5728<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::set&lt;int&gt; s = {1,2,3};\n\n\/\/ find\uff1a\u627e\u5230\u8fd4\u56de\u8fed\u4ee3\u5668\uff0c\u5426\u5219\u8fd4\u56de end()\nstd::set&lt;int&gt;::iterator it = s.find(2);\nif (it != s.end()) {\n    \/\/ \u627e\u5230\u4e86 *it == 2\n}\n\n\/\/ count\uff1aset \u4e2d\u53ea\u53ef\u80fd\u662f 0 \u6216 1\nif (s.count(2) != 0) {\n    \/\/ \u5b58\u5728\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u63d2\u5165\uff08\u91cd\u590d\u4f1a\u5931\u8d25\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::pair&lt;std::set&lt;int&gt;::iterator, bool&gt; r = s.insert(5);\nif (r.second) {\n    \/\/ \u63d2\u5165\u6210\u529f\n} else {\n    \/\/ \u5143\u7d20\u5df2\u5b58\u5728\uff0c\u672a\u63d2\u5165\uff0cr.first \u6307\u5411\u5df2\u6709\u5143\u7d20\n}\n\n\/\/ \u4e5f\u53ef\u4ee5\u6279\u91cf\u63d2\u5165\uff08C++11 initializer_list\uff09\uff1a\ns.insert({7, 8, 9});<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5220\u9664<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ \u6309\u503c\u5220\u9664\uff1a\ns.erase(2);   \/\/ \u8fd4\u56de\u5220\u9664\u4e2a\u6570\uff1a0 \u6216 1\n\n\/\/ \u6309\u8fed\u4ee3\u5668\u5220\u9664\uff1a\nstd::set&lt;int&gt;::iterator it = s.find(3);\nif (it != s.end()) s.erase(it);\n\n\/\/ \u6309\u8303\u56f4\u5220\u9664\uff1a\ns.erase(s.begin(), s.end()); \/\/ \u6e05\u7a7a\uff08\u4e5f\u53ef\u4ee5\u7528 clear\uff09<\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a \/ \u5927\u5c0f<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>s.clear();\ns.size();\ns.empty();<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08\u6709\u5e8f\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (const auto&amp; x : s) {\n    \/\/ x \u6309\u5e8f\u8f93\u51fa\n}\n\nfor (std::set&lt;int&gt;::const_iterator it = s.begin(); it != s.end(); ++it) {\n    int x = *it;\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u8303\u56f4\u67e5\u8be2\uff08\u6709\u5e8f set \u7684\u4f18\u52bf\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ \u7b2c\u4e00\u4e2a &gt;= key\nstd::set&lt;int&gt;::iterator it1 = s.lower_bound(5);\n\n\/\/ \u7b2c\u4e00\u4e2a &gt; key\nstd::set&lt;int&gt;::iterator it2 = s.upper_bound(5);\n\n\/\/ \u7b49\u4e8e key \u7684\u8303\u56f4\uff08set \u8981\u4e48 0 \u4e2a\u8981\u4e48 1 \u4e2a\uff09\nstd::pair&lt;std::set&lt;int&gt;::iterator, std::set&lt;int&gt;::iterator&gt; rg = s.equal_range(5);\n\n\/\/ \u5178\u578b\u7528\u6cd5\uff1a\u904d\u5386\u533a\u95f4 &#91;L, R)\nfor (auto it = s.lower_bound(L); it != s.lower_bound(R); ++it) {\n    \/\/ *it in &#91;L, R)\n}\n<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5178\u578b\u7528\u9014<\/h5>\n\n\n\n<ul>\n<li>\u53bb\u91cd + \u4fdd\u6301\u6709\u5e8f<\/li>\n\n\n\n<li>\u9700\u8981\u505a\u8303\u56f4\u67e5\u8be2\uff08<code>lower_bound\/upper_bound<\/code>\uff09<\/li>\n\n\n\n<li>\u9891\u7e41\u5224\u65ad\u201c\u67d0\u5143\u7d20\u662f\u5426\u51fa\u73b0\u8fc7\u201d<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ul>\n<li><strong>set \u91cc\u5143\u7d20\u4e0d\u80fd\u91cd\u590d<\/strong>\uff1a\u63d2\u5165\u91cd\u590d\u5143\u7d20\u4f1a\u5931\u8d25\uff08\u4e0d\u4f1a\u62a5\u9519\uff0c\u53ea\u662f <code>insert().second == false<\/code>\uff09<\/li>\n\n\n\n<li><strong>\u5143\u7d20\u662f\u201c\u53ea\u8bfb\u201d\u7684<\/strong>\uff1a\u4e0d\u80fd\u901a\u8fc7\u8fed\u4ee3\u5668\u4fee\u6539\u5143\u7d20\u503c\uff0c\u56e0\u4e3a\u6539\u503c\u53ef\u80fd\u7834\u574f\u6392\u5e8f\u7ed3\u6784\uff0c\u60f3\u201c\u4fee\u6539\u5143\u7d20\u201d\u901a\u5e38\u505a\u6cd5\uff1a<code>erase(old)<\/code> \u518d <code>insert(new)<\/code><\/li>\n\n\n\n<li><code>find\/count<\/code> \u662f <strong>O(logN)<\/strong>\uff0c\u4e0d\u662f O(1)\uff08\u6811\u7ed3\u6784\uff09<\/li>\n\n\n\n<li>\u904d\u5386\u987a\u5e8f\u662f <strong>\u6309\u6392\u5e8f\u89c4\u5219<\/strong>\uff0c\u4e0d\u662f\u63d2\u5165\u987a\u5e8f<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">6) <code>std::unordered_map&lt;K, V&gt;<\/code>\uff08\u54c8\u5e0c\u952e\u503c\u8868\uff0c\u5e73\u5747 O(1)\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;unordered_map&gt;<\/code><br>\uff08\u5e38\u7528\uff1a<code>#include &lt;utility&gt;<\/code> \u7528 <code>std::make_pair<\/code>\uff09<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u5b58\u50a8 <strong>\u952e\u503c\u5bf9 (key, value)<\/strong>\uff0c<strong>key \u552f\u4e00<\/strong><\/li>\n\n\n\n<li><strong>\u4e0d\u6392\u5e8f<\/strong>\uff08\u904d\u5386\u987a\u5e8f\u4e0d\u53ef\u9884\u6d4b\uff0c\u4f1a\u968f rehash \u6539\u53d8\uff09<\/li>\n\n\n\n<li>\u5e95\u5c42\u662f <strong>\u54c8\u5e0c\u8868<\/strong><\/li>\n\n\n\n<li>\u5e73\u5747\u67e5\u627e\/\u63d2\u5165\/\u5220\u9664 <strong>O(1)<\/strong>\uff0c\u6700\u574f\u53ef\u80fd <strong>O(N)<\/strong>\uff08\u54c8\u5e0c\u51b2\u7a81\u6781\u7aef\u60c5\u51b5\uff09<\/li>\n\n\n\n<li>\u9002\u5408\uff1a\u53ea\u60f3\u5feb\u901f\u67e5\u627e\uff0c\u4e0d\u5173\u5fc3\u987a\u5e8f<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code>std::unordered_map&lt;int, std::string&gt; um1; \/\/ \u7a7a\n\nstd::unordered_map&lt;int, std::string&gt; um2 = {\n    {1, \"one\"},\n    {2, \"two\"}\n};<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u67e5\u8be2 \/ \u5224\u65ad\u662f\u5426\u5b58\u5728\uff08\u4e0d\u4f1a\u63d2\u5165\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::unordered_map&lt;int,int&gt; um;\n\nauto it = um.find(10);        \/\/ \u627e\u5230\u8fd4\u56de\u8fed\u4ee3\u5668\uff0c\u5426\u5219 end()\nif (it != um.end()) {\n    int v = it-&gt;second;\n}\n\nif (um.count(10) != 0) {      \/\/ 0 \u6216 1\n    \/\/ \u5b58\u5728\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u8bbf\u95ee \/ \u4fee\u6539\uff08\u5b58\u5728\u5219\u6539\uff0c\u4e0d\u5b58\u5728\u5219\u63d2\u5165\u9ed8\u8ba4\u503c\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>um&#91;10] = 5;        \/\/ \u4e0d\u5b58\u5728\u5219\u63d2\u5165 {10, 0} \u518d\u8d4b\u503c\u4e3a 5\nint x = um&#91;99];    \/\/ \u4e0d\u5b58\u5728\u5219\u63d2\u5165 {99, 0} \u5e76\u8fd4\u56de 0\n\n\/\/ \u5982\u679c\u4f60\u4e0d\u60f3\u63d2\u5165\uff0c\u7528 find\uff0c\u6216\u7528 at\uff08C++11 \u6709\uff0ckey \u4e0d\u5b58\u5728\u629b\u5f02\u5e38\uff09\uff1a\nint v = um.at(10); \/\/ key \u4e0d\u5b58\u5728\u4f1a\u629b std::out_of_range<\/code><\/pre>\n\n\n\n<ul>\n<li>\u63d2\u5165\uff08\u4e0d\u4f1a\u8986\u76d6\u5df2\u6709 key\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>auto ret = um.insert(std::make_pair(1, 100));\n\/\/ ret: pair&lt;iterator, bool&gt;\nif (ret.second) {\n    \/\/ \u63d2\u5165\u6210\u529f\n} else {\n    \/\/ key \u5df2\u5b58\u5728\uff0c\u672a\u63d2\u5165\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5220\u9664<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>um.erase(10);   \/\/ \u6309 key \u5220\u9664\uff0c\u8fd4\u56de\u5220\u9664\u4e2a\u6570\uff080 \u6216 1\uff09\n\nauto it = um.find(5);\nif (it != um.end()) um.erase(it); \/\/ \u6309\u8fed\u4ee3\u5668\u5220\u9664<\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a \/ \u5927\u5c0f<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>um.clear();\num.size();\num.empty();<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08\u65e0\u5e8f\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (const auto&amp; kv : um) {\n    \/\/ kv.first, kv.second\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>rehash \/ \u8d1f\u8f7d\u56e0\u5b50\uff08\u6027\u80fd\u76f8\u5173\uff0c\u8fdb\u9636\u4f46\u5f88\u5e38\u7528\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>um.reserve(1000);        \/\/ \u9884\u7559\uff08\u51cf\u5c11 rehash \u6b21\u6570\uff09\num.rehash(2048);         \/\/ \u5f3a\u5236\u6876\u6570\u91cf\uff08bucket count\uff09\u81f3\u5c11\u5230\u6307\u5b9a\u503c\nfloat lf = um.load_factor();      \/\/ \u5f53\u524d\u8d1f\u8f7d\u56e0\u5b50\num.max_load_factor(0.7f);         \/\/ \u8bbe\u5b9a\u6700\u5927\u8d1f\u8f7d\u56e0\u5b50\uff08\u9ed8\u8ba4\u901a\u5e38 1.0\uff09\n\/\/ reserve \u5f88\u5b9e\u7528\uff1a\u5f53\u4f60\u9884\u4f30\u5143\u7d20\u5f88\u591a\u65f6\uff0c\u63d0\u524d reserve \u80fd\u663e\u8457\u51cf\u5c11 rehash\u3002<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><strong>\u904d\u5386\u987a\u5e8f\u4e0d\u7a33\u5b9a<\/strong>\uff1a\u4e0d\u8981\u4f9d\u8d56\u8f93\u51fa\u987a\u5e8f<\/li>\n\n\n\n<li><code>operator[]<\/code> \u4f1a <strong>\u63d2\u5165\u9ed8\u8ba4\u503c<\/strong>\uff1a\u53ea\u60f3\u67e5\u5b58\u5728\u7528 <code>find\/count<\/code><\/li>\n\n\n\n<li><strong>rehash \u4f1a\u4f7f\u8fed\u4ee3\u5668\u5931\u6548<\/strong>\uff08\u4ee5\u53ca bucket \u76f8\u5173\u72b6\u6001\u53d8\u5316\uff09<\/li>\n\n\n\n<li>key \u7c7b\u578b\u9700\u8981 <code>std::hash&lt;K&gt;<\/code> \u652f\u6301\uff1b\u81ea\u5b9a\u4e49\u7c7b\u578b\u8981\u63d0\u4f9b hash \u548c\u76f8\u7b49\u5224\u65ad\uff08\u89c1\u4e0b\u65b9\uff09<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\">\u81ea\u5b9a\u4e49 key\uff08hash + equal\uff09<\/h5>\n\n\n\n<p>\u4f8b\u5982\u4f60\u7528 <code>struct Key { int a,b; };<\/code> \u505a key\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>#include &lt;unordered_map&gt;<br><br>struct Key {<br>    int a, b;<br>};<br><br>struct KeyHash {<br>    std::size_t operator()(const Key&amp; k) const {<br>        \/\/ \u7b80\u5355\u7ec4\u5408\uff08\u793a\u4f8b\uff09<br>        return std::hash&lt;int&gt;()(k.a) ^ (std::hash&lt;int&gt;()(k.b) &lt;&lt; 1);<br>    }<br>};<br><br>struct KeyEq {<br>    bool operator()(const Key&amp; x, const Key&amp; y) const {<br>        return x.a == y.a &amp;&amp; x.b == y.b;<br>    }<br>};<br><br>std::unordered_map&lt;Key, int, KeyHash, KeyEq&gt; um;<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4e0e map \u7684\u9009\u62e9<\/h5>\n\n\n\n<ul>\n<li>\u8981\u6392\u5e8f\/\u8303\u56f4\u67e5\u8be2\uff08lower_bound \u7b49\uff09\uff1a\u7528 <code>map<\/code><\/li>\n\n\n\n<li>\u53ea\u8981\u5feb\u901f\u67e5\u627e\uff1a\u7528 <code>unordered_map<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">7) <code>std::unordered_set&lt;T&gt;<\/code>\uff08\u54c8\u5e0c\u96c6\u5408\uff0c\u5e73\u5747 O(1)\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;unordered_set&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u5b58\u50a8 <strong>\u5143\u7d20\uff08value\uff09<\/strong>\uff0c\u6bcf\u4e2a\u5143\u7d20 <strong>\u552f\u4e00<\/strong><\/li>\n\n\n\n<li><strong>\u4e0d\u6392\u5e8f<\/strong>\uff0c\u904d\u5386\u987a\u5e8f\u4e0d\u53ef\u9884\u6d4b<\/li>\n\n\n\n<li>\u5e73\u5747\u67e5\u627e\/\u63d2\u5165\/\u5220\u9664 <strong>O(1)<\/strong><\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-preformatted\"><code>std::unordered_set&lt;int&gt; us1;<br>std::unordered_set&lt;int&gt; us2 = {3, 1, 2, 2}; \/\/ \u53bb\u91cd\u540e\u5305\u542b {1,2,3}<br><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u67e5\u8be2\/\u5b58\u5728\u6027<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>auto it = us2.find(2);\nif (it != us2.end()) {}\n\nif (us2.count(2) != 0) {} \/\/ 0 \u6216 1<\/code><\/pre>\n\n\n\n<ul>\n<li>\u63d2\u5165\uff08\u91cd\u590d\u5931\u8d25\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>auto ret = us2.insert(5); \/\/ pair&lt;iterator,bool&gt;\nif (!ret.second) {\n    \/\/ 5 \u5df2\u5b58\u5728\n}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u5220\u9664\/\u6e05\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>us2.erase(2); \/\/ 0\u62161\nus2.clear();<\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08\u65e0\u5e8f\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>for (const auto&amp; x : us2) {}<\/code><\/pre>\n\n\n\n<ul>\n<li>\u6027\u80fd\u76f8\u5173<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>us2.reserve(1000);\nus2.max_load_factor(0.7f);<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751\uff08\u91cd\u70b9\uff09<\/h5>\n\n\n\n<ol>\n<li><strong>\u65e0\u5e8f<\/strong>\uff1a\u4e0d\u8981\u671f\u5f85\u5347\u5e8f\/\u63d2\u5165\u987a\u5e8f<\/li>\n\n\n\n<li><strong>rehash \u53ef\u80fd\u5bfc\u81f4\u8fed\u4ee3\u5668\u5931\u6548<\/strong><\/li>\n\n\n\n<li>\u81ea\u5b9a\u4e49\u7c7b\u578b\u540c\u6837\u9700\u8981 hash + equal\uff08\u548c unordered_map \u7c7b\u4f3c\uff09<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\"><code>unordered_*<\/code> vs <code>map\/set<\/code> \u5982\u4f55\u9009\u62e9\uff08\u5feb\u901f\u9009\u578b\uff09<\/h5>\n\n\n\n<p>\u7528 <code>unordered_map \/ unordered_set<\/code>\uff1a<\/p>\n\n\n\n<ul>\n<li>\u53ea\u5173\u5fc3\u201c\u662f\u5426\u5b58\u5728\/\u5feb\u901f\u67e5\u627e\u201d<\/li>\n\n\n\n<li>\u4e0d\u9700\u8981\u6392\u5e8f\u3001\u4e0d\u9700\u8981\u8303\u56f4\u67e5\u8be2<\/li>\n\n\n\n<li>\u8ffd\u6c42\u5e73\u5747\u6027\u80fd O(1)<\/li>\n<\/ul>\n\n\n\n<p> \u7528 <code>map \/ set<\/code>\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9700\u8981\u6309 key \u6709\u5e8f\u904d\u5386<\/li>\n\n\n\n<li>\u9700\u8981\u8303\u56f4\u67e5\u8be2\uff1a<code>lower_bound\/upper_bound<\/code><\/li>\n\n\n\n<li>\u5e0c\u671b\u590d\u6742\u5ea6\u7a33\u5b9a O(logN)\uff08\u4e0d\u4f1a\u9000\u5316\u5230 O(N)\uff09<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">8) <code>std::deque&lt;T&gt;<\/code>\uff08\u53cc\u7aef\u961f\u5217\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;deque&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li><strong>\u53cc\u7aef\u64cd\u4f5c\u5feb<\/strong>\uff1a\u5728\u961f\u9996\/\u961f\u5c3e\u63d2\u5165\u3001\u5220\u9664\u90fd\u662f <strong>O(1)<\/strong>\uff08\u5747\u644a\uff09<\/li>\n\n\n\n<li>\u652f\u6301 <strong>\u968f\u673a\u8bbf\u95ee<\/strong>\uff1a<code>d[i]<\/code> \/ <code>d.at(i)<\/code>\uff08O(1)\uff09<\/li>\n\n\n\n<li><strong>\u4e0d\u662f\u8fde\u7eed\u5185\u5b58<\/strong>\uff08\u901a\u5e38\u662f\u5206\u6bb5\u8fde\u7eed\uff09\uff0c\u56e0\u6b64\uff1a\n<ul>\n<li><code>data()<\/code> \u5728 C++11 \u7684 <code>deque<\/code> <strong>\u4e0d\u4fdd\u8bc1\u5b58\u5728\/\u4e0d\u53ef\u7528\u4f5c\u8fde\u7eed\u6570\u7ec4\u6307\u9488<\/strong><\/li>\n\n\n\n<li>\u904d\u5386\u4e5f\u5f88\u5feb\uff0c\u4f46 cache \u53cb\u597d\u7a0b\u5ea6\u4e00\u822c\u4e0d\u5982 <code>vector<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u5e38\u89c1\u7528\u9014\uff1a\n<ul>\n<li>\u9700\u8981\u9891\u7e41 <code>push_front<\/code> \u7684\u573a\u666f<\/li>\n\n\n\n<li><code>queue\/stack<\/code> \u7684\u9ed8\u8ba4\u5e95\u5c42\u5bb9\u5668<\/li>\n\n\n\n<li>\u6ed1\u52a8\u7a97\u53e3\u3001\u53cc\u7aef\u64cd\u4f5c\u7684\u961f\u5217\u903b\u8f91<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::deque&lt;int&gt; d1;                \/\/ \u7a7a\nstd::deque&lt;int&gt; d2(5);             \/\/ 5 \u4e2a 0\nstd::deque&lt;double&gt; d3(6, 0.0);     \/\/ 6 \u4e2a 0.0\nstd::deque&lt;int&gt; d4 = {1,2,3};      \/\/ \u5217\u8868\u521d\u59cb\u5316<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\uff08\u8bfb \/ \u5199\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>d&#91;i];          \/\/ \u4e0d\u68c0\u67e5\u8d8a\u754c\uff08\u8d8a\u754c=\u672a\u5b9a\u4e49\u884c\u4e3a\uff09\nd.at(i);       \/\/ \u8d8a\u754c\u629b std::out_of_range\nd.front();     \/\/ \u961f\u9996\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09\nd.back();      \/\/ \u961f\u5c3e\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u53cc\u7aef\u63d2\u5165 \/ \u5220\u9664\uff08deque \u7684\u6838\u5fc3\u4f18\u52bf\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>d.push_back(x);     \/\/ \u5c3e\u90e8\u8ffd\u52a0\nd.push_front(x);    \/\/ \u5934\u90e8\u8ffd\u52a0\n\nd.pop_back();       \/\/ \u5220\u9664\u5c3e\u90e8\nd.pop_front();      \/\/ \u5220\u9664\u5934\u90e8<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u4e2d\u95f4\u63d2\u5165 \/ \u5220\u9664\uff08\u4e00\u822c\u4e3a O(N)\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>d.insert(d.begin() + pos, x);\nd.erase(d.begin() + pos);\n\nd.erase(d.begin() + l, d.begin() + r); \/\/ \u5220\u9664\u533a\u95f4 &#91;l, r)<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u8d4b\u503c \/ \u91cd\u7f6e \/ \u8c03\u6574\u5927\u5c0f<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>d.clear();               \/\/ \u6e05\u7a7a\nd.assign(6, 0.0);        \/\/ \u91cd\u7f6e\u4e3a 6 \u4e2a 0.0\nd.resize(10);            \/\/ \u6539\u957f\u5ea6\uff08\u6269\u5c55\u8865\u9ed8\u8ba4\u503c T()\uff09\nd.resize(10, 3.14);      \/\/ \u6269\u5c55\u7528 3.14 \u586b\u5145<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u5927\u5c0f \/ \u5224\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>d.size();\nd.empty();<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08C++11\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>for (const auto&amp; x : d) { \/* \u53ea\u8bfb *\/ }\nfor (auto&amp; x : d) { \/* \u53ef\u4fee\u6539 *\/ }\n\nfor (auto it = d.begin(); it != d.end(); ++it) {\n    \/\/ *it\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u6ed1\u52a8\u7a97\u53e3\uff08\u53cc\u7aef\u961f\u5217\u5178\u578b\u573a\u666f\uff09<\/h5>\n\n\n\n<p>\u7ef4\u62a4\u4e00\u4e2a\u201c\u5355\u8c03\u961f\u5217\u201d\u6c42\u7a97\u53e3\u6700\u5927\u503c\uff08\u6838\u5fc3\u601d\u60f3\u793a\u4f8b\uff09\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;deque&gt;\n#include &lt;vector&gt;\n\n\/\/ \u8fd9\u91cc\u53ea\u5c55\u793a deque \u7684 push_front\/push_back\/pop_front\/pop_back \u7684\u4f7f\u7528\u601d\u8def<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4e0e <code>vector<\/code> \u7684\u9009\u62e9\u5efa\u8bae<\/h5>\n\n\n\n<p>\u9009 <code>deque<\/code>\uff1a<\/p>\n\n\n\n<ul>\n<li>\u7ecf\u5e38\u5728 <strong>\u5934\u90e8<\/strong> \u63d2\u5165\/\u5220\u9664\uff08<code>push_front\/pop_front<\/code>\uff09<\/li>\n\n\n\n<li>\u9700\u8981\u968f\u673a\u8bbf\u95ee\u4f46\u4e0d\u8981\u6c42\u8fde\u7eed\u5185\u5b58<\/li>\n<\/ul>\n\n\n\n<p>\u9009 <code>vector<\/code>\uff1a<\/p>\n\n\n\n<ul>\n<li>\u4e3b\u8981\u5728 <strong>\u5c3e\u90e8<\/strong> \u64cd\u4f5c<\/li>\n\n\n\n<li>\u9700\u8981 <code>data()<\/code> \u8fde\u7eed\u5185\u5b58\uff08\u4f20 C \u63a5\u53e3\/\u9ad8\u6027\u80fd\u62f7\u8d1d\uff09<\/li>\n\n\n\n<li>\u66f4\u5f3a\u7684 cache \u53cb\u597d\u6027<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><code>front()\/back()<\/code> \u5728\u7a7a deque \u4e0a\u8c03\u7528\u662f <strong>\u672a\u5b9a\u4e49\u884c\u4e3a<\/strong>\uff1a\u5148 <code>empty()<\/code><\/li>\n\n\n\n<li><code>deque<\/code> \u901a\u5e38 <strong>\u4e0d\u662f\u8fde\u7eed\u5185\u5b58<\/strong>\uff1a\u4e0d\u8981\u628a\u5b83\u5f53\u6570\u7ec4\u6307\u9488\u7528\uff08C++11 \u4e0b\u4e0d\u8981\u4f9d\u8d56 <code>data()<\/code>\uff09<\/li>\n\n\n\n<li>\u4e2d\u95f4 <code>insert\/erase<\/code> \u4ecd\u53ef\u80fd\u662f <strong>O(N)<\/strong>\uff08\u9700\u8981\u79fb\u52a8\u5143\u7d20\uff09<\/li>\n\n\n\n<li>\u8fed\u4ee3\u5668\u5931\u6548\u89c4\u5219\u6bd4 <code>list\/map<\/code> \u66f4\u201c\u654f\u611f\u201d\uff1a\u63d2\u5165\/\u5220\u9664\u53ef\u80fd\u5bfc\u81f4\u90e8\u5206\u8fed\u4ee3\u5668\u5931\u6548\uff08\u4fdd\u5b88\u505a\u6cd5\uff1a\u63d2\u5165\/\u5220\u9664\u540e\u4e0d\u8981\u590d\u7528\u65e7\u8fed\u4ee3\u5668\uff09<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">9) <code>std::list&lt;T><\/code>\uff08\u53cc\u5411\u94fe\u8868\uff09<\/h3>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;list&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u5e95\u5c42\u662f <strong>\u53cc\u5411\u94fe\u8868<\/strong>\uff08\u6bcf\u4e2a\u8282\u70b9\u5b58\u5143\u7d20 + \u524d\u540e\u6307\u9488\uff09<\/li>\n\n\n\n<li><strong>\u4efb\u610f\u4f4d\u7f6e\u63d2\u5165\/\u5220\u9664\u5f88\u5feb<\/strong>\uff1a\u7ed9\u5b9a\u8fed\u4ee3\u5668\u65f6 <strong>O(1)<\/strong><\/li>\n\n\n\n<li><strong>\u4e0d\u652f\u6301\u968f\u673a\u8bbf\u95ee<\/strong>\uff1a\u6ca1\u6709 <code>operator[]<\/code>\uff0c\u4e0d\u80fd <code>it + n<\/code><\/li>\n\n\n\n<li>\u904d\u5386\u8bbf\u95ee\u662f O(N)\uff0ccache \u53cb\u597d\u6027\u8f83\u5dee\uff08\u8282\u70b9\u5206\u6563\uff09<\/li>\n\n\n\n<li>\u8fed\u4ee3\u5668\u5728\u63d2\u5165\u65f6\u901a\u5e38\u7a33\u5b9a\uff08\u5220\u9664\u53ea\u4f1a\u4f7f\u88ab\u5220\u8282\u70b9\u7684\u8fed\u4ee3\u5668\u5931\u6548\uff09<\/li>\n\n\n\n<li>\u9002\u5408\uff1a\u9891\u7e41\u5728\u4e2d\u95f4\u63d2\u5165\/\u5220\u9664\u3001\u9700\u8981\u8fed\u4ee3\u5668\u957f\u671f\u6709\u6548\u7684\u573a\u666f<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::list&lt;int&gt; l1;             \/\/ \u7a7a\nstd::list&lt;int&gt; l2(5);          \/\/ 5 \u4e2a 0\nstd::list&lt;double&gt; l3(6, 0.0);  \/\/ 6 \u4e2a 0.0\nstd::list&lt;int&gt; l4 = {1,2,3};   \/\/ \u5217\u8868\u521d\u59cb\u5316<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u8bbf\u95ee<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.front();     \/\/ \u9996\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09\nl.back();      \/\/ \u5c3e\u5143\u7d20\uff08\u8981\u6c42\u975e\u7a7a\uff09<\/code><\/code><\/pre>\n\n\n\n<p><code>std::list<\/code> \u6ca1\u6709 <code>[]<\/code>\u3001\u6ca1\u6709 <code>at()<\/code>\u3002<\/p>\n\n\n\n<ul>\n<li>\u63d2\u5165 \/ \u5220\u9664\uff08list \u7684\u6838\u5fc3\u4f18\u52bf\uff09<\/li>\n<\/ul>\n\n\n\n<p>\u5934\u5c3e\u63d2\u5165\u5220\u9664<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.push_front(x);\nl.push_back(x);\n\nl.pop_front();\nl.pop_back();<\/code><\/code><\/pre>\n\n\n\n<p>\u4efb\u610f\u4f4d\u7f6e\u63d2\u5165\u5220\u9664\uff08\u7ed9\u5b9a\u8fed\u4ee3\u5668\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>auto it = l.begin();\n++it;                       \/\/ \u6307\u5411\u7b2c\u4e8c\u4e2a\u5143\u7d20\nl.insert(it, 99);           \/\/ \u5728 it \u524d\u63d2\u5165 99\uff08O(1)\uff09\nl.erase(it);                \/\/ \u5220\u9664 it \u6307\u5411\u5143\u7d20\uff08O(1)\uff09\uff0c\u8fd4\u56de\u4e0b\u4e00\u4e2a\u8fed\u4ee3\u5668<\/code><\/code><\/pre>\n\n\n\n<p>\u5220\u9664\u533a\u95f4<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.erase(first, last);       \/\/ \u5220\u9664 &#91;first, last)<\/code><\/code><\/pre>\n\n\n\n<p>\u6309\u503c\u5220\u9664\uff08\u975e\u5e38\u5e38\u7528\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.remove(3);                \/\/ \u5220\u9664\u6240\u6709\u503c\u7b49\u4e8e 3 \u7684\u5143\u7d20\uff08O(N)\uff09<\/code><\/code><\/pre>\n\n\n\n<p>\u6761\u4ef6\u5220\u9664\uff08C++11\uff0clambda\uff09\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.remove_if(&#91;](int x){ return x % 2 == 0; }); \/\/ \u5220\u9664\u6240\u6709\u5076\u6570<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a \/ \u5927\u5c0f<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.clear();\nl.size();\nl.empty();<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u904d\u5386\uff08C++11\uff09<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>for (const auto&amp; x : l) { \/* \u53ea\u8bfb *\/ }\nfor (auto&amp; x : l) { \/* \u53ef\u4fee\u6539 *\/ }\n\nfor (auto it = l.begin(); it != l.end(); ++it) {\n    \/\/ *it\n}<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>list \u4e13\u6709\/\u5e38\u7528\u9ad8\u7ea7\u64cd\u4f5c\uff08\u5f88\u591a\u4eba\u5ffd\u7565\uff0c\u4f46\u5f88\u5f3a\uff09<\/li>\n<\/ul>\n\n\n\n<p><code>splice<\/code>\uff1a\u628a\u53e6\u4e00\u4e2a list \u7684\u8282\u70b9\u201c\u6458\u8fc7\u6765\u201d\uff08\u51e0\u4e4e O(1)\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::list&lt;int&gt; a = {1,2,3};\nstd::list&lt;int&gt; b = {10,20,30};\n\nauto pos = a.begin();\n++pos; \/\/ \u6307\u54112\n\n\/\/ \u628a b \u7684\u6240\u6709\u5143\u7d20\u79fb\u52a8\u5230 a \u7684 pos \u524d\u9762\uff08\u4e0d\u62f7\u8d1d\u5143\u7d20\uff0c\u79fb\u52a8\u8282\u70b9\uff09\na.splice(pos, b);\n\/\/ \u6b64\u540e b \u53d8\u7a7a\uff0ca \u53d8\u4e3a {1,10,20,30,2,3}<\/code><\/code><\/pre>\n\n\n\n<p><code>unique<\/code>\uff1a\u53bb\u6389\u76f8\u90bb\u91cd\u590d\uff08\u53ea\u5904\u7406\u76f8\u90bb\uff01\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::list&lt;int&gt; l = {1,1,2,2,2,3};\nl.unique(); \/\/ \u7ed3\u679c {1,2,3}<\/code><\/code><\/pre>\n\n\n\n<p>\u5982\u679c\u4f60\u8981\u201c\u5168\u5c40\u53bb\u91cd\u201d\uff0c\u901a\u5e38\u5148 <code>sort()<\/code> \u518d <code>unique()<\/code>\u3002<\/p>\n\n\n\n<p><code>sort<\/code>\uff1alist \u81ea\u5e26\u6392\u5e8f\uff08\u56e0\u4e3a\u4e0d\u80fd\u968f\u673a\u8bbf\u95ee\uff0c\u6240\u4ee5\u4e0d\u80fd\u7528 std::sort\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.sort(); \/\/ \u9ed8\u8ba4\u5347\u5e8f<\/code><\/code><\/pre>\n\n\n\n<p>\u81ea\u5b9a\u4e49\u6392\u5e8f\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.sort(&#91;](int a, int b){ return a &gt; b; }); \/\/ \u964d\u5e8f<\/code><\/code><\/pre>\n\n\n\n<p><code>merge<\/code>\uff1a\u5408\u5e76\u4e24\u4e2a\u5df2\u6392\u5e8f list\uff08\u7ecf\u5178 O(N)\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::list&lt;int&gt; a = {1,3,5};\nstd::list&lt;int&gt; b = {2,4,6};\na.merge(b); \/\/ a={1,2,3,4,5,6}, b \u53d8\u7a7a<\/code><\/code><\/pre>\n\n\n\n<p><code>reverse<\/code>\uff1a\u53cd\u8f6c<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>l.reverse();<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u9700\u8981\u9891\u7e41\u4e2d\u95f4\u63d2\u5165\/\u5220\u9664\u7684\u573a\u666f<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;list&gt;\n\nstd::list&lt;int&gt; l = {1,2,3,4};\n\n\/\/ \u627e\u5230\u5143\u7d20 3 \u7684\u4f4d\u7f6e\u540e\u5220\u9664\uff08\u8fed\u4ee3\u5668\u5220\u9664\u662f O(1)\uff09\nfor (auto it = l.begin(); it != l.end(); ++it) {\n    if (*it == 3) {\n        l.erase(it);\n        break;\n    }\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><strong>\u4e0d\u80fd\u968f\u673a\u8bbf\u95ee<\/strong>\uff1a<code>l[i]<\/code>\u3001<code>it + n<\/code> \u90fd\u4e0d\u884c<\/li>\n\n\n\n<li><code>std::sort<\/code> \u4e0d\u80fd\u7528\u4e8e list\uff08\u9700\u8981\u968f\u673a\u8bbf\u95ee\u8fed\u4ee3\u5668\uff09\uff0c\u8981\u7528 <code>l.sort()<\/code><\/li>\n\n\n\n<li><code>front\/back<\/code> \u7a7a list \u8c03\u7528\u662f\u672a\u5b9a\u4e49\u884c\u4e3a\uff1a\u5148 <code>empty()<\/code><\/li>\n\n\n\n<li><code>unique()<\/code> \u53ea\u53bb\u6389 <strong>\u76f8\u90bb\u91cd\u590d<\/strong>\uff0c\u8981\u5168\u5c40\u53bb\u91cd\u901a\u5e38\u8981\u5148\u6392\u5e8f<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\">\u4ec0\u4e48\u65f6\u5019\u9009 <code>list<\/code><\/h5>\n\n\n\n<p>\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9891\u7e41\u5728\u4e2d\u95f4\u63d2\u5165\/\u5220\u9664\uff08\u5e76\u4e14\u4f60\u6301\u6709\u8fed\u4ee3\u5668\u4f4d\u7f6e\uff09<\/li>\n\n\n\n<li>\u9700\u8981 <code>splice\/merge<\/code> \u8fd9\u79cd\u201c\u79fb\u52a8\u8282\u70b9\u4e0d\u62f7\u8d1d\u201d\u7684\u80fd\u529b<\/li>\n\n\n\n<li>\u9700\u8981\u63d2\u5165\/\u5220\u9664\u540e\u8fed\u4ee3\u5668\u5c3d\u91cf\u7a33\u5b9a<\/li>\n<\/ul>\n\n\n\n<p>\u4e0d\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9700\u8981\u5927\u91cf\u968f\u673a\u8bbf\u95ee\u3001\u4e0b\u6807\u8bbf\u95ee \u2192 \u7528 <code>vector\/deque<\/code><\/li>\n\n\n\n<li>\u8ffd\u6c42\u904d\u5386\u6027\u80fd\uff08cache\uff09 \u2192 <code>vector<\/code> \u901a\u5e38\u66f4\u5feb<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">10) \u5bb9\u5668\u9002\u914d\u5668\uff1a<code>stack \/ queue \/ priority_queue<\/code><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\"><code>std::stack&lt;T&gt;<\/code>\uff08\u6808 LIFO\uff0c\u540e\u8fdb\u5148\u51fa\uff09<\/h4>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;stack&gt;<\/code><br><strong>\u53ef\u9009<\/strong>\uff1a\u5982\u679c\u4f60\u6307\u5b9a\u5e95\u5c42\u5bb9\u5668\uff0c\u53ef\u80fd\u8fd8\u9700\u8981 <code>#include &lt;deque&gt;<\/code> \u6216 <code>#include &lt;vector&gt;<\/code> \u6216 <code>#include &lt;list&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li><strong>\u540e\u8fdb\u5148\u51fa\uff08LIFO\uff09<\/strong>\uff1a\u6700\u540e\u5165\u6808\u7684\u6700\u5148\u51fa\u6808<\/li>\n\n\n\n<li>\u662f\u4e00\u4e2a<strong>\u5bb9\u5668\u9002\u914d\u5668<\/strong>\uff08adapter\uff09\uff1a\u5185\u90e8\u7528\u522b\u7684\u5bb9\u5668\u5b9e\u73b0\n<ul>\n<li>\u9ed8\u8ba4\u5e95\u5c42\u5bb9\u5668\uff1a<code>std::deque&lt;T&gt;<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u4e0d\u652f\u6301\u904d\u5386<\/strong>\uff08\u6ca1\u6709 <code>begin()\/end()<\/code>\uff09<\/li>\n\n\n\n<li>\u5e38\u7528\u573a\u666f\uff1a\u62ec\u53f7\u5339\u914d\u3001\u8868\u8fbe\u5f0f\u6c42\u503c\u3001DFS\u3001\u64a4\u9500\/\u56de\u9000\u3001\u51fd\u6570\u8c03\u7528\u6808\u6a21\u578b<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521b\u5efa \/ \u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::stack&lt;int&gt; st;                      \/\/ \u9ed8\u8ba4\u5e95\u5c42 deque&lt;int&gt;\n\n\/\/ \u6307\u5b9a\u5e95\u5c42\u5bb9\u5668\uff08\u53ef\u9009\uff09\uff1a\u4f8b\u5982\u7528 vector \u505a\u5e95\u5c42\nstd::stack&lt;int, std::vector&lt;int&gt; &gt; st2;<\/code>\n\/\/\u5e95\u5c42\u5bb9\u5668\u5fc5\u987b\u652f\u6301\uff1a<span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">push_back \/ pop_back \/ back \/ empty \/ size<\/span><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>1\uff09\u5165\u6808 \/ \u51fa\u6808<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>st.push(x);      \/\/ \u5165\u6808\uff08\u538b\u6808\uff09\nst.pop();        \/\/ \u51fa\u6808\uff08\u5f39\u6808\uff09\u26a0\ufe0f\u4e0d\u8fd4\u56de\u88ab\u5220\u5143\u7d20\n<\/code>\/\/ <span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u4e0d\u4f1a\u8fd4\u56de\u5143\u7d20\uff1b\u8981\u5148 <\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">top()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u53d6\u503c\u518d <\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u3002<\/span><\/code><\/pre>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\u6808\u9876<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>st.top();        \/\/ \u8bbf\u95ee\u6808\u9876\u5143\u7d20\uff08\u6700\u540e\u5165\u6808\u7684\uff09<\/code><\/code><\/pre>\n\n\n\n<p>\u524d\u63d0\uff1a\u6808\u975e\u7a7a\uff0c\u5426\u5219\u672a\u5b9a\u4e49\u884c\u4e3a\u3002\u901a\u5e38\u5148\u5224\u65ad\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>if (!st.empty()) {\n    int x = st.top();\n}<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u5927\u5c0f \/ \u5224\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>st.size();\nst.empty();<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a\uff08stack \u6ca1\u6709 clear\uff09<\/li>\n<\/ul>\n\n\n\n<p><code>std::stack<\/code> <strong>\u6ca1\u6709<\/strong> <code>clear()<\/code> \u6210\u5458\u51fd\u6570\uff0c\u6e05\u7a7a\u65b9\u5f0f\uff1a<\/p>\n\n\n\n<p><strong>\u65b9\u5f0f A\uff1a\u5faa\u73af pop<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>while (!st.empty()) st.pop();<\/code><\/code><\/pre>\n\n\n\n<p><strong>\u65b9\u5f0f B\uff1a\u4e0e\u7a7a\u6808 swap\uff08\u5e38\u7528\u4e14\u5feb\uff09<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::stack&lt;int&gt; empty;\nst.swap(empty);<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u4ea4\u6362<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::stack&lt;int&gt; a, b;\na.swap(b);<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u5178\u578b\u7528\u6cd5\u6a21\u677f\uff08\u53d6\u51fa\u5e76\u5904\u7406\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;stack&gt;\n\nstd::stack&lt;int&gt; st;\nst.push(1);\nst.push(2);\nst.push(3);\n\nwhile (!st.empty()) {\n    int x = st.top();\n    st.pop();\n    \/\/ \u5904\u7406 x\uff08\u8f93\u51fa\u987a\u5e8f\uff1a3,2,1\uff09\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u62ec\u53f7\u5339\u914d\uff08\u7ecf\u5178\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;stack&gt;\n#include &lt;string&gt;\n\nbool isValid(const std::string&amp; s) {\n    std::stack&lt;char&gt; st;\n    for (char c : s) {\n        if (c == '(' || c == '&#91;' || c == '{') st.push(c);\n        else {\n            if (st.empty()) return false;\n            char t = st.top(); st.pop();\n            if ((c == ')' &amp;&amp; t != '(') ||\n                (c == ']' &amp;&amp; t != '&#91;') ||\n                (c == '}' &amp;&amp; t != '{')) return false;\n        }\n    }\n    return st.empty();\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><code>pop()<\/code> <strong>\u4e0d\u8fd4\u56de\u503c<\/strong>\uff1a\u8981\u5148 <code>top()<\/code> \u518d <code>pop()<\/code><\/li>\n\n\n\n<li><code>top()<\/code> \u5728\u7a7a\u6808\u4e0a\u8c03\u7528\u662f <strong>\u672a\u5b9a\u4e49\u884c\u4e3a<\/strong>\uff1a\u5148 <code>empty()<\/code><\/li>\n\n\n\n<li><code>std::stack<\/code> <strong>\u4e0d\u80fd\u904d\u5386<\/strong>\uff1a\u8981\u904d\u5386\u5c31\u7528\u5e95\u5c42\u5bb9\u5668\uff08\u5982 <code>vector\/deque<\/code>\uff09\u81ea\u5df1\u7ba1\u7406<\/li>\n\n\n\n<li><code>std::stack<\/code> <strong>\u6ca1\u6709 <code>clear()<\/code><\/strong>\uff1a\u7528\u5faa\u73af <code>pop<\/code> \u6216 <code>swap<\/code> \u6e05\u7a7a<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\">\u4ec0\u4e48\u65f6\u5019\u9009 <code>stack<\/code><\/h5>\n\n\n\n<p>\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>LIFO \u903b\u8f91\uff08\u56de\u9000\/\u64a4\u9500\u3001DFS\u3001\u89e3\u6790\u5668\u3001\u62ec\u53f7\u5339\u914d\uff09<\/li>\n<\/ul>\n\n\n\n<p>\u4e0d\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9700\u8981\u904d\u5386\u6216\u968f\u673a\u8bbf\u95ee<\/li>\n\n\n\n<li>\u9700\u8981 FIFO \u2192 \u7528 <code>queue<\/code><\/li>\n\n\n\n<li>\u9700\u8981\u6309\u4f18\u5148\u7ea7 \u2192 \u7528 <code>priority_queue<\/code><\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\"><code>std::queue&lt;T&gt;<\/code>\uff08\u961f\u5217 FIFO\uff0c\u5148\u8fdb\u5148\u51fa\uff09<\/h4>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;queue&gt;<\/code><br><strong>\u53ef\u9009<\/strong>\uff1a\u5982\u679c\u8981\u6307\u5b9a\u5e95\u5c42\u5bb9\u5668\uff0c\u53ef\u80fd\u8fd8\u9700\u8981 <code>#include &lt;deque&gt;<\/code> \u6216 <code>#include &lt;list&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li><strong>\u5148\u8fdb\u5148\u51fa\uff08FIFO\uff09<\/strong>\uff1a\u5148\u5165\u961f\u7684\u5148\u51fa\u961f<\/li>\n\n\n\n<li>\u662f\u4e00\u4e2a<strong>\u5bb9\u5668\u9002\u914d\u5668<\/strong>\uff08adapter\uff09\uff1a\u5185\u90e8\u7528\u522b\u7684\u5bb9\u5668\u5b9e\u73b0\uff08\u9ed8\u8ba4 <code>std::deque&lt;T&gt;<\/code>\uff09<\/li>\n\n\n\n<li><strong>\u4e0d\u652f\u6301\u904d\u5386<\/strong>\uff08\u6ca1\u6709 <code>begin()\/end()<\/code>\uff09\uff0c\u53ea\u80fd\u901a\u8fc7\u63a5\u53e3\u64cd\u4f5c\u961f\u9996\/\u961f\u5c3e<\/li>\n\n\n\n<li>\u5e38\u7528\u573a\u666f\uff1aBFS\u3001\u4efb\u52a1\u961f\u5217\u3001\u751f\u4ea7\u8005-\u6d88\u8d39\u8005\u7f13\u51b2\uff08\u5355\u7ebf\u7a0b\u903b\u8f91\uff09<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521b\u5efa \/ \u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::queue&lt;int&gt; q;                 \/\/ \u9ed8\u8ba4\u5e95\u5c42\u5bb9\u5668 deque&lt;int&gt;\n\n\/\/ \u6307\u5b9a\u5e95\u5c42\u5bb9\u5668\uff08\u53ef\u9009\uff09\uff1a\u4f8b\u5982\u7528 list \u4f5c\u4e3a\u5e95\u5c42\nstd::queue&lt;int, std::list&lt;int&gt; &gt; q2;\n<\/code>\n\/\/\u5e95\u5c42\u5bb9\u5668\u5fc5\u987b\u652f\u6301\uff1a<span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">push_back \/ pop_front \/ front \/ back \/ empty \/ size<\/span><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-constrained wp-block-group-is-layout-constrained\">\n<ul>\n<li>\u5165\u961f \/ \u51fa\u961f<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>q.push(x);      \/\/ \u5165\u961f\uff08\u653e\u5230\u961f\u5c3e\uff09\nq.pop();        \/\/ \u51fa\u961f\uff08\u5220\u9664\u961f\u9996\u5143\u7d20\uff09\u26a0\ufe0f\u4e0d\u8fd4\u56de\u88ab\u5220\u5143\u7d20\n<\/code>\/\/ <span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span>\u4e0d\u4f1a\u8fd4\u56de\u5143\u7d20\uff1b\u8981\u5148 <span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">front()<\/span> \u53d6\u503c\u518d <span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span><\/code><\/pre>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\u961f\u9996 \/ \u961f\u5c3e<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>q.front();      \/\/ \u8bbf\u95ee\u961f\u9996\u5143\u7d20\uff08\u6700\u5148\u5165\u961f\u7684\uff09\nq.back();       \/\/ \u8bbf\u95ee\u961f\u5c3e\u5143\u7d20\uff08\u6700\u540e\u5165\u961f\u7684\uff09<\/code><\/code><\/pre>\n\n\n\n<p>\u524d\u63d0\uff1a\u961f\u5217\u975e\u7a7a\uff08\u5426\u5219\u672a\u5b9a\u4e49\u884c\u4e3a\uff09\u3002\u901a\u5e38\u5148\u5224\u65ad\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>if (!q.empty()) {\n    int x = q.front();\n}<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u5927\u5c0f \/ \u5224\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>q.size();       \/\/ \u5143\u7d20\u4e2a\u6570\nq.empty();      \/\/ \u662f\u5426\u4e3a\u7a7a<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a\uff08queue \u6ca1\u6709 clear\uff09<\/li>\n<\/ul>\n\n\n\n<p><code>std::queue<\/code> <strong>\u6ca1\u6709<\/strong> <code>clear()<\/code> \u6210\u5458\u51fd\u6570\u3002\u6e05\u7a7a\u65b9\u5f0f\uff1a<\/p>\n\n\n\n<p><strong>\u65b9\u5f0f A\uff1a\u5faa\u73af pop<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>while (!q.empty()) q.pop();<\/code><\/code><\/pre>\n\n\n\n<p><strong>\u65b9\u5f0f B\uff1a\u4e0e\u7a7a\u961f\u5217 swap\uff08\u5e38\u7528\u4e14\u5feb\uff09<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::queue&lt;int&gt; empty;\nq.swap(empty);<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u4ea4\u6362<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::queue&lt;int&gt; q1, q2;\nq1.swap(q2);<\/code><\/code><\/pre>\n<\/div><\/div>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u5178\u578b\u7528\u6cd5\u6a21\u677f\uff08\u53d6\u51fa\u5e76\u5904\u7406\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n\nstd::queue&lt;int&gt; q;\nq.push(1);\nq.push(2);\nq.push(3);\n\nwhile (!q.empty()) {\n    int x = q.front();\n    q.pop();\n    \/\/ \u5904\u7406 x\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1aBFS\uff08\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff09\u6838\u5fc3\u5199\u6cd5<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n\nstd::queue&lt;int&gt; q;\nq.push(start);\n\nwhile (!q.empty()) {\n    int u = q.front();\n    q.pop();\n\n    \/\/ for (v in neighbors&#91;u]) if (!vis&#91;v]) { vis&#91;v]=true; q.push(v); }\n}<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><code>pop()<\/code> <strong>\u4e0d\u8fd4\u56de\u503c<\/strong>\uff1a\u8981\u5148 <code>front()<\/code> \u518d <code>pop()<\/code><\/li>\n\n\n\n<li><code>front()\/back()<\/code> \u5728\u7a7a\u961f\u5217\u4e0a\u8c03\u7528\u662f <strong>\u672a\u5b9a\u4e49\u884c\u4e3a<\/strong>\uff1a\u5148 <code>empty()<\/code><\/li>\n\n\n\n<li><code>std::queue<\/code> <strong>\u4e0d\u80fd\u904d\u5386<\/strong>\uff1a\u5982\u679c\u4f60\u9700\u8981\u904d\u5386\/\u968f\u673a\u8bbf\u95ee\uff0c\u8003\u8651\u76f4\u63a5\u7528 <code>deque\/vector<\/code><\/li>\n\n\n\n<li><code>std::queue<\/code> <strong>\u6ca1\u6709 <code>clear()<\/code><\/strong>\uff1a\u7528\u5faa\u73af <code>pop<\/code> \u6216 <code>swap<\/code> \u6e05\u7a7a<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\">\u4ec0\u4e48\u65f6\u5019\u9009 <code>queue<\/code><\/h5>\n\n\n\n<p>\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>FIFO \u4efb\u52a1\u5904\u7406<\/li>\n\n\n\n<li>BFS<\/li>\n\n\n\n<li>\u5355\u7ebf\u7a0b\u6216\u7528\u9501\u4fdd\u62a4\u7684\u751f\u4ea7\u8005-\u6d88\u8d39\u8005\u961f\u5217\uff08\u7b80\u5355\u7248\uff09<\/li>\n<\/ul>\n\n\n\n<p>\u4e0d\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9700\u8981\u6309\u5e8f\u904d\u5386\u3001\u968f\u673a\u8bbf\u95ee<\/li>\n\n\n\n<li>\u9700\u8981\u6309\u4f18\u5148\u7ea7\u51fa\u961f\uff08\u7528 <code>priority_queue<\/code>\uff09<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\"><code>std::priority_queue&lt;T&gt;<\/code>\uff08\u4f18\u5148\u961f\u5217\/\u5806\uff09<\/h4>\n\n\n\n<p><strong>\u5934\u6587\u4ef6<\/strong>\uff1a<code>#include &lt;queue&gt;<\/code><br><strong>\u6ce8\u610f<\/strong>\uff1a\u5e38\u7528\u8fd8\u4f1a\u7528\u5230\uff1a<code>#include &lt;vector&gt;<\/code>\u3001<code>#include &lt;functional&gt;<\/code><\/p>\n\n\n\n<h5 class=\"wp-block-heading\">\u7279\u70b9<\/h5>\n\n\n\n<ul>\n<li>\u6bcf\u6b21 <code>top()<\/code> \u62ff\u5230\u7684\u662f\u201c<strong>\u4f18\u5148\u7ea7\u6700\u9ad8<\/strong>\u201d\u7684\u5143\u7d20<\/li>\n\n\n\n<li>\u9ed8\u8ba4\u662f <strong>\u5927\u9876\u5806<\/strong>\uff08\u6700\u5927\u503c\u4f18\u5148\u51fa\uff09<\/li>\n\n\n\n<li>\u662f\u4e00\u4e2a<strong>\u5bb9\u5668\u9002\u914d\u5668<\/strong>\uff1a\u5e95\u5c42\u9ed8\u8ba4 <code>std::vector&lt;T&gt;<\/code><\/li>\n\n\n\n<li><strong>\u4e0d\u652f\u6301\u904d\u5386<\/strong>\uff08\u6ca1\u6709 <code>begin()\/end()<\/code>\uff09\uff0c\u53ea\u80fd\u901a\u8fc7 <code>top\/push\/pop<\/code><\/li>\n\n\n\n<li>\u5e38\u7528\u573a\u666f\uff1aTopK\u3001\u8c03\u5ea6\u5668\u3001Dijkstra\/A*\u3001\u5408\u5e76 K \u4e2a\u6709\u5e8f\u5e8f\u5217\u3001\u4e8b\u4ef6\u6a21\u62df<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">\u521b\u5efa \/ \u521d\u59cb\u5316\uff08C++11\uff09<\/h5>\n\n\n\n<p>1\uff09\u9ed8\u8ba4\uff1a\u5927\u9876\u5806\uff08\u6700\u5927\u5143\u7d20\u5728 top\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n\nstd::priority_queue&lt;int&gt; pq;<\/code><\/code><\/pre>\n\n\n\n<p>2\uff09\u5c0f\u9876\u5806\uff08\u6700\u5c0f\u5143\u7d20\u5728 top\uff0c\u6700\u5e38\u7528\u914d\u7f6e\uff09<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n#include &lt;vector&gt;\n#include &lt;functional&gt;\n\nstd::priority_queue&lt;int, std::vector&lt;int&gt;, std::greater&lt;int&gt; &gt; minpq;<\/code>\n\/\/ \u8bf4\u660e\uff1a\u6a21\u677f\u53c2\u6570\u542b\u4e49\npriority_queue&lt;T, Container, Compare&gt;\n\nContainer \u9ed8\u8ba4 vector&lt;T&gt;\nCompare \u9ed8\u8ba4 std::less&lt;T&gt;\uff08\u56e0\u6b64\u662f\u5927\u9876\u5806\uff09<\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u64cd\u4f5c<\/h5>\n\n\n\n<ul>\n<li>\u63d2\u5165 \/ \u5f39\u51fa<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>pq.push(x);      \/\/ \u63d2\u5165\npq.pop();        \/\/ \u5f39\u51fa\u5806\u9876\uff08\u26a0\ufe0f\u4e0d\u8fd4\u56de\u5143\u7d20\uff09\n<\/code>\/\/ <span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u4e0d\u8fd4\u56de\u503c\uff1a\u8981\u5148 <\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">top()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u518d <\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">pop()<\/span><span style=\"background-color: initial; font-size: inherit; color: inherit; letter-spacing: -0.015em;\">\u3002<\/span><\/code><\/pre>\n\n\n\n<ul>\n<li>\u8bbf\u95ee\u5806\u9876<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>pq.top();        \/\/ \u67e5\u770b\u5806\u9876\u5143\u7d20\uff08\u4f18\u5148\u7ea7\u6700\u9ad8\uff09<\/code><\/code><\/pre>\n\n\n\n<p>\u524d\u63d0\uff1a\u961f\u5217\u975e\u7a7a\uff0c\u5426\u5219\u672a\u5b9a\u4e49\u884c\u4e3a\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>if (!pq.empty()) {\n    int x = pq.top();\n}<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u5927\u5c0f \/ \u5224\u7a7a<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code><code>pq.size();\npq.empty();<\/code><\/code><\/pre>\n\n\n\n<ul>\n<li>\u6e05\u7a7a\uff08priority_queue \u6ca1\u6709 clear\uff09<\/li>\n<\/ul>\n\n\n\n<p><strong>\u65b9\u5f0f A\uff1a\u5faa\u73af pop<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>while (!pq.empty()) pq.pop();<\/code><\/code><\/pre>\n\n\n\n<p><strong>\u65b9\u5f0f B\uff1aswap \u7a7a\u961f\u5217\uff08\u5e38\u7528\u4e14\u5feb\uff09<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>std::priority_queue&lt;int&gt; empty;\npq.swap(empty);<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u5927\u9876\u5806\u57fa\u672c\u7528\u6cd5<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n#include &lt;iostream&gt;\n\nstd::priority_queue&lt;int&gt; pq;\npq.push(3);\npq.push(1);\npq.push(5);\n\nwhile (!pq.empty()) {\n    std::cout &lt;&lt; pq.top() &lt;&lt; \" \";\n    pq.pop();\n}\n\/\/ \u8f93\u51fa\uff1a5 3 1<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1a\u5c0f\u9876\u5806\uff08\u6700\u5c0f\u4f18\u5148\uff09<\/h5>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n#include &lt;vector&gt;\n#include &lt;functional&gt;\n#include &lt;iostream&gt;\n\nstd::priority_queue&lt;int, std::vector&lt;int&gt;, std::greater&lt;int&gt; &gt; pq;\npq.push(3);\npq.push(1);\npq.push(5);\n\nwhile (!pq.empty()) {\n    std::cout &lt;&lt; pq.top() &lt;&lt; \" \";\n    pq.pop();\n}\n\/\/ \u8f93\u51fa\uff1a1 3 5<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u4f8b\u5b50\uff1aTop K \u6700\u5927\u503c\uff08\u7528\u5c0f\u9876\u5806\u66f4\u7701\uff09<\/h5>\n\n\n\n<p>\u601d\u8def\uff1a\u4fdd\u6301\u5806\u5927\u5c0f\u4e3a K\uff0c\u5c0f\u9876\u5806\u91cc\u5b58\u201c\u5f53\u524d\u6700\u5927\u7684 K \u4e2a\u201d\uff0c\u5806\u9876\u662f\u8fd9 K \u4e2a\u91cc\u6700\u5c0f\u7684\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n#include &lt;vector&gt;\n#include &lt;functional&gt;\n\nstd::vector&lt;int&gt; nums = {5, 2, 9, 1, 7, 3};\nint K = 3;\n\nstd::priority_queue&lt;int, std::vector&lt;int&gt;, std::greater&lt;int&gt; &gt; heap;\n\nfor (size_t i = 0; i &lt; nums.size(); ++i) {\n    heap.push(nums&#91;i]);\n    if ((int)heap.size() &gt; K) heap.pop();\n}\n\/\/ heap \u91cc\u5c31\u662f\u6700\u5927\u7684 3 \u4e2a\u6570\uff0cheap.top() \u662f\u8fd9 3 \u4e2a\u91cc\u6700\u5c0f\u7684<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u81ea\u5b9a\u4e49\u6bd4\u8f83\u5668\uff08\u5b58\u7ed3\u6784\u4f53\/\u6309\u67d0\u5b57\u6bb5\u6392\uff09<\/h5>\n\n\n\n<p>\u5047\u8bbe\u8981\u6309 <code>priority<\/code> \u5927\u7684\u4f18\u5148\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>#include &lt;queue&gt;\n#include &lt;vector&gt;\n\nstruct Task {\n    int id;\n    int priority;\n};\n\n\/\/ Compare\uff1a\u8fd4\u56de true \u8868\u793a \u201ca \u7684\u4f18\u5148\u7ea7\u6bd4 b \u4f4e\u201d\uff08\u653e\u5230\u540e\u9762\uff09\n\/\/ \u8fd9\u6837 top() \u5c31\u662f priority \u6700\u5927\u7684\nstruct Cmp {\n    bool operator()(const Task&amp; a, const Task&amp; b) const {\n        return a.priority &lt; b.priority; \/\/ priority \u5927\u7684\u66f4\u9760\u524d\n    }\n};\n\nstd::priority_queue&lt;Task, std::vector&lt;Task&gt;, Cmp&gt; pq;<\/code><\/code><\/pre>\n\n\n\n<p>\u4f7f\u7528\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><code>pq.push(Task{1, 10});\npq.push(Task{2, 5});\nTask t = pq.top(); \/\/ id=1<\/code><\/code><\/pre>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u89c1\u5751<\/h5>\n\n\n\n<ol>\n<li><code>pop()<\/code> <strong>\u4e0d\u8fd4\u56de\u503c<\/strong>\uff1a\u8981\u5148 <code>top()<\/code> \u518d <code>pop()<\/code><\/li>\n\n\n\n<li>\u7a7a\u961f\u5217\u8c03\u7528 <code>top()<\/code> \u662f <strong>\u672a\u5b9a\u4e49\u884c\u4e3a<\/strong>\uff1a\u5148 <code>empty()<\/code><\/li>\n\n\n\n<li><code>priority_queue<\/code> <strong>\u4e0d\u80fd\u904d\u5386<\/strong>\uff1a\u5982\u679c\u4f60\u60f3\u201c\u67e5\u770b\u6240\u6709\u5143\u7d20\u201d\uff0c\u53ea\u80fd\u4e0d\u65ad <code>pop<\/code>\uff08\u4f1a\u7834\u574f\u7ed3\u6784\uff09\uff0c\u6216\u81ea\u5df1\u989d\u5916\u590d\u5236\u4e00\u4efd\u518d pop<\/li>\n\n\n\n<li>\u6bd4\u8f83\u5668\u65b9\u5411\u5bb9\u6613\u5199\u53cd\uff1a\n<ul>\n<li>\u9ed8\u8ba4\u662f\u5927\u9876\u5806<\/li>\n\n\n\n<li>\u5c0f\u9876\u5806\u8981\u7528 <code>std::greater&lt;T&gt;<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u4fee\u6539\u5806\u9876\u5143\u7d20\uff1a\u4e0d\u80fd\u76f4\u63a5\u6539 <code>top()<\/code> \u5bf9\u5e94\u7684\u5e95\u5c42\u503c\uff08\u4f1a\u7834\u574f\u5806\uff09\uff0c\u6b63\u786e\u505a\u6cd5\u662f <code>pop<\/code> \u518d <code>push<\/code> \u65b0\u503c<\/li>\n<\/ol>\n\n\n\n<h5 class=\"wp-block-heading\">\u4ec0\u4e48\u65f6\u5019\u9009 <code>priority_queue<\/code><\/h5>\n\n\n\n<p>\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u603b\u662f\u8981\u62ff\u6700\u5927\/\u6700\u5c0f<\/li>\n\n\n\n<li>TopK<\/li>\n\n\n\n<li>\u6700\u77ed\u8def\uff08Dijkstra\uff1a\u901a\u5e38\u7528\u5c0f\u9876\u5806\uff09<\/li>\n\n\n\n<li>\u4efb\u52a1\u8c03\u5ea6\uff08\u6309\u4f18\u5148\u7ea7\u5904\u7406\uff09<\/li>\n<\/ul>\n\n\n\n<p>\u4e0d\u9002\u5408\uff1a<\/p>\n\n\n\n<ul>\n<li>\u9700\u8981\u6309\u63d2\u5165\u987a\u5e8f FIFO \u2192 \u7528 <code>queue<\/code><\/li>\n\n\n\n<li>\u9700\u8981\u968f\u673a\u8bbf\u95ee\/\u904d\u5386 \u2192 \u7528 <code>vector\/deque<\/code> \u81ea\u5df1\u7ba1\u7406<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h5 class=\"wp-block-heading\">\u5e38\u7528\u7b97\u6cd5\u5934\u6587\u4ef6\uff08\u914d\u5408\u5bb9\u5668\u7ecf\u5e38\u7528\uff09<\/h5>\n\n\n\n<ul>\n<li><code>#include &lt;algorithm&gt;<\/code>\uff1a<code>sort\/find\/copy\/min\/max\/...<\/code><\/li>\n\n\n\n<li><code>#include &lt;numeric&gt;<\/code>\uff1a<code>accumulate<\/code><\/li>\n\n\n\n<li><code>#include &lt;iterator&gt;<\/code>\uff1a<code>std::begin\/std::end<\/code>\uff08C++11\uff09<\/li>\n\n\n\n<li><code>#include &lt;functional&gt;<\/code>\uff1a\u6bd4\u8f83\u5668 <code>std::greater&lt;&gt;<\/code> \u7b49<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">\u590d\u6742\u5ea6\u901f\u67e5\u8868<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th>\u5bb9\u5668<\/th><th>\u67e5\u627e<\/th><th>\u63d2\u5165\/\u5220\u9664<\/th><th>\u4e0b\u6807\u8bbf\u95ee<\/th><th>\u662f\u5426\u6709\u5e8f<\/th><\/tr><\/thead><tbody><tr><td>vector<\/td><td>O(N)<\/td><td>\u672b\u5c3e\u5747\u644aO(1)\uff0c\u4e2d\u95f4O(N)<\/td><td>O(1)<\/td><td>\u5426<\/td><\/tr><tr><td>array<\/td><td>O(N)<\/td><td>\u4e0d\u652f\u6301\u53d8\u957f<\/td><td>O(1)<\/td><td>\u5426<\/td><\/tr><tr><td>deque<\/td><td>O(N)<\/td><td>\u5934\u5c3eO(1)\uff0c\u4e2d\u95f4O(N)<\/td><td>O(1)<\/td><td>\u5426<\/td><\/tr><tr><td>list<\/td><td>O(N)<\/td><td>\u7ed9\u8fed\u4ee3\u5668\u63d2\u5220O(1)<\/td><td>\u4e0d\u652f\u6301<\/td><td>\u5426<\/td><\/tr><tr><td>set\/map<\/td><td>O(logN)<\/td><td>O(logN)<\/td><td>\u4e0d\u652f\u6301\uff08map\u53ef\u7528[]\u6309key\uff09<\/td><td>\u662f<\/td><\/tr><tr><td>unordered_set\/map<\/td><td>\u5e73\u5747O(1)<\/td><td>\u5e73\u5747O(1)<\/td><td>map\u53ef[]<\/td><td>\u5426<\/td><\/tr><tr><td>stack\/queue<\/td><td>&#8211;<\/td><td>push\/pop O(1)<\/td><td>&#8211;<\/td><td>&#8211;<\/td><\/tr><\/tbody><\/table><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>\u5bb9\u5668\u5927\u7c7b \u5171\u540c\u63a5\u53e3\uff08\u5927\u591a\u6570\u90fd\u6709\uff09 1) std::vector&lt;T&gt;\uff08\u52a8\u6001\u6570\u7ec4\uff09 \u5934\u6587\u4ef6\uff1a#inc [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"cybocfi_hide_featured_image":"","footnotes":""},"categories":[45],"tags":[69,70,71],"views":132,"_links":{"self":[{"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/posts\/987"}],"collection":[{"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=987"}],"version-history":[{"count":8,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/posts\/987\/revisions"}],"predecessor-version":[{"id":1032,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=\/wp\/v2\/posts\/987\/revisions\/1032"}],"wp:attachment":[{"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=987"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=987"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.coni.top\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=987"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}