////////////////////////////////////////////////////////////////////////////// | |
// | |
// (C) Copyright Ion Gaztanaga 2008-2009. 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. | |
// | |
////////////////////////////////////////////////////////////////////////////// | |
/* Stable vector. | |
* | |
* Copyright 2008 Joaquin M Lopez Munoz. | |
* 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) | |
*/ | |
#ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP | |
#define BOOST_CONTAINER_STABLE_VECTOR_HPP | |
#if (defined _MSC_VER) && (_MSC_VER >= 1200) | |
# pragma once | |
#endif | |
#include "detail/config_begin.hpp" | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP | |
#include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP | |
#include <boost/mpl/bool.hpp> | |
#include <boost/mpl/not.hpp> | |
#include <boost/noncopyable.hpp> | |
#include <boost/type_traits/is_integral.hpp> | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_ITERATORS_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP | |
#include <boost/pointer_to_other.hpp> | |
#include <boost/get_pointer.hpp> | |
#include <algorithm> | |
#include <stdexcept> | |
#include <memory> | |
///@cond | |
#define STABLE_VECTOR_USE_CONTAINERS_VECTOR | |
#if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) | |
#include INCLUDE_BOOST_CONTAINER_VECTOR_HPP | |
#else | |
#include <vector> | |
#endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR | |
//#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING | |
#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) | |
#include <boost/assert.hpp> | |
#endif | |
///@endcond | |
namespace boost { | |
namespace container { | |
///@cond | |
namespace stable_vector_detail{ | |
template<class SmartPtr> | |
struct smart_ptr_type | |
{ | |
typedef typename SmartPtr::value_type value_type; | |
typedef value_type *pointer; | |
static pointer get (const SmartPtr &smartptr) | |
{ return smartptr.get();} | |
}; | |
template<class T> | |
struct smart_ptr_type<T*> | |
{ | |
typedef T value_type; | |
typedef value_type *pointer; | |
static pointer get (pointer ptr) | |
{ return ptr;} | |
}; | |
template<class Ptr> | |
inline typename smart_ptr_type<Ptr>::pointer get_pointer(const Ptr &ptr) | |
{ return smart_ptr_type<Ptr>::get(ptr); } | |
template <class C> | |
class clear_on_destroy | |
{ | |
public: | |
clear_on_destroy(C &c) | |
: c_(c), do_clear_(true) | |
{} | |
void release() | |
{ do_clear_ = false; } | |
~clear_on_destroy() | |
{ | |
if(do_clear_){ | |
c_.clear(); | |
c_.clear_pool(); | |
} | |
} | |
private: | |
clear_on_destroy(const clear_on_destroy &); | |
clear_on_destroy &operator=(const clear_on_destroy &); | |
C &c_; | |
bool do_clear_; | |
}; | |
template<class VoidPtr> | |
struct node_type_base | |
{/* | |
node_type_base(VoidPtr p) | |
: up(p) | |
{}*/ | |
node_type_base() | |
{} | |
void set_pointer(VoidPtr p) | |
{ up = p; } | |
VoidPtr up; | |
}; | |
template<typename VoidPointer, typename T> | |
struct node_type | |
: public node_type_base<VoidPointer> | |
{ | |
#if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
node_type() | |
: value() | |
{} | |
template<class ...Args> | |
node_type(Args &&...args) | |
: value(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...) | |
{} | |
#else //BOOST_CONTAINERS_PERFECT_FORWARDING | |
node_type() | |
: value() | |
{} | |
#define BOOST_PP_LOCAL_MACRO(n) \ | |
template<BOOST_PP_ENUM_PARAMS(n, class P)> \ | |
node_type(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ | |
: value(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \ | |
{} \ | |
//! | |
#define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) | |
#include BOOST_PP_LOCAL_ITERATE() | |
#endif//BOOST_CONTAINERS_PERFECT_FORWARDING | |
void set_pointer(VoidPointer p) | |
{ node_type_base<VoidPointer>::set_pointer(p); } | |
T value; | |
}; | |
template<typename T, typename Reference, typename Pointer> | |
class iterator | |
: public std::iterator< std::random_access_iterator_tag | |
, typename std::iterator_traits<Pointer>::value_type | |
, typename std::iterator_traits<Pointer>::difference_type | |
, Pointer | |
, Reference> | |
{ | |
typedef typename boost::pointer_to_other | |
<Pointer, void>::type void_ptr; | |
typedef node_type<void_ptr, T> node_type_t; | |
typedef typename boost::pointer_to_other | |
<void_ptr, node_type_t>::type node_type_ptr_t; | |
typedef typename boost::pointer_to_other | |
<void_ptr, void_ptr>::type void_ptr_ptr; | |
friend class iterator<T, const T, typename boost::pointer_to_other<Pointer, T>::type>; | |
public: | |
typedef std::random_access_iterator_tag iterator_category; | |
typedef T value_type; | |
typedef typename std::iterator_traits | |
<Pointer>::difference_type difference_type; | |
typedef Pointer pointer; | |
typedef Reference reference; | |
iterator() | |
{} | |
explicit iterator(node_type_ptr_t pn) | |
: pn(pn) | |
{} | |
iterator(const iterator<T, T&, typename boost::pointer_to_other<Pointer, T>::type >& x) | |
: pn(x.pn) | |
{} | |
private: | |
static node_type_ptr_t node_ptr_cast(void_ptr p) | |
{ | |
using boost::get_pointer; | |
return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); | |
} | |
static void_ptr_ptr void_ptr_ptr_cast(void_ptr p) | |
{ | |
using boost::get_pointer; | |
return void_ptr_ptr(static_cast<void_ptr*>(stable_vector_detail::get_pointer(p))); | |
} | |
reference dereference() const | |
{ return pn->value; } | |
bool equal(const iterator& x) const | |
{ return pn==x.pn; } | |
void increment() | |
{ pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+1)); } | |
void decrement() | |
{ pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)-1)); } | |
void advance(std::ptrdiff_t n) | |
{ pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+n)); } | |
std::ptrdiff_t distance_to(const iterator& x)const | |
{ return void_ptr_ptr_cast(x.pn->up) - void_ptr_ptr_cast(pn->up); } | |
public: | |
//Pointer like operators | |
reference operator*() const { return this->dereference(); } | |
pointer operator->() const { return pointer(&this->dereference()); } | |
//Increment / Decrement | |
iterator& operator++() | |
{ this->increment(); return *this; } | |
iterator operator++(int) | |
{ iterator tmp(*this); ++*this; return iterator(tmp); } | |
iterator& operator--() | |
{ this->decrement(); return *this; } | |
iterator operator--(int) | |
{ iterator tmp(*this); --*this; return iterator(tmp); } | |
reference operator[](difference_type off) const | |
{ | |
iterator tmp(*this); | |
tmp += off; | |
return *tmp; | |
} | |
iterator& operator+=(difference_type off) | |
{ | |
pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+off)); | |
return *this; | |
} | |
iterator operator+(difference_type off) const | |
{ | |
iterator tmp(*this); | |
tmp += off; | |
return tmp; | |
} | |
friend iterator operator+(difference_type off, const iterator& right) | |
{ | |
iterator tmp(right); | |
tmp += off; | |
return tmp; | |
} | |
iterator& operator-=(difference_type off) | |
{ *this += -off; return *this; } | |
iterator operator-(difference_type off) const | |
{ | |
iterator tmp(*this); | |
tmp -= off; | |
return tmp; | |
} | |
difference_type operator-(const iterator& right) const | |
{ | |
void_ptr_ptr p1 = void_ptr_ptr_cast(this->pn->up); | |
void_ptr_ptr p2 = void_ptr_ptr_cast(right.pn->up); | |
return p1 - p2; | |
} | |
//Comparison operators | |
bool operator== (const iterator& r) const | |
{ return pn == r.pn; } | |
bool operator!= (const iterator& r) const | |
{ return pn != r.pn; } | |
bool operator< (const iterator& r) const | |
{ return void_ptr_ptr_cast(pn->up) < void_ptr_ptr_cast(r.pn->up); } | |
bool operator<= (const iterator& r) const | |
{ return void_ptr_ptr_cast(pn->up) <= void_ptr_ptr_cast(r.pn->up); } | |
bool operator> (const iterator& r) const | |
{ return void_ptr_ptr_cast(pn->up) > void_ptr_ptr_cast(r.pn->up); } | |
bool operator>= (const iterator& r) const | |
{ return void_ptr_ptr_cast(pn->up) >= void_ptr_ptr_cast(r.pn->up); } | |
node_type_ptr_t pn; | |
}; | |
template<class Allocator, unsigned int Version> | |
struct select_multiallocation_chain | |
{ | |
typedef typename Allocator::multiallocation_chain type; | |
}; | |
template<class Allocator> | |
struct select_multiallocation_chain<Allocator, 1> | |
{ | |
typedef typename Allocator::template | |
rebind<void>::other::pointer void_ptr; | |
typedef containers_detail::basic_multiallocation_chain | |
<void_ptr> multialloc_cached_counted; | |
typedef boost::container::containers_detail::transform_multiallocation_chain | |
<multialloc_cached_counted, typename Allocator::value_type> type; | |
}; | |
} //namespace stable_vector_detail | |
#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) | |
#define STABLE_VECTOR_CHECK_INVARIANT \ | |
invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \ | |
BOOST_JOIN(check_invariant_,__LINE__).touch(); | |
#else | |
#define STABLE_VECTOR_CHECK_INVARIANT | |
#endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) | |
/// @endcond | |
//!Help taken from (<a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" > Introducing stable_vector</a>) | |
//! | |
//!We present stable_vector, a fully STL-compliant stable container that provides | |
//!most of the features of std::vector except element contiguity. | |
//! | |
//!General properties: stable_vector satisfies all the requirements of a container, | |
//!a reversible container and a sequence and provides all the optional operations | |
//!present in std::vector. Like std::vector, iterators are random access. | |
//!stable_vector does not provide element contiguity; in exchange for this absence, | |
//!the container is stable, i.e. references and iterators to an element of a stable_vector | |
//!remain valid as long as the element is not erased, and an iterator that has been | |
//!assigned the return value of end() always remain valid until the destruction of | |
//!the associated stable_vector. | |
//! | |
//!Operation complexity: The big-O complexities of stable_vector operations match | |
//!exactly those of std::vector. In general, insertion/deletion is constant time at | |
//!the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector | |
//!does not internally perform any value_type destruction, copy or assignment | |
//!operations other than those exactly corresponding to the insertion of new | |
//!elements or deletion of stored elements, which can sometimes compensate in terms | |
//!of performance for the extra burden of doing more pointer manipulation and an | |
//!additional allocation per element. | |
//! | |
//!Exception safety: As stable_vector does not internally copy elements around, some | |
//!operations provide stronger exception safety guarantees than in std::vector: | |
template<typename T, typename Allocator> | |
class stable_vector | |
{ | |
///@cond | |
typedef typename containers_detail:: | |
move_const_ref_type<T>::type insert_const_ref_type; | |
typedef typename Allocator::template | |
rebind<void>::other::pointer void_ptr; | |
typedef typename Allocator::template | |
rebind<void_ptr>::other::pointer void_ptr_ptr; | |
typedef stable_vector_detail::node_type | |
<void_ptr, T> node_type_t; | |
typedef typename Allocator::template | |
rebind<node_type_t>::other::pointer node_type_ptr_t; | |
typedef stable_vector_detail::node_type_base | |
<void_ptr> node_type_base_t; | |
typedef typename Allocator::template | |
rebind<node_type_base_t>::other::pointer node_type_base_ptr_t; | |
typedef | |
#if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) | |
::boost::container:: | |
#else | |
::std:: | |
#endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR | |
vector<void_ptr, | |
typename Allocator:: | |
template rebind<void_ptr>::other | |
> impl_type; | |
typedef typename impl_type::iterator impl_iterator; | |
typedef typename impl_type::const_iterator const_impl_iterator; | |
typedef ::boost::container::containers_detail:: | |
integral_constant<unsigned, 1> allocator_v1; | |
typedef ::boost::container::containers_detail:: | |
integral_constant<unsigned, 2> allocator_v2; | |
typedef ::boost::container::containers_detail::integral_constant | |
<unsigned, boost::container::containers_detail:: | |
version<Allocator>::value> alloc_version; | |
typedef typename Allocator:: | |
template rebind<node_type_t>::other node_allocator_type; | |
node_type_ptr_t allocate_one() | |
{ return this->allocate_one(alloc_version()); } | |
node_type_ptr_t allocate_one(allocator_v1) | |
{ return get_al().allocate(1); } | |
node_type_ptr_t allocate_one(allocator_v2) | |
{ return get_al().allocate_one(); } | |
void deallocate_one(node_type_ptr_t p) | |
{ return this->deallocate_one(p, alloc_version()); } | |
void deallocate_one(node_type_ptr_t p, allocator_v1) | |
{ get_al().deallocate(p, 1); } | |
void deallocate_one(node_type_ptr_t p, allocator_v2) | |
{ get_al().deallocate_one(p); } | |
friend class stable_vector_detail::clear_on_destroy<stable_vector>; | |
///@endcond | |
public: | |
// types: | |
typedef typename Allocator::reference reference; | |
typedef typename Allocator::const_reference const_reference; | |
typedef typename Allocator::pointer pointer; | |
typedef typename Allocator::const_pointer const_pointer; | |
typedef stable_vector_detail::iterator | |
<T,T&, pointer> iterator; | |
typedef stable_vector_detail::iterator | |
<T,const T&, const_pointer> const_iterator; | |
typedef typename impl_type::size_type size_type; | |
typedef typename iterator::difference_type difference_type; | |
typedef T value_type; | |
typedef Allocator allocator_type; | |
typedef std::reverse_iterator<iterator> reverse_iterator; | |
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
///@cond | |
private: | |
BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(stable_vector) | |
static const size_type ExtraPointers = 3; | |
typedef typename stable_vector_detail:: | |
select_multiallocation_chain | |
< node_allocator_type | |
, alloc_version::value | |
>::type multiallocation_chain; | |
///@endcond | |
public: | |
// construct/copy/destroy: | |
explicit stable_vector(const Allocator& al=Allocator()) | |
: internal_data(al),impl(al) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
} | |
explicit stable_vector(size_type n) | |
: internal_data(Allocator()),impl(Allocator()) | |
{ | |
stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); | |
this->resize(n); | |
STABLE_VECTOR_CHECK_INVARIANT; | |
cod.release(); | |
} | |
stable_vector(size_type n, const T& t, const Allocator& al=Allocator()) | |
: internal_data(al),impl(al) | |
{ | |
stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); | |
this->insert(this->cbegin(), n, t); | |
STABLE_VECTOR_CHECK_INVARIANT; | |
cod.release(); | |
} | |
template <class InputIterator> | |
stable_vector(InputIterator first,InputIterator last,const Allocator& al=Allocator()) | |
: internal_data(al),impl(al) | |
{ | |
stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); | |
this->insert(this->cbegin(), first, last); | |
STABLE_VECTOR_CHECK_INVARIANT; | |
cod.release(); | |
} | |
stable_vector(const stable_vector& x) | |
: internal_data(x.get_al()),impl(x.get_al()) | |
{ | |
stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); | |
this->insert(this->cbegin(), x.begin(), x.end()); | |
STABLE_VECTOR_CHECK_INVARIANT; | |
cod.release(); | |
} | |
stable_vector(BOOST_MOVE_MACRO_RV_REF(stable_vector) x) | |
: internal_data(x.get_al()),impl(x.get_al()) | |
{ this->swap(x); } | |
~stable_vector() | |
{ | |
this->clear(); | |
clear_pool(); | |
} | |
stable_vector& operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(stable_vector) x) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
if (this != &x) { | |
this->assign(x.begin(), x.end()); | |
} | |
return *this; | |
} | |
stable_vector& operator=(BOOST_MOVE_MACRO_RV_REF(stable_vector) x) | |
{ | |
if (&x != this){ | |
this->swap(x); | |
x.clear(); | |
} | |
return *this; | |
} | |
template<typename InputIterator> | |
void assign(InputIterator first,InputIterator last) | |
{ | |
assign_dispatch(first, last, boost::is_integral<InputIterator>()); | |
} | |
void assign(size_type n,const T& t) | |
{ | |
typedef constant_iterator<value_type, difference_type> cvalue_iterator; | |
return assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); | |
} | |
allocator_type get_allocator()const {return get_al();} | |
// iterators: | |
iterator begin() | |
{ return (impl.empty()) ? end(): iterator(node_ptr_cast(impl.front())) ; } | |
const_iterator begin()const | |
{ return (impl.empty()) ? cend() : const_iterator(node_ptr_cast(impl.front())) ; } | |
iterator end() {return iterator(get_end_node());} | |
const_iterator end()const {return const_iterator(get_end_node());} | |
reverse_iterator rbegin() {return reverse_iterator(this->end());} | |
const_reverse_iterator rbegin()const {return const_reverse_iterator(this->end());} | |
reverse_iterator rend() {return reverse_iterator(this->begin());} | |
const_reverse_iterator rend()const {return const_reverse_iterator(this->begin());} | |
const_iterator cbegin()const {return this->begin();} | |
const_iterator cend()const {return this->end();} | |
const_reverse_iterator crbegin()const{return this->rbegin();} | |
const_reverse_iterator crend()const {return this->rend();} | |
// capacity: | |
size_type size() const | |
{ return impl.empty() ? 0 : (impl.size() - ExtraPointers); } | |
size_type max_size() const | |
{ return impl.max_size() - ExtraPointers; } | |
size_type capacity() const | |
{ | |
if(!impl.capacity()){ | |
return 0; | |
} | |
else{ | |
const size_type num_nodes = this->impl.size() + this->internal_data.pool_size; | |
const size_type num_buck = this->impl.capacity(); | |
return (num_nodes < num_buck) ? num_nodes : num_buck; | |
} | |
} | |
bool empty() const | |
{ return impl.empty() || impl.size() == ExtraPointers; } | |
void resize(size_type n, const T& t) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
if(n > size()) | |
this->insert(this->cend(), n - this->size(), t); | |
else if(n < this->size()) | |
this->erase(this->cbegin() + n, this->cend()); | |
} | |
void resize(size_type n) | |
{ | |
typedef default_construct_iterator<value_type, difference_type> default_iterator; | |
STABLE_VECTOR_CHECK_INVARIANT; | |
if(n > size()) | |
this->insert(this->cend(), default_iterator(n - this->size()), default_iterator()); | |
else if(n < this->size()) | |
this->erase(this->cbegin() + n, this->cend()); | |
} | |
void reserve(size_type n) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
if(n > this->max_size()) | |
throw std::bad_alloc(); | |
size_type size = this->size(); | |
size_type old_capacity = this->capacity(); | |
if(n > old_capacity){ | |
this->initialize_end_node(n); | |
const void * old_ptr = &impl[0]; | |
impl.reserve(n + ExtraPointers); | |
bool realloced = &impl[0] != old_ptr; | |
//Fix the pointers for the newly allocated buffer | |
if(realloced){ | |
this->align_nodes(impl.begin(), impl.begin()+size+1); | |
} | |
//Now fill pool if data is not enough | |
if((n - size) > this->internal_data.pool_size){ | |
this->add_to_pool((n - size) - this->internal_data.pool_size); | |
} | |
} | |
} | |
// element access: | |
reference operator[](size_type n){return value(impl[n]);} | |
const_reference operator[](size_type n)const{return value(impl[n]);} | |
const_reference at(size_type n)const | |
{ | |
if(n>=size()) | |
throw std::out_of_range("invalid subscript at stable_vector::at"); | |
return operator[](n); | |
} | |
reference at(size_type n) | |
{ | |
if(n>=size()) | |
throw std::out_of_range("invalid subscript at stable_vector::at"); | |
return operator[](n); | |
} | |
reference front() | |
{ return value(impl.front()); } | |
const_reference front()const | |
{ return value(impl.front()); } | |
reference back() | |
{ return value(*(&impl.back() - ExtraPointers)); } | |
const_reference back()const | |
{ return value(*(&impl.back() - ExtraPointers)); } | |
// modifiers: | |
void push_back(insert_const_ref_type x) | |
{ return priv_push_back(x); } | |
#if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) | |
void push_back(T &x) { push_back(const_cast<const T &>(x)); } | |
template<class U> | |
void push_back(const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) | |
{ return priv_push_back(u); } | |
#endif | |
void push_back(BOOST_MOVE_MACRO_RV_REF(T) t) | |
{ this->insert(end(), BOOST_CONTAINER_MOVE_NAMESPACE::move(t)); } | |
void pop_back() | |
{ this->erase(this->end()-1); } | |
iterator insert(const_iterator position, insert_const_ref_type x) | |
{ return this->priv_insert(position, x); } | |
#if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) | |
iterator insert(const_iterator position, T &x) { return this->insert(position, const_cast<const T &>(x)); } | |
template<class U> | |
iterator insert(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) | |
{ return this->priv_insert(position, u); } | |
#endif | |
iterator insert(const_iterator position, BOOST_MOVE_MACRO_RV_REF(T) x) | |
{ | |
typedef repeat_iterator<T, difference_type> repeat_it; | |
typedef BOOST_CONTAINER_MOVE_NAMESPACE::move_iterator<repeat_it> repeat_move_it; | |
//Just call more general insert(pos, size, value) and return iterator | |
size_type pos_n = position - cbegin(); | |
this->insert(position | |
,repeat_move_it(repeat_it(x, 1)) | |
,repeat_move_it(repeat_it())); | |
return iterator(this->begin() + pos_n); | |
} | |
void insert(const_iterator position, size_type n, const T& t) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
this->insert_not_iter(position, n, t); | |
} | |
template <class InputIterator> | |
void insert(const_iterator position,InputIterator first, InputIterator last) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
this->insert_iter(position,first,last, | |
boost::mpl::not_<boost::is_integral<InputIterator> >()); | |
} | |
#if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
//! <b>Effects</b>: Inserts an object of type T constructed with | |
//! std::forward<Args>(args)... in the end of the vector. | |
//! | |
//! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. | |
//! | |
//! <b>Complexity</b>: Amortized constant time. | |
template<class ...Args> | |
void emplace_back(Args &&...args) | |
{ | |
typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; | |
EmplaceFunctor &&ef = EmplaceFunctor(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); | |
this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); | |
} | |
//! <b>Requires</b>: position must be a valid iterator of *this. | |
//! | |
//! <b>Effects</b>: Inserts an object of type T constructed with | |
//! std::forward<Args>(args)... before position | |
//! | |
//! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. | |
//! | |
//! <b>Complexity</b>: If position is end(), amortized constant time | |
//! Linear time otherwise. | |
template<class ...Args> | |
iterator emplace(const_iterator position, Args && ...args) | |
{ | |
//Just call more general insert(pos, size, value) and return iterator | |
size_type pos_n = position - cbegin(); | |
typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; | |
EmplaceFunctor &&ef = EmplaceFunctor(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); | |
this->insert(position, EmplaceIterator(ef), EmplaceIterator()); | |
return iterator(this->begin() + pos_n); | |
} | |
#else | |
void emplace_back() | |
{ | |
typedef emplace_functor<node_type_t> EmplaceFunctor; | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; | |
EmplaceFunctor ef; | |
this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); | |
} | |
iterator emplace(const_iterator position) | |
{ | |
typedef emplace_functor<node_type_t> EmplaceFunctor; | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; | |
EmplaceFunctor ef; | |
size_type pos_n = position - this->cbegin(); | |
this->insert(position, EmplaceIterator(ef), EmplaceIterator()); | |
return iterator(this->begin() + pos_n); | |
} | |
#define BOOST_PP_LOCAL_MACRO(n) \ | |
template<BOOST_PP_ENUM_PARAMS(n, class P)> \ | |
void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ | |
{ \ | |
typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ | |
<node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ | |
EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ | |
this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); \ | |
} \ | |
\ | |
template<BOOST_PP_ENUM_PARAMS(n, class P)> \ | |
iterator emplace(const_iterator pos, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ | |
{ \ | |
typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ | |
<node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ | |
typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ | |
EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ | |
size_type pos_n = pos - this->cbegin(); \ | |
this->insert(pos, EmplaceIterator(ef), EmplaceIterator()); \ | |
return iterator(this->begin() + pos_n); \ | |
} \ | |
//! | |
#define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) | |
#include BOOST_PP_LOCAL_ITERATE() | |
#endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING | |
iterator erase(const_iterator position) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
difference_type d=position-this->cbegin(); | |
impl_iterator it=impl.begin()+d; | |
this->delete_node(*it); | |
impl.erase(it); | |
this->align_nodes(impl.begin()+d,get_last_align()); | |
return this->begin()+d; | |
} | |
iterator erase(const_iterator first, const_iterator last) | |
{ return priv_erase(first, last, alloc_version()); } | |
void swap(stable_vector & x) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
this->swap_impl(*this,x); | |
} | |
void clear() | |
{ this->erase(this->cbegin(),this->cend()); } | |
/// @cond | |
private: | |
iterator priv_insert(const_iterator position, const value_type &t) | |
{ | |
typedef constant_iterator<value_type, difference_type> cvalue_iterator; | |
return this->insert_iter(position, cvalue_iterator(t, 1), cvalue_iterator(), std::forward_iterator_tag()); | |
} | |
void priv_push_back(const value_type &t) | |
{ this->insert(end(), t); } | |
void clear_pool(allocator_v1) | |
{ | |
if(!impl.empty() && impl.back()){ | |
void_ptr &p1 = *(impl.end()-2); | |
void_ptr &p2 = impl.back(); | |
multiallocation_chain holder; | |
holder.incorporate_after(holder.before_begin(), p1, p2, this->internal_data.pool_size); | |
while(!holder.empty()){ | |
node_type_ptr_t n = holder.front(); | |
holder.pop_front(); | |
this->deallocate_one(n); | |
} | |
p1 = p2 = 0; | |
this->internal_data.pool_size = 0; | |
} | |
} | |
void clear_pool(allocator_v2) | |
{ | |
if(!impl.empty() && impl.back()){ | |
void_ptr &p1 = *(impl.end()-2); | |
void_ptr &p2 = impl.back(); | |
multiallocation_chain holder; | |
holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); | |
get_al().deallocate_individual(BOOST_CONTAINER_MOVE_NAMESPACE::move(holder)); | |
p1 = p2 = 0; | |
this->internal_data.pool_size = 0; | |
} | |
} | |
void clear_pool() | |
{ | |
this->clear_pool(alloc_version()); | |
} | |
void add_to_pool(size_type n) | |
{ | |
this->add_to_pool(n, alloc_version()); | |
} | |
void add_to_pool(size_type n, allocator_v1) | |
{ | |
size_type remaining = n; | |
while(remaining--){ | |
this->put_in_pool(this->allocate_one()); | |
} | |
} | |
void add_to_pool(size_type n, allocator_v2) | |
{ | |
void_ptr &p1 = *(impl.end()-2); | |
void_ptr &p2 = impl.back(); | |
multiallocation_chain holder; | |
holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); | |
BOOST_STATIC_ASSERT((::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<multiallocation_chain>::value == true)); | |
multiallocation_chain m (get_al().allocate_individual(n)); | |
holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n); | |
this->internal_data.pool_size += n; | |
std::pair<void_ptr, void_ptr> data(holder.extract_data()); | |
p1 = data.first; | |
p2 = data.second; | |
} | |
void put_in_pool(node_type_ptr_t p) | |
{ | |
void_ptr &p1 = *(impl.end()-2); | |
void_ptr &p2 = impl.back(); | |
multiallocation_chain holder; | |
holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); | |
holder.push_front(p); | |
++this->internal_data.pool_size; | |
std::pair<void_ptr, void_ptr> ret(holder.extract_data()); | |
p1 = ret.first; | |
p2 = ret.second; | |
} | |
node_type_ptr_t get_from_pool() | |
{ | |
if(!impl.back()){ | |
return node_type_ptr_t(0); | |
} | |
else{ | |
void_ptr &p1 = *(impl.end()-2); | |
void_ptr &p2 = impl.back(); | |
multiallocation_chain holder; | |
holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); | |
node_type_ptr_t ret = holder.front(); | |
holder.pop_front(); | |
--this->internal_data.pool_size; | |
if(!internal_data.pool_size){ | |
p1 = p2 = 0; | |
} | |
else{ | |
std::pair<void_ptr, void_ptr> data(holder.extract_data()); | |
p1 = data.first; | |
p2 = data.second; | |
} | |
return ret; | |
} | |
} | |
void insert_iter_prolog(size_type n, difference_type d) | |
{ | |
initialize_end_node(n); | |
const void* old_ptr = &impl[0]; | |
//size_type old_capacity = capacity(); | |
//size_type old_size = size(); | |
impl.insert(impl.begin()+d, n, 0); | |
bool realloced = &impl[0] != old_ptr; | |
//Fix the pointers for the newly allocated buffer | |
if(realloced){ | |
align_nodes(impl.begin(), impl.begin()+d); | |
} | |
} | |
template<typename InputIterator> | |
void assign_dispatch(InputIterator first, InputIterator last, boost::mpl::false_) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
iterator first1 = this->begin(); | |
iterator last1 = this->end(); | |
for ( ; first1 != last1 && first != last; ++first1, ++first) | |
*first1 = *first; | |
if (first == last){ | |
this->erase(first1, last1); | |
} | |
else{ | |
this->insert(last1, first, last); | |
} | |
} | |
template<typename Integer> | |
void assign_dispatch(Integer n, Integer t, boost::mpl::true_) | |
{ | |
typedef constant_iterator<value_type, difference_type> cvalue_iterator; | |
this->assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); | |
} | |
iterator priv_erase(const_iterator first, const_iterator last, allocator_v1) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
difference_type d1 = first - this->cbegin(), d2 = last - this->cbegin(); | |
if(d1 != d2){ | |
impl_iterator it1(impl.begin() + d1), it2(impl.begin() + d2); | |
for(impl_iterator it = it1; it != it2; ++it) | |
this->delete_node(*it); | |
impl.erase(it1, it2); | |
this->align_nodes(impl.begin() + d1, get_last_align()); | |
} | |
return iterator(this->begin() + d1); | |
} | |
impl_iterator get_last_align() | |
{ | |
return impl.end() - (ExtraPointers - 1); | |
} | |
const_impl_iterator get_last_align() const | |
{ | |
return impl.cend() - (ExtraPointers - 1); | |
} | |
template<class AllocatorVersion> | |
iterator priv_erase(const_iterator first, const_iterator last, AllocatorVersion, | |
typename boost::container::containers_detail::enable_if_c | |
<boost::container::containers_detail::is_same<AllocatorVersion, allocator_v2> | |
::value>::type * = 0) | |
{ | |
STABLE_VECTOR_CHECK_INVARIANT; | |
return priv_erase(first, last, allocator_v1()); | |
} | |
static node_type_ptr_t node_ptr_cast(void_ptr p) | |
{ | |
using boost::get_pointer; | |
return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); | |
} | |
static node_type_base_ptr_t node_base_ptr_cast(void_ptr p) | |
{ | |
using boost::get_pointer; | |
return node_type_base_ptr_t(static_cast<node_type_base_t*>(stable_vector_detail::get_pointer(p))); | |
} | |
static value_type& value(void_ptr p) | |
{ | |
return node_ptr_cast(p)->value; | |
} | |
void initialize_end_node(size_type impl_capacity = 0) | |
{ | |
if(impl.empty()){ | |
impl.reserve(impl_capacity + ExtraPointers); | |
impl.resize (ExtraPointers, void_ptr(0)); | |
impl[0] = &this->internal_data.end_node; | |
this->internal_data.end_node.up = &impl[0]; | |
} | |
} | |
void readjust_end_node() | |
{ | |
if(!this->impl.empty()){ | |
void_ptr &end_node_ref = *(this->get_last_align()-1); | |
end_node_ref = this->get_end_node(); | |
this->internal_data.end_node.up = &end_node_ref; | |
} | |
else{ | |
this->internal_data.end_node.up = void_ptr(&this->internal_data.end_node.up); | |
} | |
} | |
node_type_ptr_t get_end_node() const | |
{ | |
const node_type_base_t* cp = &this->internal_data.end_node; | |
node_type_base_t* p = const_cast<node_type_base_t*>(cp); | |
return node_ptr_cast(p); | |
} | |
template<class Iter> | |
void_ptr new_node(void_ptr up, Iter it) | |
{ | |
node_type_ptr_t p = this->allocate_one(); | |
try{ | |
boost::container::construct_in_place(&*p, it); | |
p->set_pointer(up); | |
} | |
catch(...){ | |
this->deallocate_one(p); | |
throw; | |
} | |
return p; | |
} | |
void delete_node(void_ptr p) | |
{ | |
node_type_ptr_t n(node_ptr_cast(p)); | |
n->~node_type_t(); | |
this->put_in_pool(n); | |
} | |
static void align_nodes(impl_iterator first,impl_iterator last) | |
{ | |
while(first!=last){ | |
node_ptr_cast(*first)->up = void_ptr(&*first); | |
++first; | |
} | |
} | |
void insert_not_iter(const_iterator position, size_type n, const T& t) | |
{ | |
typedef constant_iterator<value_type, difference_type> cvalue_iterator; | |
this->insert_iter(position, cvalue_iterator(t, n), cvalue_iterator(), std::forward_iterator_tag()); | |
} | |
template <class InputIterator> | |
void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::true_) | |
{ | |
typedef typename std::iterator_traits<InputIterator>::iterator_category category; | |
this->insert_iter(position, first, last, category()); | |
} | |
template <class InputIterator> | |
void insert_iter(const_iterator position,InputIterator first,InputIterator last,std::input_iterator_tag) | |
{ | |
for(; first!=last; ++first){ | |
this->insert(position, *first); | |
} | |
} | |
template <class InputIterator> | |
iterator insert_iter(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag) | |
{ | |
size_type n = (size_type)std::distance(first,last); | |
difference_type d = position-this->cbegin(); | |
if(n){ | |
this->insert_iter_prolog(n, d); | |
const impl_iterator it(impl.begin() + d); | |
this->insert_iter_fwd(it, first, last, n); | |
//Fix the pointers for the newly allocated buffer | |
this->align_nodes(it + n, get_last_align()); | |
} | |
return this->begin() + d; | |
} | |
template <class FwdIterator> | |
void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v1) | |
{ | |
size_type i=0; | |
try{ | |
while(first!=last){ | |
*(it + i) = this->new_node(void_ptr((void*)(&*(it + i))), first); | |
++first; | |
++i; | |
} | |
} | |
catch(...){ | |
impl.erase(it + i, it + n); | |
this->align_nodes(it + i, get_last_align()); | |
throw; | |
} | |
} | |
template <class FwdIterator> | |
void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v2) | |
{ | |
multiallocation_chain mem(get_al().allocate_individual(n)); | |
size_type i = 0; | |
node_type_ptr_t p = 0; | |
try{ | |
while(first != last){ | |
p = mem.front(); | |
mem.pop_front(); | |
//This can throw | |
boost::container::construct_in_place(&*p, first); | |
p->set_pointer(void_ptr((void*)(&*(it + i)))); | |
++first; | |
*(it + i) = p; | |
++i; | |
} | |
} | |
catch(...){ | |
get_al().deallocate_one(p); | |
get_al().deallocate_many(BOOST_CONTAINER_MOVE_NAMESPACE::move(mem)); | |
impl.erase(it+i, it+n); | |
this->align_nodes(it+i,get_last_align()); | |
throw; | |
} | |
} | |
template <class FwdIterator> | |
void insert_iter_fwd(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n) | |
{ | |
size_type i = 0; | |
node_type_ptr_t p = 0; | |
try{ | |
while(first != last){ | |
p = get_from_pool(); | |
if(!p){ | |
insert_iter_fwd_alloc(it+i, first, last, n-i, alloc_version()); | |
break; | |
} | |
//This can throw | |
boost::container::construct_in_place(&*p, first); | |
p->set_pointer(void_ptr(&*(it+i))); | |
++first; | |
*(it+i)=p; | |
++i; | |
} | |
} | |
catch(...){ | |
put_in_pool(p); | |
impl.erase(it+i,it+n); | |
this->align_nodes(it+i,get_last_align()); | |
throw; | |
} | |
} | |
template <class InputIterator> | |
void insert_iter(const_iterator position, InputIterator first, InputIterator last, boost::mpl::false_) | |
{ | |
this->insert_not_iter(position, first, last); | |
} | |
static void swap_impl(stable_vector& x,stable_vector& y) | |
{ | |
using std::swap; | |
swap(x.get_al(),y.get_al()); | |
swap(x.impl,y.impl); | |
swap(x.internal_data.pool_size, y.internal_data.pool_size); | |
x.readjust_end_node(); | |
y.readjust_end_node(); | |
} | |
#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) | |
bool invariant()const | |
{ | |
if(impl.empty()) | |
return !capacity() && !size(); | |
if(get_end_node() != *(impl.end() - ExtraPointers)){ | |
return false; | |
} | |
for(const_impl_iterator it=impl.begin(),it_end=get_last_align();it!=it_end;++it){ | |
if(node_ptr_cast(*it)->up != &*it) | |
return false; | |
} | |
size_type n = capacity()-size(); | |
const void_ptr &pool_head = impl.back(); | |
size_type num_pool = 0; | |
node_type_ptr_t p = node_ptr_cast(pool_head); | |
while(p){ | |
++num_pool; | |
p = p->up; | |
} | |
return n >= num_pool; | |
} | |
class invariant_checker:private boost::noncopyable | |
{ | |
const stable_vector* p; | |
public: | |
invariant_checker(const stable_vector& v):p(&v){} | |
~invariant_checker(){BOOST_ASSERT(p->invariant());} | |
void touch(){} | |
}; | |
#endif | |
struct ebo_holder | |
: node_allocator_type | |
{ | |
ebo_holder(const allocator_type &a) | |
: node_allocator_type(a), pool_size(0), end_node() | |
{ | |
end_node.set_pointer(void_ptr(&end_node.up)); | |
} | |
size_type pool_size; | |
node_type_base_t end_node; | |
} internal_data; | |
node_allocator_type &get_al() { return internal_data; } | |
const node_allocator_type &get_al() const { return internal_data; } | |
impl_type impl; | |
/// @endcond | |
}; | |
template <typename T,typename Allocator> | |
bool operator==(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); | |
} | |
template <typename T,typename Allocator> | |
bool operator< (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); | |
} | |
template <typename T,typename Allocator> | |
bool operator!=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return !(x==y); | |
} | |
template <typename T,typename Allocator> | |
bool operator> (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return y<x; | |
} | |
template <typename T,typename Allocator> | |
bool operator>=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return !(x<y); | |
} | |
template <typename T,typename Allocator> | |
bool operator<=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) | |
{ | |
return !(x>y); | |
} | |
// specialized algorithms: | |
template <typename T, typename Allocator> | |
void swap(stable_vector<T,Allocator>& x,stable_vector<T,Allocator>& y) | |
{ | |
x.swap(y); | |
} | |
/// @cond | |
#undef STABLE_VECTOR_CHECK_INVARIANT | |
/// @endcond | |
}} | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP | |
#endif //BOOST_CONTAINER_STABLE_VECTOR_HPP |