{"id":143,"date":"2025-07-08T18:38:03","date_gmt":"2025-07-08T10:38:03","guid":{"rendered":"http:\/\/www.tgwttt.xyz\/?p=143"},"modified":"2025-11-24T16:42:03","modified_gmt":"2025-11-24T08:42:03","slug":"%e7%94%a8%e7%ba%a2%e9%bb%91%e6%a0%91%e6%89%8b%e6%92%95map-set-%e5%8f%8a%e5%85%b6%e8%bf%ad%e4%bb%a3%e5%99%a8%e7%9a%84%e4%bd%bf%e7%94%a8","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=143","title":{"rendered":"\u7528\u7ea2\u9ed1\u6811\u624b\u6495map\/set \u53ca\u5176\u8fed\u4ee3\u5668\u7684\u4f7f\u7528"},"content":{"rendered":"\n

\u672c\u6587\u4ee3\u7801\u5df2\u5728gitee\u4e0a\u5f00\u6e90\u4ee3\u7801\u4ed3\u5e93\u5730\u5740https:\/\/gitee.com\/tgwTTT\/c-lreant<\/a><\/p>\n\n\n\n

\u5b66\u4e60\u4e4b\u524d\u5efa\u8bae\u5148\u9605\u8bfb\u535a\u4e3b\u4ee5\u524d\u7684\u6587\u7ae0http:\/\/www.tgwttt.xyz\/?p=124<\/a><\/p>\n\n\n\n

\u672c\u7bc7\u535a\u5ba2\u662f\u5bf9map\/set\u7684\u5e95\u5c42\u4ee3\u7801\u5b9e\u73b0\uff0cmap\/set\u662fc++\u4e2d\u5e38\u7528\u548c\u91cd\u8981\u7684\u5bb9\u5668\uff0c\u4e8c\u8005\u5e95\u5c42\u5b9e\u73b0\u903b\u8f91\u4e00\u81f4\uff0c\u5747\u4e3a\u7ea2\u9ed1\u6811\uff08\u5982\u4e0b\u56fe\uff09\uff0c\u4ec5\u4ec5\u662fkey\/key-value\u7684\u533a\u522b\u3002<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

map\u548cvalue\u7684\u5e95\u5c42\u4f7f\u7528\u4e86\u76f8\u540c\u7684\u4ee3\u7801\uff0c\u867d\u7136\u6570\u636e\u7c7b\u578b\u4e0d\u4e00\u6837\uff0c\u4f46\u662f\u8fd8\u662f\u6ca1\u6709\u5206\u5f00\u5199\uff0c\u4e0b\u9762\u662f\u4ee3\u7801\u7684\u5b9e\u73b0\u7684\u5206\u6790\u3002<\/p>\n\n\n\n

\u9996\u5148\u4e3a\u4e86\u533a\u5206pair,\u5355\u72ec\u6570\u636e\uff0c\u4ed6\u5f15\u5165\u4e86\u4eff\u51fd\u6570\u53bb\u533a\u5206 map\u51fd\u6570\uff1a<\/p>\n\n\n\n

class map
{
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};<\/p>\n\n\n\n

\u540c\u7406set\u51fd\u6570\u7684\u5b9e\u73b0<\/p>\n\n\n\n

class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
}; \u5c06\u4eff\u51fd\u6570\u4f5c\u4e3a\u53c2\u6570\u4f20\u5165\u7ea2\u9ed1\u6811\u4ee5\u8fbe\u5230\u51fd\u6570\u6570\u636e\u7684\u4e00\u81f4\u6027\u6545\u5e95\u5c42\u7ea2\u9ed1\u6811\u7684\u5b9a\u4e49\u4e3a\uff1a<\/p>\n\n\n\n

template
class RBTree
{
typedef RBTreeNode Node;<\/p>\n\n\n\n

private:
Node* _root = nullptr; }<\/p>\n\n\n\n

\u4e0b\u9762\u53ea\u9700\u8981\u4fee\u6539\u4e00\u4e0b\u63d2\u5165\u51fd\u6570pair Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;<\/p>\n\n\n\n

    \/\/return pair(Iterator(_root, _root), true);\n    return { Iterator(_root, _root), true };\n}\n\nKeyOfT kot;\nNode* parent = nullptr;\nNode* cur = _root;\nwhile (cur)\n{\n    if (kot(cur->_data) < kot(data))\n    {\n        parent = cur;\n        cur = cur->_right;\n    }\n    else if (kot(cur->_data) > kot(data))\n    {\n        parent = cur;\n        cur = cur->_left;\n    }\n    else\n    {\n        return { Iterator(cur, _root), false };\n    }\n}\n\ncur = new Node(data);\nNode* newnode = cur;\ncur->_col = RED;\nif (kot(parent->_data) < kot(data))\n{\n    parent->_right = cur;\n}\nelse\n{\n    parent->_left = cur;\n}\n\/\/ \u94fe\u63a5\u7236\u4eb2\ncur->_parent = parent;\n\n\/\/ \u7236\u4eb2\u662f\u7ea2\u8272\uff0c\u51fa\u73b0\u8fde\u7eed\u7684\u7ea2\u8272\u8282\u70b9\uff0c\u9700\u8981\u5904\u7406\nwhile (parent && parent->_col == RED)\n{\n    Node* grandfather = parent->_parent;\n    if (parent == grandfather->_left)\n    {\n        \/\/   g\n        \/\/ p   u\n        Node* uncle = grandfather->_right;\n        if (uncle && uncle->_col == RED)\n        {\n            \/\/ \u53d8\u8272\n            parent->_col = uncle->_col = BLACK;\n            grandfather->_col = RED;\n\n            \/\/ \u7ee7\u7eed\u5f80\u4e0a\u5904\u7406\n            cur = grandfather;\n            parent = cur->_parent;\n        }\n        else\n        {\n            if (cur == parent->_left)\n            {\n                \/\/     g\n                \/\/   p    u\n                \/\/ c\n                RotateR(grandfather);\n                parent->_col = BLACK;\n                grandfather->_col = RED;\n            }\n            else\n            {\n                \/\/      g\n                \/\/   p    u\n                \/\/     c\n                RotateL(parent);\n                RotateR(grandfather);\n                cur->_col = BLACK;\n                grandfather->_col = RED;\n            }\n\n            break;\n        }\n    }\n    else\n    {\n        \/\/   g\n        \/\/ u   p\n        Node* uncle = grandfather->_left;\n        \/\/ \u53d4\u53d4\u5b58\u5728\u4e14\u4e3a\u7ea2\uff0c-\u300b\u53d8\u8272\u5373\u53ef\n        if (uncle && uncle->_col == RED)\n        {\n            parent->_col = uncle->_col = BLACK;\n            grandfather->_col = RED;\n\n            \/\/ \u7ee7\u7eed\u5f80\u4e0a\u5904\u7406\n            cur = grandfather;\n            parent = cur->_parent;\n        }\n        else \/\/ \u53d4\u53d4\u4e0d\u5b58\u5728\uff0c\u6216\u8005\u5b58\u5728\u4e14\u4e3a\u9ed1\n        {\n            \/\/ \u60c5\u51b5\u4e8c\uff1a\u53d4\u53d4\u4e0d\u5b58\u5728\u6216\u8005\u5b58\u5728\u4e14\u4e3a\u9ed1\n            \/\/ \u65cb\u8f6c+\u53d8\u8272\n            \/\/   g\n            \/\/ u   p\n            \/\/       c\n            if (cur == parent->_right)\n            {\n                RotateL(grandfather);\n                parent->_col = BLACK;\n                grandfather->_col = RED;\n            }\n            else\n            {\n                RotateR(parent);\n                RotateL(grandfather);\n                cur->_col = BLACK;\n                grandfather->_col = RED;\n            }\n\n            break;\n        }\n    }\n}\n\n_root->_col = BLACK;\n\nreturn { Iterator(newnode, _root), true };<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;<\/p>\n\n\n\n
