备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
首先贴一张deque的内存组成图:
stl_deque.h:
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) |
inline size_t __deque_buf_size( size_t n, size_t sz) |
return n != 0 ? n : (sz < 512 ? size_t (512 / sz) : size_t (1)); |
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
template < class T, class Ref, class Ptr, size_t BufSiz> |
struct __deque_iterator { |
typedef __deque_iterator<T, T&, T*, BufSiz> iterator; |
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator; |
static size_t buffer_size() { return __deque_buf_size(BufSiz, sizeof (T)); } |
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
template < class T, class Ref, class Ptr> |
struct __deque_iterator { |
typedef __deque_iterator<T, T&, T*> iterator; |
typedef __deque_iterator<T, const T&, const T*> const_iterator; |
static size_t buffer_size() { return __deque_buf_size(0, sizeof (T)); } |
typedef random_access_iterator_tag iterator_category; |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef __deque_iterator self; |
__deque_iterator(T* x, map_pointer y) |
: cur(x), first(*y), last(*y + buffer_size()), node(y) {} |
__deque_iterator() : cur(0), first(0), last(0), node(0) {} |
__deque_iterator( const iterator& x) |
: cur(x.cur), first(x.first), last(x.last), node(x.node) {} |
reference operator*() const { return *cur; } |
#ifndef __SGI_STL_NO_ARROW_OPERATOR |
pointer operator->() const { return &(operator*()); } |
#endif /* __SGI_STL_NO_ARROW_OPERATOR */ |
difference_type operator-( const self& x) const { |
return difference_type(buffer_size()) * (node - x.node - 1) + |
(cur - first) + (x.last - x.cur); |
self& operator+=(difference_type n) { |
difference_type offset = n + (cur - first); |
if (offset >= 0 && offset < difference_type(buffer_size())) |
difference_type node_offset = |
offset > 0 ? offset / difference_type(buffer_size()) |
: -difference_type((-offset - 1) / buffer_size()) - 1; |
set_node(node + node_offset); |
cur = first + (offset - node_offset * difference_type(buffer_size())); |
self operator+(difference_type n) const { |
self& operator-=(difference_type n) { return * this += -n; } |
self operator-(difference_type n) const { |
reference operator[](difference_type n) const { return *(* this + n); } |
bool operator==( const self& x) const { return cur == x.cur; } |
bool operator!=( const self& x) const { return !(* this == x); } |
bool operator<( const self& x) const { |
return (node == x.node) ? (cur < x.cur) : (node < x.node); |
void set_node(map_pointer new_node) { |
last = first + difference_type(buffer_size()); |
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION |
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
template < class T, class Ref, class Ptr, size_t BufSiz> |
inline random_access_iterator_tag |
iterator_category( const __deque_iterator<T, Ref, Ptr, BufSiz>&) { |
return random_access_iterator_tag(); |
template < class T, class Ref, class Ptr, size_t BufSiz> |
inline T* value_type( const __deque_iterator<T, Ref, Ptr, BufSiz>&) { |
template < class T, class Ref, class Ptr, size_t BufSiz> |
inline ptrdiff_t * distance_type( const __deque_iterator<T, Ref, Ptr, BufSiz>&) { |
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
template < class T, class Ref, class Ptr> |
inline random_access_iterator_tag |
iterator_category( const __deque_iterator<T, Ref, Ptr>&) { |
return random_access_iterator_tag(); |
template < class T, class Ref, class Ptr> |
inline T* value_type( const __deque_iterator<T, Ref, Ptr>&) { return 0; } |
template < class T, class Ref, class Ptr> |
inline ptrdiff_t * distance_type( const __deque_iterator<T, Ref, Ptr>&) { |
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
template < class T, class Alloc = alloc, size_t BufSiz = 0> |
typedef value_type* pointer; |
typedef const value_type* const_pointer; |
typedef value_type& reference; |
typedef const value_type& const_reference; |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
typedef __deque_iterator<T, T&, T*, BufSiz> iterator; |
typedef __deque_iterator<T, const T&, const T&, BufSiz> const_iterator; |
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
typedef __deque_iterator<T, T&, T*> iterator; |
typedef __deque_iterator<T, const T&, const T*> const_iterator; |
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION |
typedef reverse_iterator<const_iterator> const_reverse_iterator; |
typedef reverse_iterator<iterator> reverse_iterator; |
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
typedef reverse_iterator<const_iterator, value_type, const_reference, |
typedef reverse_iterator<iterator, value_type, reference, difference_type> |
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
typedef pointer* map_pointer; |
typedef simple_alloc<value_type, Alloc> data_allocator; |
typedef simple_alloc<pointer, Alloc> map_allocator; |
static size_type buffer_size() { |
return __deque_buf_size(BufSiz, sizeof (value_type)); |
static size_type initial_map_size() { return 8; } |
iterator begin() { return start; } |
iterator end() { return finish; } |
const_iterator begin() const { return start; } |
const_iterator end() const { return finish; } |
reverse_iterator rbegin() { return reverse_iterator(finish); } |
reverse_iterator rend() { return reverse_iterator(start); } |
const_reverse_iterator rbegin() const { |
return const_reverse_iterator(finish); |
const_reverse_iterator rend() const { |
return const_reverse_iterator(start); |
reference operator[](size_type n) { return start[difference_type(n)]; } |
const_reference operator[](size_type n) const { |
return start[difference_type(n)]; |
reference front() { return *start; } |
const_reference front() const { return *start; } |
const_reference back() const { |
const_iterator tmp = finish; |
size_type size() const { return finish - start;; } |
size_type max_size() const { return size_type(-1); } |
bool empty() const { return finish == start; } |
: start(), finish(), map(0), map_size(0) |
: start(), finish(), map(0), map_size(0) |
create_map_and_nodes(x.size()); |
uninitialized_copy(x.begin(), x.end(), start); |
__STL_UNWIND(destroy_map_and_nodes()); |
deque(size_type n, const value_type& value) |
: start(), finish(), map(0), map_size(0) |
fill_initialize(n, value); |
deque( int n, const value_type& value) |
: start(), finish(), map(0), map_size(0) |
fill_initialize(n, value); |
deque( long n, const value_type& value) |
: start(), finish(), map(0), map_size(0) |
fill_initialize(n, value); |
explicit deque(size_type n) |
: start(), finish(), map(0), map_size(0) |
fill_initialize(n, value_type()); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
deque(InputIterator first, InputIterator last) |
: start(), finish(), map(0), map_size(0) |
range_initialize(first, last, iterator_category(first)); |
#else /* __STL_MEMBER_TEMPLATES */ |
deque( const value_type* first, const value_type* last) |
: start(), finish(), map(0), map_size(0) |
create_map_and_nodes(last - first); |
uninitialized_copy(first, last, start); |
__STL_UNWIND(destroy_map_and_nodes()); |
deque(const_iterator first, const_iterator last) |
: start(), finish(), map(0), map_size(0) |
create_map_and_nodes(last - first); |
uninitialized_copy(first, last, start); |
__STL_UNWIND(destroy_map_and_nodes()); |
#endif /* __STL_MEMBER_TEMPLATES */ |
deque& operator= ( const deque& x) { |
const size_type len = size(); |
erase(copy(x.begin(), x.end(), start), finish); |
const_iterator mid = x.begin() + difference_type(len); |
copy(x.begin(), mid, start); |
insert(finish, mid, x.end()); |
__STD::swap(start, x.start); |
__STD::swap(finish, x.finish); |
__STD::swap(map_size, x.map_size); |
void push_back( const value_type& t) { |
if (finish.cur != finish.last - 1) { |
construct(finish.cur, t); |
void push_front( const value_type& t) { |
if (start.cur != start.first) { |
construct(start.cur - 1, t); |
if (finish.cur != finish.first) { |
if (start.cur != start.last - 1) { |
iterator insert(iterator position, const value_type& x) { |
if (position.cur == start.cur) { |
else if (position.cur == finish.cur) { |
return insert_aux(position, x); |
iterator insert(iterator position) { return insert(position, value_type()); } |
void insert(iterator pos, size_type n, const value_type& x); |
void insert(iterator pos, int n, const value_type& x) { |
insert(pos, (size_type) n, x); |
void insert(iterator pos, long n, const value_type& x) { |
insert(pos, (size_type) n, x); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
void insert(iterator pos, InputIterator first, InputIterator last) { |
insert(pos, first, last, iterator_category(first)); |
#else /* __STL_MEMBER_TEMPLATES */ |
void insert(iterator pos, const value_type* first, const value_type* last); |
void insert(iterator pos, const_iterator first, const_iterator last); |
#endif /* __STL_MEMBER_TEMPLATES */ |
void resize(size_type new_size, const value_type& x) { |
const size_type len = size(); |
erase(start + new_size, finish); |
insert(finish, new_size - len, x); |
void resize(size_type new_size) { resize(new_size, value_type()); } |
iterator erase(iterator pos) { |
difference_type index = pos - start; |
if (index < (size() >> 1)) { |
copy_backward(start, pos, next); |
iterator erase(iterator first, iterator last); |
void create_map_and_nodes(size_type num_elements); |
void destroy_map_and_nodes(); |
void fill_initialize(size_type n, const value_type& value); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
void range_initialize(InputIterator first, InputIterator last, |
template < class ForwardIterator> |
void range_initialize(ForwardIterator first, ForwardIterator last, |
#endif /* __STL_MEMBER_TEMPLATES */ |
void push_back_aux( const value_type& t); |
void push_front_aux( const value_type& t); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
void insert(iterator pos, InputIterator first, InputIterator last, |
template < class ForwardIterator> |
void insert(iterator pos, ForwardIterator first, ForwardIterator last, |
#endif /* __STL_MEMBER_TEMPLATES */ |
iterator insert_aux(iterator pos, const value_type& x); |
void insert_aux(iterator pos, size_type n, const value_type& x); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class ForwardIterator> |
void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last, |
#else /* __STL_MEMBER_TEMPLATES */ |
void insert_aux(iterator pos, |
const value_type* first, const value_type* last, |
void insert_aux(iterator pos, const_iterator first, const_iterator last, |
#endif /* __STL_MEMBER_TEMPLATES */ |
iterator reserve_elements_at_front(size_type n) { |
size_type vacancies = start.cur - start.first; |
new_elements_at_front(n - vacancies); |
return start - difference_type(n); |
iterator reserve_elements_at_back(size_type n) { |
size_type vacancies = (finish.last - finish.cur) - 1; |
new_elements_at_back(n - vacancies); |
return finish + difference_type(n); |
void new_elements_at_front(size_type new_elements); |
void new_elements_at_back(size_type new_elements); |
void destroy_nodes_at_front(iterator before_start); |
void destroy_nodes_at_back(iterator after_finish); |
void reserve_map_at_back (size_type nodes_to_add = 1) { |
if (nodes_to_add + 1 > map_size - (finish.node - map)) |
reallocate_map(nodes_to_add, false ); |
void reserve_map_at_front (size_type nodes_to_add = 1) { |
if (nodes_to_add > start.node - map) |
reallocate_map(nodes_to_add, true ); |
void reallocate_map(size_type nodes_to_add, bool add_at_front); |
pointer allocate_node() { return data_allocator::allocate(buffer_size()); } |
void deallocate_node(pointer n) { |
data_allocator::deallocate(n, buffer_size()); |
#ifdef __STL_NON_TYPE_TMPL_PARAM_BUG |
bool operator==( const deque<T, Alloc, 0>& x) const { |
return size() == x.size() && equal(begin(), end(), x.begin()); |
bool operator!=( const deque<T, Alloc, 0>& x) const { |
return size() != x.size() || !equal(begin(), end(), x.begin()); |
bool operator<( const deque<T, Alloc, 0>& x) const { |
return lexicographical_compare(begin(), end(), x.begin(), x.end()); |
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert(iterator pos, |
size_type n, const value_type& x) { |
if (pos.cur == start.cur) { |
iterator new_start = reserve_elements_at_front(n); |
uninitialized_fill(new_start, start, x); |
else if (pos.cur == finish.cur) { |
iterator new_finish = reserve_elements_at_back(n); |
uninitialized_fill(finish, new_finish, x); |
#ifndef __STL_MEMBER_TEMPLATES |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert(iterator pos, |
const value_type* last) { |
size_type n = last - first; |
if (pos.cur == start.cur) { |
iterator new_start = reserve_elements_at_front(n); |
uninitialized_copy(first, last, new_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
else if (pos.cur == finish.cur) { |
iterator new_finish = reserve_elements_at_back(n); |
uninitialized_copy(first, last, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
insert_aux(pos, first, last, n); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert(iterator pos, |
size_type n = last - first; |
if (pos.cur == start.cur) { |
iterator new_start = reserve_elements_at_front(n); |
uninitialized_copy(first, last, new_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
else if (pos.cur == finish.cur) { |
iterator new_finish = reserve_elements_at_back(n); |
uninitialized_copy(first, last, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
insert_aux(pos, first, last, n); |
#endif /* __STL_MEMBER_TEMPLATES */ |
template < class T, class Alloc, size_t BufSize> |
deque<T, Alloc, BufSize>::iterator |
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) { |
if (first == start && last == finish) { |
difference_type n = last - first; |
difference_type elems_before = first - start; |
if (elems_before < (size() - n) / 2) { |
copy_backward(start, first, last); |
iterator new_start = start + n; |
destroy(start, new_start); |
for (map_pointer cur = start.node; cur < new_start.node; ++cur) |
data_allocator::deallocate(*cur, buffer_size()); |
copy(last, finish, first); |
iterator new_finish = finish - n; |
destroy(new_finish, finish); |
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur) |
data_allocator::deallocate(*cur, buffer_size()); |
return start + elems_before; |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::clear() { |
for (map_pointer node = start.node + 1; node < finish.node; ++node) { |
destroy(*node, *node + buffer_size()); |
data_allocator::deallocate(*node, buffer_size()); |
if (start.node != finish.node) { |
destroy(start.cur, start.last); |
destroy(finish.first, finish.cur); |
data_allocator::deallocate(finish.first, buffer_size()); |
destroy(start.cur, finish.cur); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) { |
size_type num_nodes = num_elements / buffer_size() + 1; |
map_size = max(initial_map_size(), num_nodes + 2); |
map = map_allocator::allocate(map_size); |
map_pointer nstart = map + (map_size - num_nodes) / 2; |
map_pointer nfinish = nstart + num_nodes - 1; |
for (cur = nstart; cur <= nfinish; ++cur) |
# ifdef __STL_USE_EXCEPTIONS |
for (map_pointer n = nstart; n < cur; ++n) |
map_allocator::deallocate(map, map_size); |
# endif /* __STL_USE_EXCEPTIONS */ |
finish.set_node(nfinish); |
finish.cur = finish.first + num_elements % buffer_size(); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::destroy_map_and_nodes() { |
for (map_pointer cur = start.node; cur <= finish.node; ++cur) |
map_allocator::deallocate(map, map_size); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::fill_initialize(size_type n, |
const value_type& value) { |
for (cur = start.node; cur < finish.node; ++cur) |
uninitialized_fill(*cur, *cur + buffer_size(), value); |
uninitialized_fill(finish.first, finish.cur, value); |
# ifdef __STL_USE_EXCEPTIONS |
for (map_pointer n = start.node; n < cur; ++n) |
destroy(*n, *n + buffer_size()); |
# endif /* __STL_USE_EXCEPTIONS */ |
#ifdef __STL_MEMBER_TEMPLATES |
template < class T, class Alloc, size_t BufSize> |
template < class InputIterator> |
void deque<T, Alloc, BufSize>::range_initialize(InputIterator first, |
for ( ; first != last; ++first) |
template < class T, class Alloc, size_t BufSize> |
template < class ForwardIterator> |
void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first, |
distance(first, last, n); |
uninitialized_copy(first, last, start); |
__STL_UNWIND(destroy_map_and_nodes()); |
#endif /* __STL_MEMBER_TEMPLATES */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::push_back_aux( const value_type& t) { |
*(finish.node + 1) = allocate_node(); |
construct(finish.cur, t_copy); |
finish.set_node(finish.node + 1); |
finish.cur = finish.first; |
__STL_UNWIND(deallocate_node(*(finish.node + 1))); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::push_front_aux( const value_type& t) { |
*(start.node - 1) = allocate_node(); |
start.set_node(start.node - 1); |
start.cur = start.last - 1; |
construct(start.cur, t_copy); |
# ifdef __STL_USE_EXCEPTIONS |
start.set_node(start.node + 1); |
deallocate_node(*(start.node - 1)); |
# endif /* __STL_USE_EXCEPTIONS */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>:: pop_back_aux() { |
deallocate_node(finish.first); |
finish.set_node(finish.node - 1); |
finish.cur = finish.last - 1; |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::pop_front_aux() { |
deallocate_node(start.first); |
start.set_node(start.node + 1); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class T, class Alloc, size_t BufSize> |
template < class InputIterator> |
void deque<T, Alloc, BufSize>::insert(iterator pos, |
InputIterator first, InputIterator last, |
copy(first, last, inserter(* this , pos)); |
template < class T, class Alloc, size_t BufSize> |
template < class ForwardIterator> |
void deque<T, Alloc, BufSize>::insert(iterator pos, |
distance(first, last, n); |
if (pos.cur == start.cur) { |
iterator new_start = reserve_elements_at_front(n); |
uninitialized_copy(first, last, new_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
else if (pos.cur == finish.cur) { |
iterator new_finish = reserve_elements_at_back(n); |
uninitialized_copy(first, last, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
insert_aux(pos, first, last, n); |
#endif /* __STL_MEMBER_TEMPLATES */ |
template < class T, class Alloc, size_t BufSize> |
typename deque<T, Alloc, BufSize>::iterator |
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) { |
difference_type index = pos - start; |
if (index < size() / 2) { |
iterator front2 = front1; |
copy(front2, pos1, front1); |
copy_backward(pos, back2, back1); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
size_type n, const value_type& x) { |
const difference_type elems_before = pos - start; |
size_type length = size(); |
if (elems_before < length / 2) { |
iterator new_start = reserve_elements_at_front(n); |
iterator old_start = start; |
pos = start + elems_before; |
if (elems_before >= difference_type(n)) { |
iterator start_n = start + difference_type(n); |
uninitialized_copy(start, start_n, new_start); |
copy(start_n, pos, old_start); |
fill(pos - difference_type(n), pos, x_copy); |
__uninitialized_copy_fill(start, pos, new_start, start, x_copy); |
fill(old_start, pos, x_copy); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
iterator new_finish = reserve_elements_at_back(n); |
iterator old_finish = finish; |
const difference_type elems_after = difference_type(length) - elems_before; |
pos = finish - elems_after; |
if (elems_after > difference_type(n)) { |
iterator finish_n = finish - difference_type(n); |
uninitialized_copy(finish_n, finish, finish); |
copy_backward(pos, finish_n, old_finish); |
fill(pos, pos + difference_type(n), x_copy); |
__uninitialized_fill_copy(finish, pos + difference_type(n), |
fill(pos, old_finish, x_copy); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class T, class Alloc, size_t BufSize> |
template < class ForwardIterator> |
void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
const difference_type elems_before = pos - start; |
size_type length = size(); |
if (elems_before < length / 2) { |
iterator new_start = reserve_elements_at_front(n); |
iterator old_start = start; |
pos = start + elems_before; |
if (elems_before >= difference_type(n)) { |
iterator start_n = start + difference_type(n); |
uninitialized_copy(start, start_n, new_start); |
copy(start_n, pos, old_start); |
copy(first, last, pos - difference_type(n)); |
ForwardIterator mid = first; |
advance(mid, difference_type(n) - elems_before); |
__uninitialized_copy_copy(start, pos, first, mid, new_start); |
copy(mid, last, old_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
iterator new_finish = reserve_elements_at_back(n); |
iterator old_finish = finish; |
const difference_type elems_after = difference_type(length) - elems_before; |
pos = finish - elems_after; |
if (elems_after > difference_type(n)) { |
iterator finish_n = finish - difference_type(n); |
uninitialized_copy(finish_n, finish, finish); |
copy_backward(pos, finish_n, old_finish); |
ForwardIterator mid = first; |
advance(mid, elems_after); |
__uninitialized_copy_copy(mid, last, pos, finish, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
#else /* __STL_MEMBER_TEMPLATES */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
const difference_type elems_before = pos - start; |
size_type length = size(); |
if (elems_before < length / 2) { |
iterator new_start = reserve_elements_at_front(n); |
iterator old_start = start; |
pos = start + elems_before; |
if (elems_before >= difference_type(n)) { |
iterator start_n = start + difference_type(n); |
uninitialized_copy(start, start_n, new_start); |
copy(start_n, pos, old_start); |
copy(first, last, pos - difference_type(n)); |
const value_type* mid = first + (difference_type(n) - elems_before); |
__uninitialized_copy_copy(start, pos, first, mid, new_start); |
copy(mid, last, old_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
iterator new_finish = reserve_elements_at_back(n); |
iterator old_finish = finish; |
const difference_type elems_after = difference_type(length) - elems_before; |
pos = finish - elems_after; |
if (elems_after > difference_type(n)) { |
iterator finish_n = finish - difference_type(n); |
uninitialized_copy(finish_n, finish, finish); |
copy_backward(pos, finish_n, old_finish); |
const value_type* mid = first + elems_after; |
__uninitialized_copy_copy(mid, last, pos, finish, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::insert_aux(iterator pos, |
const difference_type elems_before = pos - start; |
size_type length = size(); |
if (elems_before < length / 2) { |
iterator new_start = reserve_elements_at_front(n); |
iterator old_start = start; |
pos = start + elems_before; |
iterator start_n = start + n; |
uninitialized_copy(start, start_n, new_start); |
copy(start_n, pos, old_start); |
copy(first, last, pos - difference_type(n)); |
const_iterator mid = first + (n - elems_before); |
__uninitialized_copy_copy(start, pos, first, mid, new_start); |
copy(mid, last, old_start); |
__STL_UNWIND(destroy_nodes_at_front(new_start)); |
iterator new_finish = reserve_elements_at_back(n); |
iterator old_finish = finish; |
const difference_type elems_after = length - elems_before; |
pos = finish - elems_after; |
iterator finish_n = finish - difference_type(n); |
uninitialized_copy(finish_n, finish, finish); |
copy_backward(pos, finish_n, old_finish); |
const_iterator mid = first + elems_after; |
__uninitialized_copy_copy(mid, last, pos, finish, finish); |
__STL_UNWIND(destroy_nodes_at_back(new_finish)); |
#endif /* __STL_MEMBER_TEMPLATES */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) { |
size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); |
reserve_map_at_front(new_nodes); |
for (i = 1; i <= new_nodes; ++i) |
*(start.node - i) = allocate_node(); |
# ifdef __STL_USE_EXCEPTIONS |
for (size_type j = 1; j < i; ++j) |
deallocate_node(*(start.node - j)); |
# endif /* __STL_USE_EXCEPTIONS */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) { |
size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size(); |
reserve_map_at_back(new_nodes); |
for (i = 1; i <= new_nodes; ++i) |
*(finish.node + i) = allocate_node(); |
# ifdef __STL_USE_EXCEPTIONS |
for (size_type j = 1; j < i; ++j) |
deallocate_node(*(finish.node + j)); |
# endif /* __STL_USE_EXCEPTIONS */ |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) { |
for (map_pointer n = before_start.node; n < start.node; ++n) |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) { |
for (map_pointer n = after_finish.node; n > finish.node; --n) |
template < class T, class Alloc, size_t BufSize> |
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, |
size_type old_num_nodes = finish.node - start.node + 1; |
size_type new_num_nodes = old_num_nodes + nodes_to_add; |
if (map_size > 2 * new_num_nodes) { |
new_nstart = map + (map_size - new_num_nodes) / 2 |
+ (add_at_front ? nodes_to_add : 0); |
if (new_nstart < start.node) |
copy(start.node, finish.node + 1, new_nstart); |
copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes); |
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2; |
map_pointer new_map = map_allocator::allocate(new_map_size); |
new_nstart = new_map + (new_map_size - new_num_nodes) / 2 |
+ (add_at_front ? nodes_to_add : 0); |
copy(start.node, finish.node + 1, new_nstart); |
map_allocator::deallocate(map, map_size); |
start.set_node(new_nstart); |
finish.set_node(new_nstart + old_num_nodes - 1); |
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG |
template < class T, class Alloc, size_t BufSiz> |
bool operator==( const deque<T, Alloc, BufSiz>& x, |
const deque<T, Alloc, BufSiz>& y) { |
return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); |
template < class T, class Alloc, size_t BufSiz> |
bool operator<( const deque<T, Alloc, BufSiz>& x, |
const deque<T, Alloc, BufSiz>& y) { |
return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); |
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ |
#if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && \ |
!defined(__STL_NON_TYPE_TMPL_PARAM_BUG) |
template < class T, class Alloc, size_t BufSiz> |
inline void swap(deque<T, Alloc, BufSiz>& x, deque<T, Alloc, BufSiz>& y) { |
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) |
发表评论