//////////////////////////////////////////////////////////////////////////////

//

// (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost

// Software License, Version 1.0. (See accompanying file

// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

//

// See http://www.boost.org/libs/container for documentation.

//

//////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP

#define BOOST_CONTAINER_CONTAINER_VECTOR_HPP

#ifndef BOOST_CONFIG_HPP

# include <boost/config.hpp>

#endif

#if defined(BOOST_HAS_PRAGMA_ONCE)

# pragma once

#endif

#include <boost/container/detail/config_begin.hpp>

#include <boost/container/detail/workaround.hpp>

// container

#include <boost/container/container_fwd.hpp>

#include <boost/container/allocator_traits.hpp>

#include <boost/container/new_allocator.hpp> //new_allocator

#include <boost/container/throw_exception.hpp>

#include <boost/container/options.hpp>

// container detail

#include <boost/container/detail/advanced_insert_int.hpp>

#include <boost/container/detail/algorithm.hpp> //equal()

#include <boost/container/detail/alloc_helpers.hpp>

#include <boost/container/detail/allocation_type.hpp>

#include <boost/container/detail/copy_move_algo.hpp>

#include <boost/container/detail/destroyers.hpp>

#include <boost/container/detail/iterator.hpp>

#include <boost/container/detail/iterators.hpp>

#include <boost/move/detail/iterator_to_raw_pointer.hpp>

#include <boost/container/detail/mpl.hpp>

#include <boost/container/detail/next_capacity.hpp>

#include <boost/container/detail/value_functors.hpp>

#include <boost/move/detail/to_raw_pointer.hpp>

#include <boost/container/detail/type_traits.hpp>

#include <boost/container/detail/version_type.hpp>

// intrusive

#include <boost/intrusive/pointer_traits.hpp>

// move

#include <boost/move/adl_move_swap.hpp>

#include <boost/move/iterator.hpp>

#include <boost/move/traits.hpp>

#include <boost/move/utility_core.hpp>

// move/detail

#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)

#include <boost/move/detail/fwd_macros.hpp>

#endif

#include <boost/move/detail/move_helpers.hpp>

// move/algo

#include <boost/move/algo/adaptive_merge.hpp>

#include <boost/move/algo/unique.hpp>

#include <boost/move/algo/predicate.hpp>

#include <boost/move/algo/detail/set_difference.hpp>

// other

#include <boost/core/no_exceptions_support.hpp>

#include <boost/assert.hpp>

#include <boost/cstdint.hpp>

//std

#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)

#include <initializer_list> //for std::initializer_list

#endif

namespace boost {

namespace container {

#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

template <class Pointer, bool IsConst>

class vec_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 dtl::if_c

< IsConst

, typename boost::intrusive::pointer_traits<Pointer>::template

rebind_pointer<const value_type>::type

, Pointer

>::type pointer;

typedef typename boost::intrusive::pointer_traits<pointer> ptr_traits;

typedef typename ptr_traits::reference reference;

#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

private:

Pointer m_ptr;

class nat

{

public:

Pointer get_ptr() const

{ return Pointer(); }

};

typedef typename dtl::if_c< IsConst

, vec_iterator<Pointer, false>

, nat>::type nonconst_iterator;

public:

BOOST_CONTAINER_FORCEINLINE const Pointer &get_ptr() const BOOST_NOEXCEPT_OR_NOTHROW

{ return m_ptr; }

BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr() BOOST_NOEXCEPT_OR_NOTHROW

{ return m_ptr; }

BOOST_CONTAINER_FORCEINLINE explicit vec_iterator(Pointer ptr) BOOST_NOEXCEPT_OR_NOTHROW

: m_ptr(ptr)

{}

#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

public:

//Constructors

BOOST_CONTAINER_FORCEINLINE vec_iterator() BOOST_NOEXCEPT_OR_NOTHROW

: m_ptr() //Value initialization to achieve "null iterators" (N3644)

{}

BOOST_CONTAINER_FORCEINLINE vec_iterator(const vec_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW

: m_ptr(other.get_ptr())

{}

BOOST_CONTAINER_FORCEINLINE vec_iterator(const nonconst_iterator &other) BOOST_NOEXCEPT_OR_NOTHROW

: m_ptr(other.get_ptr())

{}

BOOST_CONTAINER_FORCEINLINE vec_iterator & operator=(const vec_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW

{ m_ptr = other.get_ptr(); return *this; }

//Pointer like operators

BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); return *m_ptr; }

BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW

{ return m_ptr; }

BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); return m_ptr[off]; }

