Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r85964 - in trunk: boost/container boost/container/detail libs/container/bench libs/container/bench/detail libs/container/doc libs/container/proj/vc7ide libs/container/test
From: igaztanaga_at_[hidden]
Date: 2013-09-26 14:05:25

Next message: andrey.semashev_at_[hidden]: "[Boost-commit] svn:boost r85965 - in trunk/libs/log: doc src"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r85963 - trunk/libs/math/test"

Author: igaztanaga
Date: 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013)
New Revision: 85964
URL: http://svn.boost.org/trac/boost/changeset/85964

Log:
Default initialization for vector-like containers
Complexity guarantees for associative container constructors and ordered input ranges
Added benchmark for associative containers
Fixes #9166

Added:
   trunk/libs/container/bench/bench_set.cpp (contents, props changed)
   trunk/libs/container/proj/vc7ide/bench_set.vcproj (contents, props changed)
Text files modified:
   trunk/boost/container/allocator_traits.hpp | 5
   trunk/boost/container/container_fwd.hpp | 17 +
   trunk/boost/container/deque.hpp | 47 ++++
   trunk/boost/container/detail/advanced_insert_int.hpp | 30 +++
   trunk/boost/container/detail/algorithms.hpp | 12 +
   trunk/boost/container/detail/allocator_version_traits.hpp | 8
   trunk/boost/container/detail/config_begin.hpp | 1
   trunk/boost/container/detail/destroyers.hpp | 11 +
   trunk/boost/container/detail/flat_tree.hpp | 98 +++++-----
   trunk/boost/container/detail/iterators.hpp | 158 +++++++++++++++--
   trunk/boost/container/detail/multiallocation_chain.hpp | 6
   trunk/boost/container/detail/node_alloc_holder.hpp | 32 +-
   trunk/boost/container/detail/tree.hpp | 206 +++++++++++++---------
   trunk/boost/container/detail/utilities.hpp | 39 ++++
   trunk/boost/container/flat_map.hpp | 6
   trunk/boost/container/flat_set.hpp | 2
   trunk/boost/container/list.hpp | 6
   trunk/boost/container/map.hpp | 6
   trunk/boost/container/set.hpp | 6
   trunk/boost/container/slist.hpp | 6
   trunk/boost/container/stable_vector.hpp | 50 ++++
   trunk/boost/container/static_vector.hpp | 39 ++++
   trunk/boost/container/string.hpp | 2
   trunk/boost/container/vector.hpp | 75 +++++++-
   trunk/libs/container/bench/Jamfile.v2 | 2
   trunk/libs/container/bench/bench_set.cpp | 348 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/container/bench/bench_static_vector.cpp | 1
   trunk/libs/container/bench/detail/varray.hpp | 4
   trunk/libs/container/bench/varray.hpp | 4
   trunk/libs/container/doc/container.qbk | 46 +++++
   trunk/libs/container/proj/vc7ide/bench_set.vcproj | 134 +++++++++++++++
   trunk/libs/container/proj/vc7ide/container.sln | 18 +
   trunk/libs/container/proj/vc7ide/container.vcproj | 3
   trunk/libs/container/test/allocator_traits_test.cpp | 51 +++++
   trunk/libs/container/test/deque_test.cpp | 4
   trunk/libs/container/test/stable_vector_test.cpp | 35 ++++
   trunk/libs/container/test/static_vector_test.cpp | 50 +++++
   trunk/libs/container/test/vector_test.cpp | 4
   trunk/libs/container/test/vector_test.hpp | 120 +++++++++++++
   39 files changed, 1450 insertions(+), 242 deletions(-)

Modified: trunk/boost/container/allocator_traits.hpp
==============================================================================
--- trunk/boost/container/allocator_traits.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/allocator_traits.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -23,6 +23,7 @@

#include <boost/container/detail/config_begin.hpp>
#include <boost/container/detail/workaround.hpp>
+#include <boost/container/container_fwd.hpp>
#include <boost/intrusive/pointer_traits.hpp>
#include <boost/intrusive/detail/memory_util.hpp>
#include <boost/container/detail/memory_util.hpp>
@@ -387,6 +388,10 @@
 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
 #include BOOST_PP_LOCAL_ITERATE()
 #endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template<class T>
+ static void priv_construct_dispatch2(boost::false_type, Alloc &, T *p, ::boost::container::default_init_t)
+ { ::new((void*)p) T; }
 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

 ///@endcond

Modified: trunk/boost/container/container_fwd.hpp
==============================================================================
--- trunk/boost/container/container_fwd.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/container_fwd.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -135,6 +135,10 @@
struct ordered_range_t
{};

+//! Value used to tag that the input range is
+//! guaranteed to be ordered
+static const ordered_range_t ordered_range = ordered_range_t();
+
//! Type used to tag that the input range is
//! guaranteed to be ordered and unique
struct ordered_unique_range_t
@@ -142,13 +146,17 @@
{};

//! Value used to tag that the input range is
-//! guaranteed to be ordered
-static const ordered_range_t ordered_range = ordered_range_t();
-
-//! Value used to tag that the input range is
//! guaranteed to be ordered and unique
static const ordered_unique_range_t ordered_unique_range = ordered_unique_range_t();

+//! Type used to tag that the input range is
+//! guaranteed to be ordered and unique
+struct default_init_t
+{};
+
+//! Value used to tag that the input range is
+//! guaranteed to be ordered and unique
+static const default_init_t default_init = default_init_t();
/// @cond

namespace detail_really_deep_namespace {
@@ -161,6 +169,7 @@
    {
       (void)ordered_range;
       (void)ordered_unique_range;
+ (void)default_init;
    }
};

Modified: trunk/boost/container/deque.hpp
==============================================================================
--- trunk/boost/container/deque.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/deque.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -540,7 +540,7 @@
 {}

 //! Effects: Constructs a deque that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
 //!
 //! Throws: If allocator_type's default constructor or copy constructor
 //! throws or T's default or copy constructor throws.
@@ -549,7 +549,24 @@
 explicit deque(size_type n)
 : Base(n, allocator_type())
 {
- container_detail::insert_default_constructed_n_proxy<Allocator, iterator> proxy(this->alloc());
+ container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy(this->alloc());
+ proxy.uninitialized_copy_n_and_update(this->begin(), n);
+ //deque_base will deallocate in case of exception...
+ }
+
+ //! Effects: Constructs a deque that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! Throws: If allocator_type's default constructor or copy constructor
+ //! throws or T's default or copy constructor throws.
+ //!
+ //! Complexity: Linear to n.
+ //!
+ //! Note: Non-standard extension
+ deque(size_type n, default_init_t)
+ : Base(n, allocator_type())
+ {
+ container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy(this->alloc());
 proxy.uninitialized_copy_n_and_update(this->begin(), n);
 //deque_base will deallocate in case of exception...
 }
@@ -949,9 +966,9 @@
 { return allocator_traits_type::max_size(this->alloc()); }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
- //! Throws: If memory allocation throws, or T's copy constructor throws.
+ //! Throws: If memory allocation throws, or T's constructor throws.
 //!
 //! Complexity: Linear to the difference between size() and new_size.
 void resize(size_type new_size)
@@ -961,7 +978,27 @@
 this->priv_erase_last_n(len - new_size);
 else{
 const size_type n = new_size - this->size();
- container_detail::insert_default_constructed_n_proxy<Allocator, iterator> proxy(this->alloc());
+ container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy(this->alloc());
+ priv_insert_back_aux_impl(n, proxy);
+ }
+ }
+
+ //! Effects: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are default initialized.
+ //!
+ //! Throws: If memory allocation throws, or T's constructor throws.
+ //!
+ //! Complexity: Linear to the difference between size() and new_size.
+ //!
+ //! Note: Non-standard extension
+ void resize(size_type new_size, default_init_t)
+ {
+ const size_type len = size();
+ if (new_size < len)
+ this->priv_erase_last_n(len - new_size);
+ else{
+ const size_type n = new_size - this->size();
+ container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy(this->alloc());
 priv_insert_back_aux_impl(n, proxy);
 }
 }

Modified: trunk/boost/container/detail/advanced_insert_int.hpp
==============================================================================
--- trunk/boost/container/detail/advanced_insert_int.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/advanced_insert_int.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -99,19 +99,43 @@
};

