tree.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 1,112 行 · 第 1/3 页

      const_iterator& operator++()       
      { prot_incr();  return *this; }

      const_iterator operator++(int)      
      { iiterator tmp = m_it; ++*this; return const_iterator(tmp);  }

      const_iterator& operator--()
      {   prot_decr(); return *this;   }

      const_iterator operator--(int)
      {  iiterator tmp = m_it; --*this; return const_iterator(tmp); }

      //Comparison operators
      bool operator==   (const const_iterator& r)  const
      {  return m_it == r.m_it;  }

      bool operator!=   (const const_iterator& r)  const
      {  return m_it != r.m_it;  }
   };

   //rbtree iterator
   class iterator : public const_iterator
   {
      private:
      explicit iterator(iiterator it)
         :  const_iterator(it)
      {}
   
      iiterator get()
      {  return this->m_it;   }

      public:
      friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
      typedef rbtree_pointer       pointer;
      typedef rbtree_reference     reference;

      //Constructors
      iterator(){}

      //Pointer like operators
      reference operator*()  const {  return  this->m_it->get_data();  }
      pointer   operator->() const {  return  pointer(&this->m_it->get_data());  }

      //Increment / Decrement
      iterator& operator++()  
         { this->prot_incr(); return *this;  }

      iterator operator++(int)
         { iiterator tmp = this->m_it; ++*this; return iterator(tmp); }
      
      iterator& operator--()
         {  this->prot_decr(); return *this;  }

      iterator operator--(int)
         {  iterator tmp = *this; --*this; return tmp; }
   };

   typedef std::reverse_iterator<iterator>        reverse_iterator;
   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;

   rbtree(const key_compare& comp = key_compare(), 
           const allocator_type& a = allocator_type())
      : AllocHolder(a, comp)
   {}

   template <class InputIterator>
   rbtree(InputIterator first, InputIterator last, const key_compare& comp,
          const allocator_type& a, bool unique_insertion)
      : AllocHolder(a, comp)
   {
      typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
      priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat());
   }

   rbtree(const rbtree& x) 
      :  AllocHolder(x, x.key_comp())
   {
      this->icont().clone_from
         (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   rbtree(const detail::moved_object<rbtree>& x) 
      :  AllocHolder(x.get(), x.get().key_comp())
   {  this->swap(x.get());  }
   #else
   rbtree(rbtree &&x) 
      :  AllocHolder(x, x.key_comp())
   {  this->swap(x);  }
   #endif

   ~rbtree()
   {  this->clear(); }

   rbtree& operator=(const rbtree& x)
   {
      if (this != &x) {
         //Transfer all the nodes to a temporary tree
         //If anything goes wrong, all the nodes will be destroyed
         //automatically
         Icont other_tree(this->icont().value_comp());
         other_tree.swap(this->icont());

         //Now recreate the source tree reusing nodes stored by other_tree
         this->icont().clone_from
            (x.icont()
            , RecyclingCloner(*this, other_tree)
            //, AllocHolder::cloner(*this)
            , Destroyer(this->node_alloc()));

         //If there are remaining nodes, destroy them
         NodePtr p;
         while((p = other_tree.unlink_leftmost_without_rebalance())){
            AllocHolder::destroy_node(p);
         }
      }
      return *this;
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   rbtree& operator=(const detail::moved_object<rbtree>& mx)
   {  this->clear(); this->swap(mx.get());   return *this;  }
   #else
   rbtree& operator=(rbtree &&mx)
   {  this->clear(); this->swap(mx);   return *this;  }
   #endif

   public:    
   // accessors:
   value_compare value_comp() const 
   {  return this->icont().value_comp().value_comp(); }

   key_compare key_comp() const 
   {  return this->icont().value_comp().value_comp().key_comp(); }

   allocator_type get_allocator() const 
   {  return allocator_type(this->node_alloc()); }

   const stored_allocator_type &get_stored_allocator() const 
   {  return this->node_alloc(); }

   stored_allocator_type &get_stored_allocator()
   {  return this->node_alloc(); }

   iterator begin()
   { return iterator(this->icont().begin()); }

   const_iterator begin() const
   {  return this->cbegin();  }

   iterator end()
   {  return iterator(this->icont().end());  }

   const_iterator end() const
   {  return this->cend();  }

   reverse_iterator rbegin()
   {  return reverse_iterator(end());  }

   const_reverse_iterator rbegin() const
   {  return this->crbegin();  }

   reverse_iterator rend()
   {  return reverse_iterator(begin());   }

   const_reverse_iterator rend() const
   {  return this->crend();   }

   //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Constant.
   const_iterator cbegin() const 
   { return const_iterator(this->non_const_icont().begin()); }

   //! <b>Effects</b>: Returns a const_iterator to the end of the container.
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Constant.
   const_iterator cend() const 
   { return const_iterator(this->non_const_icont().end()); }

   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 
   //! of the reversed container. 
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Constant.
   const_reverse_iterator crbegin() const 
   { return const_reverse_iterator(cend()); } 

   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
   //! of the reversed container. 
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Constant.
   const_reverse_iterator crend() const 
   { return const_reverse_iterator(cbegin()); }

   bool empty() const 
   {  return !this->size();  }

   size_type size() const 
   {  return this->icont().size();   }

   size_type max_size() const 
   {  return AllocHolder::max_size();  }

   void swap(ThisType& x)
   {  AllocHolder::swap(x);   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   void swap(const detail::moved_object<rbtree>& mt) 
   {  this->swap(mt.get());   }
   #else
   void swap(rbtree &&mt) 
   {  this->swap(mt);   }
   #endif

   public:

   typedef typename Icont::insert_commit_data insert_commit_data;

   // insert/erase
   std::pair<iterator,bool> insert_unique_check
      (const key_type& key, insert_commit_data &data)
   {
      std::pair<iiterator, bool> ret = 
         this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data);
      return std::pair<iterator, bool>(iterator(ret.first), ret.second);
   }

   std::pair<iterator,bool> insert_unique_check
      (const_iterator hint, const key_type& key, insert_commit_data &data)
   {
      std::pair<iiterator, bool> ret = 
         this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data);
      return std::pair<iterator, bool>(iterator(ret.first), ret.second);
   }

   iterator insert_unique_commit(const value_type& v, insert_commit_data &data)
   {
      NodePtr tmp = AllocHolder::create_node(v);
      iiterator it(this->icont().insert_unique_commit(*tmp, data));
      return iterator(it);
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   template<class MovableConvertible>
   iterator insert_unique_commit
      (const detail::moved_object<MovableConvertible>& mv, insert_commit_data &data)
   {
      NodePtr tmp = AllocHolder::create_node(mv);
      iiterator it(this->icont().insert_unique_commit(*tmp, data));
      return iterator(it);
   }
   #else
   template<class MovableConvertible>
   iterator insert_unique_commit
      (MovableConvertible && mv, insert_commit_data &data)
   {
      NodePtr tmp = AllocHolder::create_node(detail::forward_impl<MovableConvertible>(mv));
      iiterator it(this->icont().insert_unique_commit(*tmp, data));
      return iterator(it);
   }
   #endif

   std::pair<iterator,bool> insert_unique(const value_type& v)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(KeyOfValue()(v), data);
      if(!ret.second)
         return ret;
      return std::pair<iterator,bool>
         (this->insert_unique_commit(v, data), true);
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   template<class MovableConvertible>
   std::pair<iterator,bool> insert_unique
      (const detail::moved_object<MovableConvertible>& mv)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(KeyOfValue()(mv.get()), data);
      if(!ret.second)
         return ret;
      return std::pair<iterator,bool>
         (this->insert_unique_commit(mv, data), true);
   }
   #else
   template<class MovableConvertible>
   std::pair<iterator,bool> insert_unique(MovableConvertible &&mv)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(KeyOfValue()(mv), data);
      if(!ret.second)
         return ret;
      return std::pair<iterator,bool>
         (this->insert_unique_commit(detail::forward_impl<MovableConvertible>(mv), data), true);
   }
   #endif

   private:
   iterator emplace_unique_impl(NodePtr p)
   {
      value_type &v = p->get_data();
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(KeyOfValue()(v), data);
      if(!ret.second){
         Destroyer(this->node_alloc())(p);
         return ret.first;
      }
      return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
   }

   iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
   {
      value_type &v = p->get_data();
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(hint, KeyOfValue()(v), data);
      if(!ret.second){
         Destroyer(this->node_alloc())(p);
         return ret.first;
      }
      return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
   }

   public:

   #ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   template <class... Args>
   iterator emplace_unique(Args&&... args)
   {  return this->emplace_unique_impl(AllocHolder::create_node(detail::forward_impl<Args>(args)...));   }

   template <class... Args>
   iterator emplace_hint_unique(const_iterator hint, Args&&... args)
   {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(detail::forward_impl<Args>(args)...));   }

   template <class... Args>
   iterator emplace_equal(Args&&... args)
   {
      NodePtr p(AllocHolder::create_node(detail::forward_impl<Args>(args)...));
      return iterator(this->icont().insert_equal(this->icont().end(), *p));
   }

   template <class... Args>
   iterator emplace_hint_equal(const_iterator hint, Args&&... args)
   {
      NodePtr p(AllocHolder::create_node(detail::forward_impl<Args>(args)...));
      return iterator(this->icont().insert_equal(hint.get(), *p));
   }

   #else //#ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   iterator emplace_unique()
   {  return this->emplace_unique_impl(AllocHolder::create_node());   }

   iterator emplace_hint_unique(const_iterator hint)
   {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node());   }

   iterator emplace_equal()
   {