//Increment / Decrement

BOOST_CONTAINER_FORCEINLINE vec_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); ++m_ptr; return *this; }

BOOST_CONTAINER_FORCEINLINE vec_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); return vec_iterator(m_ptr++); }

BOOST_CONTAINER_FORCEINLINE vec_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); --m_ptr; return *this; }

BOOST_CONTAINER_FORCEINLINE vec_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(!!m_ptr); return vec_iterator(m_ptr--); }

//Arithmetic

BOOST_CONTAINER_FORCEINLINE vec_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(m_ptr || !off); m_ptr += off; return *this; }

BOOST_CONTAINER_FORCEINLINE vec_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(m_ptr || !off); m_ptr -= off; return *this; }

BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(const vec_iterator &x, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(x.m_ptr || !off); return vec_iterator(x.m_ptr+off); }

BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(right.m_ptr || !off); right.m_ptr += off; return right; }

BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT(left.m_ptr || !off); left.m_ptr -= off; return left; }

BOOST_CONTAINER_FORCEINLINE friend difference_type operator-(const vec_iterator &left, const vec_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW

{ return left.m_ptr - right.m_ptr; }

//Comparison operators

BOOST_CONTAINER_FORCEINLINE friend bool operator== (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr == r.m_ptr; }

BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr != r.m_ptr; }

BOOST_CONTAINER_FORCEINLINE friend bool operator< (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr < r.m_ptr; }

BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr <= r.m_ptr; }

BOOST_CONTAINER_FORCEINLINE friend bool operator> (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr > r.m_ptr; }

BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW

{ return l.m_ptr >= r.m_ptr; }

};

template<class BiDirPosConstIt, class BiDirValueIt>

struct vector_insert_ordered_cursor

{

typedef typename iterator_traits<BiDirPosConstIt>::value_type size_type;

typedef typename iterator_traits<BiDirValueIt>::reference reference;

BOOST_CONTAINER_FORCEINLINE vector_insert_ordered_cursor(BiDirPosConstIt posit, BiDirValueIt valueit)

: last_position_it(posit), last_value_it(valueit)

{}

void operator --()

{

--last_value_it;

--last_position_it;

while(this->get_pos() == size_type(-1)){

--last_value_it;

--last_position_it;

}

}

BOOST_CONTAINER_FORCEINLINE size_type get_pos() const

{ return *last_position_it; }

BOOST_CONTAINER_FORCEINLINE reference get_val()

{ return *last_value_it; }

BiDirPosConstIt last_position_it;

BiDirValueIt last_value_it;

};

struct initial_capacity_t{};

template<class Pointer, bool IsConst>

BOOST_CONTAINER_FORCEINLINE const Pointer &vector_iterator_get_ptr(const vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW

{ return it.get_ptr(); }

template<class Pointer, bool IsConst>

BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr(vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW

{ return it.get_ptr(); }

struct vector_uninitialized_size_t {};

static const vector_uninitialized_size_t vector_uninitialized_size = vector_uninitialized_size_t();

template <class T>

struct vector_value_traits_base

{

static const bool trivial_dctr = dtl::is_trivially_destructible<T>::value;

static const bool trivial_dctr_after_move = has_trivial_destructor_after_move<T>::value;

static const bool trivial_copy = dtl::is_trivially_copy_constructible<T>::value;

static const bool nothrow_copy = dtl::is_nothrow_copy_constructible<T>::value || trivial_copy;

static const bool trivial_assign = dtl::is_trivially_copy_assignable<T>::value;

static const bool nothrow_assign = dtl::is_nothrow_copy_assignable<T>::value || trivial_assign;

};

template <class Allocator>

struct vector_value_traits

: public vector_value_traits_base<typename Allocator::value_type>

{

typedef vector_value_traits_base<typename Allocator::value_type> base_t;

//This is the anti-exception array destructor

//to deallocate values already constructed

typedef typename dtl::if_c

<base_t::trivial_dctr

,dtl::null_scoped_destructor_n<Allocator>

,dtl::scoped_destructor_n<Allocator>

>::type ArrayDestructor;

//This is the anti-exception array deallocator

typedef dtl::scoped_array_deallocator<Allocator> ArrayDeallocator;

};

//!This struct deallocates and allocated memory

template < class Allocator

, class StoredSizeType

, class AllocatorVersion = typename dtl::version<Allocator>::type

>

struct vector_alloc_holder

: public Allocator

{

private:

BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)

public:

typedef Allocator allocator_type;

typedef StoredSizeType stored_size_type;

typedef boost::container::allocator_traits<allocator_type> allocator_traits_type;

typedef typename allocator_traits_type::pointer pointer;

typedef typename allocator_traits_type::size_type size_type;

typedef typename allocator_traits_type::value_type value_type;

static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator)

{

(void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc;

const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||

!allocator_traits_type::storage_is_unpropagable(from_alloc, p);

return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc));

}