parent->_left = subLR;\nif (subLR)\n    subLR->_parent = parent;\n\nNode* pParent = parent->_parent;\n\nsubL->_right = parent;\nparent->_parent = subL;\n\nif (parent == _root)\n{\n    _root = subL;\n    subL->_parent = nullptr;\n}\nelse\n{\n    if (pParent->_left == parent)\n    {\n        pParent->_left = subL;\n    }\n    else\n    {\n        pParent->_right = subL;\n    }\n\n    subL->_parent = pParent;\n}<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;<\/p>\n\n\n\n
Node* parentParent = parent->_parent;\nsubR->_left = parent;\nparent->_parent = subR;\nif (parentParent == nullptr)\n{\n    _root = subR;\n    subR->_parent = nullptr;\n}\nelse\n{\n    if (parent == parentParent->_left)\n    {\n        parentParent->_left = subR;\n    }\n    else\n    {\n        parentParent->_right = subR;\n    }\n    subR->_parent = parentParent;\n}<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key) { cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}<\/p>\n\n\n\n
return nullptr;<\/code><\/pre>\n\n\n\n
}<\/p>\n\n\n\n
\u5176\u4f59\u4e0e\u4e0a\u7bc7\u6587\u7ae0\u5747\u76f8\u540c\uff0c\u53ea\u9700\u53bb\u66ff\u4ee3key\u7684\u503c\u5373\u53ef<\/p>\n\n\n\n
\u4e0b\u9762\u662f\u8fed\u4ee3\u5668\u7684\u5b9e\u73b0\uff0c\u8fed\u4ee3\u5668\u7684\u5b9e\u73b0\u5f88\u7b80\u5355\u4e3b\u8981\u662f*it++\u65f6\u7684\u5b9e\u73b0\uff0c\u770b\u4e0b\u56fe<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u5f53it\u4e3a\u7a7a\u65f6\u7ed3\u675f\u5faa\u73af                                                                                                                                                           \u6211\u4eec\u67e5\u627e\u65f6\uff0c\u9075\u5faa\u67e5\u627e\u53f3\u5b50\u6811\u6700\u6700\u5de6\u8fb9\u7684\u503c\uff0c\u5982\u67e5\u627e10\u7684\u4e0b\u4e00\u4f4d\u5c31\u662f15                                                                       \u5f53\u53f3\u5b50\u6811\u4e3a\u7a7a\u662f\uff0c\u6211\u4eec\u5c31\u5faa\u73af\u627e\u627e\u5230\u5b69\u5b50\u662f\u7236\u4eb2\u5de6\u8fb9\u7684\u7956\u5148\uff0c\u5982\u67e5\u627e15\u7684\u4e0b\u4e00\u4f4d\u65f6\u5c31\u5fc5\u987b\u5411\u4e0a\u67e5\u627e\u76f4\u5230\u627e\u523018<\/p>\n\n\n\n
\u4e0b\u9762\u662f\u4ee3\u7801\u5b9e\u73b0<\/p>\n\n\n\n
template
struct RBTreeIterator
{
typedef RBTreeNode Node;
typedef RBTreeIterator Self;<\/p>\n\n\n\n
Node* _node;\nNode* _root;\n\n\nRBTreeIterator(Node* node, Node* root)\n    :_node(node)\n    , _root(root)\n{\n}\n\nSelf operator++()\n{\n    if (_node->_right)\n    {\n        \/\/ \u53f3\u4e0d\u4e3a\u7a7a\uff0c\u4e2d\u5e8f\u4e0b\u4e00\u4e2a\u8bbf\u95ee\u7684\u8282\u70b9\u662f\u53f3\u5b50\u6811\u7684\u6700\u5de6(\u6700\u5c0f)\u8282\u70b9\n        Node* min = _node->_right;\n        while (min->_left)\n        {\n            min = min->_left;\n        }\n\n        _node = min;\n    }\n    else\n    {\n        \/\/ \u53f3\u4e3a\u7a7a\uff0c\u7956\u5148\u91cc\u9762\u5b69\u5b50\u662f\u7236\u4eb2\u5de6\u7684\u90a3\u4e2a\u7956\u5148\n        Node* cur = _node;\n        Node* parent = cur->_parent;\n        while (parent && cur == parent->_right)\n        {\n            cur = parent;\n            parent = cur->_parent;\n        }\n\n        _node = parent;\n    }\n\n    return *this;\n}\n\nSelf operator--()\n{\n    if (_node == nullptr)  \/\/ --end()\n    {\n        \/\/ --end()\uff0c\u7279\u6b8a\u5904\u7406\uff0c\u8d70\u5230\u4e2d\u5e8f\u6700\u540e\u4e00\u4e2a\u7ed3\u70b9\uff0c\u6574\u68f5\u6811\u7684\u6700\u53f3\u7ed3\u70b9\n        Node* rightMost = _root;\n        while (rightMost && rightMost->_right)\n        {\n            rightMost = rightMost->_right;\n        }\n        _node = rightMost;\n    }\n    else if (_node->_left)\n    {\n        \/\/ \u5de6\u5b50\u6811\u4e0d\u4e3a\u7a7a\uff0c\u4e2d\u5e8f\u5de6\u5b50\u6811\u6700\u540e\u4e00\u4e2a\n        Node* rightMost = _node->_left;\n        while (rightMost->_right)\n        {\n            rightMost = rightMost->_right;\n        }\n        _node = rightMost;\n    }\n    else\n    {\n        \/\/ \u5b69\u5b50\u662f\u7236\u4eb2\u53f3\u7684\u90a3\u4e2a\u7956\u5148\n        Node* cur = _node;\n        Node* parent = cur->_parent;\n        while (parent && cur == parent->_left)\n        {\n            cur = parent;\n            parent = cur->_parent;\n        }\n        _node = parent;\n    }\n\n    return *this;\n}\n\nRef operator*()\n{\n    return _node->_data;\n}\n\nPtr operator->()\n{\n    return &_node->_data;\n}\n\nbool operator!= (const Self& s) const\n{\n    return _node != s._node;\n}\n\nbool operator== (const Self& s) const\n{\n    return _node == s._node;\n}<\/code><\/pre>\n\n\n\n
};<\/p>\n\n\n\n
\u4eca\u5929\u7684\u66f4\u65b0\u5c31\u5230\u8fd9\u91cc\uff0c\u5982\u6709\u4e0d\u5bf9\uff0c\u70e6\u8bf7\u7559\u8a00\uff0c\u8c22\u8c22\uff01\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"
\u672c\u6587\u4ee3\u7801\u5df2\u5728gitee\u4e0a\u5f00\u6e90\u4ee3\u7801\u4ed3\u5e93\u5730\u5740https:\/\/gitee.com\/tgwTTT\/c-lreant \u5b66…<\/p>\n","protected":false},"author":1,"featured_media":144,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[4],"tags":[],"class_list":["post-143","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/143","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=143"}],"version-history":[{"count":4,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/143\/revisions"}],"predecessor-version":[{"id":879,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/143\/revisions\/879"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/144"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=143"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}