slist.hpp

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

   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()).
   //! 
   //! <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 unique()
   {  this->unique(value_equal());  }

   //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 
   //!   elements that satisfy some binary predicate from the list.
   //! 
   //! <b>Throws</b>: If pred throws.
   //! 
   //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons).
   //! 
   //! <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 unique(Pred pred)
   {
      typedef ValueCompareToNodeCompare<Pred> Predicate;
      this->icont().unique_and_dispose(Predicate(pred), Destroyer(this->node_alloc()));
   }

   //! <b>Requires</b>: The lists x and *this must be distinct. 
   //!
   //! <b>Effects</b>: This function removes all of x's elements and inserts them
   //!   in order into *this according to std::less<value_type>. The merge is stable; 
   //!   that is, if an element from *this is equivalent to one from x, then the element 
   //!   from *this will precede the one from x. 
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: This function is linear time: it performs at most
   //!   size() + x.size() - 1 comparisons.
   void merge(slist& x)
   {  this->merge(x, value_less()); }

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

   //! <b>Requires</b>: p must be a comparison function that induces a strict weak
   //!   ordering and both *this and x must be sorted according to that ordering
   //!   The lists x and *this must be distinct. 
   //! 
   //! <b>Effects</b>: This function removes all of x's elements and inserts them
   //!   in order into *this. The merge is stable; that is, if an element from *this is 
   //!   equivalent to one from x, then the element from *this will precede the one from x. 
   //! 
   //! <b>Throws</b>: Nothing.
   //! 
   //! <b>Complexity</b>: This function is linear time: it performs at most
   //!   size() + x.size() - 1 comparisons.
   //! 
   //! <b>Note</b>: Iterators and references to *this are not invalidated.
   template <class StrictWeakOrdering> 
   void merge(slist& x, StrictWeakOrdering comp)
   {
      if((NodeAlloc&)*this == (NodeAlloc&)x){
         this->icont().merge(x.icont(),
            ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
      }
      else{
         throw std::runtime_error("list::merge called with unequal allocators");
      }
   }

   //template <class StrictWeakOrdering> 
   //void merge(const detail::moved_object<slist>& x, StrictWeakOrdering comp)
   //{  this->merge(x.get(), comp);  }

   //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 
   //!   The sort is stable, that is, the relative order of equivalent elements is preserved.
   //! 
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Notes</b>: Iterators and references are not invalidated.
   //! 
   //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
   //!   is the list's size.
   void sort()
   {  this->sort(value_less());  }

   //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 
   //!   The sort is stable, that is, the relative order of equivalent elements is preserved.
   //! 
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Notes</b>: Iterators and references are not invalidated.
   //! 
   //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
   //!   is the list's size.
   template <class StrictWeakOrdering> 
   void sort(StrictWeakOrdering comp)
   {
      // nothing if the slist has length 0 or 1.
      if (this->size() < 2)
         return;
      this->icont().sort(ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
   }

   /// @cond
   private:

   //Iterator range version
   template<class InpIterator>
   void priv_create_and_insert_nodes
      (const_iterator prev, InpIterator beg, InpIterator end)
   {
      typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat;
      priv_create_and_insert_nodes(prev, beg, end, alloc_version(), ItCat());
   }

   template<class InpIterator>
   void priv_create_and_insert_nodes
      (const_iterator prev, InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag)
   {
      for (; beg != end; ++beg){
         this->icont().insert_after(prev.get(), *this->create_node_from_it(beg));
         ++prev;
      }
   }

   template<class InpIterator>
   void priv_create_and_insert_nodes
      (const_iterator prev, InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag)
   {  //Just forward to the default one
      priv_create_and_insert_nodes(prev, beg, end, allocator_v1(), std::input_iterator_tag());
   }

   class insertion_functor;
   friend class insertion_functor;

   class insertion_functor
   {
      Icont &icont_;
      typename Icont::const_iterator prev_;

      public:
      insertion_functor(Icont &icont, typename Icont::const_iterator prev)
         :  icont_(icont), prev_(prev)
      {}

      void operator()(Node &n)
      {  prev_ = this->icont_.insert_after(prev_, n); }
   };

   template<class FwdIterator>
   void priv_create_and_insert_nodes
      (const_iterator prev, FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag)
   {
      //Optimized allocation and construction
      this->allocate_many_and_construct
         (beg, std::distance(beg, end), insertion_functor(this->icont(), prev.get()));
   }

   //Default constructed version
   void priv_create_and_insert_nodes(const_iterator prev, size_type n)
   {
      typedef default_construct_iterator<value_type, difference_type> default_iterator;
      this->priv_create_and_insert_nodes(prev, default_iterator(n), default_iterator());
   }

   //Copy constructed version
   void priv_create_and_insert_nodes(const_iterator prev, size_type n, const T& x)
   {
      typedef constant_iterator<value_type, difference_type> cvalue_iterator;
      this->priv_create_and_insert_nodes(prev, cvalue_iterator(x, n), cvalue_iterator());
   }

   //Dispatch to detect iterator range or integer overloads
   template <class InputIter>
   void priv_insert_dispatch(const_iterator prev,
                             InputIter first, InputIter last,
                             detail::false_)
   {  this->priv_create_and_insert_nodes(prev, first, last);   }

   template<class Integer>
   void priv_insert_dispatch(const_iterator prev, Integer n, Integer x, detail::true_) 
   {  this->priv_create_and_insert_nodes(prev, n, x);  }

   void priv_fill_assign(size_type n, const T& val) 
   {
      iterator end_n(this->end());
      iterator prev(this->before_begin());
      iterator node(this->begin());
      for ( ; node != end_n && n > 0 ; --n){
         *node = val;
         prev = node;
         ++node;
      }
      if (n > 0)
         this->priv_create_and_insert_nodes(prev, n, val);
      else
         this->erase_after(prev, end_n);
   }

   template <class Int>
   void priv_assign_dispatch(Int n, Int val, detail::true_)
   {  this->priv_fill_assign((size_type) n, (T)val); }

   template <class InpIt>
   void priv_assign_dispatch(InpIt first, InpIt last, detail::false_)
   {
      iterator end_n(this->end());
      iterator prev(this->before_begin());
      iterator node(this->begin());
      while (node != end_n && first != last){
         *node = *first;
         prev = node;
         ++node;
         ++first;
      }
      if (first != last)
         this->priv_create_and_insert_nodes(prev, first, last);
      else
         this->erase_after(prev, end_n);
   }

   template <class Int>
   void priv_insert_after_range_dispatch(const_iterator prev_pos, Int n, Int x, detail::true_) 
   {  this->priv_create_and_insert_nodes(prev_pos, n, x);  }

   template <class InIter>
   void priv_insert_after_range_dispatch(const_iterator prev_pos, InIter first, InIter last, detail::false_) 
   {  this->priv_create_and_insert_nodes(prev_pos, first, last); }

   //Functors for member algorithm defaults
   struct value_less
   {
      bool operator()(const value_type &a, const value_type &b) const
         {  return a < b;  }
   };

   struct value_equal
   {
      bool operator()(const value_type &a, const value_type &b) const
         {  return a == b;  }
   };

   struct value_equal_to_this
   {
      explicit value_equal_to_this(const value_type &ref)
         : m_ref(ref){}

      bool operator()(const value_type &val) const
         {  return m_ref == val;  }

      const value_type &m_ref;
   };
   /// @endcond
};

template <class T, class A>
inline bool 
operator==(const slist<T,A>& x, const slist<T,A>& y)
{
   if(x.size() != y.size()){
      return false;
   }
   typedef typename slist<T,A>::const_iterator const_iterator;
   const_iterator end1 = x.end();

   const_iterator i1 = x.begin();
   const_iterator i2 = y.begin();
   while (i1 != end1 && *i1 == *i2){
      ++i1;
      ++i2;
   }
   return i1 == end1;
}

template <class T, class A>
inline bool
operator<(const slist<T,A>& sL1, const slist<T,A>& sL2)
{
   return std::lexicographical_compare
      (sL1.begin(), sL1.end(), sL2.begin(), sL2.end());
}

template <class T, class A>
inline bool 
operator!=(const slist<T,A>& sL1, const slist<T,A>& sL2) 
   {  return !(sL1 == sL2);   }

template <class T, class A>
inline bool 
operator>(const slist<T,A>& sL1, const slist<T,A>& sL2) 
   {  return sL2 < sL1; }

template <class T, class A>
inline bool 
operator<=(const slist<T,A>& sL1, const slist<T,A>& sL2)
   {  return !(sL2 < sL1); }

template <class T, class A>
inline bool 
operator>=(const slist<T,A>& sL1, const slist<T,A>& sL2)
   {  return !(sL1 < sL2); }

#ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
template <class T, class A>
inline void swap(slist<T,A>& x, slist<T,A>& y) 
   {  x.swap(y);  }

template <class T, class A>
inline void swap(const detail::moved_object<slist<T,A> >& x, slist<T,A>& y) 
   {  x.get().swap(y);  }

template <class T, class A>
inline void swap(slist<T,A>& x, const detail::moved_object<slist<T,A> >& y) 
   {  x.swap(y.get());  }
#else
template <class T, class A>
inline void swap(slist<T,A>&&x, slist<T,A>&&y) 
   {  x.swap(y);  }
#endif

/// @cond

//!This class is movable
template <class T, class A>
struct is_movable<slist<T, A> >
{
   enum {   value = true };
};

//!This class is movable
template <class A, class VoidPointer>
struct is_movable<detail::slist_node<A, VoidPointer> >
{
   enum {   value = true };
};

//!This class is movable
/*
template <class A>
struct is_movable<detail::slist_alloc<A> >
{
   enum {   value = true };
};
*/
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
template <class T, class A>
struct has_trivial_destructor_after_move<slist<T, A> >
{
   enum {   value = has_trivial_destructor<A>::value  };
};
/// @endcond

}} //namespace boost{  namespace interprocess{

// Specialization of insert_iterator so that insertions will be constant
// time rather than linear time.

///@cond

//Ummm, I don't like to define things in namespace std, but 
//there is no other way
namespace std {

template <class T, class A>
class insert_iterator<boost::interprocess::slist<T, A> > 
{
 protected:
   typedef boost::interprocess::slist<T, A> Container;
   Container* container;
   typename Container::iterator iter;
   public:
   typedef Container           container_type;
   typedef output_iterator_tag iterator_category;
   typedef void                value_type;
   typedef void                difference_type;
   typedef void                pointer;
   typedef void                reference;

   insert_iterator(Container& x, 
                   typename Container::iterator i, 
                   bool is_previous = false) 
      : container(&x), iter(is_previous ? i : x.previous(i)){ }

   insert_iterator<Container>& 
      operator=(const typename Container::value_type& value) 
   { 
      iter = container->insert_after(iter, value);
      return *this;
   }
   insert_iterator<Container>& operator*(){ return *this; }
   insert_iterator<Container>& operator++(){ return *this; }
   insert_iterator<Container>& operator++(int){ return *this; }
};

}  //namespace std;

///@endcond

#include <boost/interprocess/detail/config_end.hpp>

#endif /* BOOST_INTERPROCESS_SLIST_HPP */