static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator)

{

(void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a;

const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||

!(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p));

return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a));

}

//Constructor, does not throw

vector_alloc_holder()

BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)

: allocator_type(), m_start(), m_size(), m_capacity()

{}

//Constructor, does not throw

template<class AllocConvertible>

explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW

: allocator_type(boost::forward<AllocConvertible>(a)), m_start(), m_size(), m_capacity()

{}

//Constructor, does not throw

template<class AllocConvertible>

vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)

: allocator_type(boost::forward<AllocConvertible>(a))

, m_start()

//Size is initialized here so vector should only call uninitialized_xxx after this

, m_size(static_cast<stored_size_type>(initial_size))

, m_capacity()

{

if(initial_size){

pointer reuse = pointer();

size_type final_cap = initial_size;

m_start = this->allocation_command(allocate_new, initial_size, final_cap, reuse);

m_capacity = static_cast<stored_size_type>(final_cap);

}

}

//Constructor, does not throw

vector_alloc_holder(vector_uninitialized_size_t, size_type initial_size)

: allocator_type()

, m_start()

//Size is initialized here so vector should only call uninitialized_xxx after this

, m_size(static_cast<stored_size_type>(initial_size))

, m_capacity()

{

if(initial_size){

pointer reuse = pointer();

size_type final_cap = initial_size;

m_start = this->allocation_command(allocate_new, initial_size, final_cap, reuse);

m_capacity = static_cast<stored_size_type>(final_cap);

}

}

vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) BOOST_NOEXCEPT_OR_NOTHROW

: allocator_type(BOOST_MOVE_BASE(allocator_type, holder))

, m_start(holder.m_start)

, m_size(holder.m_size)

, m_capacity(holder.m_capacity)

{

holder.m_start = pointer();

holder.m_size = holder.m_capacity = 0;

}

vector_alloc_holder(initial_capacity_t, pointer p, size_type capacity, BOOST_RV_REF(vector_alloc_holder) holder)

: allocator_type(BOOST_MOVE_BASE(allocator_type, holder))

, m_start(p)

, m_size(holder.m_size)

, m_capacity(static_cast<stored_size_type>(capacity))

{

allocator_type &this_alloc = this->alloc();

allocator_type &x_alloc = holder.alloc();

if(this->is_propagable_from(x_alloc, holder.start(), this_alloc, true)){

if(this->m_capacity){

this->deallocate(this->m_start, this->m_capacity);

}

m_start = holder.m_start;

m_capacity = holder.m_capacity;

holder.m_start = pointer();

holder.m_capacity = holder.m_size = 0;

}

else if(this->m_capacity < holder.m_size){

size_type const n = holder.m_size;

pointer reuse = pointer();

size_type final_cap = n;

m_start = this->allocation_command(allocate_new, n, final_cap, reuse);

m_capacity = static_cast<stored_size_type>(final_cap);

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

}

}

vector_alloc_holder(initial_capacity_t, pointer p, size_type n)

BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)

: allocator_type()

, m_start(p)

, m_size()

//n is guaranteed to fit into stored_size_type

, m_capacity(static_cast<stored_size_type>(n))

{}

template<class AllocFwd>

vector_alloc_holder(initial_capacity_t, pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a)

: allocator_type(::boost::forward<AllocFwd>(a))

, m_start(p)

, m_size()

, m_capacity(n)

{}

BOOST_CONTAINER_FORCEINLINE ~vector_alloc_holder() BOOST_NOEXCEPT_OR_NOTHROW

{

if(this->m_capacity){

this->deallocate(this->m_start, this->m_capacity);

}

}

BOOST_CONTAINER_FORCEINLINE pointer allocation_command(boost::container::allocation_type command,

size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse)

