slist.hpp

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

   //! <b>Effects</b>: Inserts an object of type T constructed with
   //!   std::forward<Args>(args)... before p
   //!
   //! <b>Throws</b>: If memory allocation throws or
   //!   T's in-place constructor throws.
   //!
   //! <b>Complexity</b>: Linear to the elements before p
   template <class... Args>
   iterator emplace(const_iterator p, Args&&... args)
   {  return this->emplace_after(this->previous(p), detail::forward_impl<Args>(args)...);  }

   //! <b>Effects</b>: Inserts an object of type T constructed with
   //!   std::forward<Args>(args)... after prev
   //!
   //! <b>Throws</b>: If memory allocation throws or
   //!   T's in-place constructor throws.
   //!
   //! <b>Complexity</b>: Constant
   template <class... Args>
   iterator emplace_after(const_iterator prev, Args&&... args)
   {
      typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator());
      new ((void*)detail::get_pointer(d.get())) Node(detail::forward_impl<Args>(args)...);
      NodePtr node = d.get();
      d.release();
      return iterator(this->icont().insert_after(prev.get(), *node));
   }

   #else //#ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   //0 args
   void emplace_front()
   {  this->emplace_after(this->cbefore_begin());   }

   iterator emplace(const_iterator p)
   {  return this->emplace_after(this->previous(p));  }

   iterator emplace_after(const_iterator prev)
   {
      typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator());
      new ((void*)detail::get_pointer(d.get())) Node();
      NodePtr node = d.get();
      d.release();
      return iterator(this->icont().insert_after(prev.get(), *node));
   }

   #define BOOST_PP_LOCAL_MACRO(n)                                                           \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
   void emplace_front(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))                 \
   {                                                                                         \
      this->emplace                                                                          \
         (this->cbegin(), BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _));         \
   }                                                                                         \
                                                                                             \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
   iterator emplace                                                                          \
      (const_iterator p, BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))              \
   {                                                                                         \
      return this->emplace_after                                                             \
         (this->previous(p), BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _));      \
   }                                                                                         \
                                                                                             \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
   iterator emplace_after                                                                    \
      (const_iterator prev, BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))           \
   {                                                                                         \
      typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator());       \
      new ((void*)detail::get_pointer(d.get()))                                              \
         Node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _));                     \
      NodePtr node = d.get();                                                                \
      d.release();                                                                           \
      return iterator(this->icont().insert_after(prev.get(), *node));                        \
   }                                                                                         \
   //!
   #define BOOST_PP_LOCAL_LIMITS (1, BOOST_INTERPROCESS_MAX_CONSTRUCTOR_PARAMETERS)
   #include BOOST_PP_LOCAL_ITERATE()

   #endif   //#ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   //! <b>Effects</b>: Erases the element after the element pointed by prev_pos
   //!    of the list.
   //!
   //! <b>Returns</b>: the first element remaining beyond the removed elements,
   //!   or end() if no such element exists.
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Constant.
   //! 
   //! <b>Note</b>: Does not invalidate iterators or references to non erased elements.
   iterator erase_after(const_iterator prev_pos)
   {
      return iterator(this->icont().erase_after_and_dispose(prev_pos.get(), Destroyer(this->node_alloc())));
   }

   //! <b>Effects</b>: Erases the range (before_first, last) from
   //!   the list. 
   //!
   //! <b>Returns</b>: the first element remaining beyond the removed elements,
   //!   or end() if no such element exists.
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Linear to the number of erased elements.
   //! 
   //! <b>Note</b>: Does not invalidate iterators or references to non erased elements.
   iterator erase_after(const_iterator before_first, const_iterator last) 
   {
      return iterator(this->icont().erase_after_and_dispose(before_first.get(), last.get(), Destroyer(this->node_alloc())));
   }

   //! <b>Requires</b>: p must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Erases the element at p p.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the number of elements before p.
   iterator erase(const_iterator p) 
   {  return iterator(this->erase_after(previous(p))); }

   //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
   //!
   //! <b>Effects</b>: Erases the elements pointed by [first, last).
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the distance between first and last plus
   //!   linear to the elements before first.
   iterator erase(const_iterator first, const_iterator last)
   {  return iterator(this->erase_after(previous(first), last)); }

   //! <b>Effects</b>: Inserts or erases elements at the end such that
   //!   the size becomes n. New elements are copy constructed from x.
   //!
   //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
   //!
   //! <b>Complexity</b>: Linear to the difference between size() and new_size.
   void resize(size_type new_size, const T& x)
   {
      typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
      while (++(cur_next = cur) != end_n && new_size > 0){
         --new_size;
         cur = cur_next;
      }
      if (cur_next != end_n) 
         this->erase_after(const_iterator(cur), const_iterator(end_n));
      else
         this->insert_after(const_iterator(cur), new_size, x);
   }

   //! <b>Effects</b>: Inserts or erases elements at the end such that
   //!   the size becomes n. New elements are default constructed.
   //!
   //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
   //!
   //! <b>Complexity</b>: Linear to the difference between size() and new_size.
   void resize(size_type new_size)
   {
      typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
      size_type len = this->size();
      size_type left = new_size;
      
      while (++(cur_next = cur) != end_n && left > 0){
         --left;
         cur = cur_next;
      }
      if (cur_next != end_n){
         this->erase_after(const_iterator(cur), const_iterator(end_n));
      }
      else{
         this->priv_create_and_insert_nodes(const_iterator(cur), new_size - len);
      }
   }

   //! <b>Effects</b>: Erases all the elements of the list.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the number of elements in the list.
   void clear() 
   {  this->icont().clear_and_dispose(Destroyer(this->node_alloc()));  }

   //! <b>Requires</b>: p must point to an element contained
   //!   by the list. x != *this
   //!
   //! <b>Effects</b>: Transfers all the elements of list x to this list, after the
   //!   the element pointed by p. No destructors or copy constructors are called.
   //!
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //!
   //! <b>Complexity</b>: Linear to the elements in x.
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
   //!    this list. Iterators of this list and all the references are not invalidated.
   void splice_after(const_iterator prev_pos, slist& x)
   {
      if((NodeAlloc&)*this == (NodeAlloc&)x){
         this->icont().splice_after(prev_pos.get(), x.icont());
      }
      else{
         throw std::runtime_error("slist::splice called with unequal allocators");
      }
   }

   //void splice_after(const_iterator prev_pos, const detail::moved_object<slist>& x)
   //{  this->splice_after(prev_pos, x.get()); }

   // Moves the element that follows prev to *this, inserting it immediately
   //  after p.  This is constant time.

   //! <b>Requires</b>: prev_pos must be a valid iterator of this.
   //!   i must point to an element contained in list x.
   //! 
   //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 
   //!   after the element pointed by prev_pos.
   //!   If prev_pos == prev or prev_pos == ++prev, this function is a null operation. 
   //! 
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //! 
   //! <b>Complexity</b>: Constant.
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
   //!   list. Iterators of this list and all the references are not invalidated.
   void splice_after(const_iterator prev_pos, slist& x, const_iterator prev)
   {
      if((NodeAlloc&)*this == (NodeAlloc&)x){
         this->icont().splice_after(prev_pos.get(), x.icont(), prev.get());
      }
      else{
         throw std::runtime_error("slist::splice called with unequal allocators");
      }
   }

   //void splice_after(const_iterator prev_pos, const detail::moved_object<slist>& x, iterator prev)
   //{  return splice_after(prev_pos, x.get(), prev);   }

   // Moves the range [before_first + 1, before_last + 1) to *this,
   //  inserting it immediately after p.  This is constant time.


   //! <b>Requires</b>: prev_pos must be a valid iterator of this.
   //!   before_first and before_last must be valid iterators of x.
   //!   prev_pos must not be contained in [before_first, before_last) range.
   //! 
   //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1)
   //!   from list x to this list, after the element pointed by prev_pos.
   //! 
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //! 
   //! <b>Complexity</b>: Linear to the number of transferred elements.
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
   //!   list. Iterators of this list and all the references are not invalidated.
   void splice_after(const_iterator prev_pos,      slist& x, 
                     const_iterator before_first,  const_iterator before_last)
   {
      if((NodeAlloc&)*this == (NodeAlloc&)x){
         this->icont().splice_after
            (prev_pos.get(), x.icont(), before_first.get(), before_last.get());
      }
      else{
         throw std::runtime_error("slist::splice called with unequal allocators");
      }
   }

   //void splice_after(const_iterator prev_pos,      const detail::moved_object<slist>& x, 
   //                  const_iterator before_first,  const_iterator before_last)
   //{  this->splice_after(prev_pos, x.get(), before_first, before_last); }

   //! <b>Requires</b>: prev_pos must be a valid iterator of this.
   //!   before_first and before_last must be valid iterators of x.
   //!   prev_pos must not be contained in [before_first, before_last) range.
   //!   n == std::distance(before_first, before_last)
   //! 
   //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1)
   //!   from list x to this list, after the element pointed by prev_pos.
   //! 
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //! 
   //! <b>Complexity</b>: Constant.
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
   //!   list. Iterators of this list and all the references are not invalidated.
   void splice_after(const_iterator prev_pos,      slist& x, 
                     const_iterator before_first,  const_iterator before_last,
                     size_type n)
   {
      if((NodeAlloc&)*this == (NodeAlloc&)x){
         this->icont().splice_after
            (prev_pos.get(), x.icont(), before_first.get(), before_last.get(), n);
      }
      else{
         throw std::runtime_error("slist::splice called with unequal allocators");
      }
   }

   //void splice_after(const_iterator prev_pos,      const detail::moved_object<slist>& x, 
   //                  const_iterator before_first,  const_iterator before_last, size_type n)
   //{  this->splice_after(prev_pos, x.get(), before_first, before_last, n); }

   //! <b>Requires</b>: p must point to an element contained
   //!   by the list. x != *this
   //!
   //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
   //!   the element pointed by p. No destructors or copy constructors are called.
   //!
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //!
   //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size().
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
   //!    this list. Iterators of this list and all the references are not invalidated.
   void splice(const_iterator p, slist& x) 
   {  this->splice_after(this->previous(p), x);  }

   //void splice(const_iterator p, const detail::moved_object<slist>& x) 
   //{  return this->splice(p, x.get());  }

   //! <b>Requires</b>: p must point to an element contained
   //!   by this list. i must point to an element contained in list x.
   //! 
   //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, 
   //!   before the the element pointed by p. No destructors or copy constructors are called.
   //!   If p == i or p == ++i, this function is a null operation. 
   //! 
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //! 
   //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i).
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
   //!   list. Iterators of this list and all the references are not invalidated.
   void splice(const_iterator p, slist& x, const_iterator i) 
   {  this->splice_after(previous(p), x, i);  }

   //void splice(const_iterator p, const detail::moved_object<slist>& x, const_iterator i)
   //{  this->splice(p, x.get(), i);   }

   //! <b>Requires</b>: p must point to an element contained
   //!   by this list. first and last must point to elements contained in list x.
   //! 
   //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, 
   //!   before the the element pointed by p. No destructors or copy constructors are called.
   //! 
   //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
   //!   are not equal.
   //! 
   //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first),
   //!   and in distance(first, last).
   //! 
   //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
   //!   list. Iterators of this list and all the references are not invalidated.
   void splice(const_iterator p, slist& x, const_iterator first, const_iterator last)
   {  this->splice_after(previous(p), x, previous(first), previous(last));  }

   //void splice(const_iterator p, const detail::moved_object<slist>& x, const_iterator first, const_iterator last)
   //{  this->splice(p, x.get(), first, last);  }

   //! <b>Effects</b>: Reverses the order of elements in the list. 
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: This function is linear time.
   //! 
   //! <b>Note</b>: Iterators and references are not invalidated
   void reverse() 
   {  this->icont().reverse();  }

   //! <b>Effects</b>: Removes all the elements that compare equal to value.
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
   //! 
   //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
   //!   and iterators to elements that are not removed remain valid.
   void remove(const T& value)
   {  remove_if(equal_to_value(value));  }

   //! <b>Effects</b>: Removes all the elements for which a specified
   //!   predicate is satisfied.
   //! 
   //! <b>Throws</b>: If pred throws.
   //! 
   //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
   //! 
   //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
   //!   and iterators to elements that are not removed remain valid.
   template <class Pred> 
   void remove_if(Pred pred)
   {
      typedef ValueCompareToNodeCompare<Pred> Predicate;
      this->icont().remove_and_dispose_if(Predicate(pred), Destroyer(this->node_alloc()));
   }

   //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 
   //!   elements that are equal from the list.