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
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 @@
{}
//! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
//!
//! <b>Throws</b>: 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...
+ }
+
+ //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
+ //! throws or T's default or copy constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to n.
+ //!
+ //! <b>Note</b>: Non-standard extension
+ deque(size_type n, default_init_t)
+ : Base(n, allocator_type())
+ {
+ 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()); }
//! <b>Effects</b>: 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.
//!
- //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
+ //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
//!
//! <b>Complexity</b>: 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);
+ }
+ }
+
+ //! <b>Effects</b>: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are default initialized.
+ //!
+ //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to the difference between size() and new_size.
+ //!
+ //! <b>Note</b>: 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
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! <b>Effects</b>:
+//! \code
+//! for (; n--; ++r, ++f)
+//! allocator_traits::construct(a, &*r);
+//! \endcode
+//!
+//! <b>Returns</b>: 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.
//!
//! <b>Note</b>: If an element is inserted it might invalidate elements.
+ //!
+ //! <b>Note</b>: 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 @@
//!
//! <b>Complexity</b>: 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()); }
//! <b>Returns</b>: 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.
//!
//! <b>Note</b>: If an element is inserted it might invalidate elements.
+ //!
+ //! <b>Note</b>: 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 @@
//!
//! <b>Complexity</b>: 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()); }
//! <b>Returns</b>: 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(); }
//! <b>Effects</b>: 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.
//!
//! <b>Throws</b>: 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.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: 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 @@
//!
//! <b>Complexity</b>: 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()); }
//! <b>Returns</b>: 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 @@
//! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: 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.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: 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 @@
//!
//! <b>Complexity</b>: 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()); }
//! <b>Returns</b>: 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 @@
//! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
//!
//! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: 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(); }
//! <b>Effects</b>: 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.
//!
//! <b>Throws</b>: 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 @@
}
//! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
//!
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor
//! throws or T's default or copy constructor throws.
@@ -584,6 +584,24 @@
}
//! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
+ //! throws or T's default or copy constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to n.
+ //!
+ //! <b>Note</b>: 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();
+ }
+
+ //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
//! and inserts n copies of value.
//!
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor
@@ -960,17 +978,35 @@
{ return this->index.max_size() - ExtraPointers; }
//! <b>Effects</b>: 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.
//!
- //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
+ //! <b>Throws</b>: If memory allocation throws, or T's default constructor throws.
//!
//! <b>Complexity</b>: 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());
+ }
+
+ //! <b>Effects</b>: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are default initialized.
+ //!
+ //! <b>Throws</b>: If memory allocation throws, or T's default constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to the difference between size() and new_size.
+ //!
+ //! <b>Note</b>: 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 @@
}
//! <b>Effects</b>: 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.
//!
//! <b>Throws</b>: 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 @@
{}
//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
- //! and inserts n default contructed values.
+ //! and inserts n value initialized values.
//!
//! <b>Throws</b>: 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()));
+ }
+
+ //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
+ //! and inserts n default initialized values.
+ //!
+ //! <b>Throws</b>: If allocator_type's default constructor or allocation
+ //! throws or T's default constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to n.
+ //!
+ //! <b>Note</b>: 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()));
}
//! <b>Effects</b>: Constructs a vector
@@ -1030,9 +1059,9 @@
{ return allocator_traits_type::max_size(this->m_holder.alloc()); }
//! <b>Effects</b>: 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.
//!
- //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
+ //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
//!
//! <b>Complexity</b>: 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());
+ }
+ }
+
+ //! <b>Effects</b>: Inserts or erases elements at the end such that
+ //! the size becomes n. New elements are value initialized.
+ //!
+ //! <b>Throws</b>: If memory allocation throws, or T's constructor throws.
+ //!
+ //! <b>Complexity</b>: Linear to the difference between size() and new_size.
+ //!
+ //! <b>Note</b>: 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<U>)
+ : 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<U>)
+ {}
+
+ 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>()){