{

typedef typename dtl::version<allocator_type>::type alloc_version;

return this->priv_allocation_command(alloc_version(), command, limit_size, prefer_in_recvd_out_size, reuse);

}

BOOST_CONTAINER_FORCEINLINE pointer allocate(size_type n)

{

const size_type max_alloc = allocator_traits_type::max_size(this->alloc());

const size_type max = max_alloc <= stored_size_type(-1) ? max_alloc : stored_size_type(-1);

if ( max < n )

boost::container::throw_length_error("get_next_capacity, allocator's max size reached");

return allocator_traits_type::allocate(this->alloc(), n);

}

BOOST_CONTAINER_FORCEINLINE void deallocate(const pointer &p, size_type n)

{

allocator_traits_type::deallocate(this->alloc(), p, n);

}

bool try_expand_fwd(size_type at_least)

{

//There is not enough memory, try to expand the old one

const size_type new_cap = this->capacity() + at_least;

size_type real_cap = new_cap;

pointer reuse = this->start();

bool const success = !!this->allocation_command(expand_fwd, new_cap, real_cap, reuse);

//Check for forward expansion

if(success){

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

++this->num_expand_fwd;

#endif

this->capacity(real_cap);

}

return success;

}

template<class GrowthFactorType>

size_type next_capacity(size_type additional_objects) const

{

BOOST_ASSERT(additional_objects > size_type(this->m_capacity - this->m_size));

size_type max = allocator_traits_type::max_size(this->alloc());

(clamp_by_stored_size_type)(max, stored_size_type());

const size_type remaining_cap = max - size_type(this->m_capacity);

const size_type min_additional_cap = additional_objects - size_type(this->m_capacity - this->m_size);

if ( remaining_cap < min_additional_cap )

boost::container::throw_length_error("get_next_capacity, allocator's max size reached");

return GrowthFactorType()( size_type(this->m_capacity), min_additional_cap, max);

}

pointer m_start;

stored_size_type m_size;

stored_size_type m_capacity;

void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW

{

boost::adl_move_swap(this->m_start, x.m_start);

boost::adl_move_swap(this->m_size, x.m_size);

boost::adl_move_swap(this->m_capacity, x.m_capacity);

}

void steal_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW

{

this->m_start = x.m_start;

this->m_size = x.m_size;

this->m_capacity = x.m_capacity;

x.m_start = pointer();

x.m_size = x.m_capacity = 0;

}

BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW

{ return *this; }

BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW

{ return *this; }

BOOST_CONTAINER_FORCEINLINE const pointer &start() const BOOST_NOEXCEPT_OR_NOTHROW

{ return m_start; }

BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW

{ return m_capacity; }

BOOST_CONTAINER_FORCEINLINE void start(const pointer &p) BOOST_NOEXCEPT_OR_NOTHROW

{ m_start = p; }

BOOST_CONTAINER_FORCEINLINE void capacity(const size_type &c) BOOST_NOEXCEPT_OR_NOTHROW

{ BOOST_ASSERT( c <= stored_size_type(-1)); m_capacity = c; }

private:

void priv_first_allocation(size_type cap)

{

if(cap){

pointer reuse = pointer();

m_start = this->allocation_command(allocate_new, cap, cap, reuse);

m_capacity = cap;

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

++this->num_alloc;

#endif

}

}

BOOST_CONTAINER_FORCEINLINE static void clamp_by_stored_size_type(size_type &, size_type)

{}

template<class SomeStoredSizeType>

BOOST_CONTAINER_FORCEINLINE static void clamp_by_stored_size_type(size_type &s, SomeStoredSizeType)

{

if (s >= SomeStoredSizeType(-1) )

s = SomeStoredSizeType(-1);

}

BOOST_CONTAINER_FORCEINLINE pointer priv_allocation_command(version_1, boost::container::allocation_type command,

size_type limit_size,

size_type &prefer_in_recvd_out_size,

pointer &reuse)

{

(void)command;

BOOST_ASSERT( (command & allocate_new));

BOOST_ASSERT(!(command & nothrow_allocation));

//First detect overflow on smaller stored_size_types

if (limit_size > stored_size_type(-1)){

boost::container::throw_length_error("get_next_capacity, allocator's max size reached");

}

(clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type());

pointer const p = this->allocate(prefer_in_recvd_out_size);

reuse = pointer();

return p;

}