template<class A, class Iterator>
-struct insert_default_constructed_n_proxy
+struct insert_value_initialized_n_proxy
{
 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;

- explicit insert_default_constructed_n_proxy(A &a)
+ explicit insert_value_initialized_n_proxy(A &a)
 : a_(a)
 {}

 void uninitialized_copy_n_and_update(Iterator p, size_type n) const
- { boost::container::uninitialized_default_alloc_n(this->a_, n, p); }
+ { boost::container::uninitialized_value_init_alloc_n(this->a_, n, p); }
+
+ void copy_n_and_update(Iterator, size_type) const
+ {
+ BOOST_ASSERT(false);
+ }
+
+ private:
+ A &a_;
+};
+
+template<class A, class Iterator>
+struct insert_default_initialized_n_proxy
+{
+ 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;
+
+
+ explicit insert_default_initialized_n_proxy(A &a)
+ : a_(a)
+ {}
+
+ void uninitialized_copy_n_and_update(Iterator p, size_type n) const
+ { boost::container::uninitialized_default_init_alloc_n(this->a_, n, p); }

 void copy_n_and_update(Iterator, size_type) const
 {

Modified: trunk/boost/container/detail/algorithms.hpp
==============================================================================
--- trunk/boost/container/detail/algorithms.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/algorithms.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -35,13 +35,13 @@
namespace container {

template<class It>
-struct is_default_construct_iterator
+struct is_value_init_construct_iterator
{
 static const bool value = false;
};

template<class U, class D>
-struct is_default_construct_iterator<default_construct_iterator<U, D> >
+struct is_value_init_construct_iterator<value_init_construct_iterator<U, D> >
{
 static const bool value = true;
};
@@ -64,11 +64,17 @@
//#endif

template<class A, class T, class U, class D>
-inline void construct_in_place(A &a, T *dest, default_construct_iterator<U, D>)
+inline void construct_in_place(A &a, T *dest, value_init_construct_iterator<U, D>)
{
 boost::container::allocator_traits<A>::construct(a, dest);
}

+template<class A, class T, class U, class D>
+inline void construct_in_place(A &a, T *dest, default_init_construct_iterator<U, D>)
+{
+ boost::container::allocator_traits<A>::construct(a, dest, default_init);
+}
+
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)
{

Modified: trunk/boost/container/detail/allocator_version_traits.hpp
==============================================================================
--- trunk/boost/container/detail/allocator_version_traits.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/allocator_version_traits.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -92,8 +92,12 @@

 static void deallocate_individual(Allocator &a, multiallocation_chain &holder)
 {
- while(!holder.empty()){
- a.deallocate(holder.pop_front(), 1);
+ size_type n = holder.size();
+ typename multiallocation_chain::iterator it = holder.begin();
+ while(n--){
+ pointer p = boost::intrusive::pointer_traits<pointer>::pointer_to(*it);
+ ++it;
+ a.deallocate(p, 1);
 }
 }

Modified: trunk/boost/container/detail/config_begin.hpp
==============================================================================
--- trunk/boost/container/detail/config_begin.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/config_begin.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -46,4 +46,5 @@
    #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
    #pragma warning (disable : 4584) // X is already a base-class of Y
+ #pragma warning (disable : 4510) // default constructor could not be generated
#endif //BOOST_MSVC

Modified: trunk/boost/container/detail/destroyers.hpp
==============================================================================
--- trunk/boost/container/detail/destroyers.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/destroyers.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -68,6 +68,9 @@
    pointer get() const
    { return m_ptr; }

+ void set(const pointer &p)
+ { m_ptr = p; }
+
    void release()
    { m_ptr = 0; }
};
@@ -87,6 +90,9 @@

    pointer get() const
    { return pointer(); }
+
+ void set(const pointer &)
+ {}
};

//!A deleter for scoped_ptr that deallocates the memory
@@ -249,6 +255,11 @@
    void release()
    { pv_ = 0; }

+
+ void set(value_type *ptr) { pv_ = ptr; }
+
+ value_type *get() const { return pv_; }
+
    private:
    value_type *pv_;
    A &a_;

Modified: trunk/boost/container/detail/flat_tree.hpp
==============================================================================
--- trunk/boost/container/detail/flat_tree.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/flat_tree.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -240,16 +240,24 @@
 , const allocator_type& a = allocator_type())
 : m_data(comp, a)
 {
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ //Call end() every iteration as reallocation might have invalidated iterators
 if(unique_insertion){
- this->insert_unique(first, last);
+ for ( ; first != last; ++first){
+ this->insert_unique(this->cend(), *first);
+ }
 }
 else{
- this->insert_equal(first, last);
+ for ( ; first != last; ++first){
+ this->insert_equal(this->cend(), *first);
+ }
 }
 }

 ~flat_tree()
- { }
+ {}

 flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
 { m_data = x.m_data; return *this; }
@@ -389,7 +397,11 @@

 template <class InIt>
 void insert_unique(InIt first, InIt last)
- { this->priv_insert_unique_loop(first, last); }
+ {
+ for ( ; first != last; ++first){
+ this->insert_unique(*first);
+ }
+ }

 template <class InIt>
 void insert_equal(InIt first, InIt last
@@ -487,7 +499,13 @@
>::type * = 0
 #endif
 )
- { this->priv_insert_unique_loop_hint(first, last); }
+ {
+ const_iterator pos(this->cend());
+ for ( ; first != last; ++first){
+ pos = this->insert_unique(pos, *first);
+ ++pos;
+ }
+ }

 template <class BidirIt>
 void insert_unique(ordered_unique_range_t, BidirIt first, BidirIt last
@@ -677,22 +695,21 @@
 // set operations:
 iterator find(const key_type& k)
 {
- const Compare &key_cmp = this->m_data.get_comp();
 iterator i = this->lower_bound(k);
-
- if (i != this->end() && key_cmp(k, KeyOfValue()(*i))){
- i = this->end();
+ iterator end_it = this->end();
+ if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
+ i = end_it;
 }
 return i;
 }

 const_iterator find(const key_type& k) const
 {
- const Compare &key_cmp = this->m_data.get_comp();
 const_iterator i = this->lower_bound(k);

- if (i != this->end() && key_cmp(k, KeyOfValue()(*i))){
- i = this->end();
+ const_iterator end_it = this->cend();
+ if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
+ i = end_it;
 }
 return i;
 }
@@ -708,19 +725,19 @@
 { 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); }
+ { return this->priv_lower_bound(this->cbegin(), this->cend(), 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); }
+ { return this->priv_upper_bound(this->cbegin(), this->cend(), 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); }
+ { return this->priv_equal_range(this->cbegin(), this->cend(), k); }

 size_type capacity() const
 { return this->m_data.m_vect.capacity(); }
@@ -817,7 +834,6 @@
 //in the remaining range [pos, end)
 return this->priv_insert_unique_prepare(pos, cend_it, val, commit_data);
 }
- //return priv_insert_unique_prepare(val, commit_data);
 }

 template<class Convertible>
@@ -835,11 +851,11 @@
 {
 const Compare &key_cmp = this->m_data.get_comp();
 KeyOfValue key_extract;
- difference_type len = last - first, half;
+ size_type len = static_cast<size_type>(last - first);
 RanIt middle;

- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type half = len >> 1;
 middle = first;
 middle += half;

@@ -854,17 +870,18 @@
 return first;
 }

+
 template <class RanIt>
 RanIt priv_upper_bound(RanIt first, RanIt last,
 const key_type & key) const
 {
 const Compare &key_cmp = this->m_data.get_comp();
 KeyOfValue key_extract;
- difference_type len = last - first, half;
+ size_type len = static_cast<size_type>(last - first);
 RanIt middle;

- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type half = len >> 1;
 middle = first;
 middle += half;

@@ -885,11 +902,11 @@
 {
 const Compare &key_cmp = this->m_data.get_comp();
 KeyOfValue key_extract;
- difference_type len = last - first, half;
- RanIt middle, left, right;
+ size_type len = static_cast<size_type>(last - first);
+ RanIt middle;

- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type half = len >> 1;
 middle = first;
 middle += half;

@@ -902,10 +919,11 @@
 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);
+ //Middle is equal to key
+ last = first;
+ last += len;
+ first = this->priv_lower_bound(first, middle, key);
+ return std::pair<RanIt, RanIt> (first, this->priv_upper_bound(++middle, last, key));
 }
 }
 return std::pair<RanIt, RanIt>(first, first);
@@ -924,24 +942,10 @@
 {
 const_iterator pos(this->cend());
 for ( ; first != last; ++first){
+ //If ordered, then try hint version
+ //to achieve constant-time complexity per insertion
 pos = this->insert_equal(pos, *first);
- }
- }
-
- template<class InIt>
- void priv_insert_unique_loop(InIt first, InIt last)
- {
- for ( ; first != last; ++first){
- this->insert_unique(*first);
- }
- }
-
- template<class InIt>
- void priv_insert_unique_loop_ordered(InIt first, InIt last)
- {
- const_iterator pos(this->cend());
- for ( ; first != last; ++first){
- pos = this->insert_unique(pos, *first);
+ ++pos;
 }
 }
};

Modified: trunk/boost/container/detail/iterators.hpp
==============================================================================
--- trunk/boost/container/detail/iterators.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/iterators.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -148,79 +148,79 @@
};

