summaryrefslogtreecommitdiff
path: root/boost/container/detail
diff options
context:
space:
mode:
authorAnas Nashif <anas.nashif@intel.com>2012-10-30 12:57:26 -0700
committerAnas Nashif <anas.nashif@intel.com>2012-10-30 12:57:26 -0700
commit1a78a62555be32868418fe52f8e330c9d0f95d5a (patch)
treed3765a80e7d3b9640ec2e930743630cd6b9fce2b /boost/container/detail
downloadboost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.gz
boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.bz2
boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.zip
Imported Upstream version 1.49.0upstream/1.49.0
Diffstat (limited to 'boost/container/detail')
-rw-r--r--boost/container/detail/adaptive_node_pool_impl.hpp648
-rw-r--r--boost/container/detail/advanced_insert_int.hpp428
-rw-r--r--boost/container/detail/algorithms.hpp60
-rw-r--r--boost/container/detail/allocation_type.hpp54
-rw-r--r--boost/container/detail/config_begin.hpp48
-rw-r--r--boost/container/detail/config_end.hpp17
-rw-r--r--boost/container/detail/destroyers.hpp163
-rw-r--r--boost/container/detail/flat_tree.hpp822
-rw-r--r--boost/container/detail/function_detector.hpp88
-rw-r--r--boost/container/detail/iterators.hpp548
-rw-r--r--boost/container/detail/math_functions.hpp113
-rw-r--r--boost/container/detail/mpl.hpp160
-rw-r--r--boost/container/detail/multiallocation_chain.hpp254
-rw-r--r--boost/container/detail/node_alloc_holder.hpp488
-rw-r--r--boost/container/detail/node_pool_impl.hpp367
-rw-r--r--boost/container/detail/pair.hpp320
-rw-r--r--boost/container/detail/pool_common.hpp52
-rw-r--r--boost/container/detail/preprocessor.hpp178
-rw-r--r--boost/container/detail/stored_ref.hpp92
-rw-r--r--boost/container/detail/transform_iterator.hpp176
-rw-r--r--boost/container/detail/tree.hpp1154
-rw-r--r--boost/container/detail/type_traits.hpp203
-rw-r--r--boost/container/detail/utilities.hpp271
-rw-r--r--boost/container/detail/value_init.hpp45
-rw-r--r--boost/container/detail/variadic_templates_tools.hpp153
-rw-r--r--boost/container/detail/version_type.hpp92
-rw-r--r--boost/container/detail/workaround.hpp31
27 files changed, 7025 insertions, 0 deletions
diff --git a/boost/container/detail/adaptive_node_pool_impl.hpp b/boost/container/detail/adaptive_node_pool_impl.hpp
new file mode 100644
index 0000000000..36495795fb
--- /dev/null
+++ b/boost/container/detail/adaptive_node_pool_impl.hpp
@@ -0,0 +1,648 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
+#define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/container_fwd.hpp>
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/utilities.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/intrusive/set.hpp>
+#include <boost/intrusive/slist.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/math_functions.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/pool_common.hpp>
+#include <boost/assert.hpp>
+#include <cstddef>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class size_type>
+struct hdr_offset_holder_t
+{
+ hdr_offset_holder_t(size_type offset = 0)
+ : hdr_offset(offset)
+ {}
+ size_type hdr_offset;
+};
+
+template<class VoidPointer, class SizeType>
+struct adaptive_pool_types
+{
+ typedef VoidPointer void_pointer;
+ typedef typename bi::make_set_base_hook
+ < bi::void_pointer<void_pointer>
+ , bi::optimize_size<true>
+ , bi::constant_time_size<false>
+ , bi::link_mode<bi::normal_link> >::type multiset_hook_t;
+
+ typedef hdr_offset_holder_t<SizeType> hdr_offset_holder;
+
+ struct block_info_t
+ :
+ public hdr_offset_holder,
+ public multiset_hook_t
+ {
+ typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t;
+ //An intrusive list of free node from this block
+ free_nodes_t free_nodes;
+ friend bool operator <(const block_info_t &l, const block_info_t &r)
+ {
+// { return l.free_nodes.size() < r.free_nodes.size(); }
+ //Let's order blocks first by free nodes and then by address
+ //so that highest address fully free blocks are deallocated.
+ //This improves returning memory to the OS (trimming).
+ const bool is_less = l.free_nodes.size() < r.free_nodes.size();
+ const bool is_equal = l.free_nodes.size() == r.free_nodes.size();
+ return is_less || (is_equal && (&l < &r));
+ }
+
+ friend bool operator ==(const block_info_t &l, const block_info_t &r)
+ { return &l == &r; }
+ };
+ typedef typename bi::make_multiset
+ <block_info_t, bi::base_hook<multiset_hook_t> >::type block_multiset_t;
+};
+
+template<class size_type>
+inline size_type calculate_alignment
+ ( size_type overhead_percent, size_type real_node_size
+ , size_type hdr_size, size_type hdr_offset_size, size_type payload_per_allocation)
+{
+ //to-do: handle real_node_size != node_size
+ const size_type divisor = overhead_percent*real_node_size;
+ const size_type dividend = hdr_offset_size*100;
+ size_type elements_per_subblock = (dividend - 1)/divisor + 1;
+ size_type candidate_power_of_2 =
+ upper_power_of_2(elements_per_subblock*real_node_size + hdr_offset_size);
+ bool overhead_satisfied = false;
+ //Now calculate the wors-case overhead for a subblock
+ const size_type max_subblock_overhead = hdr_size + payload_per_allocation;
+ while(!overhead_satisfied){
+ elements_per_subblock = (candidate_power_of_2 - max_subblock_overhead)/real_node_size;
+ const size_type overhead_size = candidate_power_of_2 - elements_per_subblock*real_node_size;
+ if(overhead_size*100/candidate_power_of_2 < overhead_percent){
+ overhead_satisfied = true;
+ }
+ else{
+ candidate_power_of_2 <<= 1;
+ }
+ }
+ return candidate_power_of_2;
+}
+
+template<class size_type>
+inline void calculate_num_subblocks
+ (size_type alignment, size_type real_node_size, size_type elements_per_block
+ , size_type &num_subblocks, size_type &real_num_node, size_type overhead_percent
+ , size_type hdr_size, size_type hdr_offset_size, size_type payload_per_allocation)
+{
+ size_type elements_per_subblock = (alignment - hdr_offset_size)/real_node_size;
+ size_type possible_num_subblock = (elements_per_block - 1)/elements_per_subblock + 1;
+ size_type hdr_subblock_elements = (alignment - hdr_size - payload_per_allocation)/real_node_size;
+ while(((possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements) < elements_per_block){
+ ++possible_num_subblock;
+ }
+ elements_per_subblock = (alignment - hdr_offset_size)/real_node_size;
+ bool overhead_satisfied = false;
+ while(!overhead_satisfied){
+ const size_type total_data = (elements_per_subblock*(possible_num_subblock-1) + hdr_subblock_elements)*real_node_size;
+ const size_type total_size = alignment*possible_num_subblock;
+ if((total_size - total_data)*100/total_size < overhead_percent){
+ overhead_satisfied = true;
+ }
+ else{
+ ++possible_num_subblock;
+ }
+ }
+ num_subblocks = possible_num_subblock;
+ real_num_node = (possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements;
+}
+
+template<class SegmentManagerBase, bool AlignOnly = false>
+class private_adaptive_node_pool_impl
+{
+ //Non-copyable
+ private_adaptive_node_pool_impl();
+ private_adaptive_node_pool_impl(const private_adaptive_node_pool_impl &);
+ private_adaptive_node_pool_impl &operator=(const private_adaptive_node_pool_impl &);
+ typedef private_adaptive_node_pool_impl this_type;
+
+ typedef typename SegmentManagerBase::void_pointer void_pointer;
+ static const typename SegmentManagerBase::
+ size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation;
+ typedef bool_<AlignOnly> IsAlignOnly;
+ typedef true_ AlignOnlyTrue;
+ typedef false_ AlignOnlyFalse;
+
+ public:
+ typedef typename node_slist<void_pointer>::node_t node_t;
+ typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t;
+ typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain;
+ typedef typename SegmentManagerBase::size_type size_type;
+
+ private:
+ typedef typename adaptive_pool_types<void_pointer, size_type>::block_info_t block_info_t;
+ typedef typename adaptive_pool_types<void_pointer, size_type>::block_multiset_t block_multiset_t;
+ typedef typename block_multiset_t::iterator block_iterator;
+ typedef typename adaptive_pool_types<void_pointer, size_type>::hdr_offset_holder hdr_offset_holder;
+
+ static const size_type MaxAlign = alignment_of<node_t>::value;
+ static const size_type HdrSize = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign;
+ static const size_type HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign;
+
+
+ public:
+ //!Segment manager typedef
+ typedef SegmentManagerBase segment_manager_base_type;
+
+ //!Constructor from a segment manager. Never throws
+ private_adaptive_node_pool_impl
+ ( segment_manager_base_type *segment_mngr_base
+ , size_type node_size
+ , size_type nodes_per_block
+ , size_type max_free_blocks
+ , unsigned char overhead_percent
+ )
+ : m_max_free_blocks(max_free_blocks)
+ , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value)))
+ //Round the size to a power of two value.
+ //This is the total memory size (including payload) that we want to
+ //allocate from the general-purpose allocator
+ , m_real_block_alignment
+ (AlignOnly ?
+ upper_power_of_2(HdrSize + m_real_node_size*nodes_per_block) :
+ calculate_alignment( (size_type)overhead_percent, m_real_node_size
+ , HdrSize, HdrOffsetSize, PayloadPerAllocation))
+ //This is the real number of nodes per block
+ , m_num_subblocks(0)
+ , m_real_num_node(AlignOnly ? (m_real_block_alignment - PayloadPerAllocation - HdrSize)/m_real_node_size : 0)
+ //General purpose allocator
+ , mp_segment_mngr_base(segment_mngr_base)
+ , m_block_multiset()
+ , m_totally_free_blocks(0)
+ {
+ if(!AlignOnly){
+ calculate_num_subblocks
+ ( m_real_block_alignment
+ , m_real_node_size
+ , nodes_per_block
+ , m_num_subblocks
+ , m_real_num_node
+ , (size_type)overhead_percent
+ , HdrSize
+ , HdrOffsetSize
+ , PayloadPerAllocation);
+ }
+ }
+
+ //!Destructor. Deallocates all allocated blocks. Never throws
+ ~private_adaptive_node_pool_impl()
+ { priv_clear(); }
+
+ size_type get_real_num_node() const
+ { return m_real_num_node; }
+
+ //!Returns the segment manager. Never throws
+ segment_manager_base_type* get_segment_manager_base()const
+ { return container_detail::to_raw_pointer(mp_segment_mngr_base); }
+
+ //!Allocates array of count elements. Can throw
+ void *allocate_node()
+ {
+ priv_invariants();
+ //If there are no free nodes we allocate a new block
+ if (m_block_multiset.empty()){
+ priv_alloc_block(1);
+ }
+ //We take the first free node the multiset can't be empty
+ return priv_take_first_node();
+ }
+
+ //!Deallocates an array pointed by ptr. Never throws
+ void deallocate_node(void *pElem)
+ {
+ multiallocation_chain chain;
+ chain.push_front(void_pointer(pElem));
+ this->priv_reinsert_nodes_in_block(chain, 1);
+ //Update free block count<
+ if(m_totally_free_blocks > m_max_free_blocks){
+ this->priv_deallocate_free_blocks(m_max_free_blocks);
+ }
+ priv_invariants();
+ }
+
+ //!Allocates n nodes.
+ //!Can throw
+ multiallocation_chain allocate_nodes(const size_type n)
+ {
+ multiallocation_chain chain;
+ size_type i = 0;
+ try{
+ priv_invariants();
+ while(i != n){
+ //If there are no free nodes we allocate all needed blocks
+ if (m_block_multiset.empty()){
+ priv_alloc_block(((n - i) - 1)/m_real_num_node + 1);
+ }
+ free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes;
+ const size_type free_nodes_count_before = free_nodes.size();
+ if(free_nodes_count_before == m_real_num_node){
+ --m_totally_free_blocks;
+ }
+ const size_type num_elems = ((n-i) < free_nodes_count_before) ? (n-i) : free_nodes_count_before;
+ for(size_type j = 0; j != num_elems; ++j){
+ void *new_node = &free_nodes.front();
+ free_nodes.pop_front();
+ chain.push_back(new_node);
+ }
+
+ if(free_nodes.empty()){
+ m_block_multiset.erase(m_block_multiset.begin());
+ }
+ i += num_elems;
+ }
+ }
+ catch(...){
+ this->deallocate_nodes(boost::move(chain));
+ throw;
+ }
+ priv_invariants();
+ return boost::move(chain);
+ }
+
+ //!Deallocates a linked list of nodes. Never throws
+ void deallocate_nodes(multiallocation_chain nodes)
+ {
+ this->priv_reinsert_nodes_in_block(nodes, nodes.size());
+ if(m_totally_free_blocks > m_max_free_blocks){
+ this->priv_deallocate_free_blocks(m_max_free_blocks);
+ }
+ }
+
+ void deallocate_free_blocks()
+ { this->priv_deallocate_free_blocks(0); }
+
+ size_type num_free_nodes()
+ {
+ typedef typename block_multiset_t::const_iterator citerator;
+ size_type count = 0;
+ citerator it (m_block_multiset.begin()), itend(m_block_multiset.end());
+ for(; it != itend; ++it){
+ count += it->free_nodes.size();
+ }
+ return count;
+ }
+
+ void swap(private_adaptive_node_pool_impl &other)
+ {
+ BOOST_ASSERT(m_max_free_blocks == other.m_max_free_blocks);
+ BOOST_ASSERT(m_real_node_size == other.m_real_node_size);
+ BOOST_ASSERT(m_real_block_alignment == other.m_real_block_alignment);
+ BOOST_ASSERT(m_real_num_node == other.m_real_num_node);
+ std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base);
+ std::swap(m_totally_free_blocks, other.m_totally_free_blocks);
+ m_block_multiset.swap(other.m_block_multiset);
+ }
+
+ //Deprecated, use deallocate_free_blocks
+ void deallocate_free_chunks()
+ { this->priv_deallocate_free_blocks(0); }
+
+ private:
+ void priv_deallocate_free_blocks(size_type max_free_blocks)
+ {
+ priv_invariants();
+ //Now check if we've reached the free nodes limit
+ //and check if we have free blocks. If so, deallocate as much
+ //as we can to stay below the limit
+ for( block_iterator itend = m_block_multiset.end()
+ ; m_totally_free_blocks > max_free_blocks
+ ; --m_totally_free_blocks
+ ){
+ BOOST_ASSERT(!m_block_multiset.empty());
+ block_iterator it = itend;
+ --it;
+ BOOST_ASSERT(it->free_nodes.size() == m_real_num_node);
+ m_block_multiset.erase_and_dispose(it, block_destroyer(this));
+ }
+ }
+
+ void priv_reinsert_nodes_in_block(multiallocation_chain &chain, size_type n)
+ {
+ block_iterator block_it(m_block_multiset.end());
+ while(n--){
+ void *pElem = container_detail::to_raw_pointer(chain.front());
+ chain.pop_front();
+ priv_invariants();
+ block_info_t *block_info = this->priv_block_from_node(pElem);
+ BOOST_ASSERT(block_info->free_nodes.size() < m_real_num_node);
+ //We put the node at the beginning of the free node list
+ node_t * to_deallocate = static_cast<node_t*>(pElem);
+ block_info->free_nodes.push_front(*to_deallocate);
+
+ block_iterator this_block(block_multiset_t::s_iterator_to(*block_info));
+ block_iterator next_block(this_block);
+ ++next_block;
+
+ //Cache the free nodes from the block
+ size_type this_block_free_nodes = this_block->free_nodes.size();
+
+ if(this_block_free_nodes == 1){
+ m_block_multiset.insert(m_block_multiset.begin(), *block_info);
+ }
+ else{
+ block_iterator next_block(this_block);
+ ++next_block;
+ if(next_block != block_it){
+ size_type next_free_nodes = next_block->free_nodes.size();
+ if(this_block_free_nodes > next_free_nodes){
+ //Now move the block to the new position
+ m_block_multiset.erase(this_block);
+ m_block_multiset.insert(*block_info);
+ }
+ }
+ }
+ //Update free block count
+ if(this_block_free_nodes == m_real_num_node){
+ ++m_totally_free_blocks;
+ }
+ priv_invariants();
+ }
+ }
+
+ node_t *priv_take_first_node()
+ {
+ BOOST_ASSERT(m_block_multiset.begin() != m_block_multiset.end());
+ //We take the first free node the multiset can't be empty
+ free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes;
+ node_t *first_node = &free_nodes.front();
+ const size_type free_nodes_count = free_nodes.size();
+ BOOST_ASSERT(0 != free_nodes_count);
+ free_nodes.pop_front();
+ if(free_nodes_count == 1){
+ m_block_multiset.erase(m_block_multiset.begin());
+ }
+ else if(free_nodes_count == m_real_num_node){
+ --m_totally_free_blocks;
+ }
+ priv_invariants();
+ return first_node;
+ }
+
+ class block_destroyer;
+ friend class block_destroyer;
+
+ class block_destroyer
+ {
+ public:
+ block_destroyer(const this_type *impl)
+ : mp_impl(impl)
+ {}
+
+ void operator()(typename block_multiset_t::pointer to_deallocate)
+ { return this->do_destroy(to_deallocate, IsAlignOnly()); }
+
+ private:
+ void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyTrue)
+ {
+ size_type free_nodes = to_deallocate->free_nodes.size();
+ (void)free_nodes;
+ BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node);
+ mp_impl->mp_segment_mngr_base->deallocate(to_deallocate);
+ }
+
+ void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyFalse)
+ {
+ size_type free_nodes = to_deallocate->free_nodes.size();
+ (void)free_nodes;
+ BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node);
+ BOOST_ASSERT(0 == to_deallocate->hdr_offset);
+ hdr_offset_holder *hdr_off_holder = mp_impl->priv_first_subblock_from_block(container_detail::to_raw_pointer(to_deallocate));
+ mp_impl->mp_segment_mngr_base->deallocate(hdr_off_holder);
+ }
+
+ const this_type *mp_impl;
+ };
+
+ //This macro will activate invariant checking. Slow, but helpful for debugging the code.
+ //#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
+ void priv_invariants()
+ #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
+ #undef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
+ {
+ //We iterate through the block tree to free the memory
+ block_iterator it(m_block_multiset.begin()),
+ itend(m_block_multiset.end()), to_deallocate;
+ if(it != itend){
+ for(++it; it != itend; ++it){
+ block_iterator prev(it);
+ --prev;
+ size_type sp = prev->free_nodes.size(),
+ si = it->free_nodes.size();
+ BOOST_ASSERT(sp <= si);
+ (void)sp; (void)si;
+ }
+ }
+ //Check that the total free nodes are correct
+ it = m_block_multiset.begin();
+ itend = m_block_multiset.end();
+ size_type total_free_nodes = 0;
+ for(; it != itend; ++it){
+ total_free_nodes += it->free_nodes.size();
+ }
+ BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*m_real_num_node);
+
+ //Check that the total totally free blocks are correct
+ it = m_block_multiset.begin();
+ itend = m_block_multiset.end();
+ total_free = 0;
+ for(; it != itend; ++it){
+ total_free += it->free_nodes.size() == m_real_num_node;
+ }
+ BOOST_ASSERT(total_free >= m_totally_free_blocks);
+
+ if(!AlignOnly){
+ //Check that header offsets are correct
+ it = m_block_multiset.begin();
+ for(; it != itend; ++it){
+ hdr_offset_holder *hdr_off_holder = priv_first_subblock_from_block(&*it);
+ for(size_type i = 0, max = m_num_subblocks; i < max; ++i){
+ BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(&*it)- reinterpret_cast<char*>(hdr_off_holder)));
+ BOOST_ASSERT(0 == ((size_type)hdr_off_holder & (m_real_block_alignment - 1)));
+ BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1)));
+ hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + m_real_block_alignment);
+ }
+ }
+ }
+ }
+ #else
+ {} //empty
+ #endif
+
+ //!Deallocates all used memory. Never throws
+ void priv_clear()
+ {
+ #ifndef NDEBUG
+ block_iterator it = m_block_multiset.begin();
+ block_iterator itend = m_block_multiset.end();
+ size_type num_free_nodes = 0;
+ for(; it != itend; ++it){
+ //Check for memory leak
+ BOOST_ASSERT(it->free_nodes.size() == m_real_num_node);
+ ++num_free_nodes;
+ }
+ BOOST_ASSERT(num_free_nodes == m_totally_free_blocks);
+ #endif
+ //Check for memory leaks
+ priv_invariants();
+ m_block_multiset.clear_and_dispose(block_destroyer(this));
+ m_totally_free_blocks = 0;
+ }
+
+ block_info_t *priv_block_from_node(void *node, AlignOnlyFalse) const
+ {
+ hdr_offset_holder *hdr_off_holder =
+ reinterpret_cast<hdr_offset_holder*>((std::size_t)node & size_type(~(m_real_block_alignment - 1)));
+ BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1)));
+ BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1)));
+ block_info_t *block = reinterpret_cast<block_info_t *>
+ (reinterpret_cast<char*>(hdr_off_holder) + hdr_off_holder->hdr_offset);
+ BOOST_ASSERT(block->hdr_offset == 0);
+ return block;
+ }
+
+ block_info_t *priv_block_from_node(void *node, AlignOnlyTrue) const
+ {
+ return (block_info_t *)((std::size_t)node & std::size_t(~(m_real_block_alignment - 1)));
+ }
+
+ block_info_t *priv_block_from_node(void *node) const
+ { return priv_block_from_node(node, IsAlignOnly()); }
+
+ hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block) const
+ {
+ hdr_offset_holder *hdr_off_holder = reinterpret_cast<hdr_offset_holder*>
+ (reinterpret_cast<char*>(block) - (m_num_subblocks-1)*m_real_block_alignment);
+ BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder)));
+ BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1)));
+ BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1)));
+ return hdr_off_holder;
+ }
+
+ //!Allocates a several blocks of nodes. Can throw
+ void priv_alloc_block(size_type n, AlignOnlyTrue)
+ {
+ size_type real_block_size = m_real_block_alignment - PayloadPerAllocation;
+ for(size_type i = 0; i != n; ++i){
+ //We allocate a new NodeBlock and put it the last
+ //element of the tree
+ char *mem_address = static_cast<char*>
+ (mp_segment_mngr_base->allocate_aligned(real_block_size, m_real_block_alignment));
+ if(!mem_address) throw std::bad_alloc();
+ ++m_totally_free_blocks;
+ block_info_t *c_info = new(mem_address)block_info_t();
+ m_block_multiset.insert(m_block_multiset.end(), *c_info);
+
+ mem_address += HdrSize;
+ //We initialize all Nodes in Node Block to insert
+ //them in the free Node list
+ typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin();
+ for(size_type i = 0; i < m_real_num_node; ++i){
+ prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *(node_t*)mem_address);
+ mem_address += m_real_node_size;
+ }
+ }
+ }
+
+ void priv_alloc_block(size_type n, AlignOnlyFalse)
+ {
+ size_type real_block_size = m_real_block_alignment*m_num_subblocks - PayloadPerAllocation;
+ size_type elements_per_subblock = (m_real_block_alignment - HdrOffsetSize)/m_real_node_size;
+ size_type hdr_subblock_elements = (m_real_block_alignment - HdrSize - PayloadPerAllocation)/m_real_node_size;
+
+ for(size_type i = 0; i != n; ++i){
+ //We allocate a new NodeBlock and put it the last
+ //element of the tree
+ char *mem_address = static_cast<char*>
+ (mp_segment_mngr_base->allocate_aligned(real_block_size, m_real_block_alignment));
+ if(!mem_address) throw std::bad_alloc();
+ ++m_totally_free_blocks;
+
+ //First initialize header information on the last subblock
+ char *hdr_addr = mem_address + m_real_block_alignment*(m_num_subblocks-1);
+ block_info_t *c_info = new(hdr_addr)block_info_t();
+ //Some structural checks
+ BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder*>(c_info)->hdr_offset) ==
+ static_cast<void*>(c_info));
+ typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin();
+ for( size_type subblock = 0, maxsubblock = m_num_subblocks - 1
+ ; subblock < maxsubblock
+ ; ++subblock, mem_address += m_real_block_alignment){
+ //Initialize header offset mark
+ new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address));
+ char *pNode = mem_address + HdrOffsetSize;
+ for(size_type i = 0; i < elements_per_subblock; ++i){
+ prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t);
+ pNode += m_real_node_size;
+ }
+ }
+ {
+ char *pNode = hdr_addr + HdrSize;
+ //We initialize all Nodes in Node Block to insert
+ //them in the free Node list
+ for(size_type i = 0; i < hdr_subblock_elements; ++i){
+ prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t);
+ pNode += m_real_node_size;
+ }
+ }
+ //Insert the block after the free node list is full
+ m_block_multiset.insert(m_block_multiset.end(), *c_info);
+ }
+ }
+
+ //!Allocates a block of nodes. Can throw std::bad_alloc
+ void priv_alloc_block(size_type n)
+ { return priv_alloc_block(n, IsAlignOnly()); }
+
+ private:
+ typedef typename boost::intrusive::pointer_traits
+ <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t;
+ const size_type m_max_free_blocks;
+ const size_type m_real_node_size;
+ //Round the size to a power of two value.
+ //This is the total memory size (including payload) that we want to
+ //allocate from the general-purpose allocator
+ const size_type m_real_block_alignment;
+ size_type m_num_subblocks;
+ //This is the real number of nodes per block
+ //const
+ size_type m_real_num_node;
+ segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager
+ block_multiset_t m_block_multiset; //Intrusive block list
+ size_type m_totally_free_blocks; //Free blocks
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
diff --git a/boost/container/detail/advanced_insert_int.hpp b/boost/container/detail/advanced_insert_int.hpp
new file mode 100644
index 0000000000..58199c7aa8
--- /dev/null
+++ b/boost/container/detail/advanced_insert_int.hpp
@@ -0,0 +1,428 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2008-2011. 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_ADVANCED_INSERT_INT_HPP
+#define BOOST_CONTAINER_ADVANCED_INSERT_INT_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+#include <boost/move/move.hpp>
+#include <iterator> //std::iterator_traits
+#include <boost/assert.hpp>
+
+namespace boost { namespace container { namespace container_detail {
+
+//This class will be interface for operations dependent on FwdIt types used advanced_insert_aux_impl
+template<class Iterator>
+struct advanced_insert_aux_int
+{
+ typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
+ virtual void copy_remaining_to(Iterator p) = 0;
+ virtual void uninitialized_copy_remaining_to(Iterator p) = 0;
+ virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first) = 0;
+ virtual void copy_some_and_update(Iterator pos, difference_type division_count, bool first) = 0;
+ virtual ~advanced_insert_aux_int() {}
+};
+
+//This class template will adapt each FwIt types to advanced_insert_aux_int
+template<class A, class FwdIt, class Iterator>
+struct advanced_insert_aux_proxy
+ : public advanced_insert_aux_int<Iterator>
+{
+ typedef boost::container::allocator_traits<A> alloc_traits;
+ typedef typename allocator_traits<A>::size_type size_type;
+ typedef typename allocator_traits<A>::value_type value_type;
+ typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type;
+
+ advanced_insert_aux_proxy(A& a, FwdIt first, FwdIt last)
+ : a_(a), first_(first), last_(last)
+ {}
+
+ virtual ~advanced_insert_aux_proxy()
+ {}
+
+ virtual void copy_remaining_to(Iterator p)
+ { ::boost::copy_or_move(first_, last_, p); }
+
+ virtual void uninitialized_copy_remaining_to(Iterator p)
+ { ::boost::container::uninitialized_copy_or_move_alloc(a_, first_, last_, p); }
+
+ virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first_n)
+ {
+ FwdIt mid = first_;
+ std::advance(mid, division_count);
+ if(first_n){
+ ::boost::container::uninitialized_copy_or_move_alloc(a_, first_, mid, pos);
+ first_ = mid;
+ }
+ else{
+ ::boost::container::uninitialized_copy_or_move_alloc(a_, mid, last_, pos);
+ last_ = mid;
+ }
+ }
+
+ virtual void copy_some_and_update(Iterator pos, difference_type division_count, bool first_n)
+ {
+ FwdIt mid = first_;
+ std::advance(mid, division_count);
+ if(first_n){
+ ::boost::copy_or_move(first_, mid, pos);
+ first_ = mid;
+ }
+ else{
+ ::boost::copy_or_move(mid, last_, pos);
+ last_ = mid;
+ }
+ }
+ A &a_;
+ FwdIt first_, last_;
+};
+
+//This class template will adapt default construction insertions to advanced_insert_aux_int
+template<class A, class Iterator>
+struct default_construct_aux_proxy
+ : public advanced_insert_aux_int<Iterator>
+{
+ typedef boost::container::allocator_traits<A> alloc_traits;
+ typedef typename allocator_traits<A>::size_type size_type;
+ typedef typename allocator_traits<A>::value_type value_type;
+ typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type;
+
+ default_construct_aux_proxy(A &a, size_type count)
+ : a_(a), count_(count)
+ {}
+
+ virtual ~default_construct_aux_proxy()
+ {}
+
+ virtual void copy_remaining_to(Iterator)
+ { //This should never be called with any count
+ BOOST_ASSERT(count_ == 0);
+ }
+
+ virtual void uninitialized_copy_remaining_to(Iterator p)
+ { this->priv_uninitialized_copy(p, count_); }
+
+ virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first_n)
+ {
+ size_type new_count;
+ if(first_n){
+ new_count = division_count;
+ }
+ else{
+ BOOST_ASSERT(difference_type(count_)>= division_count);
+ new_count = count_ - division_count;
+ }
+ this->priv_uninitialized_copy(pos, new_count);
+ }
+
+ virtual void copy_some_and_update(Iterator , difference_type division_count, bool first_n)
+ {
+ BOOST_ASSERT(count_ == 0);
+ size_type new_count;
+ if(first_n){
+ new_count = division_count;
+ }
+ else{
+ BOOST_ASSERT(difference_type(count_)>= division_count);
+ new_count = count_ - division_count;
+ }
+ //This function should never called with a count different to zero
+ BOOST_ASSERT(new_count == 0);
+ (void)new_count;
+ }
+
+ private:
+ void priv_uninitialized_copy(Iterator p, const size_type n)
+ {
+ BOOST_ASSERT(n <= count_);
+ Iterator orig_p = p;
+ size_type i = 0;
+ try{
+ for(; i < n; ++i, ++p){
+ alloc_traits::construct(a_, container_detail::to_raw_pointer(&*p));
+ }
+ }
+ catch(...){
+ while(i--){
+ alloc_traits::destroy(a_, container_detail::to_raw_pointer(&*orig_p++));
+ }
+ throw;
+ }
+ count_ -= n;
+ }
+ A &a_;
+ size_type count_;
+};
+
+}}} //namespace boost { namespace container { namespace container_detail {
+
+#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+#include <boost/container/detail/variadic_templates_tools.hpp>
+#include <boost/container/detail/stored_ref.hpp>
+#include <boost/move/move.hpp>
+#include <typeinfo>
+//#include <iostream> //For debugging purposes
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+
+//This class template will adapt emplace construction insertions of movable types
+//to advanced_insert_aux_int
+template<class A, class Iterator, class ...Args>
+struct advanced_insert_aux_non_movable_emplace
+ : public advanced_insert_aux_int<Iterator>
+{
+ typedef boost::container::allocator_traits<A> alloc_traits;
+ typedef typename allocator_traits<A>::size_type size_type;
+ typedef typename allocator_traits<A>::value_type value_type;
+ typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type;
+ typedef typename build_number_seq<sizeof...(Args)>::type index_tuple_t;
+
+ explicit advanced_insert_aux_non_movable_emplace(A &a, Args&&... args)
+ : a_(a)
+ , args_(args...)
+ , used_(false)
+ {}
+
+ ~advanced_insert_aux_non_movable_emplace()
+ {}
+
+ virtual void copy_remaining_to(Iterator)
+ //This code can't be called since value_type is not movable or copyable
+ { BOOST_ASSERT(false); }
+
+ virtual void uninitialized_copy_remaining_to(Iterator p)
+ { this->priv_uninitialized_copy_remaining_to(index_tuple_t(), p); }
+
+ virtual void uninitialized_copy_some_and_update(Iterator p, difference_type division_count, bool first_n)
+ { this->priv_uninitialized_copy_some_and_update(index_tuple_t(), p, division_count, first_n); }
+
+ virtual void copy_some_and_update(Iterator, difference_type, bool )
+ //This code can't be called since value_type is not movable or copyable
+ { BOOST_ASSERT(false); }
+
+ private:
+ template<int ...IdxPack>
+ void priv_uninitialized_copy_some_and_update(const index_tuple<IdxPack...>&, Iterator p, difference_type division_count, bool first_n)
+ {
+ BOOST_ASSERT(division_count <=1);
+ if((first_n && division_count == 1) || (!first_n && division_count == 0)){
+ if(!used_){
+ alloc_traits::construct( a_
+ , container_detail::to_raw_pointer(&*p)
+ , ::boost::container::container_detail::
+ stored_ref<Args>::forward(get<IdxPack>(args_))...
+ );
+ used_ = true;
+ }
+ }
+ }
+
+ template<int ...IdxPack>
+ void priv_uninitialized_copy_remaining_to(const index_tuple<IdxPack...>&, Iterator p)
+ {
+ if(!used_){
+ alloc_traits::construct( a_
+ , container_detail::to_raw_pointer(&*p)
+ , ::boost::container::container_detail::
+ stored_ref<Args>::forward(get<IdxPack>(args_))...
+ );
+ used_ = true;
+ }
+ }
+
+ protected:
+ A &a_;
+ tuple<Args&...> args_;
+ bool used_;
+};
+
+//This class template will adapt emplace construction insertions of movable types
+//to advanced_insert_aux_int
+template<class A, class Iterator, class ...Args>
+struct advanced_insert_aux_emplace
+ : public advanced_insert_aux_non_movable_emplace<A, Iterator, Args...>
+{
+ typedef advanced_insert_aux_non_movable_emplace<A, Iterator, Args...> base_t;
+ typedef typename base_t::value_type value_type;
+ typedef typename base_t::difference_type difference_type;
+ typedef typename base_t::index_tuple_t index_tuple_t;
+
+ explicit advanced_insert_aux_emplace(A &a, Args&&... args)
+ : base_t(a, boost::forward<Args>(args)...)
+ {}
+
+ ~advanced_insert_aux_emplace()
+ {}
+
+ //Override only needed functions
+ virtual void copy_remaining_to(Iterator p)
+ { this->priv_copy_remaining_to(index_tuple_t(), p); }
+
+ virtual void copy_some_and_update(Iterator p, difference_type division_count, bool first_n)
+ { this->priv_copy_some_and_update(index_tuple_t(), p, division_count, first_n); }
+
+ private:
+ template<int ...IdxPack>
+ void priv_copy_remaining_to(const index_tuple<IdxPack...>&, Iterator p)
+ {
+ if(!this->used_){
+ *p = boost::move(value_type (
+ ::boost::container::container_detail::stored_ref<Args>::forward(get<IdxPack>(this->args_))...));
+ this->used_ = true;
+ }
+ }
+
+ template<int ...IdxPack>
+ void priv_copy_some_and_update(const index_tuple<IdxPack...>&, Iterator p, difference_type division_count, bool first_n)
+ {
+ BOOST_ASSERT(division_count <=1);
+ if((first_n && division_count == 1) || (!first_n && division_count == 0)){
+ if(!this->used_){
+ *p = boost::move(value_type(
+ ::boost::container::container_detail::stored_ref<Args>::forward(get<IdxPack>(this->args_))...));
+ this->used_ = true;
+ }
+ }
+ }
+};
+
+}}} //namespace boost { namespace container { namespace container_detail {
+
+#else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+#include <boost/container/detail/preprocessor.hpp>
+#include <boost/container/detail/value_init.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+#define BOOST_PP_LOCAL_MACRO(n) \
+template<class A, class Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, class P) > \
+struct BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_non_movable_emplace, n), arg) \
+ : public advanced_insert_aux_int<Iterator> \
+{ \
+ typedef boost::container::allocator_traits<A> alloc_traits; \
+ typedef typename allocator_traits<A>::size_type size_type; \
+ typedef typename allocator_traits<A>::value_type value_type; \
+ typedef typename advanced_insert_aux_int<Iterator>::difference_type \
+ difference_type; \
+ \
+ BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_non_movable_emplace, n), arg) \
+ ( A &a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \
+ : a_(a) \
+ , used_(false) \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_INIT, _) \
+ {} \
+ \
+ virtual void copy_remaining_to(Iterator) \
+ { BOOST_ASSERT(false); } \
+ \
+ virtual void uninitialized_copy_remaining_to(Iterator p) \
+ { \
+ if(!used_){ \
+ alloc_traits::construct \
+ ( a_ \
+ , container_detail::to_raw_pointer(&*p) \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \
+ ); \
+ used_ = true; \
+ } \
+ } \
+ \
+ virtual void uninitialized_copy_some_and_update \
+ (Iterator p, difference_type division_count, bool first_n) \
+ { \
+ BOOST_ASSERT(division_count <=1); \
+ if((first_n && division_count == 1) || (!first_n && division_count == 0)){ \
+ if(!used_){ \
+ alloc_traits::construct \
+ ( a_ \
+ , container_detail::to_raw_pointer(&*p) \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \
+ ); \
+ used_ = true; \
+ } \
+ } \
+ } \
+ \
+ virtual void copy_some_and_update(Iterator, difference_type, bool) \
+ { BOOST_ASSERT(false); } \
+ \
+ A &a_; \
+ bool used_; \
+ BOOST_PP_REPEAT(n, BOOST_CONTAINER_PP_PARAM_DEFINE, _) \
+}; \
+ \
+template<class A, class Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, class P) > \
+struct BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_emplace, n), arg) \
+ : BOOST_PP_CAT(BOOST_PP_CAT( \
+ advanced_insert_aux_non_movable_emplace, n), arg) \
+ < A, Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P) > \
+{ \
+ typedef BOOST_PP_CAT(BOOST_PP_CAT( \
+ advanced_insert_aux_non_movable_emplace, n), arg) \
+ <A, Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P) > base_t; \
+ typedef typename base_t::value_type value_type; \
+ typedef typename base_t::difference_type difference_type; \
+ \
+ BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_emplace, n), arg) \
+ ( A &a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \
+ : base_t(a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ) \
+ {} \
+ \
+ virtual void copy_remaining_to(Iterator p) \
+ { \
+ if(!this->used_){ \
+ value_type v BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \
+ BOOST_PP_RPAREN_IF(n); \
+ *p = boost::move(v); \
+ this->used_ = true; \
+ } \
+ } \
+ \
+ virtual void copy_some_and_update \
+ (Iterator p, difference_type division_count, bool first_n) \
+ { \
+ BOOST_ASSERT(division_count <=1); \
+ if((first_n && division_count == 1) || (!first_n && division_count == 0)){ \
+ if(!this->used_){ \
+ value_type v BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \
+ BOOST_PP_RPAREN_IF(n); \
+ *p = boost::move(v); \
+ this->used_ = true; \
+ } \
+ } \
+ } \
+}; \
+//!
+
+#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+#include BOOST_PP_LOCAL_ITERATE()
+
+}}} //namespace boost { namespace container { namespace container_detail {
+
+#endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_ADVANCED_INSERT_INT_HPP
diff --git a/boost/container/detail/algorithms.hpp b/boost/container/detail/algorithms.hpp
new file mode 100644
index 0000000000..a2713f50f1
--- /dev/null
+++ b/boost/container/detail/algorithms.hpp
@@ -0,0 +1,60 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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_DETAIL_ALGORITHMS_HPP
+#define BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+#include <boost/type_traits/has_trivial_copy.hpp>
+#include <boost/type_traits/has_trivial_assign.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
+
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/iterators.hpp>
+
+
+#include <cstring>
+
+namespace boost {
+namespace container {
+
+template<class A, class T, class InpIt>
+inline void construct_in_place(A &a, T* dest, InpIt source)
+{ boost::container::allocator_traits<A>::construct(a, dest, *source); }
+//#endif
+
+template<class A, class T, class U, class D>
+inline void construct_in_place(A &a, T *dest, default_construct_iterator<U, D>)
+{
+ boost::container::allocator_traits<A>::construct(a, dest);
+}
+
+template<class A, class T, class U, class EF, class D>
+inline void construct_in_place(A &a, T *dest, emplace_iterator<U, EF, D> ei)
+{
+ ei.construct_in_place(a, dest);
+}
+
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP
+
diff --git a/boost/container/detail/allocation_type.hpp b/boost/container/detail/allocation_type.hpp
new file mode 100644
index 0000000000..edad487c57
--- /dev/null
+++ b/boost/container/detail/allocation_type.hpp
@@ -0,0 +1,54 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_ALLOCATION_TYPE_HPP
+#define BOOST_CONTAINER_ALLOCATION_TYPE_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+namespace boost {
+namespace container {
+
+/// @cond
+enum allocation_type_v
+{
+ // constants for allocation commands
+ allocate_new_v = 0x01,
+ expand_fwd_v = 0x02,
+ expand_bwd_v = 0x04,
+// expand_both = expand_fwd | expand_bwd,
+// expand_or_new = allocate_new | expand_both,
+ shrink_in_place_v = 0x08,
+ nothrow_allocation_v = 0x10,
+ zero_memory_v = 0x20,
+ try_shrink_in_place_v = 0x40
+};
+
+typedef int allocation_type;
+/// @endcond
+static const allocation_type allocate_new = (allocation_type)allocate_new_v;
+static const allocation_type expand_fwd = (allocation_type)expand_fwd_v;
+static const allocation_type expand_bwd = (allocation_type)expand_bwd_v;
+static const allocation_type shrink_in_place = (allocation_type)shrink_in_place_v;
+static const allocation_type try_shrink_in_place= (allocation_type)try_shrink_in_place_v;
+static const allocation_type nothrow_allocation = (allocation_type)nothrow_allocation_v;
+static const allocation_type zero_memory = (allocation_type)zero_memory_v;
+
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //BOOST_CONTAINER_ALLOCATION_TYPE_HPP
diff --git a/boost/container/detail/config_begin.hpp b/boost/container/detail/config_begin.hpp
new file mode 100644
index 0000000000..bd44daacfe
--- /dev/null
+++ b/boost/container/detail/config_begin.hpp
@@ -0,0 +1,48 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_CONFIG_INCLUDED
+#define BOOST_CONTAINER_CONTAINER_DETAIL_CONFIG_INCLUDED
+#include <boost/config.hpp>
+
+#endif //BOOST_CONTAINER_CONTAINER_DETAIL_CONFIG_INCLUDED
+
+#ifdef BOOST_MSVC
+ #ifndef _CRT_SECURE_NO_DEPRECATE
+ #define BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE
+ #define _CRT_SECURE_NO_DEPRECATE
+ #endif
+ #pragma warning (push)
+ #pragma warning (disable : 4702) // unreachable code
+ #pragma warning (disable : 4706) // assignment within conditional expression
+ #pragma warning (disable : 4127) // conditional expression is constant
+ #pragma warning (disable : 4146) // unary minus operator applied to unsigned type, result still unsigned
+ #pragma warning (disable : 4284) // odd return type for operator->
+ #pragma warning (disable : 4244) // possible loss of data
+ #pragma warning (disable : 4251) // "identifier" : class "type" needs to have dll-interface to be used by clients of class "type2"
+ #pragma warning (disable : 4267) // conversion from "X" to "Y", possible loss of data
+ #pragma warning (disable : 4275) // non DLL-interface classkey "identifier" used as base for DLL-interface classkey "identifier"
+ #pragma warning (disable : 4355) // "this" : used in base member initializer list
+ #pragma warning (disable : 4503) // "identifier" : decorated name length exceeded, name was truncated
+ #pragma warning (disable : 4511) // copy constructor could not be generated
+ #pragma warning (disable : 4512) // assignment operator could not be generated
+ #pragma warning (disable : 4514) // unreferenced inline removed
+ #pragma warning (disable : 4521) // Disable "multiple copy constructors specified"
+ #pragma warning (disable : 4522) // "class" : multiple assignment operators specified
+ #pragma warning (disable : 4675) // "method" should be declared "static" and have exactly one parameter
+ #pragma warning (disable : 4710) // function not inlined
+ #pragma warning (disable : 4711) // function selected for automatic inline expansion
+ #pragma warning (disable : 4786) // identifier truncated in debug info
+ #pragma warning (disable : 4996) // "function": was declared deprecated
+ #pragma warning (disable : 4197) // top-level volatile in cast is ignored
+ #pragma warning (disable : 4541) // 'typeid' used on polymorphic type 'boost::exception'
+ // with /GR-; unpredictable behavior may result
+ #pragma warning (disable : 4673) // throwing '' the following types will not be considered at the catch site
+ #pragma warning (disable : 4671) // the copy constructor is inaccessible
+#endif //BOOST_MSVC
diff --git a/boost/container/detail/config_end.hpp b/boost/container/detail/config_end.hpp
new file mode 100644
index 0000000000..b71fabcdae
--- /dev/null
+++ b/boost/container/detail/config_end.hpp
@@ -0,0 +1,17 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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.
+//
+//////////////////////////////////////////////////////////////////////////////
+#if defined BOOST_MSVC
+ #pragma warning (pop)
+ #ifdef BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE
+ #undef BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE
+ #undef _CRT_SECURE_NO_DEPRECATE
+ #endif
+#endif
+
diff --git a/boost/container/detail/destroyers.hpp b/boost/container/detail/destroyers.hpp
new file mode 100644
index 0000000000..26ae089aa6
--- /dev/null
+++ b/boost/container/detail/destroyers.hpp
@@ -0,0 +1,163 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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_DESTROYERS_HPP
+#define BOOST_CONTAINER_DESTROYERS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/version_type.hpp>
+#include <boost/container/detail/utilities.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+//!A deleter for scoped_ptr that deallocates the memory
+//!allocated for an array of objects using a STL allocator.
+template <class Allocator>
+struct scoped_array_deallocator
+{
+ typedef boost::container::allocator_traits<Allocator> AllocTraits;
+ typedef typename AllocTraits::pointer pointer;
+ typedef typename AllocTraits::size_type size_type;
+
+ scoped_array_deallocator(pointer p, Allocator& a, size_type length)
+ : m_ptr(p), m_alloc(a), m_length(length) {}
+
+ ~scoped_array_deallocator()
+ { if (m_ptr) m_alloc.deallocate(m_ptr, m_length); }
+
+ void release()
+ { m_ptr = 0; }
+
+ private:
+ pointer m_ptr;
+ Allocator& m_alloc;
+ size_type m_length;
+};
+
+template <class Allocator>
+struct null_scoped_array_deallocator
+{
+ typedef boost::container::allocator_traits<Allocator> AllocTraits;
+ typedef typename AllocTraits::pointer pointer;
+ typedef typename AllocTraits::size_type size_type;
+
+ null_scoped_array_deallocator(pointer, Allocator&, size_type)
+ {}
+
+ void release()
+ {}
+};
+
+
+//!A deleter for scoped_ptr that destroys
+//!an object using a STL allocator.
+template <class Allocator>
+struct scoped_destructor_n
+{
+ typedef boost::container::allocator_traits<Allocator> AllocTraits;
+ typedef typename AllocTraits::pointer pointer;
+ typedef typename AllocTraits::value_type value_type;
+ typedef typename AllocTraits::size_type size_type;
+
+ scoped_destructor_n(pointer p, Allocator& a, size_type n)
+ : m_p(p), m_a(a), m_n(n)
+ {}
+
+ void release()
+ { m_p = 0; }
+
+ void increment_size(size_type inc)
+ { m_n += inc; }
+
+ ~scoped_destructor_n()
+ {
+ if(!m_p) return;
+ value_type *raw_ptr = container_detail::to_raw_pointer(m_p);
+ for(size_type i = 0; i < m_n; ++i, ++raw_ptr)
+ AllocTraits::destroy(m_a, raw_ptr);
+ }
+
+ private:
+ pointer m_p;
+ Allocator & m_a;
+ size_type m_n;
+};
+
+//!A deleter for scoped_ptr that destroys
+//!an object using a STL allocator.
+template <class Allocator>
+struct null_scoped_destructor_n
+{
+ typedef boost::container::allocator_traits<Allocator> AllocTraits;
+ typedef typename AllocTraits::pointer pointer;
+ typedef typename AllocTraits::size_type size_type;
+
+ null_scoped_destructor_n(pointer, Allocator&, size_type)
+ {}
+
+ void increment_size(size_type)
+ {}
+
+ void release()
+ {}
+};
+
+template <class Allocator>
+class allocator_destroyer
+{
+ typedef boost::container::allocator_traits<Allocator> AllocTraits;
+ typedef typename AllocTraits::value_type value_type;
+ typedef typename AllocTraits::pointer pointer;
+ typedef container_detail::integral_constant<unsigned,
+ boost::container::container_detail::
+ version<Allocator>::value> alloc_version;
+ typedef container_detail::integral_constant<unsigned, 1> allocator_v1;
+ typedef container_detail::integral_constant<unsigned, 2> allocator_v2;
+
+ private:
+ Allocator & a_;
+
+ private:
+ void priv_deallocate(const pointer &p, allocator_v1)
+ { AllocTraits::deallocate(a_,p, 1); }
+
+ void priv_deallocate(const pointer &p, allocator_v2)
+ { a_.deallocate_one(p); }
+
+ public:
+ allocator_destroyer(Allocator &a)
+ : a_(a)
+ {}
+
+ void operator()(const pointer &p)
+ {
+ AllocTraits::destroy(a_, container_detail::to_raw_pointer(p));
+ priv_deallocate(p, alloc_version());
+ }
+};
+
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DESTROYERS_HPP
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp
new file mode 100644
index 0000000000..44438386a3
--- /dev/null
+++ b/boost/container/detail/flat_tree.hpp
@@ -0,0 +1,822 @@
+////////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_FLAT_TREE_HPP
+#define BOOST_CONTAINER_FLAT_TREE_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+#include <boost/container/container_fwd.hpp>
+
+#include <algorithm>
+#include <functional>
+#include <utility>
+
+#include <boost/type_traits/has_trivial_destructor.hpp>
+#include <boost/move/move.hpp>
+
+#include <boost/container/detail/utilities.hpp>
+#include <boost/container/detail/pair.hpp>
+#include <boost/container/vector.hpp>
+#include <boost/container/detail/value_init.hpp>
+#include <boost/container/detail/destroyers.hpp>
+
+namespace boost {
+
+namespace container {
+
+namespace container_detail {
+
+template<class Compare, class Value, class KeyOfValue>
+class flat_tree_value_compare
+ : private Compare
+{
+ typedef Value first_argument_type;
+ typedef Value second_argument_type;
+ typedef bool return_type;
+ public:
+ flat_tree_value_compare()
+ : Compare()
+ {}
+
+ flat_tree_value_compare(const Compare &pred)
+ : Compare(pred)
+ {}
+
+ bool operator()(const Value& lhs, const Value& rhs) const
+ {
+ KeyOfValue key_extract;
+ return Compare::operator()(key_extract(lhs), key_extract(rhs));
+ }
+
+ const Compare &get_comp() const
+ { return *this; }
+
+ Compare &get_comp()
+ { return *this; }
+};
+
+template<class Pointer>
+struct get_flat_tree_iterators
+{
+ typedef typename container_detail::
+ vector_iterator<Pointer> iterator;
+ typedef typename container_detail::
+ vector_const_iterator<Pointer> const_iterator;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+};
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+class flat_tree
+{
+ typedef boost::container::vector<Value, A> vector_t;
+ typedef A allocator_t;
+
+ public:
+ typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
+
+ private:
+ struct Data
+ //Inherit from value_compare to do EBO
+ : public value_compare
+ {
+ BOOST_COPYABLE_AND_MOVABLE(Data)
+
+ public:
+ Data()
+ : value_compare(), m_vect()
+ {}
+
+ Data(const Data &d)
+ : value_compare(d), m_vect(d.m_vect)
+ {}
+
+ Data(BOOST_RV_REF(Data) d)
+ : value_compare(boost::move(d)), m_vect(boost::move(d.m_vect))
+ {}
+
+ Data(const Compare &comp)
+ : value_compare(comp), m_vect()
+ {}
+
+ Data(const Compare &comp,
+ const allocator_t &alloc)
+ : value_compare(comp), m_vect(alloc)
+ {}
+
+ Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
+ {
+ this->value_compare::operator=(d);
+ m_vect = d.m_vect;
+ return *this;
+ }
+
+ Data& operator=(BOOST_RV_REF(Data) d)
+ {
+ this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
+ m_vect = boost::move(d.m_vect);
+ return *this;
+ }
+
+ void swap(Data &d)
+ {
+ value_compare& mycomp = *this, & othercomp = d;
+ container_detail::do_swap(mycomp, othercomp);
+ this->m_vect.swap(d.m_vect);
+ }
+
+ vector_t m_vect;
+ };
+
+ Data m_data;
+ BOOST_COPYABLE_AND_MOVABLE(flat_tree)
+
+ public:
+
+ typedef typename vector_t::value_type value_type;
+ typedef typename vector_t::pointer pointer;
+ typedef typename vector_t::const_pointer const_pointer;
+ typedef typename vector_t::reference reference;
+ typedef typename vector_t::const_reference const_reference;
+ typedef Key key_type;
+ typedef Compare key_compare;
+ typedef typename vector_t::allocator_type allocator_type;
+ typedef typename vector_t::size_type size_type;
+ typedef typename vector_t::difference_type difference_type;
+ typedef typename vector_t::iterator iterator;
+ typedef typename vector_t::const_iterator const_iterator;
+ typedef typename vector_t::reverse_iterator reverse_iterator;
+ typedef typename vector_t::const_reverse_iterator const_reverse_iterator;
+
+ //!Standard extension
+ typedef allocator_type stored_allocator_type;
+
+ flat_tree()
+ : m_data()
+ { }
+
+ explicit flat_tree(const Compare& comp)
+ : m_data(comp)
+ { }
+
+ flat_tree(const Compare& comp, const allocator_type& a)
+ : m_data(comp, a)
+ { }
+
+ flat_tree(const flat_tree& x)
+ : m_data(x.m_data)
+ { }
+
+ flat_tree(BOOST_RV_REF(flat_tree) x)
+ : m_data(boost::move(x.m_data))
+ { }
+
+ template <class InputIterator>
+ flat_tree( ordered_range_t, InputIterator first, InputIterator last
+ , const Compare& comp = Compare()
+ , const allocator_type& a = allocator_type())
+ : m_data(comp, a)
+ { this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); }
+
+ ~flat_tree()
+ { }
+
+ flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
+ { m_data = x.m_data; return *this; }
+
+ flat_tree& operator=(BOOST_RV_REF(flat_tree) mx)
+ { m_data = boost::move(mx.m_data); return *this; }
+
+ public:
+ // accessors:
+ Compare key_comp() const
+ { return this->m_data.get_comp(); }
+
+ allocator_type get_allocator() const
+ { return this->m_data.m_vect.get_allocator(); }
+
+ const stored_allocator_type &get_stored_allocator() const
+ { return this->m_data.m_vect.get_stored_allocator(); }
+
+ stored_allocator_type &get_stored_allocator()
+ { return this->m_data.m_vect.get_stored_allocator(); }
+
+ iterator begin()
+ { return this->m_data.m_vect.begin(); }
+
+ const_iterator begin() const
+ { return this->cbegin(); }
+
+ const_iterator cbegin() const
+ { return this->m_data.m_vect.begin(); }
+
+ iterator end()
+ { return this->m_data.m_vect.end(); }
+
+ const_iterator end() const
+ { return this->cend(); }
+
+ const_iterator cend() const
+ { return this->m_data.m_vect.end(); }
+
+ reverse_iterator rbegin()
+ { return reverse_iterator(this->end()); }
+
+ const_reverse_iterator rbegin() const
+ { return this->crbegin(); }
+
+ const_reverse_iterator crbegin() const
+ { return const_reverse_iterator(this->cend()); }
+
+ reverse_iterator rend()
+ { return reverse_iterator(this->begin()); }
+
+ const_reverse_iterator rend() const
+ { return this->crend(); }
+
+ const_reverse_iterator crend() const
+ { return const_reverse_iterator(this->cbegin()); }
+
+ bool empty() const
+ { return this->m_data.m_vect.empty(); }
+
+ size_type size() const
+ { return this->m_data.m_vect.size(); }
+
+ size_type max_size() const
+ { return this->m_data.m_vect.max_size(); }
+
+ void swap(flat_tree& other)
+ { this->m_data.swap(other.m_data); }
+
+ public:
+ // insert/erase
+ std::pair<iterator,bool> insert_unique(const value_type& val)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, val);
+ }
+ return ret;
+ }
+
+ std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, boost::move(val));
+ }
+ return ret;
+ }
+
+
+ iterator insert_equal(const value_type& val)
+ {
+ iterator i = this->upper_bound(KeyOfValue()(val));
+ i = this->m_data.m_vect.insert(i, val);
+ return i;
+ }
+
+ iterator insert_equal(BOOST_RV_REF(value_type) mval)
+ {
+ iterator i = this->upper_bound(KeyOfValue()(mval));
+ i = this->m_data.m_vect.insert(i, boost::move(mval));
+ return i;
+ }
+
+ iterator insert_unique(const_iterator pos, const value_type& val)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, val, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, val);
+ }
+ return ret.first;
+ }
+
+ iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) mval)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, mval, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, boost::move(mval));
+ }
+ return ret.first;
+ }
+
+ iterator insert_equal(const_iterator pos, const value_type& val)
+ {
+ insert_commit_data data;
+ priv_insert_equal_prepare(pos, val, data);
+ return priv_insert_commit(data, val);
+ }
+
+ iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval)
+ {
+ insert_commit_data data;
+ priv_insert_equal_prepare(pos, mval, data);
+ return priv_insert_commit(data, boost::move(mval));
+ }
+
+ template <class InIt>
+ void insert_unique(InIt first, InIt last)
+ {
+ for ( ; first != last; ++first)
+ this->insert_unique(*first);
+ }
+
+ template <class InIt>
+ void insert_equal(InIt first, InIt last)
+ {
+ typedef typename
+ std::iterator_traits<InIt>::iterator_category ItCat;
+ priv_insert_equal(first, last, ItCat());
+ }
+
+ #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <class... Args>
+ std::pair<iterator, bool> emplace_unique(Args&&... args)
+ {
+ value_type && val = value_type(boost::forward<Args>(args)...);
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ priv_insert_unique_prepare(val, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, boost::move(val));
+ }
+ return ret;
+ }
+
+ template <class... Args>
+ iterator emplace_hint_unique(const_iterator hint, Args&&... args)
+ {
+ value_type && val = value_type(boost::forward<Args>(args)...);
+ insert_commit_data data;
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data);
+ if(ret.second){
+ ret.first = priv_insert_commit(data, boost::move(val));
+ }
+ return ret.first;
+ }
+
+ template <class... Args>
+ iterator emplace_equal(Args&&... args)
+ {
+ value_type &&val = value_type(boost::forward<Args>(args)...);
+ iterator i = this->upper_bound(KeyOfValue()(val));
+ i = this->m_data.m_vect.insert(i, boost::move(val));
+ return i;
+ }
+
+ template <class... Args>
+ iterator emplace_hint_equal(const_iterator hint, Args&&... args)
+ {
+ value_type &&val = value_type(boost::forward<Args>(args)...);
+ insert_commit_data data;
+ priv_insert_equal_prepare(hint, val, data);
+ return priv_insert_commit(data, boost::move(val));
+ }
+
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ std::pair<iterator, bool> \
+ emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \
+ value_type &val = vval; \
+ insert_commit_data data; \
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data); \
+ if(ret.second){ \
+ ret.first = priv_insert_commit(data, boost::move(val)); \
+ } \
+ return ret; \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint_unique(const_iterator hint \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \
+ value_type &val = vval; \
+ insert_commit_data data; \
+ std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data); \
+ if(ret.second){ \
+ ret.first = priv_insert_commit(data, boost::move(val)); \
+ } \
+ return ret.first; \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \
+ value_type &val = vval; \
+ iterator i = this->upper_bound(KeyOfValue()(val)); \
+ i = this->m_data.m_vect.insert(i, boost::move(val)); \
+ return i; \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint_equal(const_iterator hint \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \
+ BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \
+ BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \
+ value_type &val = vval; \
+ insert_commit_data data; \
+ priv_insert_equal_prepare(hint, val, data); \
+ return priv_insert_commit(data, boost::move(val)); \
+ } \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ iterator erase(const_iterator position)
+ { return this->m_data.m_vect.erase(position); }
+
+ size_type erase(const key_type& k)
+ {
+ std::pair<iterator,iterator > itp = this->equal_range(k);
+ size_type ret = static_cast<size_type>(itp.second-itp.first);
+ if (ret){
+ this->m_data.m_vect.erase(itp.first, itp.second);
+ }
+ return ret;
+ }
+
+ iterator erase(const_iterator first, const_iterator last)
+ { return this->m_data.m_vect.erase(first, last); }
+
+ void clear()
+ { this->m_data.m_vect.clear(); }
+
+ //! <b>Effects</b>: Tries to deallocate the excess of memory created
+ // with previous allocations. The size of the vector is unchanged
+ //!
+ //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to size().
+ void shrink_to_fit()
+ { this->m_data.m_vect.shrink_to_fit(); }
+
+ // set operations:
+ iterator find(const key_type& k)
+ {
+ const Compare &key_comp = this->m_data.get_comp();
+ iterator i = this->lower_bound(k);
+
+ if (i != this->end() && key_comp(k, KeyOfValue()(*i))){
+ i = this->end();
+ }
+ return i;
+ }
+
+ const_iterator find(const key_type& k) const
+ {
+ const Compare &key_comp = this->m_data.get_comp();
+ const_iterator i = this->lower_bound(k);
+
+ if (i != this->end() && key_comp(k, KeyOfValue()(*i))){
+ i = this->end();
+ }
+ return i;
+ }
+
+ size_type count(const key_type& k) const
+ {
+ std::pair<const_iterator, const_iterator> p = this->equal_range(k);
+ size_type n = p.second - p.first;
+ return n;
+ }
+
+ iterator lower_bound(const key_type& k)
+ { return this->priv_lower_bound(this->begin(), this->end(), k); }
+
+ const_iterator lower_bound(const key_type& k) const
+ { return this->priv_lower_bound(this->begin(), this->end(), k); }
+
+ iterator upper_bound(const key_type& k)
+ { return this->priv_upper_bound(this->begin(), this->end(), k); }
+
+ const_iterator upper_bound(const key_type& k) const
+ { return this->priv_upper_bound(this->begin(), this->end(), k); }
+
+ std::pair<iterator,iterator> equal_range(const key_type& k)
+ { return this->priv_equal_range(this->begin(), this->end(), k); }
+
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
+ { return this->priv_equal_range(this->begin(), this->end(), k); }
+
+ size_type capacity() const
+ { return this->m_data.m_vect.capacity(); }
+
+ void reserve(size_type count)
+ { this->m_data.m_vect.reserve(count); }
+
+ private:
+ struct insert_commit_data
+ {
+ const_iterator position;
+ };
+
+ // insert/erase
+ void priv_insert_equal_prepare
+ (const_iterator pos, const value_type& val, insert_commit_data &data)
+ {
+ // N1780
+ // To insert val at pos:
+ // if pos == end || val <= *pos
+ // if pos == begin || val >= *(pos-1)
+ // insert val before pos
+ // else
+ // insert val before upper_bound(val)
+ // else
+ // insert val before lower_bound(val)
+ const value_compare &value_comp = this->m_data;
+
+ if(pos == this->cend() || !value_comp(*pos, val)){
+ if (pos == this->cbegin() || !value_comp(val, pos[-1])){
+ data.position = pos;
+ }
+ else{
+ data.position =
+ this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
+ }
+ }
+ else{
+ data.position =
+ this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
+ }
+ }
+
+ std::pair<iterator,bool> priv_insert_unique_prepare
+ (const_iterator beg, const_iterator end, const value_type& val, insert_commit_data &commit_data)
+ {
+ const value_compare &value_comp = this->m_data;
+ commit_data.position = this->priv_lower_bound(beg, end, KeyOfValue()(val));
+ return std::pair<iterator,bool>
+ ( *reinterpret_cast<iterator*>(&commit_data.position)
+ , commit_data.position == end || value_comp(val, *commit_data.position));
+ }
+
+ std::pair<iterator,bool> priv_insert_unique_prepare
+ (const value_type& val, insert_commit_data &commit_data)
+ { return priv_insert_unique_prepare(this->begin(), this->end(), val, commit_data); }
+
+ std::pair<iterator,bool> priv_insert_unique_prepare
+ (const_iterator pos, const value_type& val, insert_commit_data &commit_data)
+ {
+ //N1780. Props to Howard Hinnant!
+ //To insert val at pos:
+ //if pos == end || val <= *pos
+ // if pos == begin || val >= *(pos-1)
+ // insert val before pos
+ // else
+ // insert val before upper_bound(val)
+ //else if pos+1 == end || val <= *(pos+1)
+ // insert val after pos
+ //else
+ // insert val before lower_bound(val)
+ const value_compare &value_comp = this->m_data;
+
+ if(pos == this->cend() || value_comp(val, *pos)){
+ if(pos != this->cbegin() && !value_comp(val, pos[-1])){
+ if(value_comp(pos[-1], val)){
+ commit_data.position = pos;
+ return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), true);
+ }
+ else{
+ return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), false);
+ }
+ }
+ return this->priv_insert_unique_prepare(this->cbegin(), pos, val, commit_data);
+ }
+
+ // Works, but increases code complexity
+ //Next check
+ //else if (value_comp(*pos, val) && !value_comp(pos[1], val)){
+ // if(value_comp(val, pos[1])){
+ // commit_data.position = pos+1;
+ // return std::pair<iterator,bool>(pos+1, true);
+ // }
+ // else{
+ // return std::pair<iterator,bool>(pos+1, false);
+ // }
+ //}
+ else{
+ //[... pos ... val ... ]
+ //The hint is before the insertion position, so insert it
+ //in the remaining range
+ return this->priv_insert_unique_prepare(pos, this->end(), val, commit_data);
+ }
+ }
+
+ template<class Convertible>
+ iterator priv_insert_commit
+ (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
+ {
+ return this->m_data.m_vect.insert
+ ( commit_data.position
+ , boost::forward<Convertible>(convertible));
+ }
+
+ template <class RanIt>
+ RanIt priv_lower_bound(RanIt first, RanIt last,
+ const key_type & key) const
+ {
+ const Compare &key_comp = this->m_data.get_comp();
+ KeyOfValue key_extract;
+ difference_type len = last - first, half;
+ RanIt middle;
+
+ while (len > 0) {
+ half = len >> 1;
+ middle = first;
+ middle += half;
+
+ if (key_comp(key_extract(*middle), key)) {
+ ++middle;
+ first = middle;
+ len = len - half - 1;
+ }
+ else
+ len = half;
+ }
+ return first;
+ }
+
+ template <class RanIt>
+ RanIt priv_upper_bound(RanIt first, RanIt last,
+ const key_type & key) const
+ {
+ const Compare &key_comp = this->m_data.get_comp();
+ KeyOfValue key_extract;
+ difference_type len = last - first, half;
+ RanIt middle;
+
+ while (len > 0) {
+ half = len >> 1;
+ middle = first;
+ middle += half;
+
+ if (key_comp(key, key_extract(*middle))) {
+ len = half;
+ }
+ else{
+ first = ++middle;
+ len = len - half - 1;
+ }
+ }
+ return first;
+ }
+
+ template <class RanIt>
+ std::pair<RanIt, RanIt>
+ priv_equal_range(RanIt first, RanIt last, const key_type& key) const
+ {
+ const Compare &key_comp = this->m_data.get_comp();
+ KeyOfValue key_extract;
+ difference_type len = last - first, half;
+ RanIt middle, left, right;
+
+ while (len > 0) {
+ half = len >> 1;
+ middle = first;
+ middle += half;
+
+ if (key_comp(key_extract(*middle), key)){
+ first = middle;
+ ++first;
+ len = len - half - 1;
+ }
+ else if (key_comp(key, key_extract(*middle))){
+ len = half;
+ }
+ else {
+ left = this->priv_lower_bound(first, middle, key);
+ first += len;
+ right = this->priv_upper_bound(++middle, first, key);
+ return std::pair<RanIt, RanIt>(left, right);
+ }
+ }
+ return std::pair<RanIt, RanIt>(first, first);
+ }
+
+ template <class FwdIt>
+ void priv_insert_equal(FwdIt first, FwdIt last, std::forward_iterator_tag)
+ {
+ size_type len = static_cast<size_type>(std::distance(first, last));
+ this->reserve(this->size()+len);
+ this->priv_insert_equal(first, last, std::input_iterator_tag());
+ }
+
+ template <class InIt>
+ void priv_insert_equal(InIt first, InIt last, std::input_iterator_tag)
+ {
+ for ( ; first != last; ++first)
+ this->insert_equal(*first);
+ }
+};
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator==(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+{
+ return x.size() == y.size() &&
+ std::equal(x.begin(), x.end(), y.begin());
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator<(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+{
+ return std::lexicographical_compare(x.begin(), x.end(),
+ y.begin(), y.end());
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator!=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+ { return !(x == y); }
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator>(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+ { return y < x; }
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator<=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+ { return !(y < x); }
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline bool
+operator>=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+ { return !(x < y); }
+
+
+template <class Key, class Value, class KeyOfValue,
+ class Compare, class A>
+inline void
+swap(flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
+ flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
+ { x.swap(y); }
+
+} //namespace container_detail {
+
+} //namespace container {
+/*
+//!has_trivial_destructor_after_move<> == true_type
+//!specialization for optimizations
+template <class K, class V, class KOV,
+class C, class A>
+struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<K, V, KOV, C, A> >
+{
+ static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+};
+*/
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif // BOOST_CONTAINER_FLAT_TREE_HPP
diff --git a/boost/container/detail/function_detector.hpp b/boost/container/detail/function_detector.hpp
new file mode 100644
index 0000000000..c37c766844
--- /dev/null
+++ b/boost/container/detail/function_detector.hpp
@@ -0,0 +1,88 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2009-2011.
+//
+// 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.
+//
+/////////////////////////////////////////////////////////////////////////////
+// This code was modified from the code posted by Alexandre Courpron in his
+// article "Interface Detection" in The Code Project:
+// http://www.codeproject.com/KB/architecture/Detector.aspx
+///////////////////////////////////////////////////////////////////////////////
+// Copyright 2007 Alexandre Courpron
+//
+// Permission to use, copy, modify, redistribute and sell this software,
+// provided that this copyright notice appears on all copies of the software.
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP
+#define BOOST_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP
+
+#include <boost/container/detail/config_begin.hpp>
+
+namespace boost {
+namespace container {
+namespace function_detector {
+
+ typedef char NotFoundType;
+ struct StaticFunctionType { NotFoundType x [2]; };
+ struct NonStaticFunctionType { NotFoundType x [3]; };
+
+ enum
+ { NotFound = 0,
+ StaticFunction = sizeof( StaticFunctionType ) - sizeof( NotFoundType ),
+ NonStaticFunction = sizeof( NonStaticFunctionType ) - sizeof( NotFoundType )
+ };
+
+} //namespace boost {
+} //namespace container {
+} //namespace function_detector {
+
+#define BOOST_CONTAINER_CREATE_FUNCTION_DETECTOR(Identifier, InstantiationKey) \
+ namespace boost { \
+ namespace container { \
+ namespace function_detector { \
+ template < class T, \
+ class NonStaticType, \
+ class NonStaticConstType, \
+ class StaticType > \
+ class DetectMember_##InstantiationKey_##Identifier { \
+ template < NonStaticType > \
+ struct TestNonStaticNonConst ; \
+ \
+ template < NonStaticConstType > \
+ struct TestNonStaticConst ; \
+ \
+ template < StaticType > \
+ struct TestStatic ; \
+ \
+ template <class U > \
+ static NonStaticFunctionType Test( TestNonStaticNonConst<&U::Identifier>*, int ); \
+ \
+ template <class U > \
+ static NonStaticFunctionType Test( TestNonStaticConst<&U::Identifier>*, int ); \
+ \
+ template <class U> \
+ static StaticFunctionType Test( TestStatic<&U::Identifier>*, int ); \
+ \
+ template <class U> \
+ static NotFoundType Test( ... ); \
+ public : \
+ static const int check = NotFound + (sizeof(Test<T>(0, 0)) - sizeof(NotFoundType));\
+ };\
+}}} //namespace boost::container::function_detector {
+
+#define BOOST_CONTAINER_DETECT_FUNCTION(Class, InstantiationKey, ReturnType, Identifier, Params) \
+ ::boost::container::function_detector::DetectMember_##InstantiationKey_##Identifier< Class,\
+ ReturnType (Class::*)Params,\
+ ReturnType (Class::*)Params const,\
+ ReturnType (*)Params \
+ >::check
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //@ifndef BOOST_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP
diff --git a/boost/container/detail/iterators.hpp b/boost/container/detail/iterators.hpp
new file mode 100644
index 0000000000..899cbe4349
--- /dev/null
+++ b/boost/container/detail/iterators.hpp
@@ -0,0 +1,548 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+// (C) Copyright Gennaro Prota 2003 - 2004.
+//
+// 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_DETAIL_ITERATORS_HPP
+#define BOOST_CONTAINER_DETAIL_ITERATORS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/move/move.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+
+#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container/detail/variadic_templates_tools.hpp>
+#include <boost/container/detail/stored_ref.hpp>
+#else
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+#include <iterator>
+
+namespace boost {
+namespace container {
+
+template <class T, class Difference = std::ptrdiff_t>
+class constant_iterator
+ : public std::iterator
+ <std::random_access_iterator_tag, T, Difference, const T*, const T &>
+{
+ typedef constant_iterator<T, Difference> this_type;
+
+ public:
+ explicit constant_iterator(const T &ref, Difference range_size)
+ : m_ptr(&ref), m_num(range_size){}
+
+ //Constructors
+ constant_iterator()
+ : m_ptr(0), m_num(0){}
+
+ constant_iterator& operator++()
+ { increment(); return *this; }
+
+ constant_iterator operator++(int)
+ {
+ constant_iterator result (*this);
+ increment();
+ return result;
+ }
+
+ constant_iterator& operator--()
+ { decrement(); return *this; }
+
+ constant_iterator operator--(int)
+ {
+ constant_iterator result (*this);
+ decrement();
+ return result;
+ }
+
+ friend bool operator== (const constant_iterator& i, const constant_iterator& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const constant_iterator& i, const constant_iterator& i2)
+ { return !(i == i2); }
+
+ friend bool operator< (const constant_iterator& i, const constant_iterator& i2)
+ { return i.less(i2); }
+
+ friend bool operator> (const constant_iterator& i, const constant_iterator& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const constant_iterator& i, const constant_iterator& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const constant_iterator& i, const constant_iterator& i2)
+ { return !(i < i2); }
+
+ friend Difference operator- (const constant_iterator& i, const constant_iterator& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ constant_iterator& operator+=(Difference off)
+ { this->advance(off); return *this; }
+
+ constant_iterator operator+(Difference off) const
+ {
+ constant_iterator other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend constant_iterator operator+(Difference off, const constant_iterator& right)
+ { return right + off; }
+
+ constant_iterator& operator-=(Difference off)
+ { this->advance(-off); return *this; }
+
+ constant_iterator operator-(Difference off) const
+ { return *this + (-off); }
+
+ const T& operator*() const
+ { return dereference(); }
+
+ const T& operator[] (Difference n) const
+ { return dereference(); }
+
+ const T* operator->() const
+ { return &(dereference()); }
+
+ private:
+ const T * m_ptr;
+ Difference m_num;
+
+ void increment()
+ { --m_num; }
+
+ void decrement()
+ { ++m_num; }
+
+ bool equal(const this_type &other) const
+ { return m_num == other.m_num; }
+
+ bool less(const this_type &other) const
+ { return other.m_num < m_num; }
+
+ const T & dereference() const
+ { return *m_ptr; }
+
+ void advance(Difference n)
+ { m_num -= n; }
+
+ Difference distance_to(const this_type &other)const
+ { return m_num - other.m_num; }
+};
+
+template <class T, class Difference = std::ptrdiff_t>
+class default_construct_iterator
+ : public std::iterator
+ <std::random_access_iterator_tag, T, Difference, const T*, const T &>
+{
+ typedef default_construct_iterator<T, Difference> this_type;
+
+ public:
+ explicit default_construct_iterator(Difference range_size)
+ : m_num(range_size){}
+
+ //Constructors
+ default_construct_iterator()
+ : m_num(0){}
+
+ default_construct_iterator& operator++()
+ { increment(); return *this; }
+
+ default_construct_iterator operator++(int)
+ {
+ default_construct_iterator result (*this);
+ increment();
+ return result;
+ }
+
+ default_construct_iterator& operator--()
+ { decrement(); return *this; }
+
+ default_construct_iterator operator--(int)
+ {
+ default_construct_iterator result (*this);
+ decrement();
+ return result;
+ }
+
+ friend bool operator== (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return !(i == i2); }
+
+ friend bool operator< (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return i.less(i2); }
+
+ friend bool operator> (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return !(i < i2); }
+
+ friend Difference operator- (const default_construct_iterator& i, const default_construct_iterator& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ default_construct_iterator& operator+=(Difference off)
+ { this->advance(off); return *this; }
+
+ default_construct_iterator operator+(Difference off) const
+ {
+ default_construct_iterator other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend default_construct_iterator operator+(Difference off, const default_construct_iterator& right)
+ { return right + off; }
+
+ default_construct_iterator& operator-=(Difference off)
+ { this->advance(-off); return *this; }
+
+ default_construct_iterator operator-(Difference off) const
+ { return *this + (-off); }
+
+ const T& operator*() const
+ { return dereference(); }
+
+ const T* operator->() const
+ { return &(dereference()); }
+
+ const T& operator[] (Difference n) const
+ { return dereference(); }
+
+ private:
+ Difference m_num;
+
+ void increment()
+ { --m_num; }
+
+ void decrement()
+ { ++m_num; }
+
+ bool equal(const this_type &other) const
+ { return m_num == other.m_num; }
+
+ bool less(const this_type &other) const
+ { return other.m_num < m_num; }
+
+ const T & dereference() const
+ {
+ static T dummy;
+ return dummy;
+ }
+
+ void advance(Difference n)
+ { m_num -= n; }
+
+ Difference distance_to(const this_type &other)const
+ { return m_num - other.m_num; }
+};
+
+template <class T, class Difference = std::ptrdiff_t>
+class repeat_iterator
+ : public std::iterator
+ <std::random_access_iterator_tag, T, Difference>
+{
+ typedef repeat_iterator<T, Difference> this_type;
+ public:
+ explicit repeat_iterator(T &ref, Difference range_size)
+ : m_ptr(&ref), m_num(range_size){}
+
+ //Constructors
+ repeat_iterator()
+ : m_ptr(0), m_num(0){}
+
+ this_type& operator++()
+ { increment(); return *this; }
+
+ this_type operator++(int)
+ {
+ this_type result (*this);
+ increment();
+ return result;
+ }
+
+ this_type& operator--()
+ { increment(); return *this; }
+
+ this_type operator--(int)
+ {
+ this_type result (*this);
+ increment();
+ return result;
+ }
+
+ friend bool operator== (const this_type& i, const this_type& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const this_type& i, const this_type& i2)
+ { return !(i == i2); }
+
+ friend bool operator< (const this_type& i, const this_type& i2)
+ { return i.less(i2); }
+
+ friend bool operator> (const this_type& i, const this_type& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const this_type& i, const this_type& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const this_type& i, const this_type& i2)
+ { return !(i < i2); }
+
+ friend Difference operator- (const this_type& i, const this_type& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ this_type& operator+=(Difference off)
+ { this->advance(off); return *this; }
+
+ this_type operator+(Difference off) const
+ {
+ this_type other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend this_type operator+(Difference off, const this_type& right)
+ { return right + off; }
+
+ this_type& operator-=(Difference off)
+ { this->advance(-off); return *this; }
+
+ this_type operator-(Difference off) const
+ { return *this + (-off); }
+
+ T& operator*() const
+ { return dereference(); }
+
+ T& operator[] (Difference n) const
+ { return dereference(); }
+
+ T *operator->() const
+ { return &(dereference()); }
+
+ private:
+ T * m_ptr;
+ Difference m_num;
+
+ void increment()
+ { --m_num; }
+
+ void decrement()
+ { ++m_num; }
+
+ bool equal(const this_type &other) const
+ { return m_num == other.m_num; }
+
+ bool less(const this_type &other) const
+ { return other.m_num < m_num; }
+
+ T & dereference() const
+ { return *m_ptr; }
+
+ void advance(Difference n)
+ { m_num -= n; }
+
+ Difference distance_to(const this_type &other)const
+ { return m_num - other.m_num; }
+};
+
+template <class T, class EmplaceFunctor, class Difference /*= std::ptrdiff_t*/>
+class emplace_iterator
+ : public std::iterator
+ <std::random_access_iterator_tag, T, Difference, const T*, const T &>
+{
+ typedef emplace_iterator this_type;
+
+ public:
+ typedef Difference difference_type;
+ explicit emplace_iterator(EmplaceFunctor&e)
+ : m_num(1), m_pe(&e){}
+
+ emplace_iterator()
+ : m_num(0), m_pe(0){}
+
+ this_type& operator++()
+ { increment(); return *this; }
+
+ this_type operator++(int)
+ {
+ this_type result (*this);
+ increment();
+ return result;
+ }
+
+ this_type& operator--()
+ { decrement(); return *this; }
+
+ this_type operator--(int)
+ {
+ this_type result (*this);
+ decrement();
+ return result;
+ }
+
+ friend bool operator== (const this_type& i, const this_type& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const this_type& i, const this_type& i2)
+ { return !(i == i2); }
+
+ friend bool operator< (const this_type& i, const this_type& i2)
+ { return i.less(i2); }
+
+ friend bool operator> (const this_type& i, const this_type& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const this_type& i, const this_type& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const this_type& i, const this_type& i2)
+ { return !(i < i2); }
+
+ friend difference_type operator- (const this_type& i, const this_type& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ this_type& operator+=(difference_type off)
+ { this->advance(off); return *this; }
+
+ this_type operator+(difference_type off) const
+ {
+ this_type other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend this_type operator+(difference_type off, const this_type& right)
+ { return right + off; }
+
+ this_type& operator-=(difference_type off)
+ { this->advance(-off); return *this; }
+
+ this_type operator-(difference_type off) const
+ { return *this + (-off); }
+
+ const T& operator*() const
+ { return dereference(); }
+
+ const T& operator[](difference_type) const
+ { return dereference(); }
+
+ const T* operator->() const
+ { return &(dereference()); }
+
+ template<class A>
+ void construct_in_place(A &a, T* ptr)
+ { (*m_pe)(a, ptr); }
+
+ private:
+ difference_type m_num;
+ EmplaceFunctor * m_pe;
+
+ void increment()
+ { --m_num; }
+
+ void decrement()
+ { ++m_num; }
+
+ bool equal(const this_type &other) const
+ { return m_num == other.m_num; }
+
+ bool less(const this_type &other) const
+ { return other.m_num < m_num; }
+
+ const T & dereference() const
+ {
+ static T dummy;
+ return dummy;
+ }
+
+ void advance(difference_type n)
+ { m_num -= n; }
+
+ difference_type distance_to(const this_type &other)const
+ { return difference_type(m_num - other.m_num); }
+};
+
+#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+template<class ...Args>
+struct emplace_functor
+{
+ typedef typename container_detail::build_number_seq<sizeof...(Args)>::type index_tuple_t;
+
+ emplace_functor(Args&&... args)
+ : args_(args...)
+ {}
+
+ template<class A, class T>
+ void operator()(A &a, T *ptr)
+ { emplace_functor::inplace_impl(a, ptr, index_tuple_t()); }
+
+ template<class A, class T, int ...IdxPack>
+ void inplace_impl(A &a, T* ptr, const container_detail::index_tuple<IdxPack...>&)
+ {
+ allocator_traits<A>::construct
+ (a, ptr, container_detail::stored_ref<Args>::forward
+ (container_detail::get<IdxPack>(args_))...);
+ }
+
+ container_detail::tuple<Args&...> args_;
+};
+
+#else
+
+#define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS(n, class P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ struct BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \
+ { \
+ BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \
+ ( BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \
+ BOOST_PP_EXPR_IF(n, :) BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_INIT, _){} \
+ \
+ template<class A, class T> \
+ void operator()(A &a, T *ptr) \
+ { \
+ allocator_traits<A>::construct \
+ (a, ptr BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) );\
+ } \
+ BOOST_PP_REPEAT(n, BOOST_CONTAINER_PP_PARAM_DEFINE, _) \
+ }; \
+ //!
+#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+#include BOOST_PP_LOCAL_ITERATE()
+
+#endif
+
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP
+
diff --git a/boost/container/detail/math_functions.hpp b/boost/container/detail/math_functions.hpp
new file mode 100644
index 0000000000..4613573d48
--- /dev/null
+++ b/boost/container/detail/math_functions.hpp
@@ -0,0 +1,113 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Stephen Cleary 2000.
+// (C) Copyright Ion Gaztanaga 2007-2011.
+//
+// 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.
+//
+// This file is a slightly modified file from Boost.Pool
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP
+#define BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP
+
+#include "config_begin.hpp"
+#include <climits>
+#include <boost/static_assert.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+// Greatest common divisor and least common multiple
+
+//
+// gcd is an algorithm that calculates the greatest common divisor of two
+// integers, using Euclid's algorithm.
+//
+// Pre: A > 0 && B > 0
+// Recommended: A > B
+template <typename Integer>
+inline Integer gcd(Integer A, Integer B)
+{
+ do
+ {
+ const Integer tmp(B);
+ B = A % B;
+ A = tmp;
+ } while (B != 0);
+
+ return A;
+}
+
+//
+// lcm is an algorithm that calculates the least common multiple of two
+// integers.
+//
+// Pre: A > 0 && B > 0
+// Recommended: A > B
+template <typename Integer>
+inline Integer lcm(const Integer & A, const Integer & B)
+{
+ Integer ret = A;
+ ret /= gcd(A, B);
+ ret *= B;
+ return ret;
+}
+
+template <typename Integer>
+inline Integer log2_ceil(const Integer & A)
+{
+ Integer i = 0;
+ Integer power_of_2 = 1;
+
+ while(power_of_2 < A){
+ power_of_2 <<= 1;
+ ++i;
+ }
+ return i;
+}
+
+template <typename Integer>
+inline Integer upper_power_of_2(const Integer & A)
+{
+ Integer power_of_2 = 1;
+
+ while(power_of_2 < A){
+ power_of_2 <<= 1;
+ }
+ return power_of_2;
+}
+
+//This function uses binary search to discover the
+//highest set bit of the integer
+inline std::size_t floor_log2 (std::size_t x)
+{
+ const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
+ const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
+ BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
+
+ std::size_t n = x;
+ std::size_t log2 = 0;
+
+ for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
+ std::size_t tmp = n >> shift;
+ if (tmp)
+ log2 += shift, n = tmp;
+ }
+
+ return log2;
+}
+
+} // namespace container_detail
+} // namespace container
+} // namespace boost
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif
diff --git a/boost/container/detail/mpl.hpp b/boost/container/detail/mpl.hpp
new file mode 100644
index 0000000000..c2d0ce41bb
--- /dev/null
+++ b/boost/container/detail/mpl.hpp
@@ -0,0 +1,160 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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_DETAIL_MPL_HPP
+#define BOOST_CONTAINER_CONTAINER_DETAIL_MPL_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include <cstddef>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template <class T, T val>
+struct integral_constant
+{
+ static const T value = val;
+ typedef integral_constant<T,val> type;
+};
+
+template< bool C_ >
+struct bool_ : integral_constant<bool, C_>
+{
+ static const bool value = C_;
+ operator bool() const { return bool_::value; }
+};
+
+typedef bool_<true> true_;
+typedef bool_<false> false_;
+
+typedef true_ true_type;
+typedef false_ false_type;
+
+typedef char yes_type;
+struct no_type
+{
+ char padding[8];
+};
+
+template <bool B, class T = void>
+struct enable_if_c {
+ typedef T type;
+};
+
+template <class T>
+struct enable_if_c<false, T> {};
+
+template <class Cond, class T = void>
+struct enable_if : public enable_if_c<Cond::value, T> {};
+
+template <class Cond, class T = void>
+struct disable_if : public enable_if_c<!Cond::value, T> {};
+
+template <bool B, class T = void>
+struct disable_if_c : public enable_if_c<!B, T> {};
+
+template <class T, class U>
+class is_convertible
+{
+ typedef char true_t;
+ class false_t { char dummy[2]; };
+ static true_t dispatch(U);
+ static false_t dispatch(...);
+ static T trigger();
+ public:
+ enum { value = sizeof(dispatch(trigger())) == sizeof(true_t) };
+};
+
+template<
+ bool C
+ , typename T1
+ , typename T2
+ >
+struct if_c
+{
+ typedef T1 type;
+};
+
+template<
+ typename T1
+ , typename T2
+ >
+struct if_c<false,T1,T2>
+{
+ typedef T2 type;
+};
+
+template<
+ typename T1
+ , typename T2
+ , typename T3
+ >
+struct if_
+{
+ typedef typename if_c<0 != T1::value, T2, T3>::type type;
+};
+
+
+template <class Pair>
+struct select1st
+// : public std::unary_function<Pair, typename Pair::first_type>
+{
+ template<class OtherPair>
+ const typename Pair::first_type& operator()(const OtherPair& x) const
+ { return x.first; }
+
+ const typename Pair::first_type& operator()(const typename Pair::first_type& x) const
+ { return x; }
+};
+
+// identity is an extension: it is not part of the standard.
+template <class T>
+struct identity
+// : public std::unary_function<T,T>
+{
+ typedef T type;
+ const T& operator()(const T& x) const
+ { return x; }
+};
+
+template<std::size_t S>
+struct ls_zeros
+{
+ static const std::size_t value = (S & std::size_t(1)) ? 0 : (1u + ls_zeros<(S >> 1u)>::value);
+};
+
+template<>
+struct ls_zeros<0>
+{
+ static const std::size_t value = 0;
+};
+
+template<>
+struct ls_zeros<1>
+{
+ static const std::size_t value = 0;
+};
+
+template <typename T> struct unvoid { typedef T type; };
+template <> struct unvoid<void> { struct type { }; };
+template <> struct unvoid<const void> { struct type { }; };
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#endif //#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_MPL_HPP
+
diff --git a/boost/container/detail/multiallocation_chain.hpp b/boost/container/detail/multiallocation_chain.hpp
new file mode 100644
index 0000000000..a67fd770bd
--- /dev/null
+++ b/boost/container/detail/multiallocation_chain.hpp
@@ -0,0 +1,254 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_MULTIALLOCATION_CHAIN_HPP
+#define BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
+
+#include "config_begin.hpp"
+#include <boost/container/container_fwd.hpp>
+#include <boost/container/detail/utilities.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/transform_iterator.hpp>
+#include <boost/intrusive/slist.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/type_traits/make_unsigned.hpp>
+#include <boost/move/move.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class VoidPointer>
+class basic_multiallocation_chain
+{
+ private:
+ typedef bi::slist_base_hook<bi::void_pointer<VoidPointer>
+ ,bi::link_mode<bi::normal_link>
+ > node;
+
+ typedef typename boost::intrusive::pointer_traits
+ <VoidPointer>::template rebind_pointer<char>::type char_ptr;
+ typedef typename boost::intrusive::
+ pointer_traits<char_ptr>::difference_type difference_type;
+
+ typedef bi::slist< node
+ , bi::linear<true>
+ , bi::cache_last<true>
+ , bi::size_type<typename boost::make_unsigned<difference_type>::type>
+ > slist_impl_t;
+ slist_impl_t slist_impl_;
+
+ static node & to_node(VoidPointer p)
+ { return *static_cast<node*>(static_cast<void*>(container_detail::to_raw_pointer(p))); }
+
+ BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_multiallocation_chain)
+
+ public:
+
+
+ typedef VoidPointer void_pointer;
+ typedef typename slist_impl_t::iterator iterator;
+ typedef typename slist_impl_t::size_type size_type;
+
+ basic_multiallocation_chain()
+ : slist_impl_()
+ {}
+
+ basic_multiallocation_chain(BOOST_RV_REF(basic_multiallocation_chain) other)
+ : slist_impl_()
+ { slist_impl_.swap(other.slist_impl_); }
+
+ basic_multiallocation_chain& operator=(BOOST_RV_REF(basic_multiallocation_chain) other)
+ {
+ basic_multiallocation_chain tmp(boost::move(other));
+ this->swap(tmp);
+ return *this;
+ }
+
+ bool empty() const
+ { return slist_impl_.empty(); }
+
+ size_type size() const
+ { return slist_impl_.size(); }
+
+ iterator before_begin()
+ { return slist_impl_.before_begin(); }
+
+ iterator begin()
+ { return slist_impl_.begin(); }
+
+ iterator end()
+ { return slist_impl_.end(); }
+
+ iterator last()
+ { return slist_impl_.last(); }
+
+ void clear()
+ { slist_impl_.clear(); }
+
+ iterator insert_after(iterator it, void_pointer m)
+ { return slist_impl_.insert_after(it, to_node(m)); }
+
+ void push_front(void_pointer m)
+ { return slist_impl_.push_front(to_node(m)); }
+
+ void push_back(void_pointer m)
+ { return slist_impl_.push_back(to_node(m)); }
+
+ void pop_front()
+ { return slist_impl_.pop_front(); }
+
+ void *front()
+ { return &*slist_impl_.begin(); }
+
+ void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_begin, iterator before_end)
+ { slist_impl_.splice_after(after_this, x.slist_impl_, before_begin, before_end); }
+
+ void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_begin, iterator before_end, size_type n)
+ { slist_impl_.splice_after(after_this, x.slist_impl_, before_begin, before_end, n); }
+
+ void splice_after(iterator after_this, basic_multiallocation_chain &x)
+ { slist_impl_.splice_after(after_this, x.slist_impl_); }
+
+ void incorporate_after(iterator after_this, void_pointer begin , iterator before_end)
+ { slist_impl_.incorporate_after(after_this, &to_node(begin), &to_node(before_end)); }
+
+ void incorporate_after(iterator after_this, void_pointer begin, void_pointer before_end, size_type n)
+ { slist_impl_.incorporate_after(after_this, &to_node(begin), &to_node(before_end), n); }
+
+ void swap(basic_multiallocation_chain &x)
+ { slist_impl_.swap(x.slist_impl_); }
+
+ static iterator iterator_to(void_pointer p)
+ { return slist_impl_t::s_iterator_to(to_node(p)); }
+
+ std::pair<void_pointer, void_pointer> extract_data()
+ {
+ std::pair<void_pointer, void_pointer> ret
+ (slist_impl_.begin().operator->()
+ ,slist_impl_.last().operator->());
+ slist_impl_.clear();
+ return ret;
+ }
+};
+
+template<class T>
+struct cast_functor
+{
+ typedef typename container_detail::add_reference<T>::type result_type;
+ template<class U>
+ result_type operator()(U &ptr) const
+ { return *static_cast<T*>(static_cast<void*>(&ptr)); }
+};
+
+template<class MultiallocationChain, class T>
+class transform_multiallocation_chain
+{
+ private:
+ BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain)
+
+ MultiallocationChain holder_;
+ typedef typename MultiallocationChain::void_pointer void_pointer;
+ typedef typename boost::intrusive::pointer_traits
+ <void_pointer>::template rebind_pointer<T>::type pointer;
+
+ static pointer cast(void_pointer p)
+ {
+ return pointer(static_cast<T*>(container_detail::to_raw_pointer(p)));
+ }
+
+ public:
+ typedef transform_iterator
+ < typename MultiallocationChain::iterator
+ , container_detail::cast_functor <T> > iterator;
+ typedef typename MultiallocationChain::size_type size_type;
+
+ transform_multiallocation_chain()
+ : holder_()
+ {}
+
+ transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other)
+ : holder_()
+ { this->swap(other); }
+
+ transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other)
+ : holder_(boost::move(other))
+ {}
+
+ transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other)
+ {
+ transform_multiallocation_chain tmp(boost::move(other));
+ this->swap(tmp);
+ return *this;
+ }
+
+ void push_front(pointer mem)
+ { holder_.push_front(mem); }
+
+ void swap(transform_multiallocation_chain &other_chain)
+ { holder_.swap(other_chain.holder_); }
+
+ void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_begin, iterator before_end, size_type n)
+ { holder_.splice_after(after_this.base(), x.holder_, before_begin.base(), before_end.base(), n); }
+
+ void incorporate_after(iterator after_this, void_pointer begin, void_pointer before_end, size_type n)
+ { holder_.incorporate_after(after_this.base(), begin, before_end, n); }
+
+ void pop_front()
+ { holder_.pop_front(); }
+
+ pointer front()
+ { return cast(holder_.front()); }
+
+ bool empty() const
+ { return holder_.empty(); }
+
+ iterator before_begin()
+ { return iterator(holder_.before_begin()); }
+
+ iterator begin()
+ { return iterator(holder_.begin()); }
+
+ iterator end()
+ { return iterator(holder_.end()); }
+
+ iterator last()
+ { return iterator(holder_.last()); }
+
+ size_type size() const
+ { return holder_.size(); }
+
+ void clear()
+ { holder_.clear(); }
+
+ iterator insert_after(iterator it, pointer m)
+ { return iterator(holder_.insert_after(it.base(), m)); }
+
+ static iterator iterator_to(pointer p)
+ { return iterator(MultiallocationChain::iterator_to(p)); }
+
+ std::pair<void_pointer, void_pointer> extract_data()
+ { return holder_.extract_data(); }
+
+ MultiallocationChain extract_multiallocation_chain()
+ {
+ return MultiallocationChain(boost::move(holder_));
+ }
+};
+
+}}}
+
+// namespace container_detail {
+// namespace container {
+// namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
diff --git a/boost/container/detail/node_alloc_holder.hpp b/boost/container/detail/node_alloc_holder.hpp
new file mode 100644
index 0000000000..9b0a0a524b
--- /dev/null
+++ b/boost/container/detail/node_alloc_holder.hpp
@@ -0,0 +1,488 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_NODE_ALLOC_HPP_
+#define BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+#include <utility>
+#include <functional>
+
+#include <boost/move/move.hpp>
+#include <boost/intrusive/options.hpp>
+
+#include <boost/container/detail/version_type.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/utilities.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/destroyers.hpp>
+
+#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+#include <boost/container/detail/algorithms.hpp>
+
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+//!A deleter for scoped_ptr that deallocates the memory
+//!allocated for an object using a STL allocator.
+template <class A>
+struct scoped_deallocator
+{
+ typedef allocator_traits<A> allocator_traits_type;
+ typedef typename allocator_traits_type::pointer pointer;
+ typedef container_detail::integral_constant<unsigned,
+ boost::container::container_detail::
+ version<A>::value> alloc_version;
+ typedef container_detail::integral_constant<unsigned, 1> allocator_v1;
+ typedef container_detail::integral_constant<unsigned, 2> allocator_v2;
+
+ private:
+ void priv_deallocate(allocator_v1)
+ { m_alloc.deallocate(m_ptr, 1); }
+
+ void priv_deallocate(allocator_v2)
+ { m_alloc.deallocate_one(m_ptr); }
+
+ BOOST_MOVABLE_BUT_NOT_COPYABLE(scoped_deallocator)
+
+ public:
+
+ pointer m_ptr;
+ A& m_alloc;
+
+ scoped_deallocator(pointer p, A& a)
+ : m_ptr(p), m_alloc(a)
+ {}
+
+ ~scoped_deallocator()
+ { if (m_ptr)priv_deallocate(alloc_version()); }
+
+ scoped_deallocator(BOOST_RV_REF(scoped_deallocator) o)
+ : m_ptr(o.m_ptr), m_alloc(o.m_alloc)
+ { o.release(); }
+
+ pointer get() const
+ { return m_ptr; }
+
+ void release()
+ { m_ptr = 0; }
+};
+
+template <class A>
+class allocator_destroyer_and_chain_builder
+{
+ typedef allocator_traits<A> allocator_traits_type;
+ typedef typename allocator_traits_type::value_type value_type;
+ typedef typename A::multiallocation_chain multiallocation_chain;
+
+ A & a_;
+ multiallocation_chain &c_;
+
+ public:
+ allocator_destroyer_and_chain_builder(A &a, multiallocation_chain &c)
+ : a_(a), c_(c)
+ {}
+
+ void operator()(const typename A::pointer &p)
+ {
+ allocator_traits<A>::destroy(a_, container_detail::to_raw_pointer(p));
+ c_.push_front(p);
+ }
+};
+
+template <class A>
+class allocator_multialloc_chain_node_deallocator
+{
+ typedef allocator_traits<A> allocator_traits_type;
+ typedef typename allocator_traits_type::value_type value_type;
+ typedef typename A::multiallocation_chain multiallocation_chain;
+ typedef allocator_destroyer_and_chain_builder<A> chain_builder;
+
+ A & a_;
+ multiallocation_chain c_;
+
+ public:
+ allocator_multialloc_chain_node_deallocator(A &a)
+ : a_(a), c_()
+ {}
+
+ chain_builder get_chain_builder()
+ { return chain_builder(a_, c_); }
+
+ ~allocator_multialloc_chain_node_deallocator()
+ {
+ if(!c_.empty())
+ a_.deallocate_individual(boost::move(c_));
+ }
+};
+
+template<class ValueCompare, class Node>
+struct node_compare
+ : private ValueCompare
+{
+ typedef typename ValueCompare::key_type key_type;
+ typedef typename ValueCompare::value_type value_type;
+ typedef typename ValueCompare::key_of_value key_of_value;
+
+ node_compare(const ValueCompare &pred)
+ : ValueCompare(pred)
+ {}
+
+ ValueCompare &value_comp()
+ { return static_cast<ValueCompare &>(*this); }
+
+ ValueCompare &value_comp() const
+ { return static_cast<const ValueCompare &>(*this); }
+
+ bool operator()(const Node &a, const Node &b) const
+ { return ValueCompare::operator()(a.get_data(), b.get_data()); }
+};
+
+template<class A, class ICont, class Pred = container_detail::nat>
+struct node_alloc_holder
+{
+ typedef allocator_traits<A> allocator_traits_type;
+ typedef node_alloc_holder<A, ICont> self_t;
+ typedef typename allocator_traits_type::value_type value_type;
+ typedef typename ICont::value_type Node;
+ typedef typename allocator_traits_type::template
+ portable_rebind_alloc<Node>::type NodeAlloc;
+ typedef allocator_traits<NodeAlloc> node_allocator_traits_type;
+ typedef A ValAlloc;
+ typedef typename node_allocator_traits_type::pointer NodePtr;
+ typedef container_detail::scoped_deallocator<NodeAlloc> Deallocator;
+ typedef typename node_allocator_traits_type::size_type size_type;
+ typedef typename node_allocator_traits_type::difference_type difference_type;
+ typedef container_detail::integral_constant<unsigned, 1> allocator_v1;
+ typedef container_detail::integral_constant<unsigned, 2> allocator_v2;
+ typedef container_detail::integral_constant<unsigned,
+ boost::container::container_detail::
+ version<NodeAlloc>::value> alloc_version;
+ typedef typename ICont::iterator icont_iterator;
+ typedef typename ICont::const_iterator icont_citerator;
+ typedef allocator_destroyer<NodeAlloc> Destroyer;
+ typedef allocator_traits<NodeAlloc> NodeAllocTraits;
+
+ private:
+ BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder)
+
+ public:
+
+ //Constructors for sequence containers
+ node_alloc_holder()
+ : members_()
+ {}
+
+ explicit node_alloc_holder(const ValAlloc &a)
+ : members_(a)
+ {}
+
+ explicit node_alloc_holder(const node_alloc_holder &x)
+ : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
+ {}
+
+ explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x)
+ : members_(boost::move(x.node_alloc()))
+ { this->icont().swap(x.icont()); }
+
+ //Constructors for associative containers
+ explicit node_alloc_holder(const ValAlloc &a, const Pred &c)
+ : members_(a, c)
+ {}
+
+ explicit node_alloc_holder(const node_alloc_holder &x, const Pred &c)
+ : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c)
+ {}
+
+ explicit node_alloc_holder(const Pred &c)
+ : members_(c)
+ {}
+
+ //helpers for move assignments
+ explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const Pred &c)
+ : members_(boost::move(x.node_alloc()), c)
+ { this->icont().swap(x.icont()); }
+
+ void copy_assign_alloc(const node_alloc_holder &x)
+ {
+ container_detail::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag;
+ container_detail::assign_alloc( static_cast<NodeAlloc &>(this->members_)
+ , static_cast<const NodeAlloc &>(x.members_), flag);
+ }
+
+ void move_assign_alloc( node_alloc_holder &x)
+ {
+ container_detail::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag;
+ container_detail::move_alloc( static_cast<NodeAlloc &>(this->members_)
+ , static_cast<NodeAlloc &>(x.members_), flag);
+ }
+
+ ~node_alloc_holder()
+ { this->clear(alloc_version()); }
+
+ size_type max_size() const
+ { return allocator_traits_type::max_size(this->node_alloc()); }
+
+ NodePtr allocate_one()
+ { return this->allocate_one(alloc_version()); }
+
+ NodePtr allocate_one(allocator_v1)
+ { return this->node_alloc().allocate(1); }
+
+ NodePtr allocate_one(allocator_v2)
+ { return this->node_alloc().allocate_one(); }
+
+ void deallocate_one(const NodePtr &p)
+ { return this->deallocate_one(p, alloc_version()); }
+
+ void deallocate_one(const NodePtr &p, allocator_v1)
+ { this->node_alloc().deallocate(p, 1); }
+
+ void deallocate_one(const NodePtr &p, allocator_v2)
+ { this->node_alloc().deallocate_one(p); }
+/*
+ template<class A, class Convertible1, class Convertible2>
+ static void construct(A &a, const NodePtr &ptr,
+ BOOST_RV_REF_2_TEMPL_ARGS(std::pair, Convertible1, Convertible2) value)
+ {
+ typedef typename Node::hook_type hook_type;
+ typedef typename Node::value_type::first_type first_type;
+ typedef typename Node::value_type::second_type second_type;
+ Node *nodeptr = container_detail::to_raw_pointer(ptr);
+
+ //Hook constructor does not throw
+ allocator_traits<A>::construct(a, static_cast<hook_type*>(nodeptr));
+
+ //Now construct pair members_holder
+ value_type *valueptr = &nodeptr->get_data();
+ allocator_traits<A>::construct(a, &valueptr->first, boost::move(value.first));
+ BOOST_TRY{
+ allocator_traits<A>::construct(a, &valueptr->second, boost::move(value.second));
+ }
+ BOOST_CATCH(...){
+ allocator_traits<A>::destroy(a, &valueptr->first);
+ BOOST_RETHROW
+ }
+ BOOST_CATCH_END
+ }
+*/
+ #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+/*
+ template<class A, class ...Args>
+ static void construct(A &a, const NodePtr &ptr, Args &&...args)
+ {
+ }
+*/
+ template<class ...Args>
+ NodePtr create_node(Args &&...args)
+ {
+ NodePtr p = this->allocate_one();
+ Deallocator node_deallocator(p, this->node_alloc());
+ allocator_traits<NodeAlloc>::construct
+ (this->node_alloc(), container_detail::to_raw_pointer(p), boost::forward<Args>(args)...);
+ node_deallocator.release();
+ return (p);
+ }
+
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ NodePtr create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ NodePtr p = this->allocate_one(); \
+ Deallocator node_deallocator(p, this->node_alloc()); \
+ allocator_traits<NodeAlloc>::construct \
+ (this->node_alloc(), container_detail::to_raw_pointer(p) \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
+ node_deallocator.release(); \
+ return (p); \
+ } \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template<class It>
+ NodePtr create_node_from_it(const It &it)
+ {
+ NodePtr p = this->allocate_one();
+ Deallocator node_deallocator(p, this->node_alloc());
+ ::boost::container::construct_in_place(this->node_alloc(), container_detail::to_raw_pointer(p), it);
+ node_deallocator.release();
+ return (p);
+ }
+
+ void destroy_node(const NodePtr &nodep)
+ {
+ allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(nodep));
+ this->deallocate_one(nodep);
+ }
+
+ void swap(node_alloc_holder &x)
+ {
+ this->icont().swap(x.icont());
+ container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
+ container_detail::swap_alloc(this->node_alloc(), x.node_alloc(), flag);
+ }
+
+ template<class FwdIterator, class Inserter>
+ FwdIterator allocate_many_and_construct
+ (FwdIterator beg, difference_type n, Inserter inserter)
+ {
+ if(n){
+ typedef typename NodeAlloc::multiallocation_chain multiallocation_chain;
+
+ //Try to allocate memory in a single block
+ multiallocation_chain mem(this->node_alloc().allocate_individual(n));
+ int constructed = 0;
+ Node *p = 0;
+ BOOST_TRY{
+ for(difference_type i = 0; i < n; ++i, ++beg, --constructed){
+ p = container_detail::to_raw_pointer(mem.front());
+ mem.pop_front();
+ //This can throw
+ constructed = 0;
+ boost::container::construct_in_place(this->node_alloc(), p, beg);
+ ++constructed;
+ //This can throw in some containers (predicate might throw)
+ inserter(*p);
+ }
+ }
+ BOOST_CATCH(...){
+ if(constructed){
+ allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(p));
+ }
+ this->node_alloc().deallocate_individual(boost::move(mem));
+ BOOST_RETHROW
+ }
+ BOOST_CATCH_END
+ }
+ return beg;
+ }
+
+ void clear(allocator_v1)
+ { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); }
+
+ void clear(allocator_v2)
+ {
+ typename NodeAlloc::multiallocation_chain chain;
+ allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain);
+ this->icont().clear_and_dispose(builder);
+ //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true));
+ if(!chain.empty())
+ this->node_alloc().deallocate_individual(boost::move(chain));
+ }
+
+ icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, allocator_v1)
+ { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); }
+
+ icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, allocator_v2)
+ {
+ allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc());
+ return this->icont().erase_and_dispose(first, last, chain_holder.get_chain_builder());
+ }
+
+ template<class Key, class Comparator>
+ size_type erase_key(const Key& k, const Comparator &comp, allocator_v1)
+ { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); }
+
+ template<class Key, class Comparator>
+ size_type erase_key(const Key& k, const Comparator &comp, allocator_v2)
+ {
+ allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc());
+ return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder());
+ }
+
+ protected:
+ struct cloner
+ {
+ cloner(node_alloc_holder &holder)
+ : m_holder(holder)
+ {}
+
+ NodePtr operator()(const Node &other) const
+ { return m_holder.create_node(other.get_data()); }
+
+ node_alloc_holder &m_holder;
+ };
+
+ struct members_holder
+ : public NodeAlloc
+ {
+ private:
+ members_holder(const members_holder&);
+ members_holder & operator=(const members_holder&);
+
+ public:
+ members_holder()
+ : NodeAlloc(), m_icont()
+ {}
+
+ template<class ConvertibleToAlloc>
+ explicit members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc)
+ : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc))
+ , m_icont()
+ {}
+
+ template<class ConvertibleToAlloc>
+ members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const Pred &c)
+ : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc))
+ , m_icont(typename ICont::value_compare(c))
+ {}
+
+ explicit members_holder(const Pred &c)
+ : NodeAlloc()
+ , m_icont(typename ICont::value_compare(c))
+ {}
+
+ //The intrusive container
+ ICont m_icont;
+ };
+
+ ICont &non_const_icont() const
+ { return const_cast<ICont&>(this->members_.m_icont); }
+
+ ICont &icont()
+ { return this->members_.m_icont; }
+
+ const ICont &icont() const
+ { return this->members_.m_icont; }
+
+ NodeAlloc &node_alloc()
+ { return static_cast<NodeAlloc &>(this->members_); }
+
+ const NodeAlloc &node_alloc() const
+ { return static_cast<const NodeAlloc &>(this->members_); }
+
+ members_holder members_;
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
diff --git a/boost/container/detail/node_pool_impl.hpp b/boost/container/detail/node_pool_impl.hpp
new file mode 100644
index 0000000000..9ee9e311c0
--- /dev/null
+++ b/boost/container/detail/node_pool_impl.hpp
@@ -0,0 +1,367 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_NODE_POOL_IMPL_HPP
+#define BOOST_CONTAINER_DETAIL_NODE_POOL_IMPL_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/container_fwd.hpp>
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/utilities.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/intrusive/set.hpp>
+#include <boost/intrusive/slist.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/math_functions.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/pool_common.hpp>
+#include <boost/assert.hpp>
+#include <cstddef>
+#include <functional> //std::unary_function
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class SegmentManagerBase>
+class private_node_pool_impl
+{
+ //Non-copyable
+ private_node_pool_impl();
+ private_node_pool_impl(const private_node_pool_impl &);
+ private_node_pool_impl &operator=(const private_node_pool_impl &);
+
+ //A node object will hold node_t when it's not allocated
+ public:
+ typedef typename SegmentManagerBase::void_pointer void_pointer;
+ typedef typename node_slist<void_pointer>::slist_hook_t slist_hook_t;
+ typedef typename node_slist<void_pointer>::node_t node_t;
+ typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t;
+ typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain;
+ typedef typename SegmentManagerBase::size_type size_type;
+
+ private:
+ typedef typename bi::make_slist
+ < node_t, bi::base_hook<slist_hook_t>
+ , bi::linear<true>
+ , bi::constant_time_size<false> >::type blockslist_t;
+ public:
+
+ //!Segment manager typedef
+ typedef SegmentManagerBase segment_manager_base_type;
+
+ //!Constructor from a segment manager. Never throws
+ private_node_pool_impl(segment_manager_base_type *segment_mngr_base, size_type node_size, size_type nodes_per_block)
+ : m_nodes_per_block(nodes_per_block)
+ , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value)))
+ //General purpose allocator
+ , mp_segment_mngr_base(segment_mngr_base)
+ , m_blocklist()
+ , m_freelist()
+ //Debug node count
+ , m_allocated(0)
+ {}
+
+ //!Destructor. Deallocates all allocated blocks. Never throws
+ ~private_node_pool_impl()
+ { this->purge_blocks(); }
+
+ size_type get_real_num_node() const
+ { return m_nodes_per_block; }
+
+ //!Returns the segment manager. Never throws
+ segment_manager_base_type* get_segment_manager_base()const
+ { return container_detail::to_raw_pointer(mp_segment_mngr_base); }
+
+ void *allocate_node()
+ { return priv_alloc_node(); }
+
+ //!Deallocates an array pointed by ptr. Never throws
+ void deallocate_node(void *ptr)
+ { priv_dealloc_node(ptr); }
+
+ //!Allocates a singly linked list of n nodes ending in null pointer.
+ multiallocation_chain allocate_nodes(const size_type n)
+ {
+ //Preallocate all needed blocks to fulfill the request
+ size_type cur_nodes = m_freelist.size();
+ if(cur_nodes < n){
+ priv_alloc_block(((n - cur_nodes) - 1)/m_nodes_per_block + 1);
+ }
+
+ //We just iterate the needed nodes to get the last we'll erase
+ typedef typename free_nodes_t::iterator free_iterator;
+ free_iterator before_last_new_it = m_freelist.before_begin();
+ for(size_type j = 0; j != n; ++j){
+ ++before_last_new_it;
+ }
+
+ //Cache the first node of the allocated range before erasing
+ free_iterator first_node(m_freelist.begin());
+ free_iterator last_node (before_last_new_it);
+
+ //Erase the range. Since we already have the distance, this is O(1)
+ m_freelist.erase_after( m_freelist.before_begin()
+ , ++free_iterator(before_last_new_it)
+ , n);
+
+ //Now take the last erased node and just splice it in the end
+ //of the intrusive list that will be traversed by the multialloc iterator.
+ multiallocation_chain chain;
+ chain.incorporate_after(chain.before_begin(), &*first_node, &*last_node, n);
+ m_allocated += n;
+ return boost::move(chain);
+ }
+
+ void deallocate_nodes(multiallocation_chain chain)
+ {
+ typedef typename multiallocation_chain::iterator iterator;
+ iterator it(chain.begin()), itend(chain.end());
+ while(it != itend){
+ void *pElem = &*it;
+ ++it;
+ priv_dealloc_node(pElem);
+ }
+ }
+
+ //!Deallocates all the free blocks of memory. Never throws
+ void deallocate_free_blocks()
+ {
+ typedef typename free_nodes_t::iterator nodelist_iterator;
+ typename blockslist_t::iterator bit(m_blocklist.before_begin()),
+ it(m_blocklist.begin()),
+ itend(m_blocklist.end());
+ free_nodes_t backup_list;
+ nodelist_iterator backup_list_last = backup_list.before_begin();
+
+ //Execute the algorithm and get an iterator to the last value
+ size_type blocksize = get_rounded_size
+ (m_real_node_size*m_nodes_per_block, (size_type) alignment_of<node_t>::value);
+
+ while(it != itend){
+ //Collect all the nodes from the block pointed by it
+ //and push them in the list
+ free_nodes_t free_nodes;
+ nodelist_iterator last_it = free_nodes.before_begin();
+ const void *addr = get_block_from_hook(&*it, blocksize);
+
+ m_freelist.remove_and_dispose_if
+ (is_between(addr, blocksize), push_in_list(free_nodes, last_it));
+
+ //If the number of nodes is equal to m_nodes_per_block
+ //this means that the block can be deallocated
+ if(free_nodes.size() == m_nodes_per_block){
+ //Unlink the nodes
+ free_nodes.clear();
+ it = m_blocklist.erase_after(bit);
+ mp_segment_mngr_base->deallocate((void*)addr);
+ }
+ //Otherwise, insert them in the backup list, since the
+ //next "remove_if" does not need to check them again.
+ else{
+ //Assign the iterator to the last value if necessary
+ if(backup_list.empty() && !m_freelist.empty()){
+ backup_list_last = last_it;
+ }
+ //Transfer nodes. This is constant time.
+ backup_list.splice_after
+ ( backup_list.before_begin()
+ , free_nodes
+ , free_nodes.before_begin()
+ , last_it
+ , free_nodes.size());
+ bit = it;
+ ++it;
+ }
+ }
+ //We should have removed all the nodes from the free list
+ BOOST_ASSERT(m_freelist.empty());
+
+ //Now pass all the node to the free list again
+ m_freelist.splice_after
+ ( m_freelist.before_begin()
+ , backup_list
+ , backup_list.before_begin()
+ , backup_list_last
+ , backup_list.size());
+ }
+
+ size_type num_free_nodes()
+ { return m_freelist.size(); }
+
+ //!Deallocates all used memory. Precondition: all nodes allocated from this pool should
+ //!already be deallocated. Otherwise, undefined behaviour. Never throws
+ void purge_blocks()
+ {
+ //check for memory leaks
+ BOOST_ASSERT(m_allocated==0);
+ size_type blocksize = get_rounded_size
+ (m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value);
+ typename blockslist_t::iterator
+ it(m_blocklist.begin()), itend(m_blocklist.end()), aux;
+
+ //We iterate though the NodeBlock list to free the memory
+ while(!m_blocklist.empty()){
+ void *addr = get_block_from_hook(&m_blocklist.front(), blocksize);
+ m_blocklist.pop_front();
+ mp_segment_mngr_base->deallocate((void*)addr);
+ }
+ //Just clear free node list
+ m_freelist.clear();
+ }
+
+ void swap(private_node_pool_impl &other)
+ {
+ BOOST_ASSERT(m_nodes_per_block == other.m_nodes_per_block);
+ BOOST_ASSERT(m_real_node_size == other.m_real_node_size);
+ std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base);
+ m_blocklist.swap(other.m_blocklist);
+ m_freelist.swap(other.m_freelist);
+ std::swap(m_allocated, other.m_allocated);
+ }
+
+ private:
+
+ struct push_in_list
+ {
+ push_in_list(free_nodes_t &l, typename free_nodes_t::iterator &it)
+ : slist_(l), last_it_(it)
+ {}
+
+ void operator()(typename free_nodes_t::pointer p) const
+ {
+ slist_.push_front(*p);
+ if(slist_.size() == 1){ //Cache last element
+ ++last_it_ = slist_.begin();
+ }
+ }
+
+ private:
+ free_nodes_t &slist_;
+ typename free_nodes_t::iterator &last_it_;
+ };
+
+ struct is_between
+ : std::unary_function<typename free_nodes_t::value_type, bool>
+ {
+ is_between(const void *addr, std::size_t size)
+ : beg_(static_cast<const char *>(addr)), end_(beg_+size)
+ {}
+
+ bool operator()(typename free_nodes_t::const_reference v) const
+ {
+ return (beg_ <= reinterpret_cast<const char *>(&v) &&
+ end_ > reinterpret_cast<const char *>(&v));
+ }
+ private:
+ const char * beg_;
+ const char * end_;
+ };
+
+ //!Allocates one node, using single segregated storage algorithm.
+ //!Never throws
+ node_t *priv_alloc_node()
+ {
+ //If there are no free nodes we allocate a new block
+ if (m_freelist.empty())
+ priv_alloc_block();
+ //We take the first free node
+ node_t *n = (node_t*)&m_freelist.front();
+ m_freelist.pop_front();
+ ++m_allocated;
+ return n;
+ }
+
+ //!Deallocates one node, using single segregated storage algorithm.
+ //!Never throws
+ void priv_dealloc_node(void *pElem)
+ {
+ //We put the node at the beginning of the free node list
+ node_t * to_deallocate = static_cast<node_t*>(pElem);
+ m_freelist.push_front(*to_deallocate);
+ BOOST_ASSERT(m_allocated>0);
+ --m_allocated;
+ }
+
+ //!Allocates several blocks of nodes. Can throw
+ void priv_alloc_block(size_type num_blocks = 1)
+ {
+ if(!num_blocks)
+ return;
+ size_type blocksize =
+ get_rounded_size(m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value);
+
+ try{
+ for(size_type i = 0; i != num_blocks; ++i){
+ //We allocate a new NodeBlock and put it as first
+ //element in the free Node list
+ char *pNode = reinterpret_cast<char*>
+ (mp_segment_mngr_base->allocate(blocksize + sizeof(node_t)));
+ char *pBlock = pNode;
+ m_blocklist.push_front(get_block_hook(pBlock, blocksize));
+
+ //We initialize all Nodes in Node Block to insert
+ //them in the free Node list
+ for(size_type i = 0; i < m_nodes_per_block; ++i, pNode += m_real_node_size){
+ m_freelist.push_front(*new (pNode) node_t);
+ }
+ }
+ }
+ catch(...){
+ //to-do: if possible, an efficient way to deallocate allocated blocks
+ throw;
+ }
+ }
+
+ //!Deprecated, use deallocate_free_blocks
+ void deallocate_free_chunks()
+ { this->deallocate_free_blocks(); }
+
+ //!Deprecated, use purge_blocks
+ void purge_chunks()
+ { this->purge_blocks(); }
+
+ private:
+ //!Returns a reference to the block hook placed in the end of the block
+ static node_t & get_block_hook (void *block, size_type blocksize)
+ {
+ return *reinterpret_cast<node_t*>(reinterpret_cast<char*>(block) + blocksize);
+ }
+
+ //!Returns the starting address of the block reference to the block hook placed in the end of the block
+ void *get_block_from_hook (node_t *hook, size_type blocksize)
+ {
+ return (reinterpret_cast<char*>(hook) - blocksize);
+ }
+
+ private:
+ typedef typename boost::intrusive::pointer_traits
+ <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t;
+
+ const size_type m_nodes_per_block;
+ const size_type m_real_node_size;
+ segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager
+ blockslist_t m_blocklist; //Intrusive container of blocks
+ free_nodes_t m_freelist; //Intrusive container of free nods
+ size_type m_allocated; //Used nodes for debugging
+};
+
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp
new file mode 100644
index 0000000000..1aeff91137
--- /dev/null
+++ b/boost/container/detail/pair.hpp
@@ -0,0 +1,320 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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_DETAIL_PAIR_HPP
+#define BOOST_CONTAINER_CONTAINER_DETAIL_PAIR_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/type_traits.hpp>
+
+#include <utility> //std::pair
+
+#include <boost/move/move.hpp>
+#include <boost/type_traits/is_class.hpp>
+
+#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template <class T1, class T2>
+struct pair;
+
+template <class T>
+struct is_pair
+{
+ static const bool value = false;
+};
+
+template <class T1, class T2>
+struct is_pair< pair<T1, T2> >
+{
+ static const bool value = true;
+};
+
+template <class T1, class T2>
+struct is_pair< std::pair<T1, T2> >
+{
+ static const bool value = true;
+};
+
+struct pair_nat;
+
+struct piecewise_construct_t { };
+static const piecewise_construct_t piecewise_construct = piecewise_construct_t();
+
+template <class T1, class T2>
+struct pair
+{
+ private:
+ BOOST_COPYABLE_AND_MOVABLE(pair)
+
+ public:
+ typedef T1 first_type;
+ typedef T2 second_type;
+
+ T1 first;
+ T2 second;
+
+ //Default constructor
+ pair()
+ : first(), second()
+ {}
+/*
+ //pair from two values
+ pair(const T1 &t1, const T2 &t2)
+ : first(t1)
+ , second(t2)
+ {}
+
+
+ //pair from two values
+ pair(BOOST_RV_REF(T1) t1, BOOST_RV_REF(T2) t2)
+ : first(::boost::move(t1))
+ , second(::boost::move(t2))
+ {}
+*/
+ template<class U, class V>
+ pair(BOOST_FWD_REF(U) u, BOOST_FWD_REF(V) v)
+ : first(::boost::forward<U>(u))
+ , second(::boost::forward<V>(v))
+ {}
+
+ //pair copy assignment
+ pair(const pair& x)
+ : first(x.first), second(x.second)
+ {}
+
+ template <class D, class S>
+ pair(const pair<D, S> &p)
+ : first(p.first), second(p.second)
+ {}
+
+ //pair move constructor
+ pair(BOOST_RV_REF(pair) p)
+ : first(::boost::move(p.first)), second(::boost::move(p.second))
+ {}
+
+ template <class D, class S>
+ pair(BOOST_RV_REF_2_TEMPL_ARGS(pair, D, S) p)
+ : first(::boost::move(p.first)), second(::boost::move(p.second))
+ {}
+
+ //std::pair copy constructor
+ pair(const std::pair<T1, T2>& x)
+ : first(x.first), second(x.second)
+ {}
+
+ template <class D, class S>
+ pair(const std::pair<D, S>& p)
+ : first(p.first), second(p.second)
+ {}
+
+ //std::pair move constructor
+ template <class D, class S>
+ pair(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, D, S) p)
+ : first(::boost::move(p.first)), second(::boost::move(p.second))
+ {}
+
+ pair(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2) p)
+ : first(::boost::move(p.first)), second(::boost::move(p.second))
+ {}
+
+ //piecewise_construct missing
+/*
+ //Variadic versions
+ template<class U>
+ pair(BOOST_CONTAINER_PP_PARAM(U, u), typename container_detail::disable_if
+ < container_detail::is_pair< typename container_detail::remove_ref_const<U>::type >, pair_nat>::type* = 0)
+ : first(::boost::forward<U>(u))
+ , second()
+ {}
+
+ #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template<class U, class V, class ...Args>
+ pair(U &&u, V &&v)
+ : first(::boost::forward<U>(u))
+ , second(::boost::forward<V>(v), ::boost::forward<Args>(args)...)
+ {}
+
+ #else
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ template<class U, BOOST_PP_ENUM_PARAMS(n, class P)> \
+ pair(BOOST_CONTAINER_PP_PARAM(U, u) \
+ ,BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ : first(::boost::forward<U>(u)) \
+ , second(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \
+ {} \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+ #endif
+*/
+ //pair copy assignment
+ pair& operator=(BOOST_COPY_ASSIGN_REF(pair) p)
+ {
+ first = p.first;
+ second = p.second;
+ return *this;
+ }
+
+ template <class D, class S>
+ pair& operator=(const pair<D, S>&p)
+ {
+ first = p.first;
+ second = p.second;
+ return *this;
+ }
+
+ //pair move assignment
+ pair& operator=(BOOST_RV_REF(pair) p)
+ {
+ first = ::boost::move(p.first);
+ second = ::boost::move(p.second);
+ return *this;
+ }
+
+ template <class D, class S>
+ pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(pair, D, S) p)
+ {
+ first = ::boost::move(p.first);
+ second = ::boost::move(p.second);
+ return *this;
+ }
+
+ //std::pair copy assignment
+ pair& operator=(const std::pair<T1, T2> &p)
+ {
+ first = p.first;
+ second = p.second;
+ return *this;
+ }
+
+ template <class D, class S>
+ pair& operator=(const std::pair<D, S> &p)
+ {
+ first = ::boost::move(p.first);
+ second = ::boost::move(p.second);
+ return *this;
+ }
+
+ //std::pair move assignment
+ pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2) p)
+ {
+ first = ::boost::move(p.first);
+ second = ::boost::move(p.second);
+ return *this;
+ }
+
+ template <class D, class S>
+ pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, D, S) p)
+ {
+ first = ::boost::move(p.first);
+ second = ::boost::move(p.second);
+ return *this;
+ }
+
+ //swap
+ void swap(pair& p)
+ {
+ using std::swap;
+ swap(this->first, p.first);
+ swap(this->second, p.second);
+ }
+};
+
+template <class T1, class T2>
+inline bool operator==(const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return static_cast<bool>(x.first == y.first && x.second == y.second); }
+
+template <class T1, class T2>
+inline bool operator< (const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return static_cast<bool>(x.first < y.first ||
+ (!(y.first < x.first) && x.second < y.second)); }
+
+template <class T1, class T2>
+inline bool operator!=(const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return static_cast<bool>(!(x == y)); }
+
+template <class T1, class T2>
+inline bool operator> (const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return y < x; }
+
+template <class T1, class T2>
+inline bool operator>=(const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return static_cast<bool>(!(x < y)); }
+
+template <class T1, class T2>
+inline bool operator<=(const pair<T1,T2>& x, const pair<T1,T2>& y)
+{ return static_cast<bool>(!(y < x)); }
+
+template <class T1, class T2>
+inline pair<T1, T2> make_pair(T1 x, T2 y)
+{ return pair<T1, T2>(x, y); }
+
+template <class T1, class T2>
+inline void swap(pair<T1, T2>& x, pair<T1, T2>& y)
+{
+ swap(x.first, y.first);
+ swap(x.second, y.second);
+}
+
+} //namespace container_detail {
+} //namespace container {
+
+
+//Without this specialization recursive flat_(multi)map instantiation fails
+//because is_enum needs to instantiate the recursive pair, leading to a compilation error).
+//This breaks the cycle clearly stating that pair is not an enum avoiding any instantiation.
+template<class T>
+struct is_enum;
+
+template<class T, class U>
+struct is_enum< ::boost::container::container_detail::pair<T, U> >
+{
+ static const bool value = false;
+};
+
+//This specialization is needed to avoid instantiation of pair in
+//is_class, and allow recursive maps.
+template <class T1, class T2>
+struct is_class< ::boost::container::container_detail::pair<T1, T2> >
+ : public ::boost::true_type
+{};
+
+#ifdef BOOST_NO_RVALUE_REFERENCES
+
+template<class T1, class T2>
+struct has_move_emulation_enabled< ::boost::container::container_detail::pair<T1, T2> >
+ : ::boost::true_type
+{};
+
+#endif
+
+
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_PAIR_HPP
diff --git a/boost/container/detail/pool_common.hpp b/boost/container/detail/pool_common.hpp
new file mode 100644
index 0000000000..c66e2cd18c
--- /dev/null
+++ b/boost/container/detail/pool_common.hpp
@@ -0,0 +1,52 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_NODE_POOL_COMMON_HPP
+#define BOOST_CONTAINER_DETAIL_NODE_POOL_COMMON_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/intrusive/slist.hpp>
+#include <new>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class VoidPointer>
+struct node_slist
+{
+ //This hook will be used to chain the individual nodes
+ typedef typename bi::make_slist_base_hook
+ <bi::void_pointer<VoidPointer>, bi::link_mode<bi::normal_link> >::type slist_hook_t;
+
+ //A node object will hold node_t when it's not allocated
+ typedef slist_hook_t node_t;
+
+ typedef typename bi::make_slist
+ <node_t, bi::linear<true>, bi::base_hook<slist_hook_t> >::type node_slist_t;
+};
+
+template<class T>
+struct is_stateless_segment_manager
+{
+ static const bool value = false;
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
diff --git a/boost/container/detail/preprocessor.hpp b/boost/container/detail/preprocessor.hpp
new file mode 100644
index 0000000000..9916fbac62
--- /dev/null
+++ b/boost/container/detail/preprocessor.hpp
@@ -0,0 +1,178 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2008-2011. 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_DETAIL_PREPROCESSOR_HPP
+#define BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include <boost/container/detail/config_begin.hpp>
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+#include <boost/container/detail/stored_ref.hpp>
+#endif //#ifndef BOOST_NO_RVALUE_REFERENCES
+
+#include <boost/container/detail/workaround.hpp>
+
+#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+//#error "This file is not needed when perfect forwarding is available"
+#endif //BOOST_CONTAINER_PERFECT_FORWARDING
+
+#include <boost/preprocessor/iteration/local.hpp>
+#include <boost/preprocessor/punctuation/paren_if.hpp>
+#include <boost/preprocessor/punctuation/comma_if.hpp>
+#include <boost/preprocessor/control/expr_if.hpp>
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/repetition/enum.hpp>
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/enum_trailing_params.hpp>
+#include <boost/preprocessor/repetition/enum_trailing.hpp>
+#include <boost/preprocessor/repetition/enum_shifted_params.hpp>
+#include <boost/preprocessor/repetition/enum_shifted.hpp>
+#include <boost/preprocessor/repetition/repeat.hpp>
+#include <boost/preprocessor/logical/not.hpp>
+#include <boost/preprocessor/arithmetic/sub.hpp>
+#include <boost/preprocessor/arithmetic/add.hpp>
+#include <boost/preprocessor/iteration/iterate.hpp>
+
+#define BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS 10
+
+//Note:
+//We define template parameters as const references to
+//be able to bind temporaries. After that we will un-const them.
+//This cast is ugly but it is necessary until "perfect forwarding"
+//is achieved in C++0x. Meanwhile, if we want to be able to
+//bind rvalues with non-const references, we have to be ugly
+#ifndef BOOST_NO_RVALUE_REFERENCES
+ #define BOOST_CONTAINER_PP_PARAM_LIST(z, n, data) \
+ BOOST_PP_CAT(P, n) && BOOST_PP_CAT(p, n) \
+ //!
+#else
+ #define BOOST_CONTAINER_PP_PARAM_LIST(z, n, data) \
+ const BOOST_PP_CAT(P, n) & BOOST_PP_CAT(p, n) \
+ //!
+#endif //#ifndef BOOST_NO_RVALUE_REFERENCES
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+ #define BOOST_CONTAINER_PP_PARAM(U, u) \
+ U && u \
+ //!
+#else
+ #define BOOST_CONTAINER_PP_PARAM(U, u) \
+ const U & u \
+ //!
+#endif //#ifndef BOOST_NO_RVALUE_REFERENCES
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+
+ #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+
+ #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \
+ BOOST_PP_CAT(m_p, n) (boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(p, n) )) \
+ //!
+
+ #else //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+
+ #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \
+ BOOST_PP_CAT(m_p, n) (static_cast<BOOST_PP_CAT(P, n)>( BOOST_PP_CAT(p, n) )) \
+ //!
+
+ #endif //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+
+#else //BOOST_NO_RVALUE_REFERENCES
+
+ #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \
+ BOOST_PP_CAT(m_p, n) (const_cast<BOOST_PP_CAT(P, n) &>(BOOST_PP_CAT(p, n))) \
+ //!
+#endif //#ifndef BOOST_NO_RVALUE_REFERENCES
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+
+ #if defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG)
+
+ #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \
+ BOOST_PP_CAT(P, n) & BOOST_PP_CAT(m_p, n); \
+ //!
+
+ #else //BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG
+
+ #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \
+ BOOST_PP_CAT(P, n) && BOOST_PP_CAT(m_p, n); \
+ //!
+
+ #endif //defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG)
+
+#else //BOOST_NO_RVALUE_REFERENCES
+
+ #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \
+ BOOST_PP_CAT(P, n) & BOOST_PP_CAT(m_p, n); \
+ //!
+#endif //#ifndef BOOST_NO_RVALUE_REFERENCES
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG)
+
+ #define BOOST_CONTAINER_PP_MEMBER_FORWARD(z, n, data) \
+ ::boost::container::container_detail::stored_ref< BOOST_PP_CAT(P, n) >::forward( BOOST_PP_CAT(this->m_p, n) ) \
+ //!
+
+#else //!defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG)
+
+ #define BOOST_CONTAINER_PP_MEMBER_FORWARD(z, n, data) \
+ boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(this->m_p, n) ) \
+ //!
+
+#endif //!defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG)
+
+#define BOOST_CONTAINER_PP_PARAM_INC(z, n, data) \
+ BOOST_PP_CAT(++this->m_p, n) \
+//!
+
+#define BOOST_CONTAINER_PP_IDENTITY(z, n, data) data
+
+
+#define BOOST_CONTAINER_PP_PARAM_FORWARD(z, n, data) \
+boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(p, n) ) \
+//!
+
+#define BOOST_CONTAINER_PP_DECLVAL(z, n, data) \
+boost::move_detail::declval< BOOST_PP_CAT(P, n) >() \
+//!
+
+#define BOOST_CONTAINER_PP_MEMBER_IT_FORWARD(z, n, data) \
+BOOST_PP_CAT(*this->m_p, n) \
+//!
+
+#define BOOST_CONTAINER_PP_TEMPLATE_PARAM_VOID_DEFAULT(z, n, data) \
+ BOOST_PP_CAT(class P, n) = void \
+//!
+
+#define BOOST_CONTAINER_PP_STATIC_PARAM_REF_DECLARE(z, n, data) \
+ static BOOST_PP_CAT(P, n) & BOOST_PP_CAT(p, n); \
+//!
+
+#define BOOST_CONTAINER_PP_PARAM_PASS(z, n, data) \
+ BOOST_PP_CAT(p, n) \
+//!
+
+#define BOOST_CONTAINER_PP_FWD_TYPE(z, n, data) \
+ typename ::boost::move_detail::forward_type< BOOST_PP_CAT(P, n) >::type \
+//!
+
+#include <boost/container/detail/config_end.hpp>
+
+//#else
+
+//#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+//#error "This file is not needed when perfect forwarding is available"
+//#endif //BOOST_CONTAINER_PERFECT_FORWARDING
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP
diff --git a/boost/container/detail/stored_ref.hpp b/boost/container/detail/stored_ref.hpp
new file mode 100644
index 0000000000..df0faa85a0
--- /dev/null
+++ b/boost/container/detail/stored_ref.hpp
@@ -0,0 +1,92 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2008-2011. 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_DETAIL_STORED_REF_HPP
+#define BOOST_CONTAINER_DETAIL_STORED_REF_HPP
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+
+namespace boost{
+namespace container{
+namespace container_detail{
+
+template<class T>
+struct stored_ref
+{
+
+ static T && forward(T &t)
+ #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+ { return t; }
+ #else
+ { return boost::move(t); }
+ #endif
+};
+
+template<class T>
+struct stored_ref<const T>
+{
+ static const T && forward(const T &t)
+ #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+ { return t; }
+ #else
+ { return static_cast<const T&&>(t); }
+ #endif
+};
+
+template<class T>
+struct stored_ref<T&&>
+{
+ static T && forward(T &t)
+ #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+ { return t; }
+ #else
+ { return boost::move(t); }
+ #endif
+};
+
+template<class T>
+struct stored_ref<const T&&>
+{
+ static const T && forward(const T &t)
+ #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES
+ { return t; }
+ #else
+ { return static_cast<const T &&>(t); }
+ #endif
+};
+
+template<class T>
+struct stored_ref<const T&>
+{
+ static const T & forward(const T &t)
+ { return t; }
+};
+
+template<class T>
+struct stored_ref<T&>
+{
+ static T & forward(T &t)
+ { return t; }
+};
+
+} //namespace container_detail{
+} //namespace container{
+} //namespace boost{
+
+#else
+#error "This header can be included only for compiler with rvalue references"
+#endif //BOOST_NO_RVALUE_REFERENCES
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //BOOST_CONTAINER_DETAIL_STORED_REF_HPP
diff --git a/boost/container/detail/transform_iterator.hpp b/boost/container/detail/transform_iterator.hpp
new file mode 100644
index 0000000000..17eca9ef61
--- /dev/null
+++ b/boost/container/detail/transform_iterator.hpp
@@ -0,0 +1,176 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+// (C) Copyright Gennaro Prota 2003 - 2004.
+//
+// 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_DETAIL_TRANSFORM_ITERATORS_HPP
+#define BOOST_CONTAINER_DETAIL_TRANSFORM_ITERATORS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <iterator>
+
+namespace boost {
+namespace container {
+
+template <class PseudoReference>
+struct operator_arrow_proxy
+{
+ operator_arrow_proxy(const PseudoReference &px)
+ : m_value(px)
+ {}
+
+ PseudoReference* operator->() const { return &m_value; }
+ // This function is needed for MWCW and BCC, which won't call operator->
+ // again automatically per 13.3.1.2 para 8
+// operator T*() const { return &m_value; }
+ mutable PseudoReference m_value;
+};
+
+template <class T>
+struct operator_arrow_proxy<T&>
+{
+ operator_arrow_proxy(T &px)
+ : m_value(px)
+ {}
+
+ T* operator->() const { return const_cast<T*>(&m_value); }
+ // This function is needed for MWCW and BCC, which won't call operator->
+ // again automatically per 13.3.1.2 para 8
+// operator T*() const { return &m_value; }
+ T &m_value;
+};
+
+template <class Iterator, class UnaryFunction>
+class transform_iterator
+ : public UnaryFunction
+ , public std::iterator
+ < typename Iterator::iterator_category
+ , typename container_detail::remove_reference<typename UnaryFunction::result_type>::type
+ , typename Iterator::difference_type
+ , operator_arrow_proxy<typename UnaryFunction::result_type>
+ , typename UnaryFunction::result_type>
+{
+ public:
+ explicit transform_iterator(const Iterator &it, const UnaryFunction &f = UnaryFunction())
+ : UnaryFunction(f), m_it(it)
+ {}
+
+ explicit transform_iterator()
+ : UnaryFunction(), m_it()
+ {}
+
+ //Constructors
+ transform_iterator& operator++()
+ { increment(); return *this; }
+
+ transform_iterator operator++(int)
+ {
+ transform_iterator result (*this);
+ increment();
+ return result;
+ }
+
+ friend bool operator== (const transform_iterator& i, const transform_iterator& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const transform_iterator& i, const transform_iterator& i2)
+ { return !(i == i2); }
+
+/*
+ friend bool operator> (const transform_iterator& i, const transform_iterator& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const transform_iterator& i, const transform_iterator& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const transform_iterator& i, const transform_iterator& i2)
+ { return !(i < i2); }
+*/
+ friend typename Iterator::difference_type operator- (const transform_iterator& i, const transform_iterator& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ transform_iterator& operator+=(typename Iterator::difference_type off)
+ { this->advance(off); return *this; }
+
+ transform_iterator operator+(typename Iterator::difference_type off) const
+ {
+ transform_iterator other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend transform_iterator operator+(typename Iterator::difference_type off, const transform_iterator& right)
+ { return right + off; }
+
+ transform_iterator& operator-=(typename Iterator::difference_type off)
+ { this->advance(-off); return *this; }
+
+ transform_iterator operator-(typename Iterator::difference_type off) const
+ { return *this + (-off); }
+
+ typename UnaryFunction::result_type operator*() const
+ { return dereference(); }
+
+ operator_arrow_proxy<typename UnaryFunction::result_type>
+ operator->() const
+ { return operator_arrow_proxy<typename UnaryFunction::result_type>(dereference()); }
+
+ Iterator & base()
+ { return m_it; }
+
+ const Iterator & base() const
+ { return m_it; }
+
+ private:
+ Iterator m_it;
+
+ void increment()
+ { ++m_it; }
+
+ void decrement()
+ { --m_it; }
+
+ bool equal(const transform_iterator &other) const
+ { return m_it == other.m_it; }
+
+ bool less(const transform_iterator &other) const
+ { return other.m_it < m_it; }
+
+ typename UnaryFunction::result_type dereference() const
+ { return UnaryFunction::operator()(*m_it); }
+
+ void advance(typename Iterator::difference_type n)
+ { std::advance(m_it, n); }
+
+ typename Iterator::difference_type distance_to(const transform_iterator &other)const
+ { return std::distance(other.m_it, m_it); }
+};
+
+template <class Iterator, class UnaryFunc>
+transform_iterator<Iterator, UnaryFunc>
+make_transform_iterator(Iterator it, UnaryFunc fun)
+{
+ return transform_iterator<Iterator, UnaryFunc>(it, fun);
+}
+
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_TRANSFORM_ITERATORS_HPP
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
new file mode 100644
index 0000000000..6cd91ed2a6
--- /dev/null
+++ b/boost/container/detail/tree.hpp
@@ -0,0 +1,1154 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_TREE_HPP
+#define BOOST_CONTAINER_TREE_HPP
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/container_fwd.hpp>
+
+#include <boost/move/move.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/type_traits/has_trivial_destructor.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/intrusive/rbtree.hpp>
+
+#include <boost/container/detail/utilities.hpp>
+#include <boost/container/detail/algorithms.hpp>
+#include <boost/container/detail/node_alloc_holder.hpp>
+#include <boost/container/detail/destroyers.hpp>
+#include <boost/container/detail/pair.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+#include <utility> //std::pair
+#include <iterator>
+#include <algorithm>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class Key, class Value, class KeyCompare, class KeyOfValue>
+struct value_compare_impl
+ : public KeyCompare
+{
+ typedef Value value_type;
+ typedef KeyCompare key_compare;
+ typedef KeyOfValue key_of_value;
+ typedef Key key_type;
+
+ value_compare_impl(const key_compare &kcomp)
+ : key_compare(kcomp)
+ {}
+
+ const key_compare &key_comp() const
+ { return static_cast<const key_compare &>(*this); }
+
+ key_compare &key_comp()
+ { return static_cast<key_compare &>(*this); }
+
+ template<class T>
+ struct is_key
+ {
+ static const bool value = is_same<const T, const key_type>::value;
+ };
+
+ template<class T>
+ typename enable_if_c<is_key<T>::value, const key_type &>::type
+ key_forward(const T &key) const
+ { return key; }
+
+ template<class T>
+ typename enable_if_c<!is_key<T>::value, const key_type &>::type
+ key_forward(const T &key) const
+ { return KeyOfValue()(key); }
+
+ template<class KeyType, class KeyType2>
+ bool operator()(const KeyType &key1, const KeyType2 &key2) const
+ { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); }
+};
+
+template<class VoidPointer>
+struct rbtree_hook
+{
+ typedef typename container_detail::bi::make_set_base_hook
+ < container_detail::bi::void_pointer<VoidPointer>
+ , container_detail::bi::link_mode<container_detail::bi::normal_link>
+ , container_detail::bi::optimize_size<true>
+ >::type type;
+};
+
+template<class T>
+struct rbtree_type
+{
+ typedef T type;
+};
+
+template<class T1, class T2>
+struct rbtree_type< std::pair<T1, T2> >
+{
+ typedef pair<T1, T2> type;
+};
+
+template <class T, class VoidPointer>
+struct rbtree_node
+ : public rbtree_hook<VoidPointer>::type
+{
+ private:
+ BOOST_COPYABLE_AND_MOVABLE(rbtree_node)
+
+ public:
+ typedef typename rbtree_hook<VoidPointer>::type hook_type;
+
+ typedef T value_type;
+ typedef typename rbtree_type<T>::type internal_type;
+
+ typedef rbtree_node<T, VoidPointer> node_type;
+
+ rbtree_node()
+ : m_data()
+ {}
+
+ rbtree_node(const rbtree_node &other)
+ : m_data(other.m_data)
+ {}
+
+ rbtree_node(BOOST_RV_REF(rbtree_node) other)
+ : m_data(boost::move(other.m_data))
+ {}
+
+ #ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ template<BOOST_PP_ENUM_PARAMS(n, class P)> \
+ rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \
+ {} \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #else //#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template<class ...Args>
+ rbtree_node(Args &&...args)
+ : m_data(boost::forward<Args>(args)...)
+ {}
+ #endif//#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ rbtree_node &operator=(const rbtree_node &other)
+ { do_assign(other.m_data); return *this; }
+
+ rbtree_node &operator=(BOOST_RV_REF(rbtree_node) other)
+ { do_move(other.m_data); return *this; }
+
+ T &get_data()
+ {
+ T* ptr = reinterpret_cast<T*>(&this->m_data);
+ return *ptr;
+ }
+
+ const T &get_data() const
+ {
+ const T* ptr = reinterpret_cast<const T*>(&this->m_data);
+ return *ptr;
+ }
+
+ private:
+ internal_type m_data;
+
+ template<class A, class B>
+ void do_assign(const std::pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = p.first;
+ m_data.second = p.second;
+ }
+
+ template<class A, class B>
+ void do_assign(const pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = p.first;
+ m_data.second = p.second;
+ }
+
+ template<class V>
+ void do_assign(const V &v)
+ { m_data = v; }
+
+ template<class A, class B>
+ void do_move(std::pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = boost::move(p.first);
+ m_data.second = boost::move(p.second);
+ }
+
+ template<class A, class B>
+ void do_move(pair<const A, B> &p)
+ {
+ const_cast<A&>(m_data.first) = boost::move(p.first);
+ m_data.second = boost::move(p.second);
+ }
+
+ template<class V>
+ void do_move(V &v)
+ { m_data = boost::move(v); }
+};
+
+}//namespace container_detail {
+
+namespace container_detail {
+
+template<class A, class ValueCompare>
+struct intrusive_rbtree_type
+{
+ typedef typename boost::container::
+ allocator_traits<A>::value_type value_type;
+ typedef typename boost::container::
+ allocator_traits<A>::void_pointer void_pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::size_type size_type;
+ typedef typename container_detail::rbtree_node
+ <value_type, void_pointer> node_type;
+ typedef node_compare<ValueCompare, node_type> node_compare_type;
+ typedef typename container_detail::bi::make_rbtree
+ <node_type
+ ,container_detail::bi::compare<node_compare_type>
+ ,container_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type>
+ ,container_detail::bi::constant_time_size<true>
+ ,container_detail::bi::size_type<size_type>
+ >::type container_type;
+ typedef container_type type ;
+};
+
+} //namespace container_detail {
+
+namespace container_detail {
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+class rbtree
+ : protected container_detail::node_alloc_holder
+ < A
+ , typename container_detail::intrusive_rbtree_type
+ <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue>
+ >::type
+ , KeyCompare
+ >
+{
+ typedef typename container_detail::intrusive_rbtree_type
+ < A, value_compare_impl
+ <Key, Value, KeyCompare, KeyOfValue>
+ >::type Icont;
+ typedef container_detail::node_alloc_holder
+ <A, Icont, KeyCompare> AllocHolder;
+ typedef typename AllocHolder::NodePtr NodePtr;
+ typedef rbtree < Key, Value, KeyOfValue
+ , KeyCompare, A> ThisType;
+ typedef typename AllocHolder::NodeAlloc NodeAlloc;
+ typedef typename AllocHolder::ValAlloc ValAlloc;
+ typedef typename AllocHolder::Node Node;
+ typedef typename Icont::iterator iiterator;
+ typedef typename Icont::const_iterator iconst_iterator;
+ typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
+ typedef typename AllocHolder::allocator_v1 allocator_v1;
+ typedef typename AllocHolder::allocator_v2 allocator_v2;
+ typedef typename AllocHolder::alloc_version alloc_version;
+
+ class RecyclingCloner;
+ friend class RecyclingCloner;
+
+ class RecyclingCloner
+ {
+ public:
+ RecyclingCloner(AllocHolder &holder, Icont &irbtree)
+ : m_holder(holder), m_icont(irbtree)
+ {}
+
+ NodePtr operator()(const Node &other) const
+ {
+ if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){
+ //First recycle a node (this can't throw)
+ try{
+ //This can throw
+ *p = other;
+ return p;
+ }
+ catch(...){
+ //If there is an exception destroy the whole source
+ m_holder.destroy_node(p);
+ while((p = m_icont.unlink_leftmost_without_rebalance())){
+ m_holder.destroy_node(p);
+ }
+ throw;
+ }
+ }
+ else{
+ return m_holder.create_node(other);
+ }
+ }
+
+ AllocHolder &m_holder;
+ Icont &m_icont;
+ };
+
+ class RecyclingMoveCloner;
+ friend class RecyclingMoveCloner;
+
+ class RecyclingMoveCloner
+ {
+ public:
+ RecyclingMoveCloner(AllocHolder &holder, Icont &irbtree)
+ : m_holder(holder), m_icont(irbtree)
+ {}
+
+ NodePtr operator()(const Node &other) const
+ {
+ if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){
+ //First recycle a node (this can't throw)
+ try{
+ //This can throw
+ *p = boost::move(other);
+ return p;
+ }
+ catch(...){
+ //If there is an exception destroy the whole source
+ m_holder.destroy_node(p);
+ while((p = m_icont.unlink_leftmost_without_rebalance())){
+ m_holder.destroy_node(p);
+ }
+ throw;
+ }
+ }
+ else{
+ return m_holder.create_node(other);
+ }
+ }
+
+ AllocHolder &m_holder;
+ Icont &m_icont;
+ };
+
+ BOOST_COPYABLE_AND_MOVABLE(rbtree)
+
+ public:
+
+ typedef Key key_type;
+ typedef Value value_type;
+ typedef A allocator_type;
+ typedef KeyCompare key_compare;
+ typedef value_compare_impl< Key, Value
+ , KeyCompare, KeyOfValue> value_compare;
+ typedef typename boost::container::
+ allocator_traits<A>::pointer pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::const_pointer const_pointer;
+ typedef typename boost::container::
+ allocator_traits<A>::reference reference;
+ typedef typename boost::container::
+ allocator_traits<A>::const_reference const_reference;
+ typedef typename boost::container::
+ allocator_traits<A>::size_type size_type;
+ typedef typename boost::container::
+ allocator_traits<A>::difference_type difference_type;
+ typedef difference_type rbtree_difference_type;
+ typedef pointer rbtree_pointer;
+ typedef const_pointer rbtree_const_pointer;
+ typedef reference rbtree_reference;
+ typedef const_reference rbtree_const_reference;
+ typedef NodeAlloc stored_allocator_type;
+
+ private:
+
+ template<class KeyValueCompare>
+ struct key_node_compare
+ : private KeyValueCompare
+ {
+ key_node_compare(const KeyValueCompare &comp)
+ : KeyValueCompare(comp)
+ {}
+
+ template<class T>
+ struct is_node
+ {
+ static const bool value = is_same<T, Node>::value;
+ };
+
+ template<class T>
+ typename enable_if_c<is_node<T>::value, const value_type &>::type
+ key_forward(const T &node) const
+ { return node.get_data(); }
+
+ template<class T>
+ typename enable_if_c<!is_node<T>::value, const T &>::type
+ key_forward(const T &key) const
+ { return key; }
+
+ template<class KeyType, class KeyType2>
+ bool operator()(const KeyType &key1, const KeyType2 &key2) const
+ { return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); }
+ };
+
+ typedef key_node_compare<value_compare> KeyNodeCompare;
+
+ public:
+ //rbtree const_iterator
+ class const_iterator
+ : public std::iterator
+ < std::bidirectional_iterator_tag
+ , value_type , rbtree_difference_type
+ , rbtree_const_pointer , rbtree_const_reference>
+ {
+ protected:
+ typedef typename Icont::iterator iiterator;
+ iiterator m_it;
+ explicit const_iterator(iiterator it) : m_it(it){}
+ void prot_incr() { ++m_it; }
+ void prot_decr() { --m_it; }
+
+ private:
+ iiterator get()
+ { return this->m_it; }
+
+ public:
+ friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
+ typedef rbtree_difference_type difference_type;
+
+ //Constructors
+ const_iterator()
+ : m_it()
+ {}
+
+ //Pointer like operators
+ const_reference operator*() const
+ { return m_it->get_data(); }
+
+ const_pointer operator->() const
+ { return const_pointer(&m_it->get_data()); }
+
+ //Increment / Decrement
+ const_iterator& operator++()
+ { prot_incr(); return *this; }
+
+ const_iterator operator++(int)
+ { iiterator tmp = m_it; ++*this; return const_iterator(tmp); }
+
+ const_iterator& operator--()
+ { prot_decr(); return *this; }
+
+ const_iterator operator--(int)
+ { iiterator tmp = m_it; --*this; return const_iterator(tmp); }
+
+ //Comparison operators
+ bool operator== (const const_iterator& r) const
+ { return m_it == r.m_it; }
+
+ bool operator!= (const const_iterator& r) const
+ { return m_it != r.m_it; }
+ };
+
+ //rbtree iterator
+ class iterator : public const_iterator
+ {
+ private:
+ explicit iterator(iiterator it)
+ : const_iterator(it)
+ {}
+
+ iiterator get()
+ { return this->m_it; }
+
+ public:
+ friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
+ typedef rbtree_pointer pointer;
+ typedef rbtree_reference reference;
+
+ //Constructors
+ iterator(){}
+
+ //Pointer like operators
+ reference operator*() const { return this->m_it->get_data(); }
+ pointer operator->() const { return pointer(&this->m_it->get_data()); }
+
+ //Increment / Decrement
+ iterator& operator++()
+ { this->prot_incr(); return *this; }
+
+ iterator operator++(int)
+ { iiterator tmp = this->m_it; ++*this; return iterator(tmp); }
+
+ iterator& operator--()
+ { this->prot_decr(); return *this; }
+
+ iterator operator--(int)
+ { iterator tmp = *this; --*this; return tmp; }
+ };
+
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ rbtree()
+ : AllocHolder(key_compare())
+ {}
+
+ rbtree(const key_compare& comp, const allocator_type& a = allocator_type())
+ : AllocHolder(a, comp)
+ {}
+
+ template <class InputIterator>
+ rbtree(InputIterator first, InputIterator last, const key_compare& comp,
+ const allocator_type& a, bool unique_insertion)
+ : AllocHolder(a, comp)
+ {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
+ priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat());
+ }
+
+ template <class InputIterator>
+ rbtree( ordered_range_t, InputIterator first, InputIterator last
+ , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type())
+ : AllocHolder(a, comp)
+ {
+ typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
+ priv_create_and_insert_ordered_nodes(first, last, alloc_version(), ItCat());
+ }
+
+ rbtree(const rbtree& x)
+ : AllocHolder(x, x.key_comp())
+ {
+ this->icont().clone_from
+ (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ }
+
+ rbtree(BOOST_RV_REF(rbtree) x)
+ : AllocHolder(boost::move(static_cast<AllocHolder&>(x)), x.key_comp())
+ {}
+
+ ~rbtree()
+ {} //AllocHolder clears the tree
+
+ rbtree& operator=(BOOST_COPY_ASSIGN_REF(rbtree) x)
+ {
+ if (&x != this){
+ NodeAlloc &this_alloc = this->get_stored_allocator();
+ const NodeAlloc &x_alloc = x.get_stored_allocator();
+ container_detail::bool_<allocator_traits<NodeAlloc>::
+ propagate_on_container_copy_assignment::value> flag;
+ if(flag && this_alloc != x_alloc){
+ this->clear();
+ }
+ this->AllocHolder::copy_assign_alloc(x);
+ //Transfer all the nodes to a temporary tree
+ //If anything goes wrong, all the nodes will be destroyed
+ //automatically
+ Icont other_tree(boost::move(this->icont()));
+
+ //Now recreate the source tree reusing nodes stored by other_tree
+ this->icont().clone_from
+ (x.icont()
+ , RecyclingCloner(*this, other_tree)
+ , Destroyer(this->node_alloc()));
+
+ //If there are remaining nodes, destroy them
+ NodePtr p;
+ while((p = other_tree.unlink_leftmost_without_rebalance())){
+ AllocHolder::destroy_node(p);
+ }
+ }
+ return *this;
+ }
+
+ rbtree& operator=(BOOST_RV_REF(rbtree) x)
+ {
+ if (&x != this){
+ NodeAlloc &this_alloc = this->node_alloc();
+ NodeAlloc &x_alloc = x.node_alloc();
+ //If allocators are equal we can just swap pointers
+ if(this_alloc == x_alloc){
+ //Destroy and swap pointers
+ this->clear();
+ this->icont() = boost::move(x.icont());
+ //Move allocator if needed
+ this->AllocHolder::move_assign_alloc(x);
+ }
+ //If unequal allocators, then do a one by one move
+ else{
+ //Transfer all the nodes to a temporary tree
+ //If anything goes wrong, all the nodes will be destroyed
+ //automatically
+ Icont other_tree(boost::move(this->icont()));
+
+ //Now recreate the source tree reusing nodes stored by other_tree
+ this->icont().clone_from
+ (x.icont()
+ , RecyclingMoveCloner(*this, other_tree)
+ , Destroyer(this->node_alloc()));
+
+ //If there are remaining nodes, destroy them
+ NodePtr p;
+ while((p = other_tree.unlink_leftmost_without_rebalance())){
+ AllocHolder::destroy_node(p);
+ }
+ }
+ }
+ return *this;
+ }
+
+ public:
+ // accessors:
+ value_compare value_comp() const
+ { return this->icont().value_comp().value_comp(); }
+
+ key_compare key_comp() const
+ { return this->icont().value_comp().value_comp().key_comp(); }
+
+ allocator_type get_allocator() const
+ { return allocator_type(this->node_alloc()); }
+
+ const stored_allocator_type &get_stored_allocator() const
+ { return this->node_alloc(); }
+
+ stored_allocator_type &get_stored_allocator()
+ { return this->node_alloc(); }
+
+ iterator begin()
+ { return iterator(this->icont().begin()); }
+
+ const_iterator begin() const
+ { return this->cbegin(); }
+
+ iterator end()
+ { return iterator(this->icont().end()); }
+
+ const_iterator end() const
+ { return this->cend(); }
+
+ reverse_iterator rbegin()
+ { return reverse_iterator(end()); }
+
+ const_reverse_iterator rbegin() const
+ { return this->crbegin(); }
+
+ reverse_iterator rend()
+ { return reverse_iterator(begin()); }
+
+ const_reverse_iterator rend() const
+ { return this->crend(); }
+
+ //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ const_iterator cbegin() const
+ { return const_iterator(this->non_const_icont().begin()); }
+
+ //! <b>Effects</b>: Returns a const_iterator to the end of the container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ const_iterator cend() const
+ { return const_iterator(this->non_const_icont().end()); }
+
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
+ //! of the reversed container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ const_reverse_iterator crbegin() const
+ { return const_reverse_iterator(cend()); }
+
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
+ //! of the reversed container.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Constant.
+ const_reverse_iterator crend() const
+ { return const_reverse_iterator(cbegin()); }
+
+ bool empty() const
+ { return !this->size(); }
+
+ size_type size() const
+ { return this->icont().size(); }
+
+ size_type max_size() const
+ { return AllocHolder::max_size(); }
+
+ void swap(ThisType& x)
+ { AllocHolder::swap(x); }
+
+ public:
+
+ typedef typename Icont::insert_commit_data insert_commit_data;
+
+ // insert/erase
+ std::pair<iterator,bool> insert_unique_check
+ (const key_type& key, insert_commit_data &data)
+ {
+ std::pair<iiterator, bool> ret =
+ this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data);
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ std::pair<iterator,bool> insert_unique_check
+ (const_iterator hint, const key_type& key, insert_commit_data &data)
+ {
+ std::pair<iiterator, bool> ret =
+ this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data);
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);
+ }
+
+ iterator insert_unique_commit(const value_type& v, insert_commit_data &data)
+ {
+ NodePtr tmp = AllocHolder::create_node(v);
+ iiterator it(this->icont().insert_unique_commit(*tmp, data));
+ return iterator(it);
+ }
+
+ template<class MovableConvertible>
+ iterator insert_unique_commit
+ (BOOST_FWD_REF(MovableConvertible) mv, insert_commit_data &data)
+ {
+ NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(mv));
+ iiterator it(this->icont().insert_unique_commit(*tmp, data));
+ return iterator(it);
+ }
+
+ std::pair<iterator,bool> insert_unique(const value_type& v)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(v), data);
+ if(!ret.second)
+ return ret;
+ return std::pair<iterator,bool>
+ (this->insert_unique_commit(v, data), true);
+ }
+
+ template<class MovableConvertible>
+ std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(mv), data);
+ if(!ret.second)
+ return ret;
+ return std::pair<iterator,bool>
+ (this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data), true);
+ }
+
+ private:
+ std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
+ {
+ value_type &v = p->get_data();
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(KeyOfValue()(v), data);
+ if(!ret.second){
+ Destroyer(this->node_alloc())(p);
+ return ret;
+ }
+ return std::pair<iterator,bool>
+ ( iterator(iiterator(this->icont().insert_unique_commit(*p, data)))
+ , true );
+ }
+
+ iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
+ {
+ value_type &v = p->get_data();
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
+ if(!ret.second){
+ Destroyer(this->node_alloc())(p);
+ return ret.first;
+ }
+ return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
+ }
+
+ public:
+
+ #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <class... Args>
+ std::pair<iterator, bool> emplace_unique(Args&&... args)
+ { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); }
+
+ template <class... Args>
+ iterator emplace_hint_unique(const_iterator hint, Args&&... args)
+ { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); }
+
+ template <class... Args>
+ iterator emplace_equal(Args&&... args)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ template <class... Args>
+ iterator emplace_hint_equal(const_iterator hint, Args&&... args)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ std::pair<iterator, bool> emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ return this->emplace_unique_impl \
+ (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint_unique(const_iterator hint \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ return this->emplace_unique_hint_impl \
+ (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ return iterator(this->icont().insert_equal(this->icont().end(), *p)); \
+ } \
+ \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace_hint_equal(const_iterator hint \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ return iterator(this->icont().insert_equal(hint.get(), *p)); \
+ } \
+ //!
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
+
+ iterator insert_unique(const_iterator hint, const value_type& v)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(v), data);
+ if(!ret.second)
+ return ret.first;
+ return this->insert_unique_commit(v, data);
+ }
+
+ template<class MovableConvertible>
+ iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ insert_commit_data data;
+ std::pair<iterator,bool> ret =
+ this->insert_unique_check(hint, KeyOfValue()(mv), data);
+ if(!ret.second)
+ return ret.first;
+ return this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data);
+ }
+
+ template <class InputIterator>
+ void insert_unique(InputIterator first, InputIterator last)
+ {
+ if(this->empty()){
+ //Insert with end hint, to achieve linear
+ //complexity if [first, last) is ordered
+ const_iterator end(this->end());
+ for( ; first != last; ++first)
+ this->insert_unique(end, *first);
+ }
+ else{
+ for( ; first != last; ++first)
+ this->insert_unique(*first);
+ }
+ }
+
+ iterator insert_equal(const value_type& v)
+ {
+ NodePtr p(AllocHolder::create_node(v));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal(BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ return iterator(this->icont().insert_equal(this->icont().end(), *p));
+ }
+
+ iterator insert_equal(const_iterator hint, const value_type& v)
+ {
+ NodePtr p(AllocHolder::create_node(v));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ template<class MovableConvertible>
+ iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ return iterator(this->icont().insert_equal(hint.get(), *p));
+ }
+
+ template <class InputIterator>
+ void insert_equal(InputIterator first, InputIterator last)
+ {
+ //Insert with end hint, to achieve linear
+ //complexity if [first, last) is ordered
+ const_iterator end(this->cend());
+ for( ; first != last; ++first)
+ this->insert_equal(end, *first);
+ }
+
+ iterator erase(const_iterator position)
+ { return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); }
+
+ size_type erase(const key_type& k)
+ { return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); }
+
+ iterator erase(const_iterator first, const_iterator last)
+ { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }
+
+ void clear()
+ { AllocHolder::clear(alloc_version()); }
+
+ // set operations:
+ iterator find(const key_type& k)
+ { return iterator(this->icont().find(k, KeyNodeCompare(value_comp()))); }
+
+ const_iterator find(const key_type& k) const
+ { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp()))); }
+
+ size_type count(const key_type& k) const
+ { return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); }
+
+ iterator lower_bound(const key_type& k)
+ { return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp()))); }
+
+ const_iterator lower_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp()))); }
+
+ iterator upper_bound(const key_type& k)
+ { return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp()))); }
+
+ const_iterator upper_bound(const key_type& k) const
+ { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); }
+
+ std::pair<iterator,iterator> equal_range(const key_type& k)
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->icont().equal_range(k, KeyNodeCompare(value_comp()));
+ return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
+ }
+
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
+ {
+ std::pair<iiterator, iiterator> ret =
+ this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp()));
+ return std::pair<const_iterator,const_iterator>
+ (const_iterator(ret.first), const_iterator(ret.second));
+ }
+
+ private:
+ //Iterator range version
+ template<class InpIterator>
+ void priv_create_and_insert_nodes
+ (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag)
+ {
+ if(unique){
+ for (; beg != end; ++beg){
+ this->insert_unique(*beg);
+ }
+ }
+ else{
+ for (; beg != end; ++beg){
+ this->insert_equal(*beg);
+ }
+ }
+ }
+
+ template<class InpIterator>
+ void priv_create_and_insert_nodes
+ (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag)
+ { //Just forward to the default one
+ priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag());
+ }
+
+ class insertion_functor;
+ friend class insertion_functor;
+
+ class insertion_functor
+ {
+ Icont &icont_;
+
+ public:
+ insertion_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.insert_equal(this->icont_.cend(), n); }
+ };
+
+
+ template<class FwdIterator>
+ void priv_create_and_insert_nodes
+ (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag)
+ {
+ if(beg != end){
+ if(unique){
+ priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag());
+ }
+ else{
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ (beg, std::distance(beg, end), insertion_functor(this->icont()));
+ }
+ }
+ }
+
+ //Iterator range version
+ template<class InpIterator>
+ void priv_create_and_insert_ordered_nodes
+ (InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag)
+ {
+ const_iterator cend_n(this->cend());
+ for (; beg != end; ++beg){
+ this->insert_before(cend_n, *beg);
+ }
+ }
+
+ template<class InpIterator>
+ void priv_create_and_insert_ordered_nodes
+ (InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag)
+ { //Just forward to the default one
+ priv_create_and_insert_ordered_nodes(beg, end, allocator_v1(), std::input_iterator_tag());
+ }
+
+ class back_insertion_functor;
+ friend class back_insertion_functor;
+
+ class back_insertion_functor
+ {
+ Icont &icont_;
+
+ public:
+ back_insertion_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.push_back(n); }
+ };
+
+
+ template<class FwdIterator>
+ void priv_create_and_insert_ordered_nodes
+ (FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag)
+ {
+ if(beg != end){
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ (beg, std::distance(beg, end), back_insertion_functor(this->icont()));
+ }
+ }
+};
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
+{
+ return x.size() == y.size() &&
+ std::equal(x.begin(), x.end(), y.begin());
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
+{
+ return std::lexicographical_compare(x.begin(), x.end(),
+ y.begin(), y.end());
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
+ return !(x == y);
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
+ return y < x;
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
+ return !(y < x);
+}
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline bool
+operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
+ return !(x < y);
+}
+
+
+template <class Key, class Value, class KeyOfValue,
+ class KeyCompare, class A>
+inline void
+swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
+ rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
+{
+ x.swap(y);
+}
+
+} //namespace container_detail {
+} //namespace container {
+/*
+//!has_trivial_destructor_after_move<> == true_type
+//!specialization for optimizations
+template <class K, class V, class KOV,
+class C, class A>
+struct has_trivial_destructor_after_move
+ <boost::container::container_detail::rbtree<K, V, KOV, C, A> >
+{
+ static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+};
+*/
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //BOOST_CONTAINER_TREE_HPP
diff --git a/boost/container/detail/type_traits.hpp b/boost/container/detail/type_traits.hpp
new file mode 100644
index 0000000000..6a0b3ed58d
--- /dev/null
+++ b/boost/container/detail/type_traits.hpp
@@ -0,0 +1,203 @@
+//////////////////////////////////////////////////////////////////////////////
+// (C) Copyright John Maddock 2000.
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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.
+//
+// The alignment_of implementation comes from John Maddock's boost::alignment_of code
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP
+#define BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+
+#include <boost/move/move.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+struct nat{};
+
+//boost::alignment_of yields to 10K lines of preprocessed code, so we
+//need an alternative
+template <typename T> struct alignment_of;
+
+template <typename T>
+struct alignment_of_hack
+{
+ char c;
+ T t;
+ alignment_of_hack();
+};
+
+template <unsigned A, unsigned S>
+struct alignment_logic
+{
+ enum{ value = A < S ? A : S };
+};
+
+template< typename T >
+struct alignment_of
+{
+ enum{ value = alignment_logic
+ < sizeof(alignment_of_hack<T>) - sizeof(T)
+ , sizeof(T)>::value };
+};
+
+//This is not standard, but should work with all compilers
+union max_align
+{
+ char char_;
+ short short_;
+ int int_;
+ long long_;
+ #ifdef BOOST_HAS_LONG_LONG
+ long long long_long_;
+ #endif
+ float float_;
+ double double_;
+ long double long_double_;
+ void * void_ptr_;
+};
+
+template<class T>
+struct remove_reference
+{
+ typedef T type;
+};
+
+template<class T>
+struct remove_reference<T&>
+{
+ typedef T type;
+};
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+
+template<class T>
+struct remove_reference<T&&>
+{
+ typedef T type;
+};
+
+#else
+
+template<class T>
+struct remove_reference< ::boost::rv<T> >
+{
+ typedef T type;
+};
+
+#endif
+
+template<class T>
+struct is_reference
+{
+ enum { value = false };
+};
+
+template<class T>
+struct is_reference<T&>
+{
+ enum { value = true };
+};
+
+template<class T>
+struct is_pointer
+{
+ enum { value = false };
+};
+
+template<class T>
+struct is_pointer<T*>
+{
+ enum { value = true };
+};
+
+template <typename T>
+struct add_reference
+{
+ typedef T& type;
+};
+
+template<class T>
+struct add_reference<T&>
+{
+ typedef T& type;
+};
+
+template<>
+struct add_reference<void>
+{
+ typedef nat &type;
+};
+
+template<>
+struct add_reference<const void>
+{
+ typedef const nat &type;
+};
+
+template <class T>
+struct add_const_reference
+{ typedef const T &type; };
+
+template <class T>
+struct add_const_reference<T&>
+{ typedef T& type; };
+
+template <typename T, typename U>
+struct is_same
+{
+ typedef char yes_type;
+ struct no_type
+ {
+ char padding[8];
+ };
+
+ template <typename V>
+ static yes_type is_same_tester(V*, V*);
+ static no_type is_same_tester(...);
+
+ static T *t;
+ static U *u;
+
+ static const bool value = sizeof(yes_type) == sizeof(is_same_tester(t,u));
+};
+
+template<class T>
+struct remove_const
+{
+ typedef T type;
+};
+
+template<class T>
+struct remove_const< const T>
+{
+ typedef T type;
+};
+
+template<class T>
+struct remove_ref_const
+{
+ typedef typename remove_const< typename remove_reference<T>::type >::type type;
+};
+
+} // namespace container_detail
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP
diff --git a/boost/container/detail/utilities.hpp b/boost/container/detail/utilities.hpp
new file mode 100644
index 0000000000..ee0fe993b2
--- /dev/null
+++ b/boost/container/detail/utilities.hpp
@@ -0,0 +1,271 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_UTILITIES_HPP
+#define BOOST_CONTAINER_DETAIL_UTILITIES_HPP
+
+#include "config_begin.hpp"
+#include <cstdio>
+#include <boost/type_traits/is_fundamental.hpp>
+#include <boost/type_traits/is_pointer.hpp>
+#include <boost/type_traits/is_enum.hpp>
+#include <boost/type_traits/is_member_pointer.hpp>
+#include <boost/type_traits/is_class.hpp>
+#include <boost/move/move.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/allocator/allocator_traits.hpp>
+#include <algorithm>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class T>
+const T &max_value(const T &a, const T &b)
+{ return a > b ? a : b; }
+
+template<class T>
+const T &min_value(const T &a, const T &b)
+{ return a < b ? a : b; }
+
+template <class SizeType>
+SizeType
+ get_next_capacity(const SizeType max_size
+ ,const SizeType capacity
+ ,const SizeType n)
+{
+// if (n > max_size - capacity)
+// throw std::length_error("get_next_capacity");
+
+ const SizeType m3 = max_size/3;
+
+ if (capacity < m3)
+ return capacity + max_value(3*(capacity+1)/5, n);
+
+ if (capacity < m3*2)
+ return capacity + max_value((capacity+1)/2, n);
+
+ return max_size;
+}
+
+template <class T>
+inline T* to_raw_pointer(T* p)
+{ return p; }
+
+template <class Pointer>
+inline typename Pointer::element_type*
+ to_raw_pointer(const Pointer &p)
+{ return boost::container::container_detail::to_raw_pointer(p.operator->()); }
+
+//!To avoid ADL problems with swap
+template <class T>
+inline void do_swap(T& x, T& y)
+{
+ using std::swap;
+ swap(x, y);
+}
+
+template<class AllocatorType>
+inline void swap_alloc(AllocatorType &, AllocatorType &, container_detail::false_type)
+ BOOST_CONTAINER_NOEXCEPT
+{}
+
+template<class AllocatorType>
+inline void swap_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type)
+{ container_detail::do_swap(l, r); }
+
+template<class AllocatorType>
+inline void assign_alloc(AllocatorType &, const AllocatorType &, container_detail::false_type)
+ BOOST_CONTAINER_NOEXCEPT
+{}
+
+template<class AllocatorType>
+inline void assign_alloc(AllocatorType &l, const AllocatorType &r, container_detail::true_type)
+{ l = r; }
+
+template<class AllocatorType>
+inline void move_alloc(AllocatorType &, AllocatorType &, container_detail::false_type)
+ BOOST_CONTAINER_NOEXCEPT
+{}
+
+template<class AllocatorType>
+inline void move_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type)
+{ l = ::boost::move(r); }
+
+//Rounds "orig_size" by excess to round_to bytes
+template<class SizeType>
+inline SizeType get_rounded_size(SizeType orig_size, SizeType round_to)
+{
+ return ((orig_size-1)/round_to+1)*round_to;
+}
+
+template <std::size_t OrigSize, std::size_t RoundTo>
+struct ct_rounded_size
+{
+ enum { value = ((OrigSize-1)/RoundTo+1)*RoundTo };
+};
+/*
+template <class _TypeT>
+struct __rw_is_enum
+{
+ struct _C_no { };
+ struct _C_yes { int _C_dummy [2]; };
+
+ struct _C_indirect {
+ // prevent classes with user-defined conversions from matching
+
+ // use double to prevent float->int gcc conversion warnings
+ _C_indirect (double);
+};
+
+// nested struct gets rid of bogus gcc errors
+struct _C_nest {
+ // supply first argument to prevent HP aCC warnings
+ static _C_no _C_is (int, ...);
+ static _C_yes _C_is (int, _C_indirect);
+
+ static _TypeT _C_make_T ();
+};
+
+enum {
+ _C_val = sizeof (_C_yes) == sizeof (_C_nest::_C_is (0, _C_nest::_C_make_T ()))
+ && !::boost::is_fundamental<_TypeT>::value
+};
+
+};
+*/
+
+template<class T>
+struct move_const_ref_type
+ : if_c
+// < ::boost::is_fundamental<T>::value || ::boost::is_pointer<T>::value || ::boost::is_member_pointer<T>::value || ::boost::is_enum<T>::value
+ < !::boost::is_class<T>::value
+ ,const T &
+ ,BOOST_CATCH_CONST_RLVALUE(T)
+ >
+{};
+
+} //namespace container_detail {
+
+//////////////////////////////////////////////////////////////////////////////
+//
+// uninitialized_move_alloc
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! <b>Effects</b>:
+//! \code
+//! for (; first != last; ++result, ++first)
+//! allocator_traits::construct(a, &*result, boost::move(*first));
+//! \endcode
+//!
+//! <b>Returns</b>: result
+template
+ <typename A,
+ typename I, // I models InputIterator
+ typename F> // F models ForwardIterator
+F uninitialized_move_alloc(A &a, I f, I l, F r)
+{
+ while (f != l) {
+ allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f));
+ ++f; ++r;
+ }
+ return r;
+}
+
+//////////////////////////////////////////////////////////////////////////////
+//
+// uninitialized_copy_alloc
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! <b>Effects</b>:
+//! \code
+//! for (; first != last; ++result, ++first)
+//! allocator_traits::construct(a, &*result, *first);
+//! \endcode
+//!
+//! <b>Returns</b>: result
+template
+ <typename A,
+ typename I, // I models InputIterator
+ typename F> // F models ForwardIterator
+F uninitialized_copy_alloc(A &a, I f, I l, F r)
+{
+ while (f != l) {
+ allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f);
+ ++f; ++r;
+ }
+ return r;
+}
+
+//////////////////////////////////////////////////////////////////////////////
+//
+// uninitialized_copy_alloc
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! <b>Effects</b>:
+//! \code
+//! for (; first != last; ++result, ++first)
+//! allocator_traits::construct(a, &*result, *first);
+//! \endcode
+//!
+//! <b>Returns</b>: result
+template
+ <typename A,
+ typename F, // F models ForwardIterator
+ typename T>
+void uninitialized_fill_alloc(A &a, F f, F l, const T &t)
+{
+ while (f != l) {
+ allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*f), t);
+ ++f;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+//
+// uninitialized_copy_or_move_alloc
+//
+//////////////////////////////////////////////////////////////////////////////
+
+template
+<typename A
+,typename I // I models InputIterator
+,typename F> // F models ForwardIterator
+F uninitialized_copy_or_move_alloc
+ (A &a, I f, I l, F r
+ ,typename boost::container::container_detail::enable_if
+ < boost::move_detail::is_move_iterator<I> >::type* = 0)
+{
+ return ::boost::container::uninitialized_move_alloc(a, f, l, r);
+}
+
+template
+<typename A
+,typename I // I models InputIterator
+,typename F> // F models ForwardIterator
+F uninitialized_copy_or_move_alloc
+ (A &a, I f, I l, F r
+ ,typename boost::container::container_detail::disable_if
+ < boost::move_detail::is_move_iterator<I> >::type* = 0)
+{
+ return ::boost::container::uninitialized_copy_alloc(a, f, l, r);
+}
+
+} //namespace container {
+} //namespace boost {
+
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP
diff --git a/boost/container/detail/value_init.hpp b/boost/container/detail/value_init.hpp
new file mode 100644
index 0000000000..afbc9c1e34
--- /dev/null
+++ b/boost/container/detail/value_init.hpp
@@ -0,0 +1,45 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011.
+//
+// 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_DETAIL_VALUE_INIT_HPP
+#define BOOST_CONTAINER_DETAIL_VALUE_INIT_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class T>
+struct value_init
+{
+ value_init()
+ : m_t()
+ {}
+
+ operator T &() { return m_t; }
+
+ T m_t;
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_VALUE_INIT_HPP
diff --git a/boost/container/detail/variadic_templates_tools.hpp b/boost/container/detail/variadic_templates_tools.hpp
new file mode 100644
index 0000000000..f21f972ab1
--- /dev/null
+++ b/boost/container/detail/variadic_templates_tools.hpp
@@ -0,0 +1,153 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2008-2011. 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_DETAIL_VARIADIC_TEMPLATES_TOOLS_HPP
+#define BOOST_CONTAINER_DETAIL_VARIADIC_TEMPLATES_TOOLS_HPP
+
+#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include "config_begin.hpp"
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <cstddef> //std::size_t
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<typename... Values>
+class tuple;
+
+template<> class tuple<>
+{};
+
+template<typename Head, typename... Tail>
+class tuple<Head, Tail...>
+ : private tuple<Tail...>
+{
+ typedef tuple<Tail...> inherited;
+
+ public:
+ tuple() { }
+
+ // implicit copy-constructor is okay
+ // Construct tuple from separate arguments.
+ tuple(typename add_const_reference<Head>::type v,
+ typename add_const_reference<Tail>::type... vtail)
+ : inherited(vtail...), m_head(v)
+ {}
+
+ // Construct tuple from another tuple.
+ template<typename... VValues>
+ tuple(const tuple<VValues...>& other)
+ : m_head(other.head()), inherited(other.tail())
+ {}
+
+ template<typename... VValues>
+ tuple& operator=(const tuple<VValues...>& other)
+ {
+ m_head = other.head();
+ tail() = other.tail();
+ return this;
+ }
+
+ typename add_reference<Head>::type head() { return m_head; }
+ typename add_reference<const Head>::type head() const { return m_head; }
+
+ inherited& tail() { return *this; }
+ const inherited& tail() const { return *this; }
+
+ protected:
+ Head m_head;
+};
+
+
+template<typename... Values>
+tuple<Values&&...> tie_forward(Values&&... values)
+{ return tuple<Values&&...>(values...); }
+
+template<int I, typename Tuple>
+struct tuple_element;
+
+template<int I, typename Head, typename... Tail>
+struct tuple_element<I, tuple<Head, Tail...> >
+{
+ typedef typename tuple_element<I-1, tuple<Tail...> >::type type;
+};
+
+template<typename Head, typename... Tail>
+struct tuple_element<0, tuple<Head, Tail...> >
+{
+ typedef Head type;
+};
+
+template<int I, typename Tuple>
+class get_impl;
+
+template<int I, typename Head, typename... Values>
+class get_impl<I, tuple<Head, Values...> >
+{
+ typedef typename tuple_element<I-1, tuple<Values...> >::type Element;
+ typedef get_impl<I-1, tuple<Values...> > Next;
+
+ public:
+ typedef typename add_reference<Element>::type type;
+ typedef typename add_const_reference<Element>::type const_type;
+ static type get(tuple<Head, Values...>& t) { return Next::get(t.tail()); }
+ static const_type get(const tuple<Head, Values...>& t) { return Next::get(t.tail()); }
+};
+
+template<typename Head, typename... Values>
+class get_impl<0, tuple<Head, Values...> >
+{
+ public:
+ typedef typename add_reference<Head>::type type;
+ typedef typename add_const_reference<Head>::type const_type;
+ static type get(tuple<Head, Values...>& t) { return t.head(); }
+ static const_type get(const tuple<Head, Values...>& t){ return t.head(); }
+};
+
+template<int I, typename... Values>
+typename get_impl<I, tuple<Values...> >::type get(tuple<Values...>& t)
+{ return get_impl<I, tuple<Values...> >::get(t); }
+
+template<int I, typename... Values>
+typename get_impl<I, tuple<Values...> >::const_type get(const tuple<Values...>& t)
+{ return get_impl<I, tuple<Values...> >::get(t); }
+
+////////////////////////////////////////////////////
+// Builds an index_tuple<0, 1, 2, ..., Num-1>, that will
+// be used to "unpack" into comma-separated values
+// in a function call.
+////////////////////////////////////////////////////
+
+template<int... Indexes>
+struct index_tuple{};
+
+template<std::size_t Num, typename Tuple = index_tuple<> >
+struct build_number_seq;
+
+template<std::size_t Num, int... Indexes>
+struct build_number_seq<Num, index_tuple<Indexes...> >
+ : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> >
+{};
+
+template<int... Indexes>
+struct build_number_seq<0, index_tuple<Indexes...> >
+{ typedef index_tuple<Indexes...> type; };
+
+
+}}} //namespace boost { namespace container { namespace container_detail {
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_VARIADIC_TEMPLATES_TOOLS_HPP
diff --git a/boost/container/detail/version_type.hpp b/boost/container/detail/version_type.hpp
new file mode 100644
index 0000000000..46344faca0
--- /dev/null
+++ b/boost/container/detail/version_type.hpp
@@ -0,0 +1,92 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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.
+//
+//////////////////////////////////////////////////////////////////////////////
+//
+// This code comes from N1953 document by Howard E. Hinnant
+//
+//////////////////////////////////////////////////////////////////////////////
+
+
+#ifndef BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP
+#define BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP
+
+#include "config_begin.hpp"
+
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/type_traits.hpp>
+
+namespace boost{
+namespace container {
+namespace container_detail {
+
+//using namespace boost;
+
+template <class T, unsigned V>
+struct version_type
+ : public container_detail::integral_constant<unsigned, V>
+{
+ typedef T type;
+
+ version_type(const version_type<T, 0>&);
+};
+
+namespace impl{
+
+template <class T,
+ bool = container_detail::is_convertible<version_type<T, 0>, typename T::version>::value>
+struct extract_version
+{
+ static const unsigned value = 1;
+};
+
+template <class T>
+struct extract_version<T, true>
+{
+ static const unsigned value = T::version::value;
+};
+
+template <class T>
+struct has_version
+{
+ private:
+ struct two {char _[2];};
+ template <class U> static two test(...);
+ template <class U> static char test(const typename U::version*);
+ public:
+ static const bool value = sizeof(test<T>(0)) == 1;
+ void dummy(){}
+};
+
+template <class T, bool = has_version<T>::value>
+struct version
+{
+ static const unsigned value = 1;
+};
+
+template <class T>
+struct version<T, true>
+{
+ static const unsigned value = extract_version<T>::value;
+};
+
+} //namespace impl
+
+template <class T>
+struct version
+ : public container_detail::integral_constant<unsigned, impl::version<T>::value>
+{
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost{
+
+#include "config_end.hpp"
+
+#endif //#define BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP
diff --git a/boost/container/detail/workaround.hpp b/boost/container/detail/workaround.hpp
new file mode 100644
index 0000000000..45ab2f2c4d
--- /dev/null
+++ b/boost/container/detail/workaround.hpp
@@ -0,0 +1,31 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2011. 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_DETAIL_WORKAROUND_HPP
+#define BOOST_CONTAINER_DETAIL_WORKAROUND_HPP
+
+#include <boost/container/detail/config_begin.hpp>
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)\
+ && !defined(BOOST_INTERPROCESS_DISABLE_VARIADIC_TMPL)
+ #define BOOST_CONTAINER_PERFECT_FORWARDING
+#endif
+
+#if defined(BOOST_NO_NOEXCEPT)
+ #define BOOST_CONTAINER_NOEXCEPT
+ #define BOOST_CONTAINER_NOEXCEPT_IF(x)
+#else
+ #define BOOST_CONTAINER_NOEXCEPT noexcept
+ #define BOOST_CONTAINER_NOEXCEPT_IF(x) noexcept(x)
+#endif
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_WORKAROUND_HPP