Alien-boost-mini
view release on metacpan or search on metacpan
include/boost/container/deque.hpp view on Meta::CPAN
#include <cstddef>
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
#include <initializer_list>
#endif
namespace boost {
namespace container {
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
template <class T, class Allocator>
class deque;
template <class T>
struct deque_value_traits
{
typedef T value_type;
static const bool trivial_dctr = dtl::is_trivially_destructible<value_type>::value;
static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value;
};
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
template<class T>
struct deque_buf_size
{
static const std::size_t min_size = 512u;
static const std::size_t sizeof_t = sizeof(T);
static const std::size_t value = sizeof_t < min_size ? (min_size/sizeof_t) : std::size_t(1);
};
namespace dtl {
// Class invariants:
// For any nonsingular iterator i:
// i.node is the address of an element in the map array. The
// contents of i.node is a pointer to the beginning of a node.
// i.first == //(i.node)
// i.last == i.first + node_size
// i.cur is a pointer in the range [i.first, i.last). NOTE:
// the implication of this is that i.cur is always a dereferenceable
// pointer, even if i is a past-the-end iterator.
// Start and Finish are always nonsingular iterators. NOTE: this means
// that an empty deque must have one node, and that a deque
// with N elements, where N is the buffer size, must have two nodes.
// For every node other than start.node and finish.node, every element
// in the node is an initialized object. If start.node == finish.node,
// then [start.cur, finish.cur) are initialized objects, and
// the elements outside that range are uninitialized storage. Otherwise,
// [start.cur, start.last) and [finish.first, finish.cur) are initialized
// objects, and [start.first, start.cur) and [finish.cur, finish.last)
// are uninitialized storage.
// [map, map + map_size) is a valid, non-empty range.
// [start.node, finish.node] is a valid range contained within
// [map, map + map_size).
// A pointer in the range [map, map + map_size) points to an allocated node
// if and only if the pointer is in the range [start.node, finish.node].
template<class Pointer, bool IsConst>
class deque_iterator
{
public:
typedef std::random_access_iterator_tag iterator_category;
typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
typedef typename if_c
< IsConst
, typename boost::intrusive::pointer_traits<Pointer>::template
rebind_pointer<const value_type>::type
, Pointer
>::type pointer;
typedef typename if_c
< IsConst
, const value_type&
, value_type&
>::type reference;
static std::size_t s_buffer_size()
{ return deque_buf_size<value_type>::value; }
typedef Pointer val_alloc_ptr;
typedef typename boost::intrusive::pointer_traits<Pointer>::
template rebind_pointer<Pointer>::type index_pointer;
Pointer m_cur;
Pointer m_first;
Pointer m_last;
index_pointer m_node;
public:
Pointer get_cur() const { return m_cur; }
Pointer get_first() const { return m_first; }
Pointer get_last() const { return m_last; }
index_pointer get_node() const { return m_node; }
deque_iterator(val_alloc_ptr x, index_pointer y) BOOST_NOEXCEPT_OR_NOTHROW
: m_cur(x), m_first(*y), m_last(*y + s_buffer_size()), m_node(y)
{}
deque_iterator() BOOST_NOEXCEPT_OR_NOTHROW
: m_cur(), m_first(), m_last(), m_node() //Value initialization to achieve "null iterators" (N3644)
{}
deque_iterator(deque_iterator<Pointer, false> const& x) BOOST_NOEXCEPT_OR_NOTHROW
: m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node())
{}
deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_NOEXCEPT_OR_NOTHROW
: m_cur(cur), m_first(first), m_last(last), m_node(node)
{}
deque_iterator<Pointer, false> unconst() const BOOST_NOEXCEPT_OR_NOTHROW
{
return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node());
}
reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
{ return *this->m_cur; }
pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
{ return this->m_cur; }
difference_type operator-(const deque_iterator& x) const BOOST_NOEXCEPT_OR_NOTHROW
{
if(!this->m_cur && !x.m_cur){
return 0;
}
return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
(this->m_cur - this->m_first) + (x.m_last - x.m_cur);
}
deque_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
{
++this->m_cur;
if (this->m_cur == this->m_last) {
this->priv_set_node(this->m_node + 1);
this->m_cur = this->m_first;
}
return *this;
}
deque_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
{
deque_iterator tmp(*this);
++*this;
return tmp;
}
deque_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
include/boost/container/deque.hpp view on Meta::CPAN
difference_type node_offset =
offset > 0 ? offset / difference_type(this->s_buffer_size())
: -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
this->priv_set_node(this->m_node + node_offset);
this->m_cur = this->m_first +
(offset - node_offset * difference_type(this->s_buffer_size()));
}
return *this;
}
deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
{ deque_iterator tmp(*this); return tmp += n; }
deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW
{ return *this += -n; }
deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
{ deque_iterator tmp(*this); return tmp -= n; }
reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW
{ return *(*this + n); }
friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return l.m_cur == r.m_cur; }
friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return l.m_cur != r.m_cur; }
friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); }
friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return r < l; }
friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return !(r < l); }
friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
{ return !(l < r); }
void priv_set_node(index_pointer new_node) BOOST_NOEXCEPT_OR_NOTHROW
{
this->m_node = new_node;
this->m_first = *new_node;
this->m_last = this->m_first + this->s_buffer_size();
}
friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW
{ return x += n; }
};
} //namespace dtl {
// Deque base class. It has two purposes. First, its constructor
// and destructor allocate (but don't initialize) storage. This makes
// exception safety easier.
template <class Allocator>
class deque_base
{
BOOST_COPYABLE_AND_MOVABLE(deque_base)
public:
typedef allocator_traits<Allocator> val_alloc_traits_type;
typedef typename val_alloc_traits_type::value_type val_alloc_val;
typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
typedef typename val_alloc_traits_type::reference val_alloc_ref;
typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
typedef typename val_alloc_traits_type::size_type val_alloc_size;
typedef typename val_alloc_traits_type::template
portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
typedef Allocator allocator_type;
typedef allocator_type stored_allocator_type;
typedef val_alloc_size size_type;
protected:
typedef deque_value_traits<val_alloc_val> traits_t;
typedef ptr_alloc_t map_allocator_type;
static size_type s_buffer_size() BOOST_NOEXCEPT_OR_NOTHROW
{ return deque_buf_size<val_alloc_val>::value; }
val_alloc_ptr priv_allocate_node()
{ return this->alloc().allocate(s_buffer_size()); }
void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
{ this->alloc().deallocate(p, s_buffer_size()); }
ptr_alloc_ptr priv_allocate_map(size_type n)
{ return this->ptr_alloc().allocate(n); }
void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW
{ this->ptr_alloc().deallocate(p, n); }
typedef dtl::deque_iterator<val_alloc_ptr, false> iterator;
typedef dtl::deque_iterator<val_alloc_ptr, true > const_iterator;
deque_base(size_type num_elements, const allocator_type& a)
: members_(a)
{ this->priv_initialize_map(num_elements); }
explicit deque_base(const allocator_type& a)
: members_(a)
{}
deque_base()
: members_()
{}
explicit deque_base(BOOST_RV_REF(deque_base) x)
: members_( boost::move(x.ptr_alloc())
, boost::move(x.alloc()) )
{}
include/boost/container/deque.hpp view on Meta::CPAN
this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size);
ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2;
ptr_alloc_ptr nfinish = nstart + num_nodes;
BOOST_TRY {
this->priv_create_nodes(nstart, nfinish);
}
BOOST_CATCH(...){
this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
this->members_.m_map = 0;
this->members_.m_map_size = 0;
BOOST_RETHROW
}
BOOST_CATCH_END
this->members_.m_start.priv_set_node(nstart);
this->members_.m_finish.priv_set_node(nfinish - 1);
this->members_.m_start.m_cur = this->members_.m_start.m_first;
this->members_.m_finish.m_cur = this->members_.m_finish.m_first +
num_elements % s_buffer_size();
// }
}
void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
{
ptr_alloc_ptr cur = nstart;
BOOST_TRY {
for (; cur < nfinish; ++cur)
*cur = this->priv_allocate_node();
}
BOOST_CATCH(...){
this->priv_destroy_nodes(nstart, cur);
BOOST_RETHROW
}
BOOST_CATCH_END
}
void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW
{
for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
this->priv_deallocate_node(*n);
}
void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW
{
if (this->members_.m_map) {
this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size);
this->members_.m_map = 0;
this->members_.m_map_size = 0;
this->members_.m_start = iterator();
this->members_.m_finish = this->members_.m_start;
}
}
enum { InitialMapSize = 8 };
protected:
struct members_holder
: public ptr_alloc_t
, public allocator_type
{
members_holder()
: map_allocator_type(), allocator_type()
, m_map(0), m_map_size(0)
, m_start(), m_finish(m_start)
{}
explicit members_holder(const allocator_type &a)
: map_allocator_type(a), allocator_type(a)
, m_map(0), m_map_size(0)
, m_start(), m_finish(m_start)
{}
template<class ValAllocConvertible, class PtrAllocConvertible>
members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va)
: map_allocator_type(boost::forward<PtrAllocConvertible>(pa))
, allocator_type (boost::forward<ValAllocConvertible>(va))
, m_map(0), m_map_size(0)
, m_start(), m_finish(m_start)
{}
ptr_alloc_ptr m_map;
val_alloc_size m_map_size;
iterator m_start;
iterator m_finish;
} members_;
ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW
{ return members_; }
const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW
{ return members_; }
allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW
{ return members_; }
const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
{ return members_; }
};
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
//! A double-ended queue is a sequence that supports random access to elements, constant time insertion
//! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
//!
//! \tparam T The type of object that is stored in the deque
//! \tparam Allocator The allocator used for all internal memory management
template <class T, class Allocator = new_allocator<T> >
#else
template <class T, class Allocator>
#endif
class deque : protected deque_base<Allocator>
{
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
private:
typedef deque_base<Allocator> Base;
#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(allocator_type) stored_allocator_type;
typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator;
typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator;
typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
private: // Internal typedefs
BOOST_COPYABLE_AND_MOVABLE(deque)
typedef typename Base::ptr_alloc_ptr index_pointer;
static size_type s_buffer_size()
{ return Base::s_buffer_size(); }
typedef allocator_traits<Allocator> allocator_traits_type;
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
public:
//////////////////////////////////////////////
//
// construct/copy/destroy
//
//////////////////////////////////////////////
//! <b>Effects</b>: Default constructors a deque.
//!
//! <b>Throws</b>: If allocator_type's default constructor throws.
//!
//! <b>Complexity</b>: Constant.
deque() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value)
: Base()
{}
//! <b>Effects</b>: Constructs a deque taking the allocator as parameter.
//!
//! <b>Throws</b>: Nothing
//!
//! <b>Complexity</b>: Constant.
explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
: Base(a)
{}
//! <b>Effects</b>: Constructs a deque
//! and inserts n value initialized values.
//!
//! <b>Throws</b>: If allocator_type's default constructor
//! throws or T's value initialization throws.
//!
//! <b>Complexity</b>: Linear to n.
explicit deque(size_type n)
: Base(n, allocator_type())
{
dtl::insert_value_initialized_n_proxy<Allocator, iterator> proxy;
proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
//deque_base will deallocate in case of exception...
}
//! <b>Effects</b>: Constructs a deque
//! and inserts n default initialized values.
//!
//! <b>Throws</b>: If allocator_type's default constructor
//! throws or T's default initialization or copy constructor throws.
//!
//! <b>Complexity</b>: Linear to n.
//!
//! <b>Note</b>: Non-standard extension
deque(size_type n, default_init_t)
: Base(n, allocator_type())
{
dtl::insert_default_initialized_n_proxy<Allocator, iterator> proxy;
proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n);
//deque_base will deallocate in case of exception...
}
//! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
//! and inserts n value initialized values.
//!
//! <b>Throws</b>: If allocator_type's default constructor
( run in 0.810 second using v1.01-cache-2.11-cpan-cdf2f3d4e48 )