template <class T, class Difference = std::ptrdiff_t>
-class default_construct_iterator
+class value_init_construct_iterator
 : public std::iterator
 <std::random_access_iterator_tag, T, Difference, const T*, const T &>
{
- typedef default_construct_iterator<T, Difference> this_type;
+ typedef value_init_construct_iterator<T, Difference> this_type;

 public:
- explicit default_construct_iterator(Difference range_size)
+ explicit value_init_construct_iterator(Difference range_size)
 : m_num(range_size){}

 //Constructors
- default_construct_iterator()
+ value_init_construct_iterator()
 : m_num(0){}

- default_construct_iterator& operator++()
+ value_init_construct_iterator& operator++()
 { increment(); return *this; }

- default_construct_iterator operator++(int)
+ value_init_construct_iterator operator++(int)
 {
- default_construct_iterator result (*this);
+ value_init_construct_iterator result (*this);
 increment();
 return result;
 }

- default_construct_iterator& operator--()
+ value_init_construct_iterator& operator--()
 { decrement(); return *this; }

- default_construct_iterator operator--(int)
+ value_init_construct_iterator operator--(int)
 {
- default_construct_iterator result (*this);
+ value_init_construct_iterator result (*this);
 decrement();
 return result;
 }

- friend bool operator== (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator== (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return i.equal(i2); }

- friend bool operator!= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator!= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return !(i == i2); }

- friend bool operator< (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator< (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return i.less(i2); }

- friend bool operator> (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator> (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return i2 < i; }

- friend bool operator<= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator<= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return !(i > i2); }

- friend bool operator>= (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend bool operator>= (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return !(i < i2); }

- friend Difference operator- (const default_construct_iterator& i, const default_construct_iterator& i2)
+ friend Difference operator- (const value_init_construct_iterator& i, const value_init_construct_iterator& i2)
 { return i2.distance_to(i); }

 //Arithmetic
- default_construct_iterator& operator+=(Difference off)
+ value_init_construct_iterator& operator+=(Difference off)
 { this->advance(off); return *this; }

- default_construct_iterator operator+(Difference off) const
+ value_init_construct_iterator operator+(Difference off) const
 {
- default_construct_iterator other(*this);
+ value_init_construct_iterator other(*this);
 other.advance(off);
 return other;
 }

- friend default_construct_iterator operator+(Difference off, const default_construct_iterator& right)
+ friend value_init_construct_iterator operator+(Difference off, const value_init_construct_iterator& right)
 { return right + off; }

- default_construct_iterator& operator-=(Difference off)
+ value_init_construct_iterator& operator-=(Difference off)
 { this->advance(-off); return *this; }

- default_construct_iterator operator-(Difference off) const
+ value_init_construct_iterator operator-(Difference off) const
 { return *this + (-off); }

 //This pseudo-iterator's dereference operations have no sense since value is not
@@ -259,6 +259,118 @@
};

template <class T, class Difference = std::ptrdiff_t>
+class default_init_construct_iterator
+ : public std::iterator
+ <std::random_access_iterator_tag, T, Difference, const T*, const T &>
+{
+ typedef default_init_construct_iterator<T, Difference> this_type;
+
+ public:
+ explicit default_init_construct_iterator(Difference range_size)
+ : m_num(range_size){}
+
+ //Constructors
+ default_init_construct_iterator()
+ : m_num(0){}
+
+ default_init_construct_iterator& operator++()
+ { increment(); return *this; }
+
+ default_init_construct_iterator operator++(int)
+ {
+ default_init_construct_iterator result (*this);
+ increment();
+ return result;
+ }
+
+ default_init_construct_iterator& operator--()
+ { decrement(); return *this; }
+
+ default_init_construct_iterator operator--(int)
+ {
+ default_init_construct_iterator result (*this);
+ decrement();
+ return result;
+ }
+
+ friend bool operator== (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return i.equal(i2); }
+
+ friend bool operator!= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return !(i == i2); }
+
+ friend bool operator< (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return i.less(i2); }
+
+ friend bool operator> (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return i2 < i; }
+
+ friend bool operator<= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return !(i > i2); }
+
+ friend bool operator>= (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return !(i < i2); }
+
+ friend Difference operator- (const default_init_construct_iterator& i, const default_init_construct_iterator& i2)
+ { return i2.distance_to(i); }
+
+ //Arithmetic
+ default_init_construct_iterator& operator+=(Difference off)
+ { this->advance(off); return *this; }
+
+ default_init_construct_iterator operator+(Difference off) const
+ {
+ default_init_construct_iterator other(*this);
+ other.advance(off);
+ return other;
+ }
+
+ friend default_init_construct_iterator operator+(Difference off, const default_init_construct_iterator& right)
+ { return right + off; }
+
+ default_init_construct_iterator& operator-=(Difference off)
+ { this->advance(-off); return *this; }
+
+ default_init_construct_iterator operator-(Difference off) const
+ { return *this + (-off); }
+
+ //This pseudo-iterator's dereference operations have no sense since value is not
+ //constructed until ::boost::container::construct_in_place is called.
+ //So comment them to catch bad uses
+ //const T& operator*() const;
+ //const T& operator[](difference_type) const;
+ //const T* operator->() const;
+
+ 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>

Modified: trunk/boost/container/detail/multiallocation_chain.hpp
==============================================================================
--- trunk/boost/container/detail/multiallocation_chain.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/multiallocation_chain.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -243,10 +243,10 @@

    iterator before_begin()
    { return iterator(holder_.before_begin()); }
-
+*/
    iterator begin()
- { return iterator(holder_.begin()); }
-
+ { return iterator(this->MultiallocationChain::begin()); }
+/*
    iterator end()
    { return iterator(holder_.end()); }

Modified: trunk/boost/container/detail/node_alloc_holder.hpp
==============================================================================
--- trunk/boost/container/detail/node_alloc_holder.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/node_alloc_holder.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -28,6 +28,7 @@
#include <boost/container/detail/type_traits.hpp>
#include <boost/container/detail/utilities.hpp>
#include <boost/container/allocator_traits.hpp>
+#include <boost/container/detail/allocator_version_traits.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/destroyers.hpp>
#include <boost/container/detail/allocator_version_traits.hpp>
@@ -80,6 +81,7 @@
 typedef typename allocator_traits_type::template
 portable_rebind_alloc<Node>::type NodeAlloc;
 typedef allocator_traits<NodeAlloc> node_allocator_traits_type;
+ typedef container_detail::allocator_version_traits<NodeAlloc> node_allocator_version_traits_type;
 typedef A ValAlloc;
 typedef typename node_allocator_traits_type::pointer NodePtr;
 typedef container_detail::scoped_deallocator<NodeAlloc> Deallocator;
@@ -233,45 +235,41 @@
 (FwdIterator beg, difference_type n, Inserter inserter)
 {
 if(n){
- /*
- NodePtr p = this->allocate_one();
- Deallocator node_deallocator(p, this->node_alloc());
- ::boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->m_data), it);
- node_deallocator.release();
- //This does not throw
- typedef typename Node::hook_type hook_type;
- ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p))) hook_type;
- return (p);
- */
- typedef typename NodeAlloc::multiallocation_chain multiallocation_chain;
+ typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain;

 //Try to allocate memory in a single block
 typedef typename multiallocation_chain::iterator multialloc_iterator;
 multiallocation_chain mem;
- this->node_alloc().allocate_individual(n, mem);
+ NodeAlloc &nalloc = this->node_alloc();
+ node_allocator_version_traits_type::allocate_individual(nalloc, n, mem);
 multialloc_iterator itbeg(mem.begin()), itlast(mem.last());
 mem.clear();
 Node *p = 0;
- NodeAlloc &nalloc = this->node_alloc();
 BOOST_TRY{
+ Deallocator node_deallocator(NodePtr(), nalloc);
+ container_detail::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0);
 while(n--){
 p = container_detail::to_raw_pointer(&*itbeg);
+ node_deallocator.set(p);
 ++itbeg;
 //This can throw
- Deallocator node_deallocator(p, nalloc);
 boost::container::construct_in_place(nalloc, container_detail::addressof(p->m_data), beg);
+ sdestructor.set(p);
 ++beg;
- node_deallocator.release();
 //This does not throw
 typedef typename Node::hook_type hook_type;
 ::new(static_cast<hook_type*>(p)) hook_type;
- //This can throw in some containers (predicate might throw)
+ //This can throw in some containers (predicate might throw).
+ //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception)
 inserter(*p);
+ sdestructor.set(0);
 }
+ sdestructor.release();
+ node_deallocator.release();
 }
 BOOST_CATCH(...){
 mem.incorporate_after(mem.last(), &*itbeg, &*itlast, n);
- this->node_alloc().deallocate_individual(mem);
+ node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), mem);
 BOOST_RETHROW
 }
 BOOST_CATCH_END

Modified: trunk/boost/container/detail/tree.hpp
==============================================================================
--- trunk/boost/container/detail/tree.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/tree.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -178,6 +178,34 @@
 { m_data = ::boost::move(v); }
};

+template<class Node, class Icont>
+class insert_equal_end_hint_functor
+{
+ Icont &icont_;
+
+ public:
+ insert_equal_end_hint_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.insert_equal(this->icont_.cend(), n); }
+};
+
+template<class Node, class Icont>
+class push_back_functor
+{
+ Icont &icont_;
+
+ public:
+ push_back_functor(Icont &icont)
+ : icont_(icont)
+ {}
+
+ void operator()(Node &n)
+ { this->icont_.push_back(n); }
+};
+
}//namespace container_detail {

namespace container_detail {
@@ -405,11 +433,19 @@
 )
 : AllocHolder(a, value_compare(comp))
 {
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ const const_iterator end_it(this->cend());
 if(unique_insertion){
- this->insert_unique(first, last);
+ for ( ; first != last; ++first){
+ this->insert_unique(end_it, *first);
+ }
 }
 else{
- this->insert_equal(first, last);
+ for ( ; first != last; ++first){
+ this->insert_equal(end_it, *first);
+ }
 }
 }

@@ -426,12 +462,19 @@
 : AllocHolder(a, value_compare(comp))
 {
 if(unique_insertion){
- this->insert_unique(first, last);
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ const const_iterator end_it(this->cend());
+ for ( ; first != last; ++first){
+ this->insert_unique(end_it, *first);
+ }
 }
 else{
 //Optimized allocation and construction
 this->allocate_many_and_construct
- (first, std::distance(first, last), insert_equal_end_hint_functor(this->icont()));
+ ( first, std::distance(first, last)
+ , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
 }
 }

@@ -447,7 +490,9 @@
 )
 : AllocHolder(a, value_compare(comp))
 {
- this->insert_equal(first, last);
+ for ( ; first != last; ++first){
+ this->push_back_impl(*first);
+ }
 }

 template <class InputIterator>
@@ -464,7 +509,8 @@
 {
 //Optimized allocation and construction
 this->allocate_many_and_construct
- (first, std::distance(first, last), push_back_functor(this->icont()));
+ ( first, std::distance(first, last)
+ , container_detail::push_back_functor<Node, Icont>(this->icont()));
 }

 rbtree(const rbtree& x)
@@ -534,8 +580,8 @@
 rbtree& operator=(BOOST_RV_REF(rbtree) x)
 {
 if (&x != this){
- NodeAlloc &this_alloc = this->node_alloc();
- NodeAlloc &x_alloc = x.node_alloc();
+ NodeAlloc &this_alloc = this->get_stored_allocator();
+ const NodeAlloc &x_alloc = x.get_stored_allocator();
 //If allocators are equal we can just swap pointers
 if(this_alloc == x_alloc){
 //Destroy and swap pointers
@@ -678,8 +724,10 @@
 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);
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_unique_commit(*tmp, data));
+ destroy_deallocator.release();
+ return ret;
 }

 template<class MovableConvertible>
