aboutsummaryrefslogtreecommitdiffstats
path: root/include/deque
diff options
context:
space:
mode:
Diffstat (limited to 'include/deque')
-rw-r--r--include/deque195
1 files changed, 141 insertions, 54 deletions
diff --git a/include/deque b/include/deque
index d3ccf2ef6f71..cb7e4e532719 100644
--- a/include/deque
+++ b/include/deque
@@ -934,7 +934,7 @@ public:
typedef _Allocator allocator_type;
typedef allocator_traits<allocator_type> __alloc_traits;
typedef typename __alloc_traits::size_type size_type;
-protected:
+
typedef _Tp value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
@@ -956,6 +956,74 @@ protected:
typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
difference_type> const_iterator;
+ struct __deque_block_range {
+ explicit __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
+ const pointer __begin_;
+ const pointer __end_;
+ };
+
+ struct __deque_range {
+ iterator __pos_;
+ const iterator __end_;
+
+ __deque_range(iterator __pos, iterator __e) _NOEXCEPT
+ : __pos_(__pos), __end_(__e) {}
+
+ explicit operator bool() const _NOEXCEPT {
+ return __pos_ != __end_;
+ }
+
+ __deque_range begin() const {
+ return *this;
+ }
+
+ __deque_range end() const {
+ return __deque_range(__end_, __end_);
+ }
+ __deque_block_range operator*() const _NOEXCEPT {
+ if (__pos_.__m_iter_ == __end_.__m_iter_) {
+ return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
+ }
+ return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);
+ }
+
+ __deque_range& operator++() _NOEXCEPT {
+ if (__pos_.__m_iter_ == __end_.__m_iter_) {
+ __pos_ = __end_;
+ } else {
+ ++__pos_.__m_iter_;
+ __pos_.__ptr_ = *__pos_.__m_iter_;
+ }
+ return *this;
+ }
+
+
+ friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
+ return __lhs.__pos_ == __rhs.__pos_;
+ }
+ friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
+ return !(__lhs == __rhs);
+ }
+ };
+
+
+
+ struct _ConstructTransaction {
+ _ConstructTransaction(__deque_base* __db, __deque_block_range& __r)
+ : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}
+
+
+ ~_ConstructTransaction() {
+ __base_->size() += (__pos_ - __begin_);
+ }
+
+ pointer __pos_;
+ const pointer __end_;
+ private:
+ const pointer __begin_;
+ __deque_base * const __base_;
+ };
+
protected:
__map __map_;
size_type __start_;
@@ -1222,6 +1290,10 @@ public:
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+ using typename __base::__deque_range;
+ using typename __base::__deque_block_range;
+ using typename __base::_ConstructTransaction;
+
// construct/copy/destroy:
_LIBCPP_INLINE_VISIBILITY
deque()
@@ -1399,7 +1471,7 @@ public:
_LIBCPP_INLINE_VISIBILITY
bool __invariants() const {return __base::__invariants();}
-private:
+
typedef typename __base::__map_const_pointer __map_const_pointer;
_LIBCPP_INLINE_VISIBILITY
@@ -1413,15 +1485,53 @@ private:
return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1;
}
_LIBCPP_INLINE_VISIBILITY
+ size_type __block_count() const
+ {
+ return __base::__map_.size();
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
size_type __front_spare() const
{
return __base::__start_;
}
_LIBCPP_INLINE_VISIBILITY
+ size_type __front_spare_blocks() const {
+ return __front_spare() / __base::__block_size;
+ }
+ _LIBCPP_INLINE_VISIBILITY
size_type __back_spare() const
{
return __capacity() - (__base::__start_ + __base::size());
}
+ _LIBCPP_INLINE_VISIBILITY
+ size_type __back_spare_blocks() const {
+ return __back_spare() / __base::__block_size;
+ }
+
+ private:
+ _LIBCPP_INLINE_VISIBILITY
+ bool __maybe_remove_front_spare(bool __keep_one = true) {
+ if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) {
+ __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(),
+ __base::__block_size);
+ __base::__map_.pop_front();
+ __base::__start_ -= __base::__block_size;
+ return true;
+ }
+ return false;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ bool __maybe_remove_back_spare(bool __keep_one = true) {
+ if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) {
+ __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(),
+ __base::__block_size);
+ __base::__map_.pop_back();
+ return true;
+ }
+ return false;
+ }
template <class _InpIter>
void __append(_InpIter __f, _InpIter __l,
@@ -1727,17 +1837,8 @@ deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
}
else
{
- if (__front_spare() >= __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
- __base::__map_.pop_front();
- __base::__start_ -= __base::__block_size;
- }
- if (__back_spare() >= __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
- __base::__map_.pop_back();
- }
+ __maybe_remove_front_spare(/*__keep_one=*/false);
+ __maybe_remove_back_spare(/*__keep_one=*/false);
}
__base::__map_.shrink_to_fit();
}
@@ -2270,8 +2371,12 @@ deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
if (__n > __back_capacity)
__add_back_capacity(__n - __back_capacity);
// __n <= __back_capacity
- for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size())
- __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f);
+ for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+ _ConstructTransaction __tx(this, __br);
+ for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
+ __alloc_traits::construct(__a, std::__to_raw_pointer(__tx.__pos_), *__f);
+ }
+ }
}
template <class _Tp, class _Allocator>
@@ -2283,8 +2388,12 @@ deque<_Tp, _Allocator>::__append(size_type __n)
if (__n > __back_capacity)
__add_back_capacity(__n - __back_capacity);
// __n <= __back_capacity
- for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
- __alloc_traits::construct(__a, _VSTD::addressof(*__i));
+ for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+ _ConstructTransaction __tx(this, __br);
+ for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
+ __alloc_traits::construct(__a, std::__to_raw_pointer(__tx.__pos_));
+ }
+ }
}
template <class _Tp, class _Allocator>
@@ -2296,8 +2405,13 @@ deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
if (__n > __back_capacity)
__add_back_capacity(__n - __back_capacity);
// __n <= __back_capacity
- for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size())
- __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v);
+ for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
+ _ConstructTransaction __tx(this, __br);
+ for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
+ __alloc_traits::construct(__a, std::__to_raw_pointer(__tx.__pos_), __v);
+ }
+ }
+
}
// Create front capacity for one block of elements.
@@ -2596,12 +2710,8 @@ deque<_Tp, _Allocator>::pop_front()
__base::__start_ / __base::__block_size) +
__base::__start_ % __base::__block_size));
--__base::size();
- if (++__base::__start_ >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
- __base::__map_.pop_front();
- __base::__start_ -= __base::__block_size;
- }
+ ++__base::__start_;
+ __maybe_remove_front_spare();
}
template <class _Tp, class _Allocator>
@@ -2615,11 +2725,7 @@ deque<_Tp, _Allocator>::pop_back()
__p / __base::__block_size) +
__p % __base::__block_size));
--__base::size();
- if (__back_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
- __base::__map_.pop_back();
- }
+ __maybe_remove_back_spare();
}
// move assign [__f, __l) to [__r, __r + (__l-__f)).
@@ -2768,23 +2874,14 @@ deque<_Tp, _Allocator>::erase(const_iterator __f)
__alloc_traits::destroy(__a, _VSTD::addressof(*__b));
--__base::size();
++__base::__start_;
- if (__front_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
- __base::__map_.pop_front();
- __base::__start_ -= __base::__block_size;
- }
+ __maybe_remove_front_spare();
}
else
{ // erase from back
iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p);
__alloc_traits::destroy(__a, _VSTD::addressof(*__i));
--__base::size();
- if (__back_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
- __base::__map_.pop_back();
- }
+ __maybe_remove_back_spare();
}
return __base::begin() + __pos;
}
@@ -2807,11 +2904,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
__alloc_traits::destroy(__a, _VSTD::addressof(*__b));
__base::size() -= __n;
__base::__start_ += __n;
- while (__front_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size);
- __base::__map_.pop_front();
- __base::__start_ -= __base::__block_size;
+ while (__maybe_remove_front_spare()) {
}
}
else
@@ -2820,10 +2913,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
for (iterator __e = __base::end(); __i != __e; ++__i)
__alloc_traits::destroy(__a, _VSTD::addressof(*__i));
__base::size() -= __n;
- while (__back_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
- __base::__map_.pop_back();
+ while (__maybe_remove_back_spare()) {
}
}
}
@@ -2844,10 +2934,7 @@ deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f)
for (iterator __p = __b + __pos; __p != __e; ++__p)
__alloc_traits::destroy(__a, _VSTD::addressof(*__p));
__base::size() -= __n;
- while (__back_spare() >= 2 * __base::__block_size)
- {
- __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size);
- __base::__map_.pop_back();
+ while (__maybe_remove_back_spare()) {
}
}
}