view release on metacpan or  search on metacpan

include/boost/container/slist.hpp  view on Meta::CPAN

   T m_data;

   T &get_data()
   {  return this->m_data;   }

   const T &get_data() const
   {  return this->m_data;   }
};

template <class T, class VoidPointer>
struct iiterator_node_value_type< slist_node<T,VoidPointer> > {
  typedef T type;
};

template<class Allocator>
struct intrusive_slist_type
{
   typedef boost::container::allocator_traits<Allocator>      allocator_traits_type;
   typedef typename allocator_traits_type::value_type value_type;
   typedef typename boost::intrusive::pointer_traits
      <typename allocator_traits_type::pointer>::template
         rebind_pointer<void>::type
            void_pointer;
   typedef typename dtl::slist_node
         <value_type, void_pointer>             node_type;

   typedef typename dtl::bi::make_slist
      <node_type
      ,dtl::bi::base_hook<typename slist_hook<void_pointer>::type>
      ,dtl::bi::constant_time_size<true>
      , dtl::bi::size_type
         <typename allocator_traits_type::size_type>
      >::type                                   container_type;
   typedef container_type                       type ;
};

}  //namespace dtl {

#endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

//! An slist is a singly linked list: a list where each element is linked to the next
//! element, but not to the previous element. That is, it is a Sequence that
//! supports forward but not backward traversal, and (amortized) constant time
//! insertion and removal of elements. Slists, like lists, have the important
//! property that insertion and splicing do not invalidate iterators to list elements,
//! and that even removal invalidates only the iterators that point to the elements
//! that are removed. The ordering of iterators may be changed (that is,
//! slist<T>::iterator might have a different predecessor or successor after a list
//! operation than it did before), but the iterators themselves will not be invalidated
//! or made to point to different elements unless that invalidation or mutation is explicit.
//!
//! The main difference between slist and list is that list's iterators are bidirectional
//! iterators, while slist's iterators are forward iterators. This means that slist is
//! less versatile than list; frequently, however, bidirectional iterators are
//! unnecessary. You should usually use slist unless you actually need the extra
//! functionality of list, because singly linked lists are smaller and faster than double
//! linked lists.
//!
//! Important performance note: like every other Sequence, slist defines the member
//! functions insert and erase. Using these member functions carelessly, however, can
//! result in disastrously slow programs. The problem is that insert's first argument is
//! an iterator p, and that it inserts the new element(s) before p. This means that
//! insert must find the iterator just before p; this is a constant-time operation
//! for list, since list has bidirectional iterators, but for slist it must find that
//! iterator by traversing the list from the beginning up to p. In other words:
//! insert and erase are slow operations anywhere but near the beginning of the slist.
//!
//! Slist provides the member functions insert_after and erase_after, which are constant
//! time operations: you should always use insert_after and erase_after whenever
//! possible. If you find that insert_after and erase_after aren't adequate for your
//! needs, and that you often need to use insert and erase in the middle of the list,
//! then you should probably use list instead of slist.
//!
//! \tparam T The type of object that is stored in the list
//! \tparam Allocator The allocator used for all internal memory management
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
template <class T, class Allocator = new_allocator<T> >
#else
template <class T, class Allocator>
#endif
class slist
   : protected dtl::node_alloc_holder
      <Allocator, typename dtl::intrusive_slist_type<Allocator>::type>
{
   #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
   typedef typename
      dtl::intrusive_slist_type<Allocator>::type           Icont;
   typedef dtl::node_alloc_holder<Allocator, Icont>        AllocHolder;
   typedef typename AllocHolder::NodePtr                    NodePtr;
   typedef typename AllocHolder::NodeAlloc                  NodeAlloc;
   typedef typename AllocHolder::ValAlloc                   ValAlloc;
   typedef typename AllocHolder::Node                       Node;
   typedef dtl::allocator_destroyer<NodeAlloc> Destroyer;
   typedef typename AllocHolder::alloc_version              alloc_version;
   typedef boost::container::
      allocator_traits<Allocator>                           allocator_traits_type;
   typedef boost::container::equal_to_value<Allocator>      equal_to_value_type;

   BOOST_COPYABLE_AND_MOVABLE(slist)
   typedef dtl::iterator_from_iiterator<typename Icont::iterator, false>  iterator_impl;
   typedef dtl::iterator_from_iiterator<typename Icont::iterator, true >  const_iterator_impl;
   #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

   public:
   //////////////////////////////////////////////
   //
   //                    types
   //
   //////////////////////////////////////////////

   typedef T                                                                  value_type;
   typedef typename ::boost::container::allocator_traits<Allocator>::pointer          pointer;
   typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer    const_pointer;
   typedef typename ::boost::container::allocator_traits<Allocator>::reference        reference;
   typedef typename ::boost::container::allocator_traits<Allocator>::const_reference  const_reference;
   typedef typename ::boost::container::allocator_traits<Allocator>::size_type        size_type;
   typedef typename ::boost::container::allocator_traits<Allocator>::difference_type  difference_type;
   typedef Allocator                                                                  allocator_type;
   typedef BOOST_CONTAINER_IMPDEF(NodeAlloc)                                  stored_allocator_type;
   typedef BOOST_CONTAINER_IMPDEF(iterator_impl)                              iterator;