pointer priv_allocation_command(version_2, boost::container::allocation_type command,

size_type limit_size,

size_type &prefer_in_recvd_out_size,

pointer &reuse)

{

//First detect overflow on smaller stored_size_types

if (limit_size > stored_size_type(-1)){

boost::container::throw_length_error("get_next_capacity, allocator's max size reached");

}

(clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type());

//Allocate memory

pointer p = this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);

//If after allocation prefer_in_recvd_out_size is not representable by stored_size_type, truncate it.

(clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type());

return p;

}

};

//!This struct deallocates and allocated memory

template <class Allocator, class StoredSizeType>

struct vector_alloc_holder<Allocator, StoredSizeType, version_0>

: public Allocator

{

private:

BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)

public:

typedef Allocator allocator_type;

typedef boost::container::

allocator_traits<allocator_type> allocator_traits_type;

typedef typename allocator_traits_type::pointer pointer;

typedef typename allocator_traits_type::size_type size_type;

typedef typename allocator_traits_type::value_type value_type;

typedef StoredSizeType stored_size_type;

template <class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion>

friend struct vector_alloc_holder;

//Constructor, does not throw

vector_alloc_holder()

BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)

: allocator_type(), m_size()

{}

//Constructor, does not throw

template<class AllocConvertible>

explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW

: allocator_type(boost::forward<AllocConvertible>(a)), m_size()

{}

//Constructor, does not throw

template<class AllocConvertible>

vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)

: allocator_type(boost::forward<AllocConvertible>(a))

, m_size(initial_size) //Size is initialized here...

{

//... and capacity here, so vector, must call uninitialized_xxx in the derived constructor

this->priv_first_allocation(initial_size);

}

//Constructor, does not throw

vector_alloc_holder(vector_uninitialized_size_t, size_type initial_size)

: allocator_type()

, m_size(initial_size) //Size is initialized here...

{

//... and capacity here, so vector, must call uninitialized_xxx in the derived constructor

this->priv_first_allocation(initial_size);

}

vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder)

: allocator_type(BOOST_MOVE_BASE(allocator_type, holder))

, m_size(holder.m_size) //Size is initialized here so vector should only call uninitialized_xxx after this

{

::boost::container::uninitialized_move_alloc_n

(this->alloc(), boost::movelib::to_raw_pointer(holder.start()), m_size, boost::movelib::to_raw_pointer(this->start()));

}

template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion>

vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> BOOST_RV_REF_END holder)

: allocator_type()

, m_size(holder.m_size) //Initialize it to m_size as first_allocation can only succeed or abort

{

//Different allocator type so we must check we have enough storage

const size_type n = holder.m_size;

this->priv_first_allocation(n);

::boost::container::uninitialized_move_alloc_n

(this->alloc(), boost::movelib::to_raw_pointer(holder.start()), n, boost::movelib::to_raw_pointer(this->start()));

}

BOOST_CONTAINER_FORCEINLINE void priv_first_allocation(size_type cap)

{

if(cap > allocator_type::internal_capacity){

throw_bad_alloc();

}

}

BOOST_CONTAINER_FORCEINLINE void deep_swap(vector_alloc_holder &x)

{

this->priv_deep_swap(x);

}

template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion>

void deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x)

{

typedef typename real_allocator<value_type, OtherAllocator>::type other_allocator_type;

if(this->m_size > other_allocator_type::internal_capacity || x.m_size > allocator_type::internal_capacity){

throw_bad_alloc();

}

this->priv_deep_swap(x);

}

BOOST_CONTAINER_FORCEINLINE void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW

{ //Containers with version 0 allocators can't be moved without moving elements one by one

throw_bad_alloc();

}

BOOST_CONTAINER_FORCEINLINE void steal_resources(vector_alloc_holder &)

{ //Containers with version 0 allocators can't be moved without moving elements one by one

throw_bad_alloc();

}

BOOST_CONTAINER_FORCEINLINE allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW

{ return *this; }

BOOST_CONTAINER_FORCEINLINE const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW

{ return *this; }

BOOST_CONTAINER_FORCEINLINE bool try_expand_fwd(size_type at_least)

{ return !at_least; }

BOOST_CONTAINER_FORCEINLINE pointer start() const BOOST_NOEXCEPT_OR_NOTHROW

{ return allocator_type::internal_storage(); }

BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW

{ return allocator_type::internal_capacity; }

stored_size_type m_size;

private:

template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion>

void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x)

{

const size_type MaxTmpStorage = sizeof(value_type)*allocator_type::internal_capacity;

value_type *const first_this = boost::movelib::to_raw_pointer(this->start());

value_type *const first_x = boost::movelib::to_raw_pointer(x.start());

if(this->m_size < x.m_size){

boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_this, this->m_size, first_x, x.m_size);

}

else{

boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_x, x.m_size, first_this, this->m_size);

}

boost::adl_move_swap(this->m_size, x.m_size);

}

};

struct growth_factor_60;

template<class T, class Default>

struct default_if_void

{

typedef T type;

};

template<class Default>

struct default_if_void<void, Default>

{

typedef Default type;

};

template<class Options, class AllocatorSizeType>

struct get_vector_opt

{

typedef vector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type

, typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type

> type;

};

template<class AllocatorSizeType>

struct get_vector_opt<void, AllocatorSizeType>

{

typedef vector_opt<growth_factor_60, AllocatorSizeType> type;

};

#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

//! A vector is a sequence that supports random access to elements, constant

//! time insertion and removal of elements at the end, and linear time insertion

//! and removal of elements at the beginning or in the middle. The number of

//! elements in a vector may vary dynamically; memory management is automatic.

//!

//! \tparam T The type of object that is stored in the vector

//! \tparam A The allocator used for all internal memory management, use void

//! for the default allocator

//! \tparam Options A type produced from \c boost::container::vector_options.

template <class T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void) >

class vector

{

public:

//////////////////////////////////////////////

//

// types

//

//////////////////////////////////////////////

typedef T value_type;

typedef BOOST_CONTAINER_IMPDEF

(typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type;

typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_t;

typedef typename allocator_traits<allocator_type>::pointer pointer;

typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;

typedef typename allocator_traits<allocator_type>::reference reference;

typedef typename allocator_traits<allocator_type>::const_reference const_reference;

typedef typename allocator_traits<allocator_type>::size_type size_type;

typedef typename allocator_traits<allocator_type>::difference_type difference_type;

typedef allocator_type stored_allocator_type;

typedef BOOST_CONTAINER_IMPDEF(vec_iterator<pointer BOOST_MOVE_I false>) iterator;

typedef BOOST_CONTAINER_IMPDEF(vec_iterator<pointer BOOST_MOVE_I true >) 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;

private:

#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

typedef typename boost::container::

allocator_traits<allocator_type>::size_type alloc_size_type;

typedef typename get_vector_opt<Options, alloc_size_type>::type options_type;

typedef typename options_type::growth_factor_type growth_factor_type;

typedef typename options_type::stored_size_type stored_size_type;

typedef value_less<T> value_less_t;

//If provided the stored_size option must specify a type that is equal or a type that is smaller.

BOOST_STATIC_ASSERT( (sizeof(stored_size_type) < sizeof(alloc_size_type) ||

dtl::is_same<stored_size_type, alloc_size_type>::value) );

typedef typename dtl::version<allocator_type>::type alloc_version;

typedef boost::container::vector_alloc_holder

<allocator_type, stored_size_type> alloc_holder_t;

alloc_holder_t m_holder;

typedef allocator_traits<allocator_type> allocator_traits_type;

template <class U, class UA, class UOptions>

friend class vector;

protected:

BOOST_CONTAINER_FORCEINLINE

static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator)

{ return alloc_holder_t::is_propagable_from(from_alloc, p, to_alloc, propagate_allocator); }

BOOST_CONTAINER_FORCEINLINE

static bool are_swap_propagable( const allocator_type &l_a, pointer l_p

, const allocator_type &r_a, pointer r_p, bool const propagate_allocator)

{ return alloc_holder_t::are_swap_propagable(l_a, l_p, r_a, r_p, propagate_allocator); }

#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

private:

BOOST_COPYABLE_AND_MOVABLE(vector)

typedef vector_value_traits<allocator_type> value_traits;

typedef constant_iterator<T, difference_type> cvalue_iterator;

protected:

BOOST_CONTAINER_FORCEINLINE void steal_resources(vector &x)

{ return this->m_holder.steal_resources(x.m_holder); }

template<class AllocFwd>

BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity, BOOST_FWD_REF(AllocFwd) a)

: m_holder(initial_capacity_t(), initial_memory, capacity, ::boost::forward<AllocFwd>(a))

{}

BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity)

: m_holder(initial_capacity_t(), initial_memory, capacity)

{}

#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED

public:

//////////////////////////////////////////////

//

// construct/copy/destroy

//

//////////////////////////////////////////////

//! <b>Effects</b>: Constructs a vector taking the allocator as parameter.

//!

//! <b>Throws</b>: Nothing.

//!

//! <b>Complexity</b>: Constant.

vector() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value)

: m_holder()

{}

//! <b>Effects</b>: Constructs a vector taking the allocator as parameter.

//!

//! <b>Throws</b>: Nothing

//!

//! <b>Complexity</b>: Constant.

explicit vector(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW

: m_holder(a)

{}

//! <b>Effects</b>: Constructs a vector and inserts n value initialized values.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's value initialization throws.

//!

//! <b>Complexity</b>: Linear to n.

explicit vector(size_type n)

: m_holder(vector_uninitialized_size, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_value_init_alloc_n

(this->m_holder.alloc(), n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a

//! and inserts n value initialized values.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's value initialization throws.

//!

//! <b>Complexity</b>: Linear to n.

explicit vector(size_type n, const allocator_type &a)

: m_holder(vector_uninitialized_size, a, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_value_init_alloc_n

(this->m_holder.alloc(), n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a

//! and inserts n default initialized values.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's default initialization throws.

//!

//! <b>Complexity</b>: Linear to n.

//!

//! <b>Note</b>: Non-standard extension

vector(size_type n, default_init_t)

: m_holder(vector_uninitialized_size, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_default_init_alloc_n

(this->m_holder.alloc(), n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a

//! and inserts n default initialized values.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's default initialization throws.

//!

//! <b>Complexity</b>: Linear to n.

//!

//! <b>Note</b>: Non-standard extension

vector(size_type n, default_init_t, const allocator_type &a)

: m_holder(vector_uninitialized_size, a, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_default_init_alloc_n

(this->m_holder.alloc(), n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector

//! and inserts n copies of value.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's copy constructor throws.

//!

//! <b>Complexity</b>: Linear to n.

vector(size_type n, const T& value)

: m_holder(vector_uninitialized_size, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_fill_alloc_n

(this->m_holder.alloc(), value, n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a

//! and inserts n copies of value.

//!

//! <b>Throws</b>: If allocation

//! throws or T's copy constructor throws.

//!

//! <b>Complexity</b>: Linear to n.

vector(size_type n, const T& value, const allocator_type& a)

: m_holder(vector_uninitialized_size, a, n)

{

#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS

this->num_alloc += n != 0;

#endif

boost::container::uninitialized_fill_alloc_n

(this->m_holder.alloc(), value, n, this->priv_raw_begin());

}

//! <b>Effects</b>: Constructs a vector

//! and inserts a copy of the range [first, last) in the vector.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's constructor taking a dereferenced InIt throws.

//!

//! <b>Complexity</b>: Linear to the range [first, last).

// template <class InIt>

// vector(InIt first, InIt last

// BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c

// < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value

// BOOST_MOVE_I dtl::nat >::type * = 0)

// ) -> vector<typename iterator_traits<InIt>::value_type, new_allocator<typename iterator_traits<InIt>::value_type>>;

template <class InIt>

vector(InIt first, InIt last

BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c

< dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value

BOOST_MOVE_I dtl::nat >::type * = 0)

)

: m_holder()

{ this->assign(first, last); }

//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a

//! and inserts a copy of the range [first, last) in the vector.

//!

//! <b>Throws</b>: If allocator_type's allocation

//! throws or T's constructor taking a dereferenced InIt throws.

//!

//! <b>Complexity</b>: Linear to the range [first, last).

// template <class InIt>

// vector(InIt first, InIt last, const allocator_type& a

// BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c

// < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value

// BOOST_MOVE_I dtl::nat >::type * = 0)

// ) -> vector<typename iterator_traits<InIt>::value_type, new_allocator<typename iterator_traits<InIt>::value_type>>;

template <class InIt>

vector(InIt first, InIt last, const allocator_type& a

BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c

< dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value

BOOST_MOVE_I dtl::nat >::type * = 0)

)

: m_holder(a)

{ this->assign(first, last); }

//! <b>Effects</b>: Copy constructs a vector.