@@ -687,8 +735,10 @@
 (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);
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_unique_commit(*tmp, data));
+ destroy_deallocator.release();
+ return ret;
 }

 std::pair<iterator,bool> insert_unique(const value_type& v)
@@ -696,10 +746,10 @@
 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);
+ if(ret.second){
+ ret.first = this->insert_unique_commit(v, data);
+ }
+ return ret;
 }

 template<class MovableConvertible>
@@ -708,13 +758,22 @@
 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);
+ if(ret.second){
+ ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data);
+ }
+ return ret;
 }

 private:
+
+ template<class MovableConvertible>
+ void push_back_impl(BOOST_FWD_REF(MovableConvertible) mv)
+ {
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ //push_back has no-throw guarantee so avoid any deallocator/destroyer
+ this->icont().push_back(*tmp);
+ }
+
 std::pair<iterator, bool> emplace_unique_impl(NodePtr p)
 {
 value_type &v = p->get_data();
@@ -760,15 +819,21 @@
 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));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 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));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
@@ -792,16 +857,22 @@
 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)); \
+ NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \
+ iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); \
+ destroy_deallocator.release(); \
+ return ret; \
 } \
 \
 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)); \
+ NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp)); \
+ destroy_deallocator.release(); \
+ return ret; \
 } \
 //!
 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
@@ -833,53 +904,53 @@
 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 hint(this->cend());
- for( ; first != last; ++first)
- hint = this->insert_unique(hint, *first);
- }
- else{
- for( ; first != last; ++first)
- this->insert_unique(*first);
- }
+ 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));
+ NodePtr tmp(AllocHolder::create_node(v));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 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));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 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));
+ NodePtr tmp(AllocHolder::create_node(v));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 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));
+ NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv)));
+ scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());
+ iterator ret(this->icont().insert_equal(hint.get(), *tmp));
+ destroy_deallocator.release();
+ return ret;
 }

 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 hint(this->cend());
 for( ; first != last; ++first)
- hint = this->insert_equal(hint, *first);
+ this->insert_equal(*first);
 }

 iterator erase(const_iterator position)
@@ -930,41 +1001,6 @@
 return std::pair<const_iterator,const_iterator>
 (const_iterator(ret.first), const_iterator(ret.second));
 }
-
- private:
-
- class insert_equal_end_hint_functor;
- friend class insert_equal_end_hint_functor;
-
- class insert_equal_end_hint_functor
- {
- Icont &icont_;
- const iconst_iterator cend_;
-
- public:
- insert_equal_end_hint_functor(Icont &icont)
- : icont_(icont), cend_(this->icont_.cend())
- {}
-
- void operator()(Node &n)
- { this->icont_.insert_equal(cend_, n); }
- };
-
- class push_back_functor;
- friend class push_back_functor;
-
- class push_back_functor
- {
- Icont &icont_;
-
- public:
- push_back_functor(Icont &icont)
- : icont_(icont)
- {}
-
- void operator()(Node &n)
- { this->icont_.push_back(n); }
- };
};

template <class Key, class Value, class KeyOfValue,

Modified: trunk/boost/container/detail/utilities.hpp
==============================================================================
--- trunk/boost/container/detail/utilities.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/detail/utilities.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -622,7 +622,7 @@

//////////////////////////////////////////////////////////////////////////////
//
-// uninitialized_default_alloc_n
+// uninitialized_value_init_alloc_n
//
//////////////////////////////////////////////////////////////////////////////

@@ -636,7 +636,7 @@
template
 <typename A,
 typename F> // F models ForwardIterator
-inline F uninitialized_default_alloc_n(A &a, typename allocator_traits<A>::difference_type n, F r)
+inline F uninitialized_value_init_alloc_n(A &a, typename allocator_traits<A>::difference_type n, F r)
{
 F back = r;
 BOOST_TRY{
@@ -657,6 +657,41 @@

//////////////////////////////////////////////////////////////////////////////
//
+// uninitialized_default_init_alloc_n
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! Effects:
+//! \code
+//! for (; n--; ++r, ++f)
+//! allocator_traits::construct(a, &*r);
+//! \endcode
+//!
+//! Returns: r
+template
+ <typename A,
+ typename F> // F models ForwardIterator
+inline F uninitialized_default_init_alloc_n(A &a, typename allocator_traits<A>::difference_type n, F r)
+{
+ F back = r;
+ BOOST_TRY{
+ while (n--) {
+ allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), default_init);
+ ++r;
+ }
+ }
+ BOOST_CATCH(...){
+ for (; back != r; ++back){
+ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back));
+ }
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+ return r;
+}
+
+//////////////////////////////////////////////////////////////////////////////
+//
// uninitialized_fill_alloc
//
//////////////////////////////////////////////////////////////////////////////

Modified: trunk/boost/container/flat_map.hpp
==============================================================================
--- trunk/boost/container/flat_map.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/flat_map.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -694,6 +694,8 @@
 //! search time plus N*size() insertion time.
 //!
 //! Note: If an element is inserted it might invalidate elements.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
 { m_flat_tree.insert_unique(ordered_unique_range, first, last); }
@@ -798,7 +800,7 @@
 //!
 //! Complexity: log(size())+count(k)
 size_type count(const key_type& x) const
- { return m_flat_tree.find(x) == m_flat_tree.end() ? 0 : 1; }
+ { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }

 //! Returns: An iterator pointing to the first element with key not less
 //! than k, or a.end() if such an element is not found.
@@ -1487,6 +1489,8 @@
 //! search time plus N*size() insertion time.
 //!
 //! Note: If an element is inserted it might invalidate elements.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 void insert(ordered_range_t, InputIterator first, InputIterator last)
 { m_flat_tree.insert_equal(ordered_range, first, last); }

Modified: trunk/boost/container/flat_set.hpp
==============================================================================
--- trunk/boost/container/flat_set.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/flat_set.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -636,7 +636,7 @@
 //!
 //! Complexity: log(size())+count(k)
 size_type count(const key_type& x) const
- { return m_flat_tree.find(x) == m_flat_tree.end() ? 0 : 1; }
+ { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }

 //! Returns: An iterator pointing to the first element with key not less
 //! than k, or a.end() if such an element is not found.

Modified: trunk/boost/container/list.hpp
==============================================================================
--- trunk/boost/container/list.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/list.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -563,7 +563,7 @@
 { return AllocHolder::max_size(); }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
 //! Throws: If memory allocation throws, or T's copy constructor throws.
 //!
@@ -571,8 +571,8 @@
 void resize(size_type new_size)
 {
 if(!priv_try_shrink(new_size)){
- typedef default_construct_iterator<value_type, difference_type> default_iterator;
- this->insert(this->cend(), default_iterator(new_size - this->size()), default_iterator());
+ typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
+ this->insert(this->cend(), value_init_iterator(new_size - this->size()), value_init_iterator());
 }
 }

Modified: trunk/boost/container/map.hpp
==============================================================================
--- trunk/boost/container/map.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/map.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -170,6 +170,8 @@
 //! unique values.
 //!
 //! Complexity: Linear in N.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 map( ordered_unique_range_t, InputIterator first, InputIterator last
 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
@@ -711,7 +713,7 @@
 //!
 //! Complexity: log(size())+count(k)
 size_type count(const key_type& x) const
- { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
+ { return static_cast<size_type>(m_tree.find(x) != m_tree.end()); }

 //! Returns: An iterator pointing to the first element with key not less
 //! than k, or a.end() if such an element is not found.
@@ -971,6 +973,8 @@
 //! Requires: [first ,last) must be ordered according to the predicate.
 //!
 //! Complexity: Linear in N.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(),
 const allocator_type& a = allocator_type())

Modified: trunk/boost/container/set.hpp
==============================================================================
--- trunk/boost/container/set.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/set.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -139,6 +139,8 @@
 //! unique values.
 //!
 //! Complexity: Linear in N.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 set( ordered_unique_range_t, InputIterator first, InputIterator last
 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
@@ -556,7 +558,7 @@
 //!
 //! Complexity: log(size())+count(k)
 size_type count(const key_type& x) const
- { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
+ { return static_cast<size_type>(m_tree.find(x) != m_tree.end()); }

 //! Returns: An iterator pointing to the first element with key not less
 //! than k, or a.end() if such an element is not found.
@@ -770,6 +772,8 @@
 //! Requires: [first ,last) must be ordered according to the predicate.
 //!
 //! Complexity: Linear in N.
+ //!
+ //! Note: Non-standard extension.
 template <class InputIterator>
 multiset( ordered_range_t, InputIterator first, InputIterator last
 , const Compare& comp = Compare()

Modified: trunk/boost/container/slist.hpp
==============================================================================
--- trunk/boost/container/slist.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/slist.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -588,7 +588,7 @@
 { return AllocHolder::max_size(); }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
 //! Throws: If memory allocation throws, or T's copy constructor throws.
 //!
@@ -597,8 +597,8 @@
 {
 const_iterator last_pos;
 if(!priv_try_shrink(new_size, last_pos)){
- typedef default_construct_iterator<value_type, difference_type> default_iterator;
- this->insert_after(last_pos, default_iterator(new_size - this->size()), default_iterator());
+ typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
+ this->insert_after(last_pos, value_init_iterator(new_size - this->size()), value_init_iterator());
 }
 }

Modified: trunk/boost/container/stable_vector.hpp
==============================================================================
--- trunk/boost/container/stable_vector.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/stable_vector.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -123,8 +123,8 @@
 rebind_pointer<void>::type
>
{
- private:
- node();
+// private:
+// node();

 public:
 typename ::boost::intrusive::pointer_traits<Pointer>::element_type value;
@@ -568,7 +568,7 @@
 }

 //! Effects: Constructs a stable_vector that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
 //!
 //! Throws: If allocator_type's default constructor or copy constructor
 //! throws or T's default or copy constructor throws.
@@ -584,6 +584,24 @@
 }

 //! Effects: Constructs a stable_vector that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! Throws: If allocator_type's default constructor or copy constructor
+ //! throws or T's default or copy constructor throws.
+ //!
+ //! Complexity: Linear to n.
+ //!
+ //! Note: Non-standard extension
+ stable_vector(size_type n, default_init_t)
+ : internal_data(), index()
+ {
+ stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
+ this->resize(n, default_init);
+ STABLE_VECTOR_CHECK_INVARIANT;
+ cod.release();
+ }
+
+ //! Effects: Constructs a stable_vector that will use a copy of allocator a
 //! and inserts n copies of value.
 //!
 //! Throws: If allocator_type's default constructor or copy constructor
@@ -960,17 +978,35 @@
 { return this->index.max_size() - ExtraPointers; }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
- //! Throws: If memory allocation throws, or T's copy constructor throws.
+ //! Throws: If memory allocation throws, or T's default constructor throws.
 //!
 //! Complexity: Linear to the difference between size() and new_size.
 void resize(size_type n)
 {
- typedef default_construct_iterator<value_type, difference_type> default_iterator;
+ typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
+ STABLE_VECTOR_CHECK_INVARIANT;
+ if(n > this->size())
+ this->insert(this->cend(), value_init_iterator(n - this->size()), value_init_iterator());
+ else if(n < this->size())
+ this->erase(this->cbegin() + n, this->cend());
+ }
+
+ //! Effects: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are default initialized.
+ //!
+ //! Throws: If memory allocation throws, or T's default constructor throws.
+ //!
+ //! Complexity: Linear to the difference between size() and new_size.
+ //!
+ //! Note: Non-standard extension
+ void resize(size_type n, default_init_t)
+ {
+ typedef default_init_construct_iterator<value_type, difference_type> default_init_iterator;
 STABLE_VECTOR_CHECK_INVARIANT;
 if(n > this->size())
- this->insert(this->cend(), default_iterator(n - this->size()), default_iterator());
+ this->insert(this->cend(), default_init_iterator(n - this->size()), default_init_iterator());
 else if(n < this->size())
 this->erase(this->cbegin() + n, this->cend());
 }

Modified: trunk/boost/container/static_vector.hpp
==============================================================================
--- trunk/boost/container/static_vector.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/static_vector.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -138,7 +138,7 @@

 //! @pre <tt>count <= capacity()</tt>
 //!
- //! @brief Constructs a static_vector containing count default constructed Values.
+ //! @brief Constructs a static_vector containing count value initialized values.
 //!
 //! @param count The number of values which will be contained in the container.
 //!
@@ -153,6 +153,24 @@

 //! @pre <tt>count <= capacity()</tt>
 //!
+ //! @brief Constructs a static_vector containing count value initialized values.
+ //!
+ //! @param count The number of values which will be contained in the container.
+ //!
+ //! @par Throws
+ //! If Value's default constructor throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ //!
+ //! @par Note
+ //! Non-standard extension
+ static_vector(size_type count, default_init_t)
+ : base_t(count, default_init_t())
+ {}
+
+ //! @pre <tt>count <= capacity()</tt>
+ //!
 //! @brief Constructs a static_vector containing count copies of value.
 //!
 //! @param count The number of copies of a values that will be contained in the container.
@@ -358,7 +376,7 @@
 //! @pre <tt>count <= capacity()</tt>
 //!
 //! @brief Inserts or erases elements at the end such that
- //! the size becomes count. New elements are default constructed.
+ //! the size becomes count. New elements are value initialized.
 //!
 //! @param count The number of elements which will be stored in the container.
 //!
@@ -372,6 +390,23 @@
 //! @pre <tt>count <= capacity()</tt>
 //!
 //! @brief Inserts or erases elements at the end such that
+ //! the size becomes count. New elements are default initialized.
+ //!
+ //! @param count The number of elements which will be stored in the container.
+ //!
+ //! @par Throws
+ //! If Value's default constructor throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ //!
+ //! @par Note
+ //! Non-standard extension
+ void resize(size_type count, default_init_t);
+
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Inserts or erases elements at the end such that
 //! the size becomes count. New elements are copy constructed from value.
 //!
 //! @param count The number of elements which will be stored in the container.

Modified: trunk/boost/container/string.hpp
==============================================================================
--- trunk/boost/container/string.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/string.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -937,7 +937,7 @@
 }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
 //! Throws: If memory allocation throws
 //!

Modified: trunk/boost/container/vector.hpp
==============================================================================
--- trunk/boost/container/vector.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/boost/container/vector.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -293,18 +293,26 @@
 template<class AllocConvertible>
 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
 : Allocator(boost::forward<AllocConvertible>(a))
+ , m_start()
 , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
+ , m_capacity()
 {
- m_start = this->allocation_command(allocate_new, initial_size, initial_size, m_capacity, m_start).first;
+ if(initial_size){
+ m_start = this->allocation_command(allocate_new, initial_size, initial_size, m_capacity, m_start).first;
+ }
 }

 //Constructor, does not throw
 explicit vector_alloc_holder(size_type initial_size)
 : Allocator()
+ , m_start()
 , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
+ , m_capacity()
 {
- m_start = this->allocation_command
- (allocate_new, initial_size, initial_size, m_capacity, m_start).first;
+ if(initial_size){
+ m_start = this->allocation_command
+ (allocate_new, initial_size, initial_size, m_capacity, m_start).first;
+ }
 }

 vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) BOOST_CONTAINER_NOEXCEPT
@@ -319,8 +327,10 @@

 void first_allocation(size_type cap)
 {
- m_start = this->allocation_command
- (allocate_new, cap, cap, m_capacity, m_start).first;
+ if(cap){
+ m_start = this->allocation_command
+ (allocate_new, cap, cap, m_capacity, m_start).first;
+ }
 }

 void first_allocation_same_allocator_type(size_type cap)
@@ -417,16 +427,18 @@
 template<class AllocConvertible>
 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
 : Allocator(boost::forward<AllocConvertible>(a))
- , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
+ , m_size(initial_size) //Size is initialized here...
 {
+ //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
 this->first_allocation(initial_size);
 }

 //Constructor, does not throw
 explicit vector_alloc_holder(size_type initial_size)
 : Allocator()
- , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
+ , m_size(initial_size) //Size is initialized here...
 {
+ //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
 this->first_allocation(initial_size);
 }

@@ -611,7 +623,7 @@
 {}

 //! Effects: Constructs a vector that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
 //!
 //! Throws: If allocator_type's default constructor or allocation
 //! throws or T's default constructor throws.
