// Vector implementation (out of line) -*- C++ -*-
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
-// Free Software Foundation, Inc.
+// Copyright (C) 2001-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
* purpose. It is provided "as is" without express or implied warranty.
*/
-/** @file vector.tcc
+/** @file bits/vector.tcc
* This is an internal header file, included by other library headers.
- * You should not attempt to use it directly.
+ * Do not attempt to use it directly. @headername{vector}
*/
#ifndef _VECTOR_TCC
#define _VECTOR_TCC 1
-_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
template<typename _Tp, typename _Alloc>
void
{
const size_type __old_size = size();
pointer __tmp = _M_allocate_and_copy(__n,
- _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_start),
- _GLIBCXX_MAKE_MOVE_ITERATOR(this->_M_impl._M_finish));
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
_M_get_Tp_allocator());
_M_deallocate(this->_M_impl._M_start,
}
}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
void
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
- this->_M_impl.construct(this->_M_impl._M_finish,
- std::forward<_Args>(__args)...);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::forward<_Args>(__args)...);
++this->_M_impl._M_finish;
}
else
- _M_insert_aux(end(), std::forward<_Args>(__args)...);
+ _M_emplace_back_aux(std::forward<_Args>(__args)...);
}
#endif
template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
+#if __cplusplus >= 201103L
+ insert(const_iterator __position, const value_type& __x)
+#else
insert(iterator __position, const value_type& __x)
+#endif
{
const size_type __n = __position - begin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
&& __position == end())
{
- this->_M_impl.construct(this->_M_impl._M_finish, __x);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
++this->_M_impl._M_finish;
}
else
{
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
+ const auto __pos = begin() + (__position - cbegin());
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
_Tp __x_copy = __x;
- _M_insert_aux(__position, std::move(__x_copy));
+ _M_insert_aux(__pos, std::move(__x_copy));
}
else
-#endif
+ _M_insert_aux(__pos, __x);
+#else
_M_insert_aux(__position, __x);
+#endif
}
return iterator(this->_M_impl._M_start + __n);
}
template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
- erase(iterator __position)
+ _M_erase(iterator __position)
{
if (__position + 1 != end())
_GLIBCXX_MOVE3(__position + 1, end(), __position);
--this->_M_impl._M_finish;
- this->_M_impl.destroy(this->_M_impl._M_finish);
+ _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
return __position;
}
template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
- erase(iterator __first, iterator __last)
+ _M_erase(iterator __first, iterator __last)
{
- if (__last != end())
- _GLIBCXX_MOVE3(__last, end(), __first);
- _M_erase_at_end(__first.base() + (end() - __last));
+ if (__first != __last)
+ {
+ if (__last != end())
+ _GLIBCXX_MOVE3(__last, end(), __first);
+ _M_erase_at_end(__first.base() + (end() - __last));
+ }
return __first;
}
{
if (&__x != this)
{
+#if __cplusplus >= 201103L
+ if (_Alloc_traits::_S_propagate_on_copy_assign())
+ {
+ if (!_Alloc_traits::_S_always_equal()
+ && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
+ {
+ // replacement allocator cannot free existing storage
+ this->clear();
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = nullptr;
+ this->_M_impl._M_finish = nullptr;
+ this->_M_impl._M_end_of_storage = nullptr;
+ }
+ std::__alloc_on_copy(_M_get_Tp_allocator(),
+ __x._M_get_Tp_allocator());
+ }
+#endif
const size_type __xlen = __x.size();
if (__xlen > capacity())
{
if (__n > capacity())
{
vector __tmp(__n, __val, _M_get_Tp_allocator());
- __tmp.swap(*this);
+ __tmp._M_impl._M_swap_data(this->_M_impl);
}
else if (__n > size())
{
std::fill(begin(), end(), __val);
- std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
- __n - size(), __val,
- _M_get_Tp_allocator());
- this->_M_impl._M_finish += __n - size();
+ this->_M_impl._M_finish =
+ std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+ __n - size(), __val,
+ _M_get_Tp_allocator());
}
else
_M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
}
}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
- emplace(iterator __position, _Args&&... __args)
+ emplace(const_iterator __position, _Args&&... __args)
{
const size_type __n = __position - begin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
&& __position == end())
{
- this->_M_impl.construct(this->_M_impl._M_finish,
- std::forward<_Args>(__args)...);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::forward<_Args>(__args)...);
++this->_M_impl._M_finish;
}
else
- _M_insert_aux(__position, std::forward<_Args>(__args)...);
+ _M_insert_aux(begin() + (__position - cbegin()),
+ std::forward<_Args>(__args)...);
return iterator(this->_M_impl._M_start + __n);
}
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
- this->_M_impl.construct(this->_M_impl._M_finish,
- _GLIBCXX_MOVE(*(this->_M_impl._M_finish
- - 1)));
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ _GLIBCXX_MOVE(*(this->_M_impl._M_finish
+ - 1)));
++this->_M_impl._M_finish;
-#ifndef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus < 201103L
_Tp __x_copy = __x;
#endif
_GLIBCXX_MOVE_BACKWARD3(__position.base(),
this->_M_impl._M_finish - 2,
this->_M_impl._M_finish - 1);
-#ifndef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus < 201103L
*__position = __x_copy;
#else
*__position = _Tp(std::forward<_Args>(__args)...);
// case, where the moves could alter a new element belonging
// to the existing vector. This is an issue only for callers
// taking the element by const lvalue ref (see 23.1/13).
- this->_M_impl.construct(__new_start + __elems_before,
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- std::forward<_Args>(__args)...);
+ _Alloc_traits::construct(this->_M_impl,
+ __new_start + __elems_before,
+#if __cplusplus >= 201103L
+ std::forward<_Args>(__args)...);
#else
- __x);
+ __x);
#endif
- __new_finish = 0;
+ __new_finish = pointer();
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
- __new_finish =
- std::__uninitialized_move_a(this->_M_impl._M_start,
- __position.base(), __new_start,
- _M_get_Tp_allocator());
++__new_finish;
- __new_finish =
- std::__uninitialized_move_a(__position.base(),
- this->_M_impl._M_finish,
- __new_finish,
- _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
}
__catch(...)
{
if (!__new_finish)
- this->_M_impl.destroy(__new_start + __elems_before);
+ _Alloc_traits::destroy(this->_M_impl,
+ __new_start + __elems_before);
else
std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
_M_deallocate(__new_start, __len);
}
}
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+ void
+ vector<_Tp, _Alloc>::
+ _M_emplace_back_aux(_Args&&... __args)
+ {
+ const size_type __len =
+ _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
+ {
+ _Alloc_traits::construct(this->_M_impl, __new_start + size(),
+ std::forward<_Args>(__args)...);
+ __new_finish = pointer();
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, this->_M_impl._M_finish,
+ __new_start, _M_get_Tp_allocator());
+
+ ++__new_finish;
+ }
+ __catch(...)
+ {
+ if (!__new_finish)
+ _Alloc_traits::destroy(this->_M_impl, __new_start + size());
+ else
+ std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
+ }
+#endif
+
template<typename _Tp, typename _Alloc>
void
vector<_Tp, _Alloc>::
}
else
{
- std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
- __n - __elems_after,
- __x_copy,
- _M_get_Tp_allocator());
- this->_M_impl._M_finish += __n - __elems_after;
+ this->_M_impl._M_finish =
+ std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+ __n - __elems_after,
+ __x_copy,
+ _M_get_Tp_allocator());
std::__uninitialized_move_a(__position.base(), __old_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
std::__uninitialized_fill_n_a(__new_start + __elems_before,
__n, __x,
_M_get_Tp_allocator());
- __new_finish = 0;
+ __new_finish = pointer();
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
- __new_finish =
- std::__uninitialized_move_a(this->_M_impl._M_start,
- __position.base(),
- __new_start,
- _M_get_Tp_allocator());
__new_finish += __n;
- __new_finish =
- std::__uninitialized_move_a(__position.base(),
- this->_M_impl._M_finish,
- __new_finish,
- _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
}
__catch(...)
{
}
}
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ void
+ vector<_Tp, _Alloc>::
+ _M_default_append(size_type __n)
+ {
+ if (__n != 0)
+ {
+ if (size_type(this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_finish) >= __n)
+ {
+ this->_M_impl._M_finish =
+ std::__uninitialized_default_n_a(this->_M_impl._M_finish,
+ __n, _M_get_Tp_allocator());
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector::_M_default_append");
+ const size_type __old_size = this->size();
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
+ {
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, this->_M_impl._M_finish,
+ __new_start, _M_get_Tp_allocator());
+ __new_finish =
+ std::__uninitialized_default_n_a(__new_finish, __n,
+ _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ std::_Destroy(__new_start, __new_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
+ }
+ }
+ }
+
+ template<typename _Tp, typename _Alloc>
+ bool
+ vector<_Tp, _Alloc>::
+ _M_shrink_to_fit()
+ {
+ if (capacity() == size())
+ return false;
+ return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
+ }
+#endif
+
template<typename _Tp, typename _Alloc>
template<typename _InputIterator>
void
pointer __new_finish(__new_start);
__try
{
- __new_finish =
- std::__uninitialized_move_a(this->_M_impl._M_start,
- __position.base(),
- __new_start,
- _M_get_Tp_allocator());
- __new_finish =
- std::__uninitialized_copy_a(__first, __last,
- __new_finish,
- _M_get_Tp_allocator());
- __new_finish =
- std::__uninitialized_move_a(__position.base(),
- this->_M_impl._M_finish,
- __new_finish,
- _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_copy_a(__first, __last,
+ __new_finish,
+ _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
}
__catch(...)
{
// vector<bool>
-
template<typename _Alloc>
void
vector<bool, _Alloc>::
- reserve(size_type __n)
+ _M_reallocate(size_type __n)
{
- if (__n > this->max_size())
- __throw_length_error(__N("vector::reserve"));
- if (this->capacity() < __n)
- {
- _Bit_type* __q = this->_M_allocate(__n);
- this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
- iterator(__q, 0));
- this->_M_deallocate();
- this->_M_impl._M_start = iterator(__q, 0);
- this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
- / int(_S_word_bit));
- }
+ _Bit_pointer __q = this->_M_allocate(__n);
+ iterator __start(std::__addressof(*__q), 0);
+ this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), __start);
+ this->_M_deallocate();
+ this->_M_impl._M_start = __start;
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
}
template<typename _Alloc>
{
const size_type __len =
_M_check_len(__n, "vector<bool>::_M_fill_insert");
- _Bit_type * __q = this->_M_allocate(__len);
- iterator __i = _M_copy_aligned(begin(), __position,
- iterator(__q, 0));
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
std::fill(__i, __i + difference_type(__n), __x);
this->_M_impl._M_finish = std::copy(__position, end(),
__i + difference_type(__n));
this->_M_deallocate();
- this->_M_impl._M_end_of_storage = (__q + ((__len
- + int(_S_word_bit) - 1)
- / int(_S_word_bit)));
- this->_M_impl._M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
}
}
{
const size_type __len =
_M_check_len(__n, "vector<bool>::_M_insert_range");
- _Bit_type * __q = this->_M_allocate(__len);
- iterator __i = _M_copy_aligned(begin(), __position,
- iterator(__q, 0));
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
__i = std::copy(__first, __last, __i);
this->_M_impl._M_finish = std::copy(__position, end(), __i);
this->_M_deallocate();
- this->_M_impl._M_end_of_storage = (__q
- + ((__len
- + int(_S_word_bit) - 1)
- / int(_S_word_bit)));
- this->_M_impl._M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
}
}
}
vector<bool, _Alloc>::
_M_insert_aux(iterator __position, bool __x)
{
- if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
+ if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
{
std::copy_backward(__position, this->_M_impl._M_finish,
this->_M_impl._M_finish + 1);
{
const size_type __len =
_M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
- _Bit_type * __q = this->_M_allocate(__len);
- iterator __i = _M_copy_aligned(begin(), __position,
- iterator(__q, 0));
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
*__i++ = __x;
this->_M_impl._M_finish = std::copy(__position, end(), __i);
this->_M_deallocate();
- this->_M_impl._M_end_of_storage = (__q + ((__len
- + int(_S_word_bit) - 1)
- / int(_S_word_bit)));
- this->_M_impl._M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
+ }
+ }
+
+ template<typename _Alloc>
+ typename vector<bool, _Alloc>::iterator
+ vector<bool, _Alloc>::
+ _M_erase(iterator __position)
+ {
+ if (__position + 1 != end())
+ std::copy(__position + 1, end(), __position);
+ --this->_M_impl._M_finish;
+ return __position;
+ }
+
+ template<typename _Alloc>
+ typename vector<bool, _Alloc>::iterator
+ vector<bool, _Alloc>::
+ _M_erase(iterator __first, iterator __last)
+ {
+ if (__first != __last)
+ _M_erase_at_end(std::copy(__last, end(), __first));
+ return __first;
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Alloc>
+ bool
+ vector<bool, _Alloc>::
+ _M_shrink_to_fit()
+ {
+ if (capacity() - size() < int(_S_word_bit))
+ return false;
+ __try
+ {
+ _M_reallocate(size());
+ return true;
+ }
+ __catch(...)
+ { return false; }
+ }
+#endif
+
+_GLIBCXX_END_NAMESPACE_CONTAINER
+} // namespace std
+
+#if __cplusplus >= 201103L
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ template<typename _Alloc>
+ size_t
+ hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
+ operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
+ {
+ size_t __hash = 0;
+ using _GLIBCXX_STD_C::_S_word_bit;
+ using _GLIBCXX_STD_C::_Bit_type;
+
+ const size_t __words = __b.size() / _S_word_bit;
+ if (__words)
+ {
+ const size_t __clength = __words * sizeof(_Bit_type);
+ __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
+ }
+
+ const size_t __extrabits = __b.size() % _S_word_bit;
+ if (__extrabits)
+ {
+ _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
+ __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
+
+ const size_t __clength
+ = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
+ if (__words)
+ __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
+ else
+ __hash = std::_Hash_impl::hash(&__hiword, __clength);
}
+
+ return __hash;
}
-_GLIBCXX_END_NESTED_NAMESPACE
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+#endif // C++11
#endif /* _VECTOR_TCC */