Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Map

コードについての説明

Splay Tree ベースの map(連想コンテナ) の実装. stl の std::map は Red Black Tree をベースとして書かれており, 検索, 挿入, 削除などにかかる最悪計算量が O(log n) という強みを持っている.
一方 Splay Tree はならし計算量で O(log n) であるもののクエリ列の確率分布に対して計算量が最適になるように adjust するため, 分布によっては $o(\log n)$ になりうるという強みがある(Red Black Tree の場合の計算量は $\Omega (\log n)$).
以下の実装では std:map ライクな実装をしており, ある程度 std::map と同様に動作する.
実装中でデストラクタなどをコメントアウトしてメモリ解放にかかる時間を節約しているが行儀が悪いのでまあ外してください(ただそれなりに速度変わる).
(追記) C++17 から std::iterator を継承して自作イテレータを構築するのが非推奨化されているので書き直す必要あり. (修正済み)

時間計算量: 各クエリならし $\O (\log n)$

コード

  1. template<class _Key, class _Tp> class MapIterator;
  2.  
  3. template<class _Key, class _Tp> class Map {
  4. private:
  5.     using iterator = MapIterator<_Key, _Tp>;
  6.     using data_type = pair<const _Key, _Tp>;
  7.     struct node {
  8.         data_type _M_data;
  9.         node *_M_left, *_M_right, *_M_parent;
  10.         node(data_type&& data) noexcept
  11.             : _M_data(move(data)), _M_left(nullptr), _M_right(nullptr), _M_parent(nullptr){}
  12.         inline const _Key& get_key() const noexcept { return _M_data.first; }
  13.         inline _Tp& get_data() noexcept { return _M_data.second; }
  14.         inline const _Tp& get_data() const noexcept { return _M_data.second; }
  15.         inline bool isRoot() const noexcept { return !_M_parent; }
  16.         void rotate(const bool right){
  17.             node *p = _M_parent, *g = p->_M_parent;
  18.             if(right){
  19.                 if((p->_M_left = _M_right)) _M_right->_M_parent = p;
  20.                 _M_right = p, p->_M_parent = this;
  21.             }else{
  22.                 if((p->_M_right = _M_left)) _M_left->_M_parent = p;
  23.                 _M_left = p, p->_M_parent = this;
  24.             }
  25.             if(!(_M_parent = g)) return;
  26.             if(g->_M_left == p) g->_M_left = this;
  27.             if(g->_M_right == p) g->_M_right = this;
  28.         }
  29.     };
  30.     friend MapIterator<_Key, _Tp>;
  31.     size_t _M_node_count;
  32.     node *_M_root, *_M_header, *_M_start;
  33.     inline void confirm_header(){
  34.         if(!_M_header){
  35.             data_type new_data;
  36.             _M_root = _M_header = _M_start = new node(move(new_data));
  37.         }
  38.     }
  39.     node *splay(node *u){
  40.         while(!(u->isRoot())){
  41.             node *p = u->_M_parent, *gp = p->_M_parent;
  42.             if(p->isRoot()){
  43.                 u->rotate((u == p->_M_left));
  44.             }else{
  45.                 bool flag = (u == p->_M_left);
  46.                 if((u == p->_M_left) == (p == gp->_M_left)){
  47.                     p->rotate(flag), u->rotate(flag);
  48.                 }else{
  49.                     u->rotate(flag), u->rotate(!flag);
  50.                 }
  51.             }
  52.         }
  53.         return _M_root = u;
  54.     }
  55.     static node *increment(node *ver){
  56.         if(ver->_M_right){
  57.             ver = ver->_M_right;
  58.             while(ver->_M_left) ver = ver->_M_left;
  59.         }else{
  60.             node *nx = ver->_M_parent;
  61.             while(ver == nx->_M_right) ver = nx, nx = nx->_M_parent;
  62.             ver = nx;
  63.         }
  64.         return ver;
  65.     }
  66.     node *join(node *ver1, node *ver2, const node *ver){
  67.         while(ver2->_M_left) ver2 = ver2->_M_left;
  68.         splay(ver2)->_M_left = ver1;
  69.         return ver1 ? (ver1->_M_parent = ver2) : (_M_start = ver2);
  70.     }
  71.     template<typename Key>
  72.     node *_find(Key&& key, bool push = false){
  73.         confirm_header();
  74.         node *cur = nullptr, *nx = _M_root;
  75.         do {
  76.             cur = nx;
  77.             if(cur == _M_header || key < cur->get_key()) nx = cur->_M_left;
  78.             else if(cur->get_key() < key) nx = cur->_M_right;
  79.             else return splay(cur);
  80.         }while(nx);
  81.         if(!push) return _M_header;
  82.         if(cur == _M_header || key < cur->get_key()){
  83.             data_type new_data(forward<Key>(key), _Tp());
  84.             nx = new node(move(new_data));
  85.             cur->_M_left = nx, nx->_M_parent = cur;
  86.             if(cur == _M_start) _M_start = nx;
  87.             return ++_M_node_count, splay(nx);
  88.         }else{
  89.             data_type new_data(forward<Key>(key), _Tp());
  90.             nx = new node(move(new_data));
  91.             cur->_M_right = nx, nx->_M_parent = cur;
  92.             return ++_M_node_count, splay(nx);
  93.         }
  94.     }
  95.     template<typename Data>
  96.     node *_insert(Data&& data){
  97.         confirm_header();
  98.         const _Key& key = data.first;
  99.         node *cur = nullptr, *nx = _M_root;
  100.         do {
  101.             cur = nx;
  102.             if(cur == _M_header || key < cur->get_key()) nx = cur->_M_left;
  103.             else if(cur->get_key() < key) nx = cur->_M_right;
  104.             else return splay(cur);
  105.         }while(nx);
  106.         if(cur == _M_header || key < cur->get_key()){
  107.             data_type new_data = forward<Data>(data);
  108.             nx = new node(move(new_data));
  109.             cur->_M_left = nx, nx->_M_parent = cur;
  110.             if(cur == _M_start) _M_start = nx;
  111.             return ++_M_node_count, splay(nx);
  112.         }else{
  113.             data_type new_data = forward<Data>(data);
  114.             nx = new node(move(new_data));
  115.             cur->_M_right = nx, nx->_M_parent = cur;
  116.             return ++_M_node_count, splay(nx);
  117.         }
  118.     }
  119.     template<typename... Args>
  120.     node *_emplace(Args&&... args){
  121.         return _insert(data_type(forward<Args>(args)...));
  122.     }
  123.     node *_erase(node *root_ver){
  124.         confirm_header();
  125.         assert(root_ver != _M_header);
  126.         if(root_ver->_M_left) root_ver->_M_left->_M_parent = nullptr;
  127.         if(root_ver->_M_right) root_ver->_M_right->_M_parent = nullptr;
  128.         node *res = join(root_ver->_M_left, root_ver->_M_right, root_ver);
  129.         delete root_ver;
  130.         return --_M_node_count, res;
  131.     }
  132.     size_t _erase(const _Key& key){
  133.         node *ver = _find(key);
  134.         if(ver == _M_header){
  135.             return 0;
  136.         }else{
  137.             _erase(ver);
  138.             return 1;
  139.         }
  140.     }
  141.     node *_lower_bound(const _Key& key){
  142.         confirm_header();
  143.         node *cur = nullptr, *nx = _M_root, *res = nullptr;
  144.         do {
  145.             cur = nx;
  146.             if(cur == _M_header){ nx = cur->_M_left; continue; }
  147.             else if(!(cur->get_key() < key)){
  148.                 nx = cur->_M_left;
  149.                 if(!res || !(res->get_key() < cur->get_key())) res = cur;
  150.             }else nx = cur->_M_right;
  151.         }while(nx);
  152.         splay(cur);
  153.         return res ? res : _M_header;
  154.     }
  155.     node *_upper_bound(const _Key& key){
  156.         confirm_header();
  157.         node *cur = nullptr, *nx = _M_root, *res = nullptr;
  158.         do {
  159.             cur = nx;
  160.             if(cur == _M_header){ nx = cur->_M_left; continue; }
  161.             else if(key < cur->get_key()){
  162.                 nx = cur->_M_left;
  163.                 if(!res || !(res->get_key() < cur->get_key())) res = cur;
  164.             }else nx = cur->_M_right;
  165.         }while(nx);
  166.         splay(cur);
  167.         return res ? res : _M_header;
  168.     }
  169.     void clear_dfs(node *cur){
  170.         if(cur->_M_left) clear_dfs(cur->_M_left);
  171.         if(cur->_M_right) clear_dfs(cur->_M_right);
  172.         delete cur;
  173.     }
  174.  
  175. public:
  176.     Map() noexcept : _M_node_count(0), _M_root(nullptr), _M_header(nullptr), _M_start(nullptr){}
  177.     Map(const Map&) = delete;
  178.     Map(Map&& another) : _M_node_count(move(another._M_node_count)){
  179.         _M_root = another._M_root, _M_header = another._M_header, _M_start = another._M_start;
  180.         another._M_root = nullptr, another._M_header = nullptr, another._M_start = nullptr;
  181.     }
  182.     Map& operator=(const Map&) = delete;
  183.     Map& operator=(Map&& another){
  184.         this->~Map();
  185.         _M_node_count = another._M_node_count;
  186.         _M_root = another._M_root, _M_header = another._M_header, _M_start = another._M_start;
  187.         another._M_root = nullptr, another._M_header = nullptr, another._M_start = nullptr;
  188.     }
  189.     // ~Map(){ if(_M_root) clear_dfs(_M_root); }
  190.     friend ostream& operator<< (ostream& os, Map& mp) noexcept {
  191.         for(auto& val : mp) os << '{' << val.first << ',' << val.second << "} ";
  192.         return os;
  193.     }
  194.     _Tp& operator[](const _Key& key){ return _find(key, true)->get_data(); }
  195.     _Tp& operator[](_Key&& key){ return _find(move(key), true)->get_data(); }
  196.     const _Tp& at(const _Key& key){
  197.         node *res = _find(key);
  198.         if(res == _M_header) __throw_out_of_range("Map::at");
  199.         return res->get_data();
  200.     }
  201.     size_t size() const noexcept { return _M_node_count; }
  202.     bool empty() const noexcept { return size() == 0; }
  203.     iterator begin() noexcept { return confirm_header(), iterator(_M_start); }
  204.     iterator end() noexcept { return confirm_header(), iterator(_M_header); }
  205.     void clear(){
  206.         if(_M_root) clear_dfs(_M_root);
  207.         _M_node_count = 0;
  208.         data_type new_data;
  209.         _M_root = _M_header = _M_start = new node(move(new_data));
  210.     }
  211.     iterator find(const _Key& key){ return iterator(_find(key)); }
  212.     iterator insert(const data_type& data){ return iterator(_insert(data)); }
  213.     iterator insert(data_type&& data){ return iterator(_insert(move(data))); }
  214.     template<typename... Args>
  215.     iterator emplace(Args&&... args){ return iterator(_emplace(forward<Args>(args)...)); }
  216.     size_t erase(const _Key& key){ return _erase(key); }
  217.     iterator erase(const iterator& itr){ return iterator(_erase(splay(itr.node_ptr))); }
  218.     iterator lower_bound(const _Key& key){ return iterator(_lower_bound(key)); }
  219.     iterator upper_bound(const _Key& key){ return iterator(_upper_bound(key)); }
  220. };
  221.  
  222. template<class _Key, class _Tp>
  223. class MapIterator {
  224. private:
  225.     friend Map<_Key, _Tp>;
  226.     typename Map<_Key, _Tp>::node *node_ptr;
  227.     using iterator_category = forward_iterator_tag;
  228.     using value_type = pair<const _Key, _Tp>;
  229.     using difference_type = pair<const _Key, _Tp>;
  230.     using pointer = pair<const _Key, _Tp>*;
  231.     using reference = pair<const _Key, _Tp>&;
  232.  
  233. private:
  234.     MapIterator(typename Map<_Key, _Tp>::node *mp) noexcept : node_ptr(mp){}
  235.  
  236. public:
  237.     MapIterator() noexcept : node_ptr(){}
  238.     MapIterator(const MapIterator& itr) noexcept : node_ptr(itr.node_ptr){}
  239.     MapIterator& operator=(const MapIterator& itr) & noexcept { return node_ptr = itr.node_ptr, *this; }
  240.     MapIterator& operator=(const MapIterator&& itr) & noexcept { return node_ptr = itr.node_ptr, *this; }
  241.     reference operator*() const { return node_ptr->_M_data; }
  242.     pointer operator->() const { return &(node_ptr->_M_data); }
  243.     MapIterator& operator++() noexcept { return node_ptr = Map<_Key, _Tp>::increment(node_ptr), *this; }
  244.     MapIterator operator++(int) const noexcept { return MapIterator(Map<_Key, _Tp>::increment(this->node_ptr)); }
  245.     bool operator==(const MapIterator& itr) const noexcept { return !(*this != itr); };
  246.     bool operator!=(const MapIterator& itr) const noexcept { return node_ptr != itr.node_ptr; }
  247. };

verify 用の問題

Codeforces : Mr. Kitayuta, the Treasure Hunter 提出コード(非想定解で std::map だと TLE するが splay 木を用いた自作 map だと通る)
AOJ : Dictionary - Map: Delete 提出コード