{"id":2123,"date":"2023-02-21T16:33:32","date_gmt":"2023-02-21T08:33:32","guid":{"rendered":"https:\/\/courtship.top\/?p=2123"},"modified":"2023-02-21T16:33:32","modified_gmt":"2023-02-21T08:33:32","slug":"%e6%b8%b8%e6%88%8f%e5%ae%9e%e6%97%b6%e6%8e%92%e8%a1%8c%e6%a6%9c","status":"publish","type":"post","link":"https:\/\/courtship.top\/index.php\/2023\/02\/21\/%e6%b8%b8%e6%88%8f%e5%ae%9e%e6%97%b6%e6%8e%92%e8%a1%8c%e6%a6%9c\/","title":{"rendered":"\u6e38\u620f\u5b9e\u65f6\u6392\u884c\u699c"},"content":{"rendered":"\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>CSDN <a class=\"\" rel=\"noreferrer noopener\" href=\"https:\/\/blog.csdn.net\/zifengzwz\" target=\"_blank\" rel=\"nofollow\" >-Zifeng-<\/a><\/p>\n<\/blockquote>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u8fd9\u91cc\u4f7f\u7528\u6807\u51c6\u5e93\u7684set\u548cunordered_map\u7b80\u5355\u5730\u5b9e\u73b0sorted_set(\u6709\u5e8f\u96c6\u5408)<\/li>\n\n\n\n<li>\u53c2\u4e0e\u6392\u540d\u7684userid\u4e0e\u6392\u540d\u6570\u636e\u4e3a\u4e00\u4e2a\u6574\u4f53\uff0c\u4f5c\u4e3aset\u7684\u5143\u7d20\u548cunordered_map\u7684\u503c\uff0cuserid\u4e3aunordered_map\u7684\u952e<\/li>\n\n\n\n<li>\u5229\u7528set\u7684\u7ea2\u9ed1\u6811\u7ed3\u6784\u8fdb\u884c\u81ea\u6392\u5e8f\uff0cunordered_map\u54c8\u5e0c\u7279\u6027\u8fdb\u884c\u5feb\u901f\u7d22\u5f15<br \/>\u9ed8\u8ba4\u6392\u540d\u4e3a\u524d1000(default_top)<\/li>\n\n\n\n<li>\u901a\u5e38\u6392\u540d\u5728\u5355\u7ebf\u7a0b\u4e2d\u8fdb\u884c\uff0c\u65e0\u9700\u8003\u8651\u591a\u7ebf\u7a0b\u5b89\u5168\uff0c\u7981\u7528\u62f7\u8d1d\u6784\u9020\u548c\u8d4b\u503c\u64cd\u4f5c<\/li>\n\n\n\n<li>\u6dfb\u52a0\u4e86begin\u548cend\u65b9\u6cd5\uff0c\u652f\u6301\u4ece\u5927\u5230\u5c0f\u7684\u8303\u56f4for\u5faa\u73af<br \/><\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>#ifndef SORTED_SET\n#define SORTED_SET\n\n#include &lt;memory>\n#include &lt;set>\n#include &lt;unordered_map>\n\ntemplate &lt;class Key, class T>\nclass sorted_set {\n public:\n  using key_type = Key;\n  using value_type = T;\n  using size_type = std::size_t;\n\n  \/\/ default: care of top 1000\n  static constexpr size_type default_top = 1000;\n\n  struct key_value_type {\n    key_type first;\n    value_type second;\n    key_value_type(const key_type&amp; k, const value_type&amp; v)\n        : first(k), second(v) {}\n  };\n  using key_value_ptr = std::shared_ptr&lt;key_value_type>;\n\n  struct key_value_less {\n    constexpr bool operator()(const key_value_ptr&amp; left,\n                              const key_value_ptr&amp; right) const {\n      if (left->second == right->second) {\n        return left->first &lt; right->first;\n      }\n      return left->second &lt; right->second;\n    }\n  };\n\n  sorted_set() : top_(default_top) {}\n  explicit sorted_set(size_type top) : top_(top == 0 ? default_top : top) {}\n  sorted_set(const sorted_set&amp;) = delete;\n  sorted_set&amp; operator=(const sorted_set&amp;) = delete;\n  ~sorted_set() = default;\n\n  sorted_set(sorted_set&amp;&amp; right)\n      : top_(right.top_),\n        map_(std::move(right.map_)),\n        set_(std::move(right.set_)) {}\n\n  sorted_set&amp; operator=(sorted_set&amp;&amp; right) noexcept {\n    top_ = right.top_;\n    map_ = std::move(right.map_);\n    set_ = std::move(right.set_);\n    return *this;\n  }\n\n  \/\/ ranged-for: large->small\n  auto begin() const { return set_.rbegin(); }\n  auto end() const { return set_.rend(); }\n\n  auto find(key_type k) { return map_.find(k); }\n  auto map_end() { return map_.end(); }\n  auto set_end() { return set_.end(); }\n\n  void insert(const key_type&amp; k, const value_type&amp; v) {\n    auto add = &#91;&amp;] {\n      key_value_ptr ptr = std::make_shared&lt;key_value_type>(k, v);\n      map_.emplace(k, ptr);\n      set_.insert(ptr);\n    };\n\n    auto it = map_.find(k);\n    if (it == map_.end()) {\n      if (set_.size() &lt; top_) {\n        add();\n      } else if (set_.size() == top_) {\n        auto val = v;\n        if (val &lt; (*set_.begin())->second) return;\n        map_.erase((*set_.begin())->first);\n        set_.erase(set_.begin());\n        add();\n      }\n    } else {\n      set_.erase(it->second);\n      map_.erase(it);\n      add();\n    }\n  }\n\n  void erase(const key_type&amp; k) {\n    auto it = map_.find(k);\n    if (it == map_.end()) return;\n    set_.erase(it->second);\n    map_.erase(it);\n  }\n\n  void clear() {\n    set_.clear();\n    map_.clear();\n  }\n\n  size_type size() { return set_.size(); }\n\n  size_type rank(const key_type&amp; k) {\n    auto it = map_.find(k);\n    if (it == map_.end() || set_.empty()) return 0;\n    size_type rank = 0;\n    for (auto n = set_.rbegin(); n != set_.rend(); ++n) {\n      ++rank;\n      if ((*n)->first == k) return rank;\n    }\n    return 0;\n  }\n\n private:\n  size_type top_;\n  std::unordered_map&lt;key_type, key_value_ptr> map_;\n  std::set&lt;key_value_ptr, key_value_less> set_;\n};\n\n#endif<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;chrono>\n#include &lt;cstdint>\n#include &lt;iostream>\n#include &lt;random>\n\n#include \"sorted_set.hpp\"\n\nstruct rank_item {\n  int score{0};\n  int64_t time{0};\n\n  bool operator&lt;(const rank_item&amp; r) {\n    if (score == r.score) {\n      return time > r.time;\n    }\n    return score &lt; r.score;\n  }\n\n  bool operator==(const rank_item&amp; r) {\n    return score == r.score &amp;&amp; time == r.time;\n  }\n};\n\n\/\/ &#91;left, right]\nint rand_num(int left, int right) {\n  static std::default_random_engine gen(std::random_device{}());\n  std::uniform_int_distribution&lt;decltype(right)> dis(left, right);\n  return dis(gen);\n}\n\nint64_t get_time_milli() {\n  auto now = std::chrono::system_clock::now().time_since_epoch();\n  return std::chrono::duration_cast&lt;std::chrono::milliseconds>(now).count();\n}\n\nint main(int argc, char* argv&#91;]) {\n  sorted_set&lt;int, rank_item> rank_info;\n  for (int i = 1; i &lt;= 10; ++i) {\n    rank_info.insert(i, rank_item{rand_num(50, 100), get_time_milli()});\n  }\n  int rank = 1;\n  for (auto&amp; n : rank_info) {\n    std::cout &lt;&lt; \"rank: \" &lt;&lt; rank &lt;&lt; \", userid: \" &lt;&lt; n->first\n              &lt;&lt; \", score: \" &lt;&lt; n->second.score &lt;&lt; std::endl;\n    ++rank;\n  }\n  return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>CSDN -Zifeng-<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"emotion":"","emotion_color":"","title_style":"","license":"","footnotes":""},"categories":[17],"tags":[],"class_list":["post-2123","post","type-post","status-publish","format-standard","hentry","category-17"],"_links":{"self":[{"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/posts\/2123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/comments?post=2123"}],"version-history":[{"count":0,"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/posts\/2123\/revisions"}],"wp:attachment":[{"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/media?parent=2123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/categories?post=2123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/courtship.top\/index.php\/wp-json\/wp\/v2\/tags?post=2123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}