summaryrefslogtreecommitdiff
path: root/boost/container/vector.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/vector.hpp')
-rw-r--r--boost/container/vector.hpp284
1 files changed, 167 insertions, 117 deletions
diff --git a/boost/container/vector.hpp b/boost/container/vector.hpp
index 1cf44c8e27..e3bc1068aa 100644
--- a/boost/container/vector.hpp
+++ b/boost/container/vector.hpp
@@ -1,6 +1,6 @@
//////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2005-2014. Distributed under the Boost
+// (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
@@ -216,7 +216,7 @@ struct vector_merge_cursor
typedef SizeType size_type;
typedef typename iterator_traits<BiDirValueIt>::reference reference;
- vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp cmp)
+ vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp &cmp)
: m_pbeg(pbeg), m_pcur(--plast), m_valueit(valueit), m_cmp(cmp)
{}
@@ -241,7 +241,7 @@ struct vector_merge_cursor
T *const m_pbeg;
T *m_pcur;
BiDirValueIt m_valueit;
- Comp m_cmp;
+ Comp &m_cmp;
};
} //namespace container_detail {
@@ -346,18 +346,17 @@ struct vector_alloc_holder
static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator)
{
(void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc;
- return (!allocator_traits_type::is_partially_propagable::value ||
- !allocator_traits_type::storage_is_unpropagable(from_alloc, p)) &&
- (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc));
+ const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
+ !allocator_traits_type::storage_is_unpropagable(from_alloc, p);
+ return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc));
}
static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator)
{
(void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a;
- return (!allocator_traits_type::is_partially_propagable::value ||
- (!allocator_traits_type::storage_is_unpropagable(r_a, r_p) &&
- !allocator_traits_type::storage_is_unpropagable(l_a, l_p))
- ) && (propagate_allocator || allocator_traits_type::equal(l_a, r_a));
+ const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
+ !(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p));
+ return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a));
}
//Constructor, does not throw
@@ -646,7 +645,7 @@ struct vector_alloc_holder<Allocator, version_0>
this->priv_deep_swap(x);
}
- void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW
+ void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW
{ //Containers with version 0 allocators can't be moved without moving elements one by one
throw_bad_alloc();
}
@@ -819,7 +818,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_value_init_alloc_n
- (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
@@ -838,7 +837,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_default_init_alloc_n
- (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
@@ -855,7 +854,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_value_init_alloc_n
- (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
@@ -874,7 +873,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_default_init_alloc_n
- (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector
@@ -891,7 +890,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_fill_alloc_n
- (this->m_holder.alloc(), value, n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), value, n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
@@ -908,7 +907,7 @@ class vector
this->num_alloc += n != 0;
#endif
boost::container::uninitialized_fill_alloc_n
- (this->m_holder.alloc(), value, n, container_detail::to_raw_pointer(this->m_holder.start()));
+ (this->m_holder.alloc(), value, n, this->priv_raw_begin());
}
//! <b>Effects</b>: Constructs a vector
@@ -952,8 +951,8 @@ class vector
this->num_alloc += x.size() != 0;
#endif
::boost::container::uninitialized_copy_alloc_n
- ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start())
- , x.size(), container_detail::to_raw_pointer(this->m_holder.start()));
+ ( this->m_holder.alloc(), x.priv_raw_begin()
+ , x.size(), this->priv_raw_begin());
}
//! <b>Effects</b>: Move constructor. Moves x's resources to *this.
@@ -1013,8 +1012,8 @@ class vector
this->num_alloc += x.size() != 0;
#endif
::boost::container::uninitialized_copy_alloc_n_source
- ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start())
- , x.size(), container_detail::to_raw_pointer(this->m_holder.start()));
+ ( this->m_holder.alloc(), x.priv_raw_begin()
+ , x.size(), this->priv_raw_begin());
}
//! <b>Effects</b>: Move constructor using the specified allocator.
@@ -1038,8 +1037,8 @@ class vector
this->num_alloc += n != 0;
#endif
::boost::container::uninitialized_move_alloc_n_source
- ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start())
- , n, container_detail::to_raw_pointer(this->m_holder.start()));
+ ( this->m_holder.alloc(), x.priv_raw_begin()
+ , n, this->priv_raw_begin());
}
}
@@ -1052,7 +1051,7 @@ class vector
~vector() BOOST_NOEXCEPT_OR_NOTHROW
{
boost::container::destroy_alloc_n
- (this->get_stored_allocator(), container_detail::to_raw_pointer(this->m_holder.start()), this->m_holder.m_size);
+ (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
//vector_alloc_holder deallocates the data
}
@@ -1098,6 +1097,7 @@ class vector
BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
|| allocator_traits_type::is_always_equal::value)
{
+ BOOST_ASSERT(&x != this);
this->priv_move_assign(boost::move(x));
return *this;
}
@@ -1177,7 +1177,7 @@ class vector
if (first == last){
//There are no more elements in the sequence, erase remaining
- T* const end_pos = this->back_raw();
+ T* const end_pos = this->priv_raw_end();
const size_type n = static_cast<size_type>(end_pos - container_detail::iterator_to_raw_pointer(cur));
this->priv_destroy_last_n(n);
}
@@ -1513,7 +1513,10 @@ class vector
//!
//! <b>Complexity</b>: Constant.
reference front() BOOST_NOEXCEPT_OR_NOTHROW
- { return *this->m_holder.start(); }
+ {
+ BOOST_ASSERT(!this->empty());
+ return *this->m_holder.start();
+ }
//! <b>Requires</b>: !empty()
//!
@@ -1524,7 +1527,10 @@ class vector
//!
//! <b>Complexity</b>: Constant.
const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
- { return *this->m_holder.start(); }
+ {
+ BOOST_ASSERT(!this->empty());
+ return *this->m_holder.start();
+ }
//! <b>Requires</b>: !empty()
//!
@@ -1536,7 +1542,7 @@ class vector
//! <b>Complexity</b>: Constant.
reference back() BOOST_NOEXCEPT_OR_NOTHROW
{
- BOOST_ASSERT(this->m_holder.m_size > 0);
+ BOOST_ASSERT(!this->empty());
return this->m_holder.start()[this->m_holder.m_size - 1];
}
@@ -1550,7 +1556,7 @@ class vector
//! <b>Complexity</b>: Constant.
const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
{
- BOOST_ASSERT(this->m_holder.m_size > 0);
+ BOOST_ASSERT(!this->empty());
return this->m_holder.start()[this->m_holder.m_size - 1];
}
@@ -1578,7 +1584,8 @@ class vector
//! <b>Complexity</b>: Constant.
const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
{
- return this->m_holder.start()[n];
+ BOOST_ASSERT(this->m_holder.m_size > n);
+ return this->m_holder.start()[n];
}
//! <b>Requires</b>: size() >= n.
@@ -1627,7 +1634,10 @@ class vector
//!
//! <b>Note</b>: Non-standard extension
size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
- { return this->priv_index_of(vector_iterator_get_ptr(p)); }
+ {
+ //Range check assert done in priv_index_of
+ return this->priv_index_of(vector_iterator_get_ptr(p));
+ }
//! <b>Requires</b>: begin() <= p <= end().
//!
@@ -1640,7 +1650,10 @@ class vector
//!
//! <b>Note</b>: Non-standard extension
size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
- { return this->priv_index_of(vector_iterator_get_ptr(p)); }
+ {
+ //Range check assert done in priv_index_of
+ return this->priv_index_of(vector_iterator_get_ptr(p));
+ }
//! <b>Requires</b>: size() > n.
//!
@@ -1651,7 +1664,10 @@ class vector
//!
//! <b>Complexity</b>: Constant.
reference at(size_type n)
- { this->priv_check_range(n); return this->m_holder.start()[n]; }
+ {
+ this->priv_throw_if_out_of_range(n);
+ return this->m_holder.start()[n];
+ }
//! <b>Requires</b>: size() > n.
//!
@@ -1662,7 +1678,10 @@ class vector
//!
//! <b>Complexity</b>: Constant.
const_reference at(size_type n) const
- { this->priv_check_range(n); return this->m_holder.start()[n]; }
+ {
+ this->priv_throw_if_out_of_range(n);
+ return this->m_holder.start()[n];
+ }
//////////////////////////////////////////////
//
@@ -1677,7 +1696,7 @@ class vector
//!
//! <b>Complexity</b>: Constant.
T* data() BOOST_NOEXCEPT_OR_NOTHROW
- { return container_detail::to_raw_pointer(this->m_holder.start()); }
+ { return this->priv_raw_begin(); }
//! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range.
//! For a non-empty vector, data() == &front().
@@ -1686,7 +1705,7 @@ class vector
//!
//! <b>Complexity</b>: Constant.
const T * data() const BOOST_NOEXCEPT_OR_NOTHROW
- { return container_detail::to_raw_pointer(this->m_holder.start()); }
+ { return this->priv_raw_begin(); }
//////////////////////////////////////////////
//
@@ -1707,7 +1726,7 @@ class vector
{
if (BOOST_LIKELY(this->room_enough())){
//There is more memory, just construct a new object at the end
- allocator_traits_type::construct(this->m_holder.alloc(), this->back_raw(), ::boost::forward<Args>(args)...);
+ allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...);
++this->m_holder.m_size;
}
else{
@@ -1731,7 +1750,7 @@ class vector
const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));
if (BOOST_LIKELY(is_room_enough)){
//There is more memory, just construct a new object at the end
- allocator_traits_type::construct(this->m_holder.alloc(), this->back_raw(), ::boost::forward<Args>(args)...);
+ allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...);
++this->m_holder.m_size;
}
return is_room_enough;
@@ -1750,6 +1769,7 @@ class vector
template<class ...Args>
iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(position));
//Just call more general insert(pos, size, value) and return iterator
typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type;
return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1
@@ -1764,7 +1784,7 @@ class vector
{\
if (BOOST_LIKELY(this->room_enough())){\
allocator_traits_type::construct (this->m_holder.alloc()\
- , this->back_raw() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
+ , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
++this->m_holder.m_size;\
}\
else{\
@@ -1780,7 +1800,7 @@ class vector
const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\
if (BOOST_LIKELY(is_room_enough)){\
allocator_traits_type::construct (this->m_holder.alloc()\
- , this->back_raw() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
+ , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
++this->m_holder.m_size;\
}\
return is_room_enough;\
@@ -1789,6 +1809,7 @@ class vector
BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
{\
+ BOOST_ASSERT(this->priv_in_range_or_end(pos));\
typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\
}\
@@ -1854,6 +1875,7 @@ class vector
//! <b>Complexity</b>: Linear to n.
iterator insert(const_iterator p, size_type n, const T& x)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(p));
container_detail::insert_n_copies_proxy<Allocator, T*> proxy(x);
return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy);
}
@@ -1879,6 +1901,7 @@ class vector
#endif
)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(pos));
const size_type n_pos = pos - this->cbegin();
iterator it(vector_iterator_get_ptr(pos));
for(;first != last; ++first){
@@ -1898,6 +1921,7 @@ class vector
>::type * = 0
)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(pos));
container_detail::insert_range_proxy<Allocator, FwdIt, T*> proxy(first);
return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), boost::container::iterator_distance(first, last), proxy);
}
@@ -1922,6 +1946,7 @@ class vector
template <class InIt>
iterator insert(const_iterator pos, size_type num, InIt first, InIt last)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(pos));
BOOST_ASSERT(container_detail::is_input_iterator<InIt>::value ||
num == static_cast<size_type>(boost::container::iterator_distance(first, last)));
(void)last;
@@ -1940,17 +1965,19 @@ class vector
//! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
iterator insert(const_iterator position, std::initializer_list<value_type> il)
{
+ //Assertion done in insert()
return this->insert(position, il.begin(), il.end());
}
#endif
- //! <b>Effects</b>: Removes the last element from the vector.
+ //! <b>Effects</b>: Removes the last element from the container.
//!
//! <b>Throws</b>: Nothing.
//!
//! <b>Complexity</b>: Constant time.
void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
{
+ BOOST_ASSERT(!this->empty());
//Destroy last element
this->priv_destroy_last();
}
@@ -1963,9 +1990,10 @@ class vector
//! last element. Constant if pos is the last element.
iterator erase(const_iterator position)
{
+ BOOST_ASSERT(this->priv_in_range(position));
const pointer p = vector_iterator_get_ptr(position);
T *const pos_ptr = container_detail::to_raw_pointer(p);
- T *const beg_ptr = container_detail::to_raw_pointer(this->m_holder.start());
+ T *const beg_ptr = this->priv_raw_begin();
T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr);
//Move elements forward and destroy last
this->priv_destroy_last(pos_ptr == new_end_ptr);
@@ -1980,8 +2008,10 @@ class vector
//! plus linear to the elements between pos and the last element.
iterator erase(const_iterator first, const_iterator last)
{
+ BOOST_ASSERT(first == last ||
+ (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
if (first != last){
- T* const old_end_ptr = this->back_raw();
+ T* const old_end_ptr = this->priv_raw_end();
T* const first_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(first));
T* const last_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(last));
T* const ptr = container_detail::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr));
@@ -2128,7 +2158,7 @@ class vector
{
const size_type old_size_pos = this->size();
this->reserve(old_size_pos + element_count);
- T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start());
+ T* const begin_ptr = this->priv_raw_begin();
size_type insertions_left = element_count;
size_type prev_pos = old_size_pos;
size_type old_hole_size = element_count;
@@ -2184,48 +2214,55 @@ class vector
void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp)
{
size_type const n = static_cast<size_type>(boost::container::iterator_distance(first, last));
- if(BOOST_LIKELY(n)){
- size_type const s = this->size();
- if(BOOST_LIKELY(s)){
- size_type const c = this->capacity();
- size_type const free_c = (c - s);
- //Use a new buffer if current one is too small for new elements,
- //or there is no room for position indexes
- bool new_buffer = false;
- if(free_c < n){
- new_buffer = true;
- }
- else if(!UniqueBool::value && free_c >= n){
- typedef container_detail::vector_merge_cursor<T, size_type, BidirIt, Compare> inserter_t;
- T* const pbeg = container_detail::to_raw_pointer(m_holder.start());
- return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp));
- }
- else if(UniqueBool::value){ //Query for room to store n + 1 indexes (+1 to guarantee potential alignment overhead).
- //No need to destroy them as they are integral types, which simplifies things a lot.
- std::size_t const sz_vlt = sizeof(value_type);
- std::size_t const sz_szt = sizeof(size_type);
- new_buffer = (c-s-n)*sz_vlt/sz_szt < (n+1);
- }
-
- if(new_buffer){
- size_type const new_size = s + n;
- size_type new_cap = new_size;
- pointer p = pointer();
- p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p);
- this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap);
- }
- else{
- //Use trailing memory to store position offsets
+ size_type const s = this->size();
+ if(BOOST_LIKELY(s)){
+ size_type const c = this->capacity();
+ size_type const free_c = (c - s);
+ //Use a new buffer if current one is too small for new elements,
+ //or there is no room for position indexes
+ if(free_c < n){
+ size_type const new_size = s + n;
+ size_type new_cap = new_size;
+ pointer p = pointer();
+ p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p);
+ this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap);
+ }
+ else if(!UniqueBool::value && free_c >= n){
+ typedef container_detail::vector_merge_cursor<T, size_type, BidirIt, Compare> inserter_t;
+ T* const pbeg = this->priv_raw_begin();
+ return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp));
+ }
+ else{ //UniqueBool::value == true and free_c >= n
+ std::size_t remaining = n;
+ static const std::size_t PosCount = 64u;
+ size_type positions[PosCount];
+ size_type *indexes = 0;
+ while(remaining){
+ //Query for room to store indexes in the remaining buffer
uintptr_t const szt_align_mask = container_detail::alignment_of<size_type>::value - 1;
- boost::uintptr_t const addr = boost::uintptr_t(container_detail::to_raw_pointer(m_holder.start()) + s + n);
- //Align memory before casting to address
- size_type *const paddr = reinterpret_cast<size_type *>((addr + szt_align_mask) & ~szt_align_mask);
- this->priv_insert_ordered_range(UniqueBool(), n, first, last, paddr, comp);
+ boost::uintptr_t const addr = boost::uintptr_t(this->priv_raw_begin() + s + n);
+ boost::uintptr_t const capaddr = boost::uintptr_t(this->priv_raw_begin() + c);
+ boost::uintptr_t const aligned_addr = (addr + szt_align_mask) & ~szt_align_mask;
+ indexes = reinterpret_cast<size_type *>(aligned_addr);
+ std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - addr)/sizeof(size_type);
+
+ //Capacity is constant, we're not going to change it
+ if(index_capacity < PosCount){
+ indexes = positions;
+ index_capacity = PosCount;
+ }
+ if(index_capacity > remaining)
+ index_capacity = remaining;
+ BidirIt limit = first;
+ boost::container::iterator_advance(limit, index_capacity);
+ this->priv_insert_ordered_range(UniqueBool(), index_capacity, first, limit, indexes, comp);
+ first = limit;
+ remaining -= index_capacity;
}
}
- else{
- this->insert(this->cend(), n, first, last);
- }
+ }
+ else{
+ this->insert(this->cend(), n, first, last);
}
}
@@ -2245,7 +2282,7 @@ class vector
//bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN);
size_type const s = this->size();
size_type remaining = n;
- T* const pbeg = container_detail::to_raw_pointer(m_holder.start());
+ T* const pbeg = this->priv_raw_begin();
T* const pend = pbeg + s;
T* pcur = pbeg;
size_type *position = positions;
@@ -2284,7 +2321,7 @@ class vector
allocator_type &a = this->m_holder.alloc();
typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap);
typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u);
- T* pbeg = container_detail::to_raw_pointer(m_holder.start());
+ T* pbeg = this->priv_raw_begin();
size_type const old_size = this->size();
T* const pend = pbeg + old_size;
T* d_first = container_detail::to_raw_pointer(new_storage);
@@ -2338,9 +2375,6 @@ class vector
pointer back_ptr() const
{ return this->m_holder.start() + this->m_holder.m_size; }
- T* back_raw() const
- { return container_detail::to_raw_pointer(this->m_holder.start()) + this->m_holder.m_size; }
-
size_type priv_index_of(pointer p) const
{
BOOST_ASSERT(this->m_holder.start() <= p);
@@ -2357,8 +2391,8 @@ class vector
this->capacity() < x.size()){
throw_bad_alloc();
}
- T* const this_start = container_detail::to_raw_pointer(m_holder.start());
- T* const other_start = container_detail::to_raw_pointer(x.m_holder.start());
+ T* const this_start = this->priv_raw_begin();
+ T* const other_start = x.priv_raw_begin();
const size_type this_sz = m_holder.m_size;
const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
@@ -2373,7 +2407,7 @@ class vector
, container_detail::is_different<OtherAllocator, allocator_type>
>::type * = 0)
{
- //for move constructor, no aliasing (&x != this) is assummed.
+ //for move assignment, no aliasing (&x != this) is assummed.
BOOST_ASSERT(this != &x);
allocator_type &this_alloc = this->m_holder.alloc();
allocator_type &x_alloc = x.m_holder.alloc();
@@ -2414,8 +2448,8 @@ class vector
this->capacity() < x.size()){
throw_bad_alloc();
}
- T* const this_start = container_detail::to_raw_pointer(m_holder.start());
- T* const other_start = container_detail::to_raw_pointer(x.m_holder.start());
+ T* const this_start = this->priv_raw_begin();
+ T* const other_start = x.priv_raw_begin();
const size_type this_sz = m_holder.m_size;
const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
@@ -2439,8 +2473,7 @@ class vector
this->shrink_to_fit();
}
container_detail::assign_alloc(this_alloc, x_alloc, flag);
- this->assign( container_detail::to_raw_pointer(x.m_holder.start())
- , container_detail::to_raw_pointer(x.m_holder.start() + x.m_holder.m_size));
+ this->assign( x.priv_raw_begin(), x.priv_raw_end() );
}
template<class Vector> //Template it to avoid it in explicit instantiations
@@ -2452,7 +2485,7 @@ class vector
{
const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start()
- , x.get_stored_allocator(), this->m_holder.start(), propagate_alloc)){
+ , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){
//Just swap internals
this->m_holder.swap_resources(x.m_holder);
}
@@ -2471,6 +2504,8 @@ class vector
, boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.nth(common_elements)))
, boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.end()))
);
+ //Destroy remaining elements
+ big.erase(big.nth(common_elements), big.cend());
}
//And now swap the allocator
container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_<propagate_alloc>());
@@ -2492,7 +2527,7 @@ class vector
pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start);
//We will reuse insert code, so create a dummy input iterator
this->priv_forward_range_insert_new_allocation
- ( container_detail::to_raw_pointer(p), new_cap, this->back_raw(), 0, this->priv_dummy_empty_proxy());
+ ( container_detail::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy());
}
void priv_reserve_no_capacity(size_type new_cap, version_2)
@@ -2514,7 +2549,7 @@ class vector
}
else{ //If there is no forward expansion, move objects, we will reuse insertion code
T * const new_mem = container_detail::to_raw_pointer(ret);
- T * const ins_pos = this->back_raw();
+ T * const ins_pos = this->priv_raw_end();
if(reuse){ //Backwards (and possibly forward) expansion
#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
++this->num_expand_bwd;
@@ -2536,7 +2571,7 @@ class vector
{
(void)moved;
if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){
- value_type* const p = this->back_raw() - 1;
+ value_type* const p = this->priv_raw_end() - 1;
allocator_traits_type::destroy(this->get_stored_allocator(), p);
}
--this->m_holder.m_size;
@@ -2546,7 +2581,7 @@ class vector
{
BOOST_ASSERT(n <= this->m_holder.m_size);
if(!value_traits::trivial_dctr){
- T* const destroy_pos = container_detail::to_raw_pointer(this->m_holder.start()) + (this->m_holder.m_size-n);
+ T* const destroy_pos = this->priv_raw_begin() + (this->m_holder.m_size-n);
boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n);
}
this->m_holder.m_size -= n;
@@ -2555,7 +2590,7 @@ class vector
template<class InpIt>
void priv_uninitialized_construct_at_end(InpIt first, InpIt last)
{
- T* const old_end_pos = this->back_raw();
+ T* const old_end_pos = this->priv_raw_end();
T* const new_end_pos = boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos);
this->m_holder.m_size += new_end_pos - old_end_pos;
}
@@ -2563,13 +2598,14 @@ class vector
void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW
{
boost::container::destroy_alloc_n
- (this->get_stored_allocator(), container_detail::to_raw_pointer(this->m_holder.start()), this->m_holder.m_size);
+ (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
this->m_holder.m_size = 0;
}
template<class U>
iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) x)
{
+ BOOST_ASSERT(this->priv_in_range_or_end(p));
return this->priv_forward_range_insert
( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy<T*, Allocator>(::boost::forward<U>(x)));
}
@@ -2586,9 +2622,7 @@ class vector
if (BOOST_LIKELY(this->room_enough())){
//There is more memory, just construct a new object at the end
allocator_traits_type::construct
- ( this->m_holder.alloc()
- , container_detail::to_raw_pointer(this->m_holder.start() + this->m_holder.m_size)
- , ::boost::forward<U>(u) );
+ ( this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<U>(u) );
++this->m_holder.m_size;
}
else{
@@ -2645,8 +2679,7 @@ class vector
#endif
this->priv_forward_range_insert_new_allocation
( container_detail::to_raw_pointer(p), sz
- , container_detail::to_raw_pointer(this->m_holder.start())
- , 0, this->priv_dummy_empty_proxy());
+ , this->priv_raw_begin(), 0, this->priv_dummy_empty_proxy());
}
}
}
@@ -2693,7 +2726,8 @@ class vector
const size_type new_cap = this->m_holder.next_capacity(n);
//Pass the hint so that allocators can take advantage of this.
- T * const new_buf = container_detail::to_raw_pointer(allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start));
+ T * const new_buf = container_detail::to_raw_pointer
+ (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start));
#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
++this->num_alloc;
#endif
@@ -2708,7 +2742,7 @@ class vector
{
//Check if we have enough memory or try to expand current memory
T *const raw_pos = container_detail::to_raw_pointer(pos);
- const size_type n_pos = raw_pos - container_detail::to_raw_pointer(this->m_holder.start());
+ const size_type n_pos = raw_pos - this->priv_raw_begin();
//There is not enough memory, allocate a new
//buffer or expand the old one.
@@ -2764,7 +2798,7 @@ class vector
else{
//Expand forward
T *const raw_pos = container_detail::to_raw_pointer(pos);
- const size_type n_pos = raw_pos - container_detail::to_raw_pointer(this->m_holder.start());
+ const size_type n_pos = raw_pos - this->priv_raw_begin();
this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy);
return iterator(this->m_holder.start() + n_pos);
}
@@ -2849,7 +2883,7 @@ class vector
BOOST_ASSERT(first_pos <= last_pos);
BOOST_ASSERT(last_pos <= limit_pos);
//
- T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start());
+ T* const begin_ptr = this->priv_raw_begin();
T* const first_ptr = begin_ptr + first_pos;
T* const last_ptr = begin_ptr + last_pos;
@@ -2879,10 +2913,16 @@ class vector
}
private:
+ T *priv_raw_begin() const
+ { return container_detail::to_raw_pointer(m_holder.start()); }
+
+ T* priv_raw_end() const
+ { return this->priv_raw_begin() + this->m_holder.m_size; }
+
template <class InsertionProxy>
void priv_forward_range_insert_at_end_expand_forward(const size_type n, InsertionProxy insert_range_proxy)
{
- T* const old_finish = this->back_raw();
+ T* const old_finish = this->priv_raw_end();
insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
this->m_holder.m_size += n;
}
@@ -2893,7 +2933,7 @@ class vector
//n can't be 0, because there is nothing to do in that case
if(BOOST_UNLIKELY(!n)) return;
//There is enough memory
- T* const old_finish = this->back_raw();
+ T* const old_finish = this->priv_raw_end();
const size_type elems_after = old_finish - pos;
if (!elems_after){
@@ -2944,10 +2984,10 @@ class vector
//Initialize with [begin(), pos) old buffer
//the start of the new buffer
- T * const old_buffer = container_detail::to_raw_pointer(this->m_holder.start());
+ T * const old_buffer = this->priv_raw_begin();
if(old_buffer){
new_finish = ::boost::container::uninitialized_move_alloc
- (this->m_holder.alloc(), container_detail::to_raw_pointer(this->m_holder.start()), pos, old_finish = new_finish);
+ (this->m_holder.alloc(), this->priv_raw_begin(), pos, old_finish = new_finish);
new_values_destroyer.increment_size(new_finish - old_finish);
}
//Initialize new objects, starting from previous point
@@ -2981,7 +3021,7 @@ class vector
{
//n can be zero to just expand capacity
//Backup old data
- T* const old_start = container_detail::to_raw_pointer(this->m_holder.start());
+ T* const old_start = this->priv_raw_begin();
const size_type old_size = this->m_holder.m_size;
T* const old_finish = old_start + old_size;
@@ -3291,7 +3331,7 @@ class vector
}
}
- void priv_check_range(size_type n) const
+ void priv_throw_if_out_of_range(size_type n) const
{
//If n is out of range, throw an out_of_range exception
if (n >= this->size()){
@@ -3299,6 +3339,16 @@ class vector
}
}
+ bool priv_in_range(const_iterator pos) const
+ {
+ return (this->begin() <= pos) && (pos < this->end());
+ }
+
+ bool priv_in_range_or_end(const_iterator pos) const
+ {
+ return (this->begin() <= pos) && (pos <= this->end());
+ }
+
#ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
public:
unsigned int num_expand_fwd;
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-13 11:06:14 +0000