@@ -620,7 +632,24 @@
 explicit vector(size_type n)
 : m_holder(n)
 {
- boost::container::uninitialized_default_alloc_n(this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ boost::container::uninitialized_value_init_alloc_n
+ (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ }
+
+ //! Effects: Constructs a vector that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! Throws: If allocator_type's default constructor or allocation
+ //! throws or T's default constructor throws.
+ //!
+ //! Complexity: Linear to n.
+ //!
+ //! Note: Non-standard extension
+ explicit vector(size_type n, default_init_t)
+ : m_holder(n)
+ {
+ boost::container::uninitialized_default_init_alloc_n
+ (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
 }

 //! Effects: Constructs a vector
@@ -1030,9 +1059,9 @@
 { return allocator_traits_type::max_size(this->m_holder.alloc()); }

 //! Effects: Inserts or erases elements at the end such that
- //! the size becomes n. New elements are default constructed.
+ //! the size becomes n. New elements are value initialized.
 //!
- //! Throws: If memory allocation throws, or T's copy constructor throws.
+ //! Throws: If memory allocation throws, or T's constructor throws.
 //!
 //! Complexity: Linear to the difference between size() and new_size.
 void resize(size_type new_size)
@@ -1044,7 +1073,29 @@
 }
 else{
 const size_type n = new_size - this->size();
- container_detail::insert_default_constructed_n_proxy<Allocator, T*> proxy(this->m_holder.alloc());
+ container_detail::insert_value_initialized_n_proxy<Allocator, T*> proxy(this->m_holder.alloc());
+ this->priv_forward_range_insert_at_end(n, proxy, alloc_version());
+ }
+ }
+
+ //! Effects: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are value initialized.
+ //!
+ //! Throws: If memory allocation throws, or T's constructor throws.
+ //!
+ //! Complexity: Linear to the difference between size() and new_size.
+ //!
+ //! Note: Non-standard extension
+ void resize(size_type new_size, default_init_t)
+ {
+ const size_type sz = this->size();
+ if (new_size < sz){
+ //Destroy last elements
+ this->priv_destroy_last_n(sz - new_size);
+ }
+ else{
+ const size_type n = new_size - this->size();
+ container_detail::insert_default_initialized_n_proxy<Allocator, T*> proxy(this->m_holder.alloc());
 this->priv_forward_range_insert_at_end(n, proxy, alloc_version());
 }
 }

Modified: trunk/libs/container/bench/Jamfile.v2
==============================================================================
--- trunk/libs/container/bench/Jamfile.v2 Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/bench/Jamfile.v2 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -21,7 +21,7 @@

    for local fileb in [ glob *.cpp ]
    {
- all_rules += [ run $(fileb) /boost/timer//boost_timer /boost/system//boost_system /boost/thread//boost_thread
+ all_rules += [ run $(fileb) /boost/timer//boost_timer
       : # additional args
       : # test-files
       : # requirements

Added: trunk/libs/container/bench/bench_set.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/container/bench/bench_set.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -0,0 +1,348 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2013-2013. 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.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#include "boost/container/set.hpp"
+#include "boost/container/flat_set.hpp"
+#include <set>
+#include <vector>
+#include <iostream>
+#include <boost/timer/timer.hpp>
+#include <algorithm>
+#include <exception>
+
+using boost::timer::cpu_timer;
+using boost::timer::cpu_times;
+using boost::timer::nanosecond_type;
+
+#ifdef NDEBUG
+static const std::size_t N = 5000;
+#else
+static const std::size_t N = 500;
+#endif
+
+void compare_times(cpu_times time_numerator, cpu_times time_denominator){
+ std::cout << "----------------------------------------------" << '\n';
+ std::cout << " wall = " << ((double)time_numerator.wall/(double)time_denominator.wall) << std::endl;
+ std::cout << "----------------------------------------------" << '\n' << std::endl;
+}
+
+std::vector<int> sorted_unique_range;
+std::vector<int> sorted_range;
+std::vector<int> random_unique_range;
+std::vector<int> random_range;
+
+void fill_ranges()
+{
+ sorted_unique_range.resize(N);
+ sorted_range.resize(N);
+ random_unique_range.resize(N);
+ random_range.resize(N);
+ std::srand (0);
+ //random_range
+ std::generate(random_unique_range.begin(), random_unique_range.end(), std::rand);
+ random_unique_range.erase(std::unique(random_unique_range.begin(), random_unique_range.end()), random_unique_range.end());
+ //random_range
+ random_range = random_unique_range;
+ random_range.insert(random_range.end(), random_unique_range.begin(), random_unique_range.end());
+ //sorted_unique_range
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ sorted_unique_range[i] = static_cast<int>(i);
+ }
+ //sorted_range
+ sorted_range = sorted_unique_range;
+ sorted_range.insert(sorted_range.end(), sorted_unique_range.begin(), sorted_unique_range.end());
+ std::sort(sorted_range.begin(), sorted_range.end());
+}
+
+template<typename T>
+cpu_times construct_time()
+{
+ cpu_timer sur_timer, sr_timer, rur_timer, rr_timer, copy_timer, assign_timer, destroy_timer;
+ //sur_timer.stop();sr_timer.stop();rur_timer.stop();rr_timer.stop();destroy_timer.stop();
+
+ cpu_timer total_time;
+ total_time.resume();
+
+ for(std::size_t i = 0; i != N; ++i){
+ {
+ sur_timer.resume();
+ T t(sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_timer.stop();
+ }
+ {
+ sr_timer.resume();
+ T t(sorted_range.begin(), sorted_range.end());
+ sr_timer.stop();
+ copy_timer.resume();
+ T taux(t);
+ copy_timer.stop();
+ assign_timer.resume();
+ t = taux;;
+ assign_timer.stop();
+ }
+ {
+ rur_timer.resume();
+ T t(random_unique_range.begin(), random_unique_range.end());
+ rur_timer.stop();
+ }
+ {
+ rr_timer.resume();
+ T t(random_range.begin(), random_range.end());
+ rr_timer.stop();
+ destroy_timer.resume();
+ }
+ destroy_timer.stop();
+ }
+ total_time.stop();
+
+ std::cout << " Construct sorted_unique_range " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Construct sorted_range " << boost::timer::format(sr_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Copy sorted range " << boost::timer::format(copy_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Assign sorted range " << boost::timer::format(assign_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Construct random_unique_range " << boost::timer::format(rur_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Construct random_range " << boost::timer::format(rr_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Destroy " << boost::timer::format(destroy_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws wall\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename T>
+cpu_times insert_time()
+{
+ cpu_timer sur_timer,sr_timer,rur_timer,rr_timer,destroy_timer;
+ sur_timer.stop();sr_timer.stop();rur_timer.stop();rr_timer.stop();
+
+ cpu_timer total_time;
+ total_time.resume();
+
+ for(std::size_t i = 0; i != N; ++i){
+ {
+ sur_timer.resume();
+ T t;
+ t.insert(sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_timer.stop();
+ }
+ {
+ sr_timer.resume();
+ T t;
+ t.insert(sorted_range.begin(), sorted_range.end());
+ sr_timer.stop();
+ }
+ {
+ rur_timer.resume();
+ T t;
+ t.insert(random_unique_range.begin(), random_unique_range.end());
+ rur_timer.stop();
+ }
+ {
+ rr_timer.resume();
+ T t;
+ t.insert(random_range.begin(), random_range.end());
+ rr_timer.stop();
+ }
+ }
+ total_time.stop();
+
+ std::cout << " Insert sorted_unique_range " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Insert sorted_range " << boost::timer::format(sr_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Insert random_unique_range " << boost::timer::format(rur_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Insert random_range " << boost::timer::format(rr_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws wall\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename T>
+cpu_times search_time()
+{
+ cpu_timer find_timer, lower_timer, upper_timer, equal_range_timer, count_timer;
+
+ T t(sorted_unique_range.begin(), sorted_unique_range.end());
+
+ cpu_timer total_time;
+ total_time.resume();
+
+ for(std::size_t i = 0; i != N; ++i){
+ //Find
+ {
+ std::size_t found = 0;
+ find_timer.resume();
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.find(sorted_unique_range[i]));
+ }
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.find(sorted_unique_range[i]));
+ }
+ find_timer.stop();
+ if(found/2 != t.size()){
+ std::cout << "ERROR! all elements not found" << std::endl;
+ }
+ }
+ //Lower
+ {
+ std::size_t found = 0;
+ lower_timer.resume();
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.lower_bound(sorted_unique_range[i]));
+ }
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.lower_bound(sorted_unique_range[i]));
+ }
+ lower_timer.stop();
+ if(found/2 != t.size()){
+ std::cout << "ERROR! all elements not found" << std::endl;
+ }
+ }
+ //Upper
+ {
+ std::size_t found = 0;
+ upper_timer.resume();
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.upper_bound(sorted_unique_range[i]));
+ }
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.end() != t.upper_bound(sorted_unique_range[i]));
+ }
+ upper_timer.stop();
+ if(found/2 != (t.size()-1)){
+ std::cout << "ERROR! all elements not found" << std::endl;
+ }
+ }
+ //Equal
+ {
+ std::size_t found = 0;
+ std::pair<typename T::iterator,typename T::iterator> ret;
+ equal_range_timer.resume();
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ ret = t.equal_range(sorted_unique_range[i]);
+ found += static_cast<std::size_t>(ret.first != ret.second);
+ }
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ ret = t.equal_range(sorted_unique_range[i]);
+ found += static_cast<std::size_t>(ret.first != ret.second);
+ }
+ equal_range_timer.stop();
+ if(found/2 != t.size()){
+ std::cout << "ERROR! all elements not found" << std::endl;
+ }
+ }
+ //Count
+ {
+ std::size_t found = 0;
+ std::pair<typename T::iterator,typename T::iterator> ret;
+ count_timer.resume();
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.count(sorted_unique_range[i]));
+ }
+ for(std::size_t i = 0, max = sorted_unique_range.size(); i != max; ++i){
+ found += static_cast<std::size_t>(t.count(sorted_unique_range[i]));
+ }
+ count_timer.stop();
+ if(found/2 != t.size()){
+ std::cout << "ERROR! all elements not found" << std::endl;
+ }
+ }
+ }
+ total_time.stop();
+
+ std::cout << " Find " << boost::timer::format(find_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Lower Bound " << boost::timer::format(lower_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Upper Bound " << boost::timer::format(upper_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Equal Range " << boost::timer::format(equal_range_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Count " << boost::timer::format(count_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws wall\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename T>
+void extensions_time()
+{
+ cpu_timer sur_timer,sur_opt_timer;
+ sur_timer.stop();sur_opt_timer.stop();
+
+ for(std::size_t i = 0; i != N; ++i){
+ {
+ sur_timer.resume();
+ T t(sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_timer.stop();
+ }
+ {
+ sur_opt_timer.resume();
+ T t(boost::container::ordered_unique_range, sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_opt_timer.stop();
+ }
+
+ }
+ std::cout << " Construct sorted_unique_range " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << " Construct sorted_unique_range (extension) " << boost::timer::format(sur_opt_timer.elapsed(), boost::timer::default_places, "%ws wall\n");
+ std::cout << "Total time (Extension/Standard):\n";
+ compare_times(sur_opt_timer.elapsed(), sur_timer.elapsed());
+}
+
+template<class BoostClass, class StdClass>
+void launch_tests(const char *BoostContName, const char *StdContName)
+{
+ try {
+ fill_ranges();
+ {
+ std::cout << "Construct benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = construct_time< BoostClass >();
+
+ std::cout << "Construct benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = construct_time< StdClass >();
+
+ std::cout << "Total time (" << BoostContName << "/" << StdContName << "):\n";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Insert benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = insert_time< BoostClass >();
+
+ std::cout << "Insert benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = insert_time< StdClass >();
+
+ std::cout << "Total time (" << BoostContName << "/" << StdContName << "):\n";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Search benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = search_time< BoostClass >();
+
+ std::cout << "Search benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = search_time< StdClass >();
+
+ std::cout << "Total time (" << BoostContName << "/" << StdContName << "):\n";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Extensions benchmark:" << BoostContName << std::endl;
+ extensions_time< BoostClass >();
+ }
+
+ }catch(std::exception e){
+ std::cout << e.what();
+ }
+}
+
+int main()
+{
+ //set vs std::set
+ launch_tests< boost::container::set<int> , std::set<int> >
+ ("boost::container::set<int>", "std::set<int>");/*
+ //multiset vs std::set
+ launch_tests< boost::container::multiset<int> , std::multiset<int> >
+ ("boost::container::multiset<int>", "std::multiset<int>");*/
+ //flat_set vs set
+ //launch_tests< boost::container::flat_set<int> , boost::container::set<int> >
+ //("boost::container::flat_set<int>", "boost::container::set<int>");
+ //flat_multiset vs multiset
+ //launch_tests< boost::container::flat_multiset<int> , boost::container::multiset<int> >
+ //("boost::container::flat_multiset<int>", "boost::container::multiset<int>");
+ return 1;
+}

Modified: trunk/libs/container/bench/bench_static_vector.cpp
==============================================================================
--- trunk/libs/container/bench/bench_static_vector.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/bench/bench_static_vector.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -20,7 +20,6 @@
#include <vector>
#include <iostream>
#include <boost/timer/timer.hpp>
-#include <set>
#include <algorithm>
#include <exception>

Modified: trunk/libs/container/bench/detail/varray.hpp
==============================================================================
--- trunk/libs/container/bench/detail/varray.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/bench/detail/varray.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -293,7 +293,7 @@

 //! @pre <tt>count <= capacity()</tt>
 //!
- //! @brief Constructs a varray containing count default constructed Values.
+ //! @brief Constructs a varray containing count value initialized Values.
 //!
 //! @param count The number of values which will be contained in the container.
 //!
@@ -616,7 +616,7 @@
 //! @pre <tt>count <= capacity()</tt>
 //!
 //! @brief Inserts or erases elements at the end such that
- //! the size becomes count. New elements are default constructed.
+ //! the size becomes count. New elements are value initialized.
 //!
 //! @param count The number of elements which will be stored in the container.
 //!

Modified: trunk/libs/container/bench/varray.hpp
==============================================================================
--- trunk/libs/container/bench/varray.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/bench/varray.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -91,7 +91,7 @@

 //! @pre <tt>count <= capacity()</tt>
 //!
- //! @brief Constructs a varray containing count default constructed Values.
+ //! @brief Constructs a varray containing count value initialized Values.
 //!
 //! @param count The number of values which will be contained in the container.
 //!
@@ -311,7 +311,7 @@
 //! @pre <tt>count <= capacity()</tt>
 //!
 //! @brief Inserts or erases elements at the end such that
- //! the size becomes count. New elements are default constructed.
+ //! the size becomes count. New elements are value initialized.
 //!
 //! @param count The number of elements which will be stored in the container.
 //!

Modified: trunk/libs/container/doc/container.qbk
==============================================================================
--- trunk/libs/container/doc/container.qbk Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/doc/container.qbk 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -502,6 +502,52 @@

[endsect]

+[section:extended_functionality Extended functionality]
+
+[section:default_initialialization Default initialization for vector-like containers]
+
+STL and most other containers value initialize new elements in common operations like
+`vector::resize(size_type n)` or `explicit vector::vector(size_type n)`.
+
+In some performance-sensitive environments, where vectors are used as a replacement for
+variable-size buffers for file or network operations,
+[@http://en.cppreference.com/w/cpp/language/value_initialization value initialization]
+is a cost that is not negligible as elements are going to be overwritten by an external source
+shortly after new elements are added to the container.
+
+[*Boost.Container] offers two new members for `vector`, `static_vector` and `stable_vector`:
+`explicit container::container(size_type n, default_init_t)` and
+`explicit container::resize(size_type n, default_init_t)`, where new elements are constructed
+using [@http://en.cppreference.com/w/cpp/language/default_initialization default initialization].
+
+[endsect]
+
+[/
+/a__section:get_stored_allocator Obtain stored allocator__a
+/
+/STL containers offer a `get_allocator()` member to obtain a copy of the allocator that
+/the container is using to allocate and construct elements. For performance reasons, some
+/applications need o
+/
+/http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
+/
+/a__endsect__a
+/
+/a__section:ordered_range_insertion Ordered range insertion (a__'ordered_unique_range__a, a__'ordered_range__a) __a
+/
+/a__endsect__a
+/
+/a__section:constant_time_range_splice Constant-time range splice__a
+/
+/a__endsect__a
+/
+/a__section:previous_element_slist Slist previous element__a
+/
+/a__endsect__a
+/]
+
+[endsect]
+
[section:Cpp11_conformance C++11 Conformance]

[*Boost.Container] aims for full C++11 conformance except reasoned deviations,

Added: trunk/libs/container/proj/vc7ide/bench_set.vcproj
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/container/proj/vc7ide/bench_set.vcproj 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -0,0 +1,134 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="bench_set"
+ ProjectGUID="{5E1C1C23-26A9-4FE5-A24E-DA735271C32B}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="../../Bin/Win32/Debug"
+ IntermediateDirectory="Debug/bench_set"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../.."
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE;BOOST_DATE_TIME_NO_LIB"
+ MinimalRebuild="TRUE"
+ ExceptionHandling="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="3"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="FALSE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ AdditionalDependencies="winmm.lib"
+ OutputFile="$(OutDir)/bench_set_d.exe"
+ LinkIncremental="1"
+ AdditionalLibraryDirectories="../../../../stage/lib"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/bench_set.pdb"
+ SubSystem="1"
+ TargetMachine="1"
+ FixedBaseAddress="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="../../Bin/Win32/Release"
+ IntermediateDirectory="Release/bench_set"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../.."
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE;BOOST_DATE_TIME_NO_LIB"
+ RuntimeLibrary="2"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="FALSE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="0"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ AdditionalDependencies="winmm.lib"
+ OutputFile="$(OutDir)/bench_set.exe"
+ LinkIncremental="1"
+ AdditionalLibraryDirectories="../../../../stage/lib"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4B737ACF-06A6-1243-CC8A-3D7D42A02A3F}">
+ <File
+ RelativePath="..\..\bench\bench_set.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>

Modified: trunk/libs/container/proj/vc7ide/container.sln
==============================================================================
--- trunk/libs/container/proj/vc7ide/container.sln Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/proj/vc7ide/container.sln 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -67,6 +67,10 @@
         ProjectSection(ProjectDependencies) = postProject
         EndProjectSection
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "bench_set", "bench_set.vcproj", "{5E1C1C23-26A9-4FE5-A24E-DA735271C32B}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
Global
         GlobalSection(SolutionConfiguration) = preSolution
                 Debug = Debug
@@ -137,12 +141,14 @@
                 {5A8D91E0-FA57-284F-84FE-D3A6BA792002}.Release.Build.0 = Release|Win32
                 {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Debug.ActiveCfg = Debug|Win32
                 {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Debug.Build.0 = Debug|Win32
- {58E1C1C3-096A-84F0-4FA2-D6BA79201C02}.Release.ActiveCfg = Release|Win32
- {58E1C1C3-096A-84F0-4FA2-D6BA79201C02}.Release.Build.0 = Release|Win32
- {58E1C1C3-096A-84F1-4FA2-D6BA79201C02}.Debug.ActiveCfg = Debug|Win32
- {58E1C1C3-096A-84F1-4FA2-D6BA79201C02}.Debug.Build.0 = Debug|Win32
- {58E1C1C3-096A-84F2-4FA2-D6BA79201C02}.Release.ActiveCfg = Release|Win32
- {58E1C1C3-096A-84F2-4FA2-D6BA79201C02}.Release.Build.0 = Release|Win32
+ {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Release.ActiveCfg = Release|Win32
+ {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Debug.ActiveCfg = Debug|Win32
+ {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Debug.Build.0 = Debug|Win32
+ {58E1C1C3-096A-84FE-4FA2-D6BA79201C02}.Release.ActiveCfg = Release|Win32
+ {5E1C1C23-26A9-4FE5-A24E-DA735271C32B}.Debug.ActiveCfg = Debug|Win32
+ {5E1C1C23-26A9-4FE5-A24E-DA735271C32B}.Debug.Build.0 = Debug|Win32
+ {5E1C1C23-26A9-4FE5-A24E-DA735271C32B}.Release.ActiveCfg = Release|Win32
+ {5E1C1C23-26A9-4FE5-A24E-DA735271C32B}.Release.Build.0 = Release|Win32
         EndGlobalSection
         GlobalSection(ExtensibilityGlobals) = postSolution
         EndGlobalSection

Modified: trunk/libs/container/proj/vc7ide/container.vcproj
==============================================================================
--- trunk/libs/container/proj/vc7ide/container.vcproj Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/proj/vc7ide/container.vcproj 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -338,6 +338,9 @@
 Name="bench"
 Filter="">
 <File
+ RelativePath="..\..\bench\Jamfile.v2">
+ </File>
+ <File
 RelativePath="..\..\bench\varray.hpp">
 </File>
 <Filter

Modified: trunk/libs/container/test/allocator_traits_test.cpp
==============================================================================
--- trunk/libs/container/test/allocator_traits_test.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/allocator_traits_test.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -25,6 +25,12 @@
 public:
 typedef T value_type;

+ template <class U>
+ SimpleAllocator(SimpleAllocator)
+ : allocate_called_(false)
+ , deallocate_called_(false)
+ {}
+
 SimpleAllocator()
 : allocate_called_(false)
 , deallocate_called_(false)
@@ -132,6 +138,13 @@
 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
 #include BOOST_PP_LOCAL_ITERATE()

+ template<class U>
+ void construct(U *p, boost::container::default_init_t)
+ {
+ construct_called_ = true;
+ ::new (p) U;
+ }
+
 //getters
 bool allocate_called() const
 { return allocate_called_; }
@@ -157,13 +170,13 @@

class copymovable
{
- bool copymoveconstructed_;
- bool moved_;
-
 BOOST_COPYABLE_AND_MOVABLE(copymovable)

 public:

+ bool copymoveconstructed_;
+ bool moved_;
+
 copymovable(int, int, int)
 : copymoveconstructed_(false), moved_(false)
 {}
@@ -316,6 +329,22 @@
 //construct
 {
 copymovable c;
+ c.copymoveconstructed_ = true;
+ c.copymoveconstructed_ = true;
+ CAllocTraits::construct(c_alloc, &c);
+ if(!c_alloc.construct_called() || c.copymoveconstructed() || c.moved()){
+ return 1;
+ }
+ }
+ {
+ int i = 5;
+ CAllocTraits::construct(c_alloc, &i, boost::container::default_init);
+ if(!c_alloc.construct_called() || i != 5){
+ return 1;
+ }
+ }
+ {
+ copymovable c;
 copymovable c2;
 CAllocTraits::construct(c_alloc, &c, c2);
 if(!c_alloc.construct_called() || !c.copymoveconstructed() || c.moved()){
@@ -332,6 +361,22 @@
 }
 {
 copymovable c;
+ c.copymoveconstructed_ = true;
+ c.copymoveconstructed_ = true;
+ SAllocTraits::construct(s_alloc, &c);
+ if(c.copymoveconstructed() || c.moved()){
+ return 1;
+ }
+ }
+ {
+ int i = 4;
+ SAllocTraits::construct(s_alloc, &i, boost::container::default_init);
+ if(i != 4){
+ return 1;
+ }
+ }
+ {
+ copymovable c;
 copymovable c2;
 SAllocTraits::construct(s_alloc, &c, c2);
 if(!c.copymoveconstructed() || c.moved()){

Modified: trunk/libs/container/test/deque_test.cpp
==============================================================================
--- trunk/libs/container/test/deque_test.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/deque_test.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -332,6 +332,10 @@
 return 1;
 if(test::vector_test<MyCopyDeque>())
 return 1;
+ if(!test::default_init_test< deque<int, test::default_init_allocator<int> > >()){
+ std::cerr << "Default init test failed" << std::endl;
+ return 1;
+ }
 }

 const test::EmplaceOptions Options = (test::EmplaceOptions)(test::EMPLACE_BACK | test::EMPLACE_FRONT | test::EMPLACE_BEFORE);

Modified: trunk/libs/container/test/stable_vector_test.cpp
==============================================================================
--- trunk/libs/container/test/stable_vector_test.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/stable_vector_test.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -66,6 +66,36 @@
 }
}

+bool default_init_test()//Test for default initialization
+{
+ typedef stable_vector<int, test::default_init_allocator<int> > svector_t;
+
+ const std::size_t Capacity = 100;
+
+ {
+ test::default_init_allocator<int>::reset_pattern(0);
+ svector_t v(Capacity, default_init);
+ svector_t::iterator it = v.begin();
+ //Compare with the pattern
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(*it != static_cast<int>(i))
+ return false;
+ }
+ }
+ {
+ test::default_init_allocator<int>::reset_pattern(100);
+ svector_t v;
+ v.resize(Capacity, default_init);
+ svector_t::iterator it = v.begin();
+ //Compare with the pattern
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(*it != static_cast<int>(i+100))
+ return false;
+ }
+ }
+ return true;
+}
+
int main()
{
 recursive_vector_test();
@@ -102,6 +132,11 @@
 if(test::vector_test<MyCopyVector>())
 return 1;

+ if(!test::default_init_test< stable_vector<int, test::default_init_allocator<int> > >()){
+ std::cerr << "Default init test failed" << std::endl;
+ return 1;
+ }
+
 const test::EmplaceOptions Options = (test::EmplaceOptions)(test::EMPLACE_BACK | test::EMPLACE_BEFORE);
 if(!boost::container::test::test_emplace
 < stable_vector<test::EmplaceInt>, Options>())

Modified: trunk/libs/container/test/static_vector_test.cpp
==============================================================================
--- trunk/libs/container/test/static_vector_test.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/static_vector_test.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -611,6 +611,53 @@
 v.emplace_back(N/2, t);
}

+bool default_init_test()//Test for default initialization
+{
+ typedef static_vector<int, 100> di_vector_t;
+
+ const std::size_t Capacity = 100;
+
+ {
+ di_vector_t v;
+ int *p = v.data();
+
+ for(std::size_t i = 0; i != Capacity; ++i, ++p){
+ *p = static_cast<int>(i);
+ }
+
+ //Destroy the vector, p stilll pointing to the storage
+ v.~di_vector_t();
+
+ di_vector_t &rv = *::new(&v)di_vector_t(Capacity, default_init);
+ di_vector_t::iterator it = rv.begin();
+
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(*it != static_cast<int>(i))
+ return false;
+ }
+
+ v.~di_vector_t();
+ }
+ {
+ di_vector_t v;
+
+ int *p = v.data();
+ for(std::size_t i = 0; i != Capacity; ++i, ++p){
+ *p = static_cast<int>(i+100);
+ }
+
+ v.resize(Capacity, default_init);
+
+ di_vector_t::iterator it = v.begin();
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(*it != static_cast<int>(i+100))
+ return false;
+ }
+ }
+
+ return true;
+}
+
int main(int, char* [])
{
 using boost::container::test::movable_and_copyable_int;
@@ -727,6 +774,9 @@
 BOOST_TEST(counting_value::count() == 0);
 test_sv_elem<shptr_value, 10>(shptr_value(50));
 test_sv_elem<movable_and_copyable_int, 10>(movable_and_copyable_int(50));
+
+ BOOST_TEST(default_init_test() == true);
+
 return boost::report_errors();
}

Modified: trunk/libs/container/test/vector_test.cpp
==============================================================================
--- trunk/libs/container/test/vector_test.cpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/vector_test.cpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -151,6 +151,10 @@
 return 1;
 if(test_expand_bwd())
 return 1;
+ if(!test::default_init_test< vector<int, test::default_init_allocator<int> > >()){
+ std::cerr << "Default init test failed" << std::endl;
+ return 1;
+ }

 MyEnumVector v;
 Test t;

Modified: trunk/libs/container/test/vector_test.hpp
==============================================================================
--- trunk/libs/container/test/vector_test.hpp Thu Sep 26 13:03:11 2013 (r85963)
+++ trunk/libs/container/test/vector_test.hpp 2013-09-26 14:05:25 EDT (Thu, 26 Sep 2013) (r85964)
@@ -31,12 +31,130 @@
#include <boost/move/utility.hpp>
#include <boost/move/iterator.hpp>
#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/static_assert.hpp>
#include "insert_test.hpp"

namespace boost{
namespace container {
namespace test{

+//
+template<int Dummy = 0>
+class default_init_allocator_base
+{
+ protected:
+ static unsigned char s_pattern;
+ static bool s_ascending;
+
+ public:
+ static void reset_pattern(unsigned char value)
+ { s_pattern = value; }
+
+ static void set_ascending(bool enable)
+ { s_ascending = enable; }
+};
+
+template<int Dummy>
+unsigned char default_init_allocator_base<Dummy>::s_pattern = 0u;
+
+template<int Dummy>
+bool default_init_allocator_base<Dummy>::s_ascending = true;
+
+template<class T>
+class default_init_allocator
+ : public default_init_allocator_base<0>
+{
+ typedef default_init_allocator_base<0> base_t;
+ public:
+ typedef T value_type;
+
+ default_init_allocator()
+ {}
+
+ template <class U>
+ default_init_allocator(default_init_allocator)
+ {}
+
+ T* allocate(std::size_t n)
+ {
+ //Initialize memory to a pattern
+ T *const p = ::new T[n];
+ unsigned char *puc_raw = reinterpret_cast<unsigned char*>(p);
+ std::size_t max = sizeof(T)*n;
+ if(base_t::s_ascending){
+ for(std::size_t i = 0; i != max; ++i){
+ puc_raw[i] = static_cast<unsigned char>(s_pattern++);
+ }
+ }
+ else{
+ for(std::size_t i = 0; i != max; ++i){
+ puc_raw[i] = static_cast<unsigned char>(s_pattern--);
+ }
+ }
+ return p;
+ }
+
+ void deallocate(T *p, std::size_t)
+ { delete[] p; }
+};
+
+template<class T>
+inline bool check_ascending_byte_pattern(const T&t)
+{
+ const unsigned char *pch = &reinterpret_cast<const unsigned char &>(t);
+ const std::size_t max = sizeof(T);
+ for(std::size_t i = 1; i != max; ++i){
+ if( (pch[i-1] != ((unsigned char)(pch[i]-1u))) ){
+ return false;
+ }
+ }
+ return true;
+}
+
+template<class T>
+inline bool check_descending_byte_pattern(const T&t)
+{
+ const unsigned char *pch = &reinterpret_cast<const unsigned char &>(t);
+ const std::size_t max = sizeof(T);
+ for(std::size_t i = 1; i != max; ++i){
+ if( (pch[i-1] != ((unsigned char)(pch[i]+1u))) ){
+ return false;
+ }
+ }
+ return true;
+}
+
+template<class IntDefaultInitAllocVector>
+bool default_init_test()//Test for default initialization
+{
+ const std::size_t Capacity = 100;
+
+ {
+ test::default_init_allocator<int>::reset_pattern(0);
+ test::default_init_allocator<int>::set_ascending(true);
+ IntDefaultInitAllocVector v(Capacity, default_init);
+ typename IntDefaultInitAllocVector::iterator it = v.begin();
+ //Compare with the pattern
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(!test::check_ascending_byte_pattern(*it))
+ return false;
+ }
+ }
+ {
+ test::default_init_allocator<int>::reset_pattern(100);
+ test::default_init_allocator<int>::set_ascending(false);
+ IntDefaultInitAllocVector v;
+ v.resize(Capacity, default_init);
+ typename IntDefaultInitAllocVector::iterator it = v.begin();
+ //Compare with the pattern
+ for(std::size_t i = 0; i != Capacity; ++i, ++it){
+ if(!test::check_descending_byte_pattern(*it))
+ return false;
+ }
+ }
+ return true;
+}
+
template<class V1, class V2>
bool vector_copyable_only(V1 *, V2 *, boost::container::container_detail::false_type)
{
@@ -100,7 +218,7 @@
int vector_test()
{
 typedef std::vector<int> MyStdVector;
- typedef typename MyBoostVector::value_type IntType;
+ typedef typename MyBoostVector::value_type IntType;
 const int max = 100;

 if(!test_range_insertion<MyBoostVector>()){

Next message: andrey.semashev_at_[hidden]: "[Boost-commit] svn:boost r85965 - in trunk/libs/log: doc src"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r85963 - trunk/libs/math/test"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk