]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Deque implementation (out of line) -*- C++ -*- |
2 | ||
dc2cf706 | 3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
12ffa228 | 4 | // 2009, 2010, 2011 |
1f9c69a9 | 5 | // Free Software Foundation, Inc. |
83144cfc PE |
6 | // |
7 | // This file is part of the GNU ISO C++ Library. This library is free | |
8 | // software; you can redistribute it and/or modify it under the | |
9 | // terms of the GNU General Public License as published by the | |
748086b7 | 10 | // Free Software Foundation; either version 3, or (at your option) |
83144cfc PE |
11 | // any later version. |
12 | ||
13 | // This library is distributed in the hope that it will be useful, | |
14 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | // GNU General Public License for more details. | |
17 | ||
748086b7 JJ |
18 | // Under Section 7 of GPL version 3, you are granted additional |
19 | // permissions described in the GCC Runtime Library Exception, version | |
20 | // 3.1, as published by the Free Software Foundation. | |
83144cfc | 21 | |
748086b7 JJ |
22 | // You should have received a copy of the GNU General Public License and |
23 | // a copy of the GCC Runtime Library Exception along with this program; | |
24 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
25 | // <http://www.gnu.org/licenses/>. | |
83144cfc PE |
26 | |
27 | /* | |
28 | * | |
29 | * Copyright (c) 1994 | |
30 | * Hewlett-Packard Company | |
31 | * | |
32 | * Permission to use, copy, modify, distribute and sell this software | |
33 | * and its documentation for any purpose is hereby granted without fee, | |
34 | * provided that the above copyright notice appear in all copies and | |
35 | * that both that copyright notice and this permission notice appear | |
36 | * in supporting documentation. Hewlett-Packard Company makes no | |
37 | * representations about the suitability of this software for any | |
38 | * purpose. It is provided "as is" without express or implied warranty. | |
39 | * | |
40 | * | |
41 | * Copyright (c) 1997 | |
42 | * Silicon Graphics Computer Systems, Inc. | |
43 | * | |
44 | * Permission to use, copy, modify, distribute and sell this software | |
45 | * and its documentation for any purpose is hereby granted without fee, | |
46 | * provided that the above copyright notice appear in all copies and | |
47 | * that both that copyright notice and this permission notice appear | |
48 | * in supporting documentation. Silicon Graphics makes no | |
49 | * representations about the suitability of this software for any | |
50 | * purpose. It is provided "as is" without express or implied warranty. | |
51 | */ | |
52 | ||
f910786b | 53 | /** @file bits/deque.tcc |
83144cfc | 54 | * This is an internal header file, included by other library headers. |
f910786b | 55 | * Do not attempt to use it directly. @headername{deque} |
83144cfc PE |
56 | */ |
57 | ||
3d7c150e BK |
58 | #ifndef _DEQUE_TCC |
59 | #define _DEQUE_TCC 1 | |
83144cfc | 60 | |
12ffa228 BK |
61 | namespace std _GLIBCXX_VISIBILITY(default) |
62 | { | |
63 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER | |
3cbc7af0 | 64 | |
dc2cf706 PC |
65 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
66 | template <typename _Tp, typename _Alloc> | |
67 | void | |
68 | deque<_Tp, _Alloc>:: | |
69 | _M_default_initialize() | |
70 | { | |
71 | _Map_pointer __cur; | |
72 | __try | |
73 | { | |
74 | for (__cur = this->_M_impl._M_start._M_node; | |
75 | __cur < this->_M_impl._M_finish._M_node; | |
76 | ++__cur) | |
77 | std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), | |
78 | _M_get_Tp_allocator()); | |
79 | std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, | |
80 | this->_M_impl._M_finish._M_cur, | |
81 | _M_get_Tp_allocator()); | |
82 | } | |
83 | __catch(...) | |
84 | { | |
85 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), | |
86 | _M_get_Tp_allocator()); | |
87 | __throw_exception_again; | |
88 | } | |
89 | } | |
90 | #endif | |
91 | ||
3971a4d2 | 92 | template <typename _Tp, typename _Alloc> |
23d4fa49 PC |
93 | deque<_Tp, _Alloc>& |
94 | deque<_Tp, _Alloc>:: | |
3971a4d2 | 95 | operator=(const deque& __x) |
83144cfc | 96 | { |
3971a4d2 PE |
97 | const size_type __len = size(); |
98 | if (&__x != this) | |
f6592a9e PC |
99 | { |
100 | if (__len >= __x.size()) | |
d2cc7f92 PC |
101 | _M_erase_at_end(std::copy(__x.begin(), __x.end(), |
102 | this->_M_impl._M_start)); | |
f6592a9e PC |
103 | else |
104 | { | |
105 | const_iterator __mid = __x.begin() + difference_type(__len); | |
03f9ea44 DM |
106 | std::copy(__x.begin(), __mid, this->_M_impl._M_start); |
107 | insert(this->_M_impl._M_finish, __mid, __x.end()); | |
f6592a9e PC |
108 | } |
109 | } | |
3971a4d2 | 110 | return *this; |
ed6814f7 BI |
111 | } |
112 | ||
4dc3e453 PC |
113 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
114 | template<typename _Tp, typename _Alloc> | |
115 | template<typename... _Args> | |
116 | void | |
117 | deque<_Tp, _Alloc>:: | |
118 | emplace_front(_Args&&... __args) | |
119 | { | |
120 | if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) | |
121 | { | |
122 | this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, | |
123 | std::forward<_Args>(__args)...); | |
124 | --this->_M_impl._M_start._M_cur; | |
125 | } | |
126 | else | |
127 | _M_push_front_aux(std::forward<_Args>(__args)...); | |
128 | } | |
129 | ||
130 | template<typename _Tp, typename _Alloc> | |
131 | template<typename... _Args> | |
132 | void | |
133 | deque<_Tp, _Alloc>:: | |
134 | emplace_back(_Args&&... __args) | |
135 | { | |
136 | if (this->_M_impl._M_finish._M_cur | |
137 | != this->_M_impl._M_finish._M_last - 1) | |
138 | { | |
139 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, | |
140 | std::forward<_Args>(__args)...); | |
141 | ++this->_M_impl._M_finish._M_cur; | |
142 | } | |
143 | else | |
144 | _M_push_back_aux(std::forward<_Args>(__args)...); | |
145 | } | |
146 | #endif | |
147 | ||
3971a4d2 | 148 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 149 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 150 | deque<_Tp, _Alloc>:: |
1b4454bf | 151 | insert(iterator __position, const value_type& __x) |
83144cfc | 152 | { |
1b4454bf | 153 | if (__position._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
154 | { |
155 | push_front(__x); | |
03f9ea44 | 156 | return this->_M_impl._M_start; |
f6592a9e | 157 | } |
1b4454bf | 158 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
159 | { |
160 | push_back(__x); | |
03f9ea44 | 161 | iterator __tmp = this->_M_impl._M_finish; |
f6592a9e PC |
162 | --__tmp; |
163 | return __tmp; | |
164 | } | |
83144cfc | 165 | else |
1b4454bf | 166 | return _M_insert_aux(__position, __x); |
83144cfc | 167 | } |
ed6814f7 | 168 | |
7ffec97f | 169 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
7ffec97f CJ |
170 | template<typename _Tp, typename _Alloc> |
171 | template<typename... _Args> | |
172 | typename deque<_Tp, _Alloc>::iterator | |
173 | deque<_Tp, _Alloc>:: | |
174 | emplace(iterator __position, _Args&&... __args) | |
175 | { | |
176 | if (__position._M_cur == this->_M_impl._M_start._M_cur) | |
177 | { | |
178 | push_front(std::forward<_Args>(__args)...); | |
179 | return this->_M_impl._M_start; | |
180 | } | |
181 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) | |
182 | { | |
183 | push_back(std::forward<_Args>(__args)...); | |
184 | iterator __tmp = this->_M_impl._M_finish; | |
185 | --__tmp; | |
186 | return __tmp; | |
187 | } | |
188 | else | |
189 | return _M_insert_aux(__position, std::forward<_Args>(__args)...); | |
190 | } | |
191 | #endif | |
192 | ||
3971a4d2 | 193 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 194 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 195 | deque<_Tp, _Alloc>:: |
3971a4d2 | 196 | erase(iterator __position) |
83144cfc | 197 | { |
3971a4d2 PE |
198 | iterator __next = __position; |
199 | ++__next; | |
1b4454bf PC |
200 | const difference_type __index = __position - begin(); |
201 | if (static_cast<size_type>(__index) < (size() >> 1)) | |
f6592a9e | 202 | { |
d2cc7f92 | 203 | if (__position != begin()) |
245a5fe5 | 204 | _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); |
f6592a9e PC |
205 | pop_front(); |
206 | } | |
3971a4d2 | 207 | else |
f6592a9e | 208 | { |
d2cc7f92 | 209 | if (__next != end()) |
245a5fe5 | 210 | _GLIBCXX_MOVE3(__next, end(), __position); |
f6592a9e PC |
211 | pop_back(); |
212 | } | |
d2cc7f92 | 213 | return begin() + __index; |
3971a4d2 | 214 | } |
ed6814f7 | 215 | |
3971a4d2 | 216 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 217 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 218 | deque<_Tp, _Alloc>:: |
3971a4d2 | 219 | erase(iterator __first, iterator __last) |
83144cfc | 220 | { |
d2cc7f92 | 221 | if (__first == begin() && __last == end()) |
f6592a9e PC |
222 | { |
223 | clear(); | |
d2cc7f92 | 224 | return end(); |
f6592a9e | 225 | } |
3971a4d2 | 226 | else |
f6592a9e PC |
227 | { |
228 | const difference_type __n = __last - __first; | |
d2cc7f92 | 229 | const difference_type __elems_before = __first - begin(); |
45dc23a6 | 230 | if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) |
f6592a9e | 231 | { |
d2cc7f92 | 232 | if (__first != begin()) |
245a5fe5 | 233 | _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); |
d2cc7f92 | 234 | _M_erase_at_begin(begin() + __n); |
f6592a9e PC |
235 | } |
236 | else | |
237 | { | |
d2cc7f92 | 238 | if (__last != end()) |
245a5fe5 | 239 | _GLIBCXX_MOVE3(__last, end(), __first); |
d2cc7f92 | 240 | _M_erase_at_end(end() - __n); |
f6592a9e | 241 | } |
d2cc7f92 | 242 | return begin() + __elems_before; |
f6592a9e | 243 | } |
3971a4d2 | 244 | } |
ed6814f7 | 245 | |
3971a4d2 | 246 | template <typename _Tp, class _Alloc> |
08addde6 | 247 | template <typename _InputIterator> |
3971a4d2 | 248 | void |
2fecaef4 PC |
249 | deque<_Tp, _Alloc>:: |
250 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
251 | std::input_iterator_tag) | |
83144cfc | 252 | { |
3971a4d2 | 253 | iterator __cur = begin(); |
43da93a7 | 254 | for (; __first != __last && __cur != end(); ++__cur, ++__first) |
3971a4d2 PE |
255 | *__cur = *__first; |
256 | if (__first == __last) | |
d2cc7f92 | 257 | _M_erase_at_end(__cur); |
3971a4d2 PE |
258 | else |
259 | insert(end(), __first, __last); | |
83144cfc | 260 | } |
ed6814f7 | 261 | |
3971a4d2 | 262 | template <typename _Tp, typename _Alloc> |
83144cfc | 263 | void |
43da93a7 | 264 | deque<_Tp, _Alloc>:: |
3971a4d2 | 265 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 266 | { |
03f9ea44 | 267 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
268 | { |
269 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
bc2631e0 | 270 | __try |
f6592a9e | 271 | { |
1985f1cd | 272 | std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, |
1b4454bf | 273 | __x, _M_get_Tp_allocator()); |
03f9ea44 | 274 | this->_M_impl._M_start = __new_start; |
f6592a9e | 275 | } |
bc2631e0 | 276 | __catch(...) |
f6592a9e | 277 | { |
0d8c9baf PC |
278 | _M_destroy_nodes(__new_start._M_node, |
279 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
280 | __throw_exception_again; |
281 | } | |
282 | } | |
03f9ea44 | 283 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
284 | { |
285 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
bc2631e0 | 286 | __try |
f6592a9e | 287 | { |
1985f1cd MA |
288 | std::__uninitialized_fill_a(this->_M_impl._M_finish, |
289 | __new_finish, __x, | |
4fd20a8f | 290 | _M_get_Tp_allocator()); |
03f9ea44 | 291 | this->_M_impl._M_finish = __new_finish; |
f6592a9e | 292 | } |
bc2631e0 | 293 | __catch(...) |
f6592a9e | 294 | { |
03f9ea44 | 295 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
ed6814f7 | 296 | __new_finish._M_node + 1); |
f6592a9e PC |
297 | __throw_exception_again; |
298 | } | |
299 | } | |
ed6814f7 | 300 | else |
3971a4d2 | 301 | _M_insert_aux(__pos, __n, __x); |
83144cfc | 302 | } |
ed6814f7 | 303 | |
dc2cf706 PC |
304 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
305 | template <typename _Tp, typename _Alloc> | |
306 | void | |
307 | deque<_Tp, _Alloc>:: | |
308 | _M_default_append(size_type __n) | |
309 | { | |
310 | if (__n) | |
311 | { | |
312 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
313 | __try | |
314 | { | |
315 | std::__uninitialized_default_a(this->_M_impl._M_finish, | |
316 | __new_finish, | |
317 | _M_get_Tp_allocator()); | |
318 | this->_M_impl._M_finish = __new_finish; | |
319 | } | |
320 | __catch(...) | |
321 | { | |
322 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, | |
323 | __new_finish._M_node + 1); | |
324 | __throw_exception_again; | |
325 | } | |
326 | } | |
327 | } | |
328 | #endif | |
329 | ||
3971a4d2 PE |
330 | template <typename _Tp, typename _Alloc> |
331 | void | |
43da93a7 | 332 | deque<_Tp, _Alloc>:: |
3971a4d2 | 333 | _M_fill_initialize(const value_type& __value) |
83144cfc | 334 | { |
3971a4d2 | 335 | _Map_pointer __cur; |
bc2631e0 | 336 | __try |
3971a4d2 | 337 | { |
03f9ea44 DM |
338 | for (__cur = this->_M_impl._M_start._M_node; |
339 | __cur < this->_M_impl._M_finish._M_node; | |
8fbc5ae7 | 340 | ++__cur) |
ba43cf0b | 341 | std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), |
4fd20a8f | 342 | __value, _M_get_Tp_allocator()); |
1985f1cd MA |
343 | std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, |
344 | this->_M_impl._M_finish._M_cur, | |
4fd20a8f | 345 | __value, _M_get_Tp_allocator()); |
3971a4d2 | 346 | } |
bc2631e0 | 347 | __catch(...) |
3971a4d2 | 348 | { |
1985f1cd | 349 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
4fd20a8f | 350 | _M_get_Tp_allocator()); |
3971a4d2 PE |
351 | __throw_exception_again; |
352 | } | |
83144cfc | 353 | } |
ed6814f7 | 354 | |
3971a4d2 PE |
355 | template <typename _Tp, typename _Alloc> |
356 | template <typename _InputIterator> | |
357 | void | |
43da93a7 | 358 | deque<_Tp, _Alloc>:: |
3971a4d2 | 359 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
6323b34e | 360 | std::input_iterator_tag) |
3971a4d2 | 361 | { |
f2ffecb1 | 362 | this->_M_initialize_map(0); |
bc2631e0 | 363 | __try |
3971a4d2 | 364 | { |
43da93a7 | 365 | for (; __first != __last; ++__first) |
3971a4d2 PE |
366 | push_back(*__first); |
367 | } | |
bc2631e0 | 368 | __catch(...) |
3971a4d2 PE |
369 | { |
370 | clear(); | |
371 | __throw_exception_again; | |
372 | } | |
373 | } | |
ed6814f7 | 374 | |
3971a4d2 PE |
375 | template <typename _Tp, typename _Alloc> |
376 | template <typename _ForwardIterator> | |
377 | void | |
43da93a7 | 378 | deque<_Tp, _Alloc>:: |
3971a4d2 | 379 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
6323b34e | 380 | std::forward_iterator_tag) |
3971a4d2 | 381 | { |
f6592a9e | 382 | const size_type __n = std::distance(__first, __last); |
f2ffecb1 | 383 | this->_M_initialize_map(__n); |
ed6814f7 | 384 | |
3971a4d2 | 385 | _Map_pointer __cur_node; |
bc2631e0 | 386 | __try |
3971a4d2 | 387 | { |
03f9ea44 DM |
388 | for (__cur_node = this->_M_impl._M_start._M_node; |
389 | __cur_node < this->_M_impl._M_finish._M_node; | |
3971a4d2 | 390 | ++__cur_node) |
1f9c69a9 PC |
391 | { |
392 | _ForwardIterator __mid = __first; | |
393 | std::advance(__mid, _S_buffer_size()); | |
394 | std::__uninitialized_copy_a(__first, __mid, *__cur_node, | |
395 | _M_get_Tp_allocator()); | |
396 | __first = __mid; | |
397 | } | |
1985f1cd MA |
398 | std::__uninitialized_copy_a(__first, __last, |
399 | this->_M_impl._M_finish._M_first, | |
4fd20a8f | 400 | _M_get_Tp_allocator()); |
3971a4d2 | 401 | } |
bc2631e0 | 402 | __catch(...) |
3971a4d2 | 403 | { |
0d8c9baf | 404 | std::_Destroy(this->_M_impl._M_start, |
1985f1cd | 405 | iterator(*__cur_node, __cur_node), |
4fd20a8f | 406 | _M_get_Tp_allocator()); |
3971a4d2 PE |
407 | __throw_exception_again; |
408 | } | |
409 | } | |
ed6814f7 | 410 | |
03f9ea44 | 411 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
7ffec97f CJ |
412 | template<typename _Tp, typename _Alloc> |
413 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
414 | template<typename... _Args> | |
415 | void | |
416 | deque<_Tp, _Alloc>:: | |
417 | _M_push_back_aux(_Args&&... __args) | |
7ffec97f CJ |
418 | #else |
419 | void | |
420 | deque<_Tp, _Alloc>:: | |
421 | _M_push_back_aux(const value_type& __t) | |
7ffec97f | 422 | #endif |
b4d9ec93 | 423 | { |
7ffec97f CJ |
424 | _M_reserve_map_at_back(); |
425 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); | |
bc2631e0 | 426 | __try |
7ffec97f | 427 | { |
b4d9ec93 | 428 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
7ffec97f | 429 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, |
b4d9ec93 PC |
430 | std::forward<_Args>(__args)...); |
431 | #else | |
432 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); | |
433 | #endif | |
7ffec97f CJ |
434 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
435 | + 1); | |
436 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; | |
437 | } | |
bc2631e0 | 438 | __catch(...) |
7ffec97f CJ |
439 | { |
440 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); | |
441 | __throw_exception_again; | |
442 | } | |
443 | } | |
ed6814f7 | 444 | |
03f9ea44 | 445 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
7ffec97f CJ |
446 | template<typename _Tp, typename _Alloc> |
447 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
448 | template<typename... _Args> | |
449 | void | |
450 | deque<_Tp, _Alloc>:: | |
451 | _M_push_front_aux(_Args&&... __args) | |
7ffec97f CJ |
452 | #else |
453 | void | |
454 | deque<_Tp, _Alloc>:: | |
455 | _M_push_front_aux(const value_type& __t) | |
7ffec97f | 456 | #endif |
b4d9ec93 | 457 | { |
7ffec97f CJ |
458 | _M_reserve_map_at_front(); |
459 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); | |
bc2631e0 | 460 | __try |
7ffec97f CJ |
461 | { |
462 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node | |
463 | - 1); | |
464 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; | |
b4d9ec93 | 465 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
7ffec97f | 466 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, |
b4d9ec93 PC |
467 | std::forward<_Args>(__args)...); |
468 | #else | |
469 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); | |
470 | #endif | |
7ffec97f | 471 | } |
bc2631e0 | 472 | __catch(...) |
7ffec97f CJ |
473 | { |
474 | ++this->_M_impl._M_start; | |
475 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); | |
476 | __throw_exception_again; | |
477 | } | |
478 | } | |
ed6814f7 | 479 | |
03f9ea44 | 480 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
3971a4d2 | 481 | template <typename _Tp, typename _Alloc> |
43da93a7 | 482 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
483 | _M_pop_back_aux() |
484 | { | |
03f9ea44 DM |
485 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
486 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); | |
487 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; | |
1985f1cd | 488 | this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); |
83144cfc | 489 | } |
ed6814f7 | 490 | |
0d8c9baf PC |
491 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
492 | // Note that if the deque has at least one element (a precondition for this | |
493 | // member function), and if | |
494 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, | |
495 | // then the deque must have at least two nodes. | |
3971a4d2 | 496 | template <typename _Tp, typename _Alloc> |
43da93a7 | 497 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
498 | _M_pop_front_aux() |
499 | { | |
1985f1cd | 500 | this->_M_impl.destroy(this->_M_impl._M_start._M_cur); |
03f9ea44 DM |
501 | _M_deallocate_node(this->_M_impl._M_start._M_first); |
502 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); | |
503 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; | |
ed6814f7 BI |
504 | } |
505 | ||
3971a4d2 PE |
506 | template <typename _Tp, typename _Alloc> |
507 | template <typename _InputIterator> | |
508 | void | |
43da93a7 | 509 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
510 | _M_range_insert_aux(iterator __pos, |
511 | _InputIterator __first, _InputIterator __last, | |
6323b34e | 512 | std::input_iterator_tag) |
f6592a9e | 513 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
ed6814f7 | 514 | |
3971a4d2 PE |
515 | template <typename _Tp, typename _Alloc> |
516 | template <typename _ForwardIterator> | |
517 | void | |
43da93a7 | 518 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
519 | _M_range_insert_aux(iterator __pos, |
520 | _ForwardIterator __first, _ForwardIterator __last, | |
6323b34e | 521 | std::forward_iterator_tag) |
3971a4d2 | 522 | { |
43da93a7 | 523 | const size_type __n = std::distance(__first, __last); |
03f9ea44 | 524 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
525 | { |
526 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
bc2631e0 | 527 | __try |
f6592a9e | 528 | { |
1985f1cd | 529 | std::__uninitialized_copy_a(__first, __last, __new_start, |
4fd20a8f | 530 | _M_get_Tp_allocator()); |
03f9ea44 | 531 | this->_M_impl._M_start = __new_start; |
f6592a9e | 532 | } |
bc2631e0 | 533 | __catch(...) |
f6592a9e | 534 | { |
0d8c9baf PC |
535 | _M_destroy_nodes(__new_start._M_node, |
536 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
537 | __throw_exception_again; |
538 | } | |
539 | } | |
03f9ea44 | 540 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
541 | { |
542 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
bc2631e0 | 543 | __try |
f6592a9e | 544 | { |
1985f1cd MA |
545 | std::__uninitialized_copy_a(__first, __last, |
546 | this->_M_impl._M_finish, | |
4fd20a8f | 547 | _M_get_Tp_allocator()); |
03f9ea44 | 548 | this->_M_impl._M_finish = __new_finish; |
f6592a9e | 549 | } |
bc2631e0 | 550 | __catch(...) |
f6592a9e | 551 | { |
03f9ea44 | 552 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
553 | __new_finish._M_node + 1); |
554 | __throw_exception_again; | |
555 | } | |
556 | } | |
3971a4d2 PE |
557 | else |
558 | _M_insert_aux(__pos, __first, __last, __n); | |
559 | } | |
ed6814f7 | 560 | |
7ffec97f CJ |
561 | template<typename _Tp, typename _Alloc> |
562 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
563 | template<typename... _Args> | |
564 | typename deque<_Tp, _Alloc>::iterator | |
565 | deque<_Tp, _Alloc>:: | |
566 | _M_insert_aux(iterator __pos, _Args&&... __args) | |
567 | { | |
568 | value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy | |
569 | #else | |
3971a4d2 | 570 | typename deque<_Tp, _Alloc>::iterator |
7ffec97f CJ |
571 | deque<_Tp, _Alloc>:: |
572 | _M_insert_aux(iterator __pos, const value_type& __x) | |
573 | { | |
574 | value_type __x_copy = __x; // XXX copy | |
575 | #endif | |
576 | difference_type __index = __pos - this->_M_impl._M_start; | |
577 | if (static_cast<size_type>(__index) < size() / 2) | |
578 | { | |
579 | push_front(_GLIBCXX_MOVE(front())); | |
580 | iterator __front1 = this->_M_impl._M_start; | |
581 | ++__front1; | |
582 | iterator __front2 = __front1; | |
583 | ++__front2; | |
584 | __pos = this->_M_impl._M_start + __index; | |
585 | iterator __pos1 = __pos; | |
586 | ++__pos1; | |
587 | _GLIBCXX_MOVE3(__front2, __pos1, __front1); | |
588 | } | |
589 | else | |
590 | { | |
591 | push_back(_GLIBCXX_MOVE(back())); | |
592 | iterator __back1 = this->_M_impl._M_finish; | |
593 | --__back1; | |
594 | iterator __back2 = __back1; | |
595 | --__back2; | |
596 | __pos = this->_M_impl._M_start + __index; | |
597 | _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); | |
598 | } | |
599 | *__pos = _GLIBCXX_MOVE(__x_copy); | |
600 | return __pos; | |
601 | } | |
ed6814f7 | 602 | |
3971a4d2 | 603 | template <typename _Tp, typename _Alloc> |
83144cfc | 604 | void |
43da93a7 | 605 | deque<_Tp, _Alloc>:: |
3971a4d2 | 606 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 607 | { |
03f9ea44 | 608 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
43da93a7 | 609 | const size_type __length = this->size(); |
3971a4d2 PE |
610 | value_type __x_copy = __x; |
611 | if (__elems_before < difference_type(__length / 2)) | |
f6592a9e PC |
612 | { |
613 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
614 | iterator __old_start = this->_M_impl._M_start; |
615 | __pos = this->_M_impl._M_start + __elems_before; | |
bc2631e0 | 616 | __try |
f6592a9e PC |
617 | { |
618 | if (__elems_before >= difference_type(__n)) | |
619 | { | |
0d8c9baf PC |
620 | iterator __start_n = (this->_M_impl._M_start |
621 | + difference_type(__n)); | |
7ffec97f | 622 | std::__uninitialized_move_a(this->_M_impl._M_start, |
ba43cf0b | 623 | __start_n, __new_start, |
4fd20a8f | 624 | _M_get_Tp_allocator()); |
03f9ea44 | 625 | this->_M_impl._M_start = __new_start; |
7ffec97f | 626 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
1b4454bf | 627 | std::fill(__pos - difference_type(__n), __pos, __x_copy); |
f6592a9e PC |
628 | } |
629 | else | |
630 | { | |
7ffec97f | 631 | std::__uninitialized_move_fill(this->_M_impl._M_start, |
0d8c9baf PC |
632 | __pos, __new_start, |
633 | this->_M_impl._M_start, | |
1985f1cd | 634 | __x_copy, |
4fd20a8f | 635 | _M_get_Tp_allocator()); |
03f9ea44 | 636 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
637 | std::fill(__old_start, __pos, __x_copy); |
638 | } | |
639 | } | |
bc2631e0 | 640 | __catch(...) |
ed6814f7 | 641 | { |
0d8c9baf PC |
642 | _M_destroy_nodes(__new_start._M_node, |
643 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
644 | __throw_exception_again; |
645 | } | |
646 | } | |
83144cfc | 647 | else |
f6592a9e PC |
648 | { |
649 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 650 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 651 | const difference_type __elems_after = |
f6592a9e | 652 | difference_type(__length) - __elems_before; |
03f9ea44 | 653 | __pos = this->_M_impl._M_finish - __elems_after; |
bc2631e0 | 654 | __try |
f6592a9e PC |
655 | { |
656 | if (__elems_after > difference_type(__n)) | |
657 | { | |
0d8c9baf PC |
658 | iterator __finish_n = (this->_M_impl._M_finish |
659 | - difference_type(__n)); | |
7ffec97f | 660 | std::__uninitialized_move_a(__finish_n, |
ba43cf0b | 661 | this->_M_impl._M_finish, |
1985f1cd | 662 | this->_M_impl._M_finish, |
4fd20a8f | 663 | _M_get_Tp_allocator()); |
03f9ea44 | 664 | this->_M_impl._M_finish = __new_finish; |
7ffec97f | 665 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
f6592a9e PC |
666 | std::fill(__pos, __pos + difference_type(__n), __x_copy); |
667 | } | |
668 | else | |
669 | { | |
7ffec97f | 670 | std::__uninitialized_fill_move(this->_M_impl._M_finish, |
f6592a9e PC |
671 | __pos + difference_type(__n), |
672 | __x_copy, __pos, | |
1985f1cd | 673 | this->_M_impl._M_finish, |
4fd20a8f | 674 | _M_get_Tp_allocator()); |
03f9ea44 | 675 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
676 | std::fill(__pos, __old_finish, __x_copy); |
677 | } | |
678 | } | |
bc2631e0 | 679 | __catch(...) |
ed6814f7 | 680 | { |
03f9ea44 | 681 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
682 | __new_finish._M_node + 1); |
683 | __throw_exception_again; | |
684 | } | |
685 | } | |
83144cfc | 686 | } |
ed6814f7 | 687 | |
3971a4d2 PE |
688 | template <typename _Tp, typename _Alloc> |
689 | template <typename _ForwardIterator> | |
690 | void | |
43da93a7 | 691 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
692 | _M_insert_aux(iterator __pos, |
693 | _ForwardIterator __first, _ForwardIterator __last, | |
694 | size_type __n) | |
83144cfc | 695 | { |
03f9ea44 | 696 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
43da93a7 | 697 | const size_type __length = size(); |
3971a4d2 | 698 | if (static_cast<size_type>(__elemsbefore) < __length / 2) |
f6592a9e PC |
699 | { |
700 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
701 | iterator __old_start = this->_M_impl._M_start; |
702 | __pos = this->_M_impl._M_start + __elemsbefore; | |
bc2631e0 | 703 | __try |
f6592a9e PC |
704 | { |
705 | if (__elemsbefore >= difference_type(__n)) | |
706 | { | |
0d8c9baf PC |
707 | iterator __start_n = (this->_M_impl._M_start |
708 | + difference_type(__n)); | |
7ffec97f | 709 | std::__uninitialized_move_a(this->_M_impl._M_start, |
ba43cf0b | 710 | __start_n, __new_start, |
4fd20a8f | 711 | _M_get_Tp_allocator()); |
03f9ea44 | 712 | this->_M_impl._M_start = __new_start; |
7ffec97f | 713 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
f6592a9e PC |
714 | std::copy(__first, __last, __pos - difference_type(__n)); |
715 | } | |
716 | else | |
717 | { | |
718 | _ForwardIterator __mid = __first; | |
719 | std::advance(__mid, difference_type(__n) - __elemsbefore); | |
7ffec97f | 720 | std::__uninitialized_move_copy(this->_M_impl._M_start, |
0d8c9baf | 721 | __pos, __first, __mid, |
1985f1cd | 722 | __new_start, |
4fd20a8f | 723 | _M_get_Tp_allocator()); |
03f9ea44 | 724 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
725 | std::copy(__mid, __last, __old_start); |
726 | } | |
727 | } | |
bc2631e0 | 728 | __catch(...) |
f6592a9e | 729 | { |
0d8c9baf PC |
730 | _M_destroy_nodes(__new_start._M_node, |
731 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
732 | __throw_exception_again; |
733 | } | |
734 | } | |
3971a4d2 PE |
735 | else |
736 | { | |
737 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 738 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 739 | const difference_type __elemsafter = |
3971a4d2 | 740 | difference_type(__length) - __elemsbefore; |
03f9ea44 | 741 | __pos = this->_M_impl._M_finish - __elemsafter; |
bc2631e0 | 742 | __try |
3971a4d2 PE |
743 | { |
744 | if (__elemsafter > difference_type(__n)) | |
f6592a9e | 745 | { |
0d8c9baf PC |
746 | iterator __finish_n = (this->_M_impl._M_finish |
747 | - difference_type(__n)); | |
7ffec97f | 748 | std::__uninitialized_move_a(__finish_n, |
1985f1cd MA |
749 | this->_M_impl._M_finish, |
750 | this->_M_impl._M_finish, | |
4fd20a8f | 751 | _M_get_Tp_allocator()); |
03f9ea44 | 752 | this->_M_impl._M_finish = __new_finish; |
7ffec97f | 753 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
f6592a9e PC |
754 | std::copy(__first, __last, __pos); |
755 | } | |
3971a4d2 | 756 | else |
f6592a9e PC |
757 | { |
758 | _ForwardIterator __mid = __first; | |
759 | std::advance(__mid, __elemsafter); | |
7ffec97f | 760 | std::__uninitialized_copy_move(__mid, __last, __pos, |
03f9ea44 | 761 | this->_M_impl._M_finish, |
1985f1cd | 762 | this->_M_impl._M_finish, |
4fd20a8f | 763 | _M_get_Tp_allocator()); |
03f9ea44 | 764 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
765 | std::copy(__first, __mid, __pos); |
766 | } | |
3971a4d2 | 767 | } |
bc2631e0 | 768 | __catch(...) |
3971a4d2 | 769 | { |
03f9ea44 | 770 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
8fbc5ae7 | 771 | __new_finish._M_node + 1); |
3971a4d2 PE |
772 | __throw_exception_again; |
773 | } | |
774 | } | |
83144cfc | 775 | } |
ed6814f7 | 776 | |
d2cc7f92 PC |
777 | template<typename _Tp, typename _Alloc> |
778 | void | |
779 | deque<_Tp, _Alloc>:: | |
780 | _M_destroy_data_aux(iterator __first, iterator __last) | |
781 | { | |
782 | for (_Map_pointer __node = __first._M_node + 1; | |
783 | __node < __last._M_node; ++__node) | |
784 | std::_Destroy(*__node, *__node + _S_buffer_size(), | |
785 | _M_get_Tp_allocator()); | |
786 | ||
787 | if (__first._M_node != __last._M_node) | |
788 | { | |
789 | std::_Destroy(__first._M_cur, __first._M_last, | |
790 | _M_get_Tp_allocator()); | |
791 | std::_Destroy(__last._M_first, __last._M_cur, | |
792 | _M_get_Tp_allocator()); | |
793 | } | |
794 | else | |
795 | std::_Destroy(__first._M_cur, __last._M_cur, | |
796 | _M_get_Tp_allocator()); | |
797 | } | |
798 | ||
3971a4d2 PE |
799 | template <typename _Tp, typename _Alloc> |
800 | void | |
43da93a7 | 801 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
802 | _M_new_elements_at_front(size_type __new_elems) |
803 | { | |
1f9c69a9 PC |
804 | if (this->max_size() - this->size() < __new_elems) |
805 | __throw_length_error(__N("deque::_M_new_elements_at_front")); | |
806 | ||
807 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) | |
808 | / _S_buffer_size()); | |
3971a4d2 PE |
809 | _M_reserve_map_at_front(__new_nodes); |
810 | size_type __i; | |
bc2631e0 | 811 | __try |
3971a4d2 PE |
812 | { |
813 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 814 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); |
3971a4d2 | 815 | } |
bc2631e0 | 816 | __catch(...) |
3971a4d2 PE |
817 | { |
818 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 819 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); |
3971a4d2 PE |
820 | __throw_exception_again; |
821 | } | |
822 | } | |
ed6814f7 | 823 | |
3971a4d2 PE |
824 | template <typename _Tp, typename _Alloc> |
825 | void | |
43da93a7 | 826 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
827 | _M_new_elements_at_back(size_type __new_elems) |
828 | { | |
1f9c69a9 PC |
829 | if (this->max_size() - this->size() < __new_elems) |
830 | __throw_length_error(__N("deque::_M_new_elements_at_back")); | |
831 | ||
832 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) | |
833 | / _S_buffer_size()); | |
3971a4d2 PE |
834 | _M_reserve_map_at_back(__new_nodes); |
835 | size_type __i; | |
bc2631e0 | 836 | __try |
3971a4d2 PE |
837 | { |
838 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 839 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); |
3971a4d2 | 840 | } |
bc2631e0 | 841 | __catch(...) |
3971a4d2 PE |
842 | { |
843 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 844 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); |
3971a4d2 PE |
845 | __throw_exception_again; |
846 | } | |
847 | } | |
ed6814f7 | 848 | |
3971a4d2 PE |
849 | template <typename _Tp, typename _Alloc> |
850 | void | |
43da93a7 | 851 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
852 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
853 | { | |
43da93a7 | 854 | const size_type __old_num_nodes |
03f9ea44 | 855 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
43da93a7 | 856 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
ed6814f7 | 857 | |
3971a4d2 | 858 | _Map_pointer __new_nstart; |
03f9ea44 | 859 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
f6592a9e | 860 | { |
03f9ea44 | 861 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
ed6814f7 | 862 | - __new_num_nodes) / 2 |
f6592a9e | 863 | + (__add_at_front ? __nodes_to_add : 0); |
03f9ea44 DM |
864 | if (__new_nstart < this->_M_impl._M_start._M_node) |
865 | std::copy(this->_M_impl._M_start._M_node, | |
1f9c69a9 PC |
866 | this->_M_impl._M_finish._M_node + 1, |
867 | __new_nstart); | |
f6592a9e | 868 | else |
03f9ea44 DM |
869 | std::copy_backward(this->_M_impl._M_start._M_node, |
870 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e PC |
871 | __new_nstart + __old_num_nodes); |
872 | } | |
3971a4d2 | 873 | else |
f6592a9e | 874 | { |
03f9ea44 DM |
875 | size_type __new_map_size = this->_M_impl._M_map_size |
876 | + std::max(this->_M_impl._M_map_size, | |
f6592a9e | 877 | __nodes_to_add) + 2; |
ed6814f7 | 878 | |
f6592a9e PC |
879 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
880 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 | |
881 | + (__add_at_front ? __nodes_to_add : 0); | |
03f9ea44 DM |
882 | std::copy(this->_M_impl._M_start._M_node, |
883 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e | 884 | __new_nstart); |
03f9ea44 | 885 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
ed6814f7 | 886 | |
03f9ea44 DM |
887 | this->_M_impl._M_map = __new_map; |
888 | this->_M_impl._M_map_size = __new_map_size; | |
f6592a9e | 889 | } |
ed6814f7 | 890 | |
03f9ea44 DM |
891 | this->_M_impl._M_start._M_set_node(__new_nstart); |
892 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); | |
83144cfc | 893 | } |
3cbc7af0 | 894 | |
62c7a041 | 895 | // Overload for deque::iterators, exploiting the "segmented-iterator |
e2bf2007 | 896 | // optimization". |
62c7a041 PC |
897 | template<typename _Tp> |
898 | void | |
899 | fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, | |
900 | const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) | |
901 | { | |
902 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; | |
903 | ||
904 | for (typename _Self::_Map_pointer __node = __first._M_node + 1; | |
905 | __node < __last._M_node; ++__node) | |
906 | std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); | |
907 | ||
908 | if (__first._M_node != __last._M_node) | |
909 | { | |
910 | std::fill(__first._M_cur, __first._M_last, __value); | |
911 | std::fill(__last._M_first, __last._M_cur, __value); | |
912 | } | |
913 | else | |
914 | std::fill(__first._M_cur, __last._M_cur, __value); | |
915 | } | |
916 | ||
e2bf2007 PC |
917 | template<typename _Tp> |
918 | _Deque_iterator<_Tp, _Tp&, _Tp*> | |
919 | copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, | |
920 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, | |
921 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
922 | { | |
923 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; | |
0800b8ea | 924 | typedef typename _Self::difference_type difference_type; |
e2bf2007 | 925 | |
0800b8ea | 926 | difference_type __len = __last - __first; |
e2bf2007 PC |
927 | while (__len > 0) |
928 | { | |
0800b8ea | 929 | const difference_type __clen |
e2bf2007 PC |
930 | = std::min(__len, std::min(__first._M_last - __first._M_cur, |
931 | __result._M_last - __result._M_cur)); | |
932 | std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); | |
933 | __first += __clen; | |
934 | __result += __clen; | |
935 | __len -= __clen; | |
936 | } | |
937 | return __result; | |
938 | } | |
939 | ||
0800b8ea PC |
940 | template<typename _Tp> |
941 | _Deque_iterator<_Tp, _Tp&, _Tp*> | |
942 | copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, | |
943 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, | |
944 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
945 | { | |
946 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; | |
947 | typedef typename _Self::difference_type difference_type; | |
948 | ||
949 | difference_type __len = __last - __first; | |
950 | while (__len > 0) | |
951 | { | |
952 | difference_type __llen = __last._M_cur - __last._M_first; | |
953 | _Tp* __lend = __last._M_cur; | |
954 | ||
955 | difference_type __rlen = __result._M_cur - __result._M_first; | |
956 | _Tp* __rend = __result._M_cur; | |
957 | ||
958 | if (!__llen) | |
959 | { | |
960 | __llen = _Self::_S_buffer_size(); | |
961 | __lend = *(__last._M_node - 1) + __llen; | |
962 | } | |
963 | if (!__rlen) | |
964 | { | |
965 | __rlen = _Self::_S_buffer_size(); | |
966 | __rend = *(__result._M_node - 1) + __rlen; | |
967 | } | |
968 | ||
969 | const difference_type __clen = std::min(__len, | |
970 | std::min(__llen, __rlen)); | |
971 | std::copy_backward(__lend - __clen, __lend, __rend); | |
972 | __last -= __clen; | |
973 | __result -= __clen; | |
974 | __len -= __clen; | |
975 | } | |
976 | return __result; | |
977 | } | |
978 | ||
e2bf2007 PC |
979 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
980 | template<typename _Tp> | |
981 | _Deque_iterator<_Tp, _Tp&, _Tp*> | |
982 | move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, | |
983 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, | |
984 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
985 | { | |
986 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; | |
0800b8ea | 987 | typedef typename _Self::difference_type difference_type; |
e2bf2007 | 988 | |
0800b8ea | 989 | difference_type __len = __last - __first; |
e2bf2007 PC |
990 | while (__len > 0) |
991 | { | |
0800b8ea | 992 | const difference_type __clen |
e2bf2007 PC |
993 | = std::min(__len, std::min(__first._M_last - __first._M_cur, |
994 | __result._M_last - __result._M_cur)); | |
995 | std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); | |
996 | __first += __clen; | |
997 | __result += __clen; | |
998 | __len -= __clen; | |
999 | } | |
1000 | return __result; | |
1001 | } | |
0800b8ea PC |
1002 | |
1003 | template<typename _Tp> | |
1004 | _Deque_iterator<_Tp, _Tp&, _Tp*> | |
1005 | move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, | |
1006 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, | |
1007 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
1008 | { | |
1009 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; | |
1010 | typedef typename _Self::difference_type difference_type; | |
1011 | ||
1012 | difference_type __len = __last - __first; | |
1013 | while (__len > 0) | |
1014 | { | |
1015 | difference_type __llen = __last._M_cur - __last._M_first; | |
1016 | _Tp* __lend = __last._M_cur; | |
1017 | ||
1018 | difference_type __rlen = __result._M_cur - __result._M_first; | |
1019 | _Tp* __rend = __result._M_cur; | |
1020 | ||
1021 | if (!__llen) | |
1022 | { | |
1023 | __llen = _Self::_S_buffer_size(); | |
1024 | __lend = *(__last._M_node - 1) + __llen; | |
1025 | } | |
1026 | if (!__rlen) | |
1027 | { | |
1028 | __rlen = _Self::_S_buffer_size(); | |
1029 | __rend = *(__result._M_node - 1) + __rlen; | |
1030 | } | |
1031 | ||
1032 | const difference_type __clen = std::min(__len, | |
1033 | std::min(__llen, __rlen)); | |
1034 | std::move_backward(__lend - __clen, __lend, __rend); | |
1035 | __last -= __clen; | |
1036 | __result -= __clen; | |
1037 | __len -= __clen; | |
1038 | } | |
1039 | return __result; | |
1040 | } | |
e2bf2007 PC |
1041 | #endif |
1042 | ||
12ffa228 BK |
1043 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1044 | } // namespace std | |
f6592a9e | 1045 | |
3d7c150e | 1046 | #endif |