view release on metacpan or  search on metacpan

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

namespace dtl{

template<class D, class S>
BOOST_CONTAINER_FORCEINLINE static D &force(S &s)
{  return *reinterpret_cast<D*>(&s); }

template<class D, class S>
BOOST_CONTAINER_FORCEINLINE static D force_copy(const S &s)
{
   const D *const vp = reinterpret_cast<const D *>(&s);
   D ret_val(*vp);
   return ret_val;
}

}  //namespace dtl{

#endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

//! A flat_map is a kind of associative container that supports unique keys (contains at
//! most one of each key value) and provides for fast retrieval of values of another
//! type T based on the keys.
//!
//! A flat_map satisfies all of the requirements of a container, a reversible
//! container and an associative container. A flat_map also provides
//! most operations described for unique keys. For a
//! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
//! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
//!
//! flat_map is similar to std::map but it's implemented by as an ordered sequence container.
//! The underlying sequence container is by default <i>vector</i> but it can also work
//! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
//!
//! Using vector-like sequence containers means that inserting a new element into a flat_map might invalidate
//! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
//! container that offers stable pointers and references). Similarly, erasing an element might invalidate
//! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
//!
//! This container provides random-access iterators.
//!
//! \tparam Key is the key_type of the map
//! \tparam Value is the <code>mapped_type</code>
//! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
//! \tparam AllocatorOrContainer is either:
//!   - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
//!     (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
//!   - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
//!     sequence container with random-access iterators..
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
#else
template <class Key, class T, class Compare, class AllocatorOrContainer>
#endif
class flat_map
{
   #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
   private:
   BOOST_COPYABLE_AND_MOVABLE(flat_map)
   //This is the tree that we should store if pair was movable
   typedef dtl::flat_tree<
                           std::pair<Key, T>,
                           dtl::select1st<Key>,
                           Compare,
                           AllocatorOrContainer> tree_t;

   //This is the real tree stored here. It's based on a movable pair
   typedef dtl::flat_tree<
                           dtl::pair<Key, T>,
                           dtl::select1st<Key>,
                           Compare,
                           typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
                           > impl_tree_t;
   impl_tree_t m_flat_tree;  // flat tree representing flat_map

   typedef typename impl_tree_t::value_type              impl_value_type;
   typedef typename impl_tree_t::const_iterator          impl_const_iterator;
   typedef typename impl_tree_t::iterator                impl_iterator;
   typedef typename impl_tree_t::allocator_type          impl_allocator_type;
   #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
   typedef std::initializer_list<impl_value_type>        impl_initializer_list;
   #endif

   typedef dtl::flat_tree_value_compare
      < Compare
      , dtl::select1st<Key>
      , std::pair<Key, T> >                              value_compare_t;
   typedef typename tree_t::iterator                     iterator_t;
   typedef typename tree_t::const_iterator               const_iterator_t;
   typedef typename tree_t::reverse_iterator             reverse_iterator_t;
   typedef typename tree_t::const_reverse_iterator       const_reverse_iterator_t;

   public:
   typedef typename impl_tree_t::stored_allocator_type   impl_stored_allocator_type;
   typedef typename impl_tree_t::sequence_type           impl_sequence_type;

   BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
   {  return m_flat_tree;  }

   BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
   {  return m_flat_tree;  }

   private:
   typedef typename tree_t::get_stored_allocator_const_return_t         get_stored_allocator_const_return_t;
   typedef typename tree_t::get_stored_allocator_noconst_return_t       get_stored_allocator_noconst_return_t;
   typedef typename impl_tree_t::get_stored_allocator_const_return_t    impl_get_stored_allocator_const_return_t;
   typedef typename impl_tree_t::get_stored_allocator_noconst_return_t  impl_get_stored_allocator_noconst_return_t;

   #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

   public:

   //////////////////////////////////////////////
   //
   //                    types
   //
   //////////////////////////////////////////////
   typedef Key                                                                      key_type;
   typedef T                                                                        mapped_type;
   typedef Compare                                                                  key_compare;
   typedef std::pair<Key, T>                                                        value_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type)                   sequence_type;
   typedef typename sequence_type::allocator_type                                   allocator_type;
   typedef ::boost::container::allocator_traits<allocator_type>                     allocator_traits_type;
   typedef typename sequence_type::pointer                                          pointer;
   typedef typename sequence_type::const_pointer                                    const_pointer;
   typedef typename sequence_type::reference                                        reference;
   typedef typename sequence_type::const_reference                                  const_reference;
   typedef typename sequence_type::size_type                                        size_type;
   typedef typename sequence_type::difference_type                                  difference_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare)                   value_compare;

   typedef typename sequence_type::iterator                                         iterator;
   typedef typename sequence_type::const_iterator                                   const_iterator;
   typedef typename sequence_type::reverse_iterator                                 reverse_iterator;
   typedef typename sequence_type::const_reverse_iterator                           const_reverse_iterator;
   typedef BOOST_CONTAINER_IMPDEF(impl_value_type)                                  movable_value_type;

   //AllocatorOrContainer::value_type must be std::pair<Key, T>
   BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, typename allocator_type::value_type>::value));

   //////////////////////////////////////////////
   //
   //          construct/copy/destroy
   //

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

#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

}  //namespace container {

//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
template <class Key, class T, class Compare, class AllocatorOrContainer>
struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, AllocatorOrContainer> >
{
   typedef typename ::boost::container::allocator_traits<AllocatorOrContainer>::pointer pointer;
   static const bool value = ::boost::has_trivial_destructor_after_move<AllocatorOrContainer>::value &&
                             ::boost::has_trivial_destructor_after_move<pointer>::value &&
                             ::boost::has_trivial_destructor_after_move<Compare>::value;
};

namespace container {

#endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

//! A flat_multimap is a kind of associative container that supports equivalent keys
//! (possibly containing multiple copies of the same key value) and provides for
//! fast retrieval of values of another type T based on the keys. 
//!
//! A flat_multimap satisfies all of the requirements of a container and of a reversible
//! container and of an associative container. For a
//! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
//! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
//!
//! flat_multimap is similar to std::multimap but it's implemented by as an ordered sequence container.
//! The underlying sequence container is by default <i>vector</i> but it can also work
//! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
//!
//! Using vector-like sequence containers means that inserting a new element into a flat_multimap might invalidate
//! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
//! container that offers stable pointers and references). Similarly, erasing an element might invalidate
//! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
//!
//! This container provides random-access iterators.
//!
//! \tparam Key is the key_type of the map
//! \tparam Value is the <code>mapped_type</code>
//! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
//! \tparam AllocatorOrContainer is either:
//!   - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
//!     (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
//!   - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
//!     sequence container with random-access iterators.
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
#else
template <class Key, class T, class Compare, class AllocatorOrContainer>
#endif
class flat_multimap
{
   #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
   private:
   BOOST_COPYABLE_AND_MOVABLE(flat_multimap)
   typedef dtl::flat_tree<
                           std::pair<Key, T>,
                           dtl::select1st<Key>,
                           Compare,
                           AllocatorOrContainer> tree_t;
   //This is the real tree stored here. It's based on a movable pair
   typedef dtl::flat_tree<
                           dtl::pair<Key, T>,
                           dtl::select1st<Key>,
                           Compare,
                           typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
                           > impl_tree_t;
   impl_tree_t m_flat_tree;  // flat tree representing flat_map

   typedef typename impl_tree_t::value_type              impl_value_type;
   typedef typename impl_tree_t::const_iterator          impl_const_iterator;
   typedef typename impl_tree_t::iterator                impl_iterator;
   typedef typename impl_tree_t::allocator_type          impl_allocator_type;
   #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
   typedef std::initializer_list<impl_value_type>        impl_initializer_list;
   #endif

   typedef dtl::flat_tree_value_compare
      < Compare
      , dtl::select1st<Key>
      , std::pair<Key, T> >                                 value_compare_t;
   typedef typename tree_t::iterator                        iterator_t;
   typedef typename tree_t::const_iterator                  const_iterator_t;
   typedef typename tree_t::reverse_iterator                reverse_iterator_t;
   typedef typename tree_t::const_reverse_iterator          const_reverse_iterator_t;

   public:
   typedef typename impl_tree_t::stored_allocator_type      impl_stored_allocator_type;
   typedef typename impl_tree_t::sequence_type              impl_sequence_type;

   BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
   {  return m_flat_tree;  }

   BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
   {  return m_flat_tree;  }

   private:
   #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

   public:

   //////////////////////////////////////////////
   //
   //                    types
   //
   //////////////////////////////////////////////
   typedef Key                                                                      key_type;
   typedef T                                                                        mapped_type;
   typedef Compare                                                                  key_compare;
   typedef std::pair<Key, T>                                                        value_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type)                   sequence_type;
   typedef typename sequence_type::allocator_type                                   allocator_type;
   typedef ::boost::container::allocator_traits<allocator_type>                     allocator_traits_type;
   typedef typename sequence_type::pointer                                          pointer;
   typedef typename sequence_type::const_pointer                                    const_pointer;
   typedef typename sequence_type::reference                                        reference;
   typedef typename sequence_type::const_reference                                  const_reference;
   typedef typename sequence_type::size_type                                        size_type;
   typedef typename sequence_type::difference_type                                  difference_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
   typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare)                   value_compare;

   typedef typename sequence_type::iterator                                         iterator;
   typedef typename sequence_type::const_iterator                                   const_iterator;
   typedef typename sequence_type::reverse_iterator                                 reverse_iterator;
   typedef typename sequence_type::const_reverse_iterator                           const_reverse_iterator;
   typedef BOOST_CONTAINER_IMPDEF(impl_value_type)                                  movable_value_type;

   //AllocatorOrContainer::value_type must be std::pair<Key, T>
   BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, typename AllocatorOrContainer::value_type>::value));

   //////////////////////////////////////////////
   //
   //          construct/copy/destroy
   //
   //////////////////////////////////////////////

   //! <b>Effects</b>: Default constructs an empty flat_map.
   //!
   //! <b>Complexity</b>: Constant.