Branch data Line data Source code
1 : : // Deque implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 : : // 2011 Free Software Foundation, Inc.
5 : : //
6 : : // This file is part of the GNU ISO C++ Library. This library is free
7 : : // software; you can redistribute it and/or modify it under the
8 : : // terms of the GNU General Public License as published by the
9 : : // Free Software Foundation; either version 3, or (at your option)
10 : : // any later version.
11 : :
12 : : // This library is distributed in the hope that it will be useful,
13 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : // GNU General Public License for more details.
16 : :
17 : : // Under Section 7 of GPL version 3, you are granted additional
18 : : // permissions described in the GCC Runtime Library Exception, version
19 : : // 3.1, as published by the Free Software Foundation.
20 : :
21 : : // You should have received a copy of the GNU General Public License and
22 : : // a copy of the GCC Runtime Library Exception along with this program;
23 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 : : // <http://www.gnu.org/licenses/>.
25 : :
26 : : /*
27 : : *
28 : : * Copyright (c) 1994
29 : : * Hewlett-Packard Company
30 : : *
31 : : * Permission to use, copy, modify, distribute and sell this software
32 : : * and its documentation for any purpose is hereby granted without fee,
33 : : * provided that the above copyright notice appear in all copies and
34 : : * that both that copyright notice and this permission notice appear
35 : : * in supporting documentation. Hewlett-Packard Company makes no
36 : : * representations about the suitability of this software for any
37 : : * purpose. It is provided "as is" without express or implied warranty.
38 : : *
39 : : *
40 : : * Copyright (c) 1997
41 : : * Silicon Graphics Computer Systems, Inc.
42 : : *
43 : : * Permission to use, copy, modify, distribute and sell this software
44 : : * and its documentation for any purpose is hereby granted without fee,
45 : : * provided that the above copyright notice appear in all copies and
46 : : * that both that copyright notice and this permission notice appear
47 : : * in supporting documentation. Silicon Graphics makes no
48 : : * representations about the suitability of this software for any
49 : : * purpose. It is provided "as is" without express or implied warranty.
50 : : */
51 : :
52 : : /** @file bits/stl_deque.h
53 : : * This is an internal header file, included by other library headers.
54 : : * Do not attempt to use it directly. @headername{deque}
55 : : */
56 : :
57 : : #ifndef _STL_DEQUE_H
58 : : #define _STL_DEQUE_H 1
59 : :
60 : : #include <bits/concept_check.h>
61 : : #include <bits/stl_iterator_base_types.h>
62 : : #include <bits/stl_iterator_base_funcs.h>
63 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
64 : : #include <initializer_list>
65 : : #endif
66 : :
67 : : namespace std _GLIBCXX_VISIBILITY(default)
68 : : {
69 : : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
70 : :
71 : : /**
72 : : * @brief This function controls the size of memory nodes.
73 : : * @param __size The size of an element.
74 : : * @return The number (not byte size) of elements per node.
75 : : *
76 : : * This function started off as a compiler kludge from SGI, but
77 : : * seems to be a useful wrapper around a repeated constant
78 : : * expression. The @b 512 is tunable (and no other code needs to
79 : : * change), but no investigation has been done since inheriting the
80 : : * SGI code. Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
81 : : * you are doing, however: changing it breaks the binary
82 : : * compatibility!!
83 : : */
84 : :
85 : : #ifndef _GLIBCXX_DEQUE_BUF_SIZE
86 : : #define _GLIBCXX_DEQUE_BUF_SIZE 512
87 : : #endif
88 : :
89 : : inline size_t
90 : 21725564 : __deque_buf_size(size_t __size)
91 : : { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
92 [ + - ]: 21725564 : ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
93 : :
94 : :
95 : : /**
96 : : * @brief A deque::iterator.
97 : : *
98 : : * Quite a bit of intelligence here. Much of the functionality of
99 : : * deque is actually passed off to this class. A deque holds two
100 : : * of these internally, marking its valid range. Access to
101 : : * elements is done as offsets of either of those two, relying on
102 : : * operator overloading in this class.
103 : : *
104 : : * All the functions are op overloads except for _M_set_node.
105 : : */
106 : : template<typename _Tp, typename _Ref, typename _Ptr>
107 : : struct _Deque_iterator
108 : : {
109 : : typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
110 : : typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
111 : :
112 : 9370062 : static size_t _S_buffer_size()
113 : 9370062 : { return __deque_buf_size(sizeof(_Tp)); }
114 : :
115 : : typedef std::random_access_iterator_tag iterator_category;
116 : : typedef _Tp value_type;
117 : : typedef _Ptr pointer;
118 : : typedef _Ref reference;
119 : : typedef size_t size_type;
120 : : typedef ptrdiff_t difference_type;
121 : : typedef _Tp** _Map_pointer;
122 : : typedef _Deque_iterator _Self;
123 : :
124 : : _Tp* _M_cur;
125 : : _Tp* _M_first;
126 : : _Tp* _M_last;
127 : : _Map_pointer _M_node;
128 : :
129 : 0 : _Deque_iterator(_Tp* __x, _Map_pointer __y)
130 : : : _M_cur(__x), _M_first(*__y),
131 : 0 : _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
132 : :
133 : 6179578 : _Deque_iterator()
134 : 6179578 : : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
135 : :
136 : 65064020 : _Deque_iterator(const iterator& __x)
137 : : : _M_cur(__x._M_cur), _M_first(__x._M_first),
138 : 65064020 : _M_last(__x._M_last), _M_node(__x._M_node) { }
139 : :
140 : : reference
141 : 40959058 : operator*() const
142 : 40959058 : { return *_M_cur; }
143 : :
144 : : pointer
145 : : operator->() const
146 : : { return _M_cur; }
147 : :
148 : : _Self&
149 : 0 : operator++()
150 : : {
151 : 0 : ++_M_cur;
152 [ # # ][ # # ]: 0 : if (_M_cur == _M_last)
[ # # ][ # # ]
[ # # ][ # # ]
153 : : {
154 : 0 : _M_set_node(_M_node + 1);
155 : 0 : _M_cur = _M_first;
156 : : }
157 : 0 : return *this;
158 : : }
159 : :
160 : : _Self
161 : : operator++(int)
162 : : {
163 : : _Self __tmp = *this;
164 : : ++*this;
165 : : return __tmp;
166 : : }
167 : :
168 : : _Self&
169 : 40858051 : operator--()
170 : : {
171 [ - + ][ - + ]: 40858051 : if (_M_cur == _M_first)
[ - + ]
172 : : {
173 : 0 : _M_set_node(_M_node - 1);
174 : 0 : _M_cur = _M_last;
175 : : }
176 : 40858051 : --_M_cur;
177 : 40858051 : return *this;
178 : : }
179 : :
180 : : _Self
181 : : operator--(int)
182 : : {
183 : : _Self __tmp = *this;
184 : : --*this;
185 : : return __tmp;
186 : : }
187 : :
188 : : _Self&
189 : : operator+=(difference_type __n)
190 : : {
191 : : const difference_type __offset = __n + (_M_cur - _M_first);
192 : : if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
193 : : _M_cur += __n;
194 : : else
195 : : {
196 : : const difference_type __node_offset =
197 : : __offset > 0 ? __offset / difference_type(_S_buffer_size())
198 : : : -difference_type((-__offset - 1)
199 : : / _S_buffer_size()) - 1;
200 : : _M_set_node(_M_node + __node_offset);
201 : : _M_cur = _M_first + (__offset - __node_offset
202 : : * difference_type(_S_buffer_size()));
203 : : }
204 : : return *this;
205 : : }
206 : :
207 : : _Self
208 : : operator+(difference_type __n) const
209 : : {
210 : : _Self __tmp = *this;
211 : : return __tmp += __n;
212 : : }
213 : :
214 : : _Self&
215 : : operator-=(difference_type __n)
216 : : { return *this += -__n; }
217 : :
218 : : _Self
219 : : operator-(difference_type __n) const
220 : : {
221 : : _Self __tmp = *this;
222 : : return __tmp -= __n;
223 : : }
224 : :
225 : : reference
226 : : operator[](difference_type __n) const
227 : : { return *(*this + __n); }
228 : :
229 : : /**
230 : : * Prepares to traverse new_node. Sets everything except
231 : : * _M_cur, which should therefore be set by the caller
232 : : * immediately afterwards, based on _M_first and _M_last.
233 : : */
234 : : void
235 : 6179578 : _M_set_node(_Map_pointer __new_node)
236 : : {
237 : 6179578 : _M_node = __new_node;
238 : 6179578 : _M_first = *__new_node;
239 : 6179578 : _M_last = _M_first + difference_type(_S_buffer_size());
240 : 6179578 : }
241 : : };
242 : :
243 : : // Note: we also provide overloads whose operands are of the same type in
244 : : // order to avoid ambiguous overload resolution when std::rel_ops operators
245 : : // are in scope (for additional details, see libstdc++/3628)
246 : : template<typename _Tp, typename _Ref, typename _Ptr>
247 : : inline bool
248 : 41759638 : operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
249 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
250 : 41759638 : { return __x._M_cur == __y._M_cur; }
251 : :
252 : : template<typename _Tp, typename _RefL, typename _PtrL,
253 : : typename _RefR, typename _PtrR>
254 : : inline bool
255 : : operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
256 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
257 : : { return __x._M_cur == __y._M_cur; }
258 : :
259 : : template<typename _Tp, typename _Ref, typename _Ptr>
260 : : inline bool
261 : : operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
262 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
263 : : { return !(__x == __y); }
264 : :
265 : : template<typename _Tp, typename _RefL, typename _PtrL,
266 : : typename _RefR, typename _PtrR>
267 : : inline bool
268 : : operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
269 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
270 : : { return !(__x == __y); }
271 : :
272 : : template<typename _Tp, typename _Ref, typename _Ptr>
273 : : inline bool
274 : : operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
275 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
276 : : { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
277 : : : (__x._M_node < __y._M_node); }
278 : :
279 : : template<typename _Tp, typename _RefL, typename _PtrL,
280 : : typename _RefR, typename _PtrR>
281 : : inline bool
282 : : operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
283 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
284 : : { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
285 : : : (__x._M_node < __y._M_node); }
286 : :
287 : : template<typename _Tp, typename _Ref, typename _Ptr>
288 : : inline bool
289 : : operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
290 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
291 : : { return __y < __x; }
292 : :
293 : : template<typename _Tp, typename _RefL, typename _PtrL,
294 : : typename _RefR, typename _PtrR>
295 : : inline bool
296 : : operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
297 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
298 : : { return __y < __x; }
299 : :
300 : : template<typename _Tp, typename _Ref, typename _Ptr>
301 : : inline bool
302 : : operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
303 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
304 : : { return !(__y < __x); }
305 : :
306 : : template<typename _Tp, typename _RefL, typename _PtrL,
307 : : typename _RefR, typename _PtrR>
308 : : inline bool
309 : : operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
310 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
311 : : { return !(__y < __x); }
312 : :
313 : : template<typename _Tp, typename _Ref, typename _Ptr>
314 : : inline bool
315 : : operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
316 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
317 : : { return !(__x < __y); }
318 : :
319 : : template<typename _Tp, typename _RefL, typename _PtrL,
320 : : typename _RefR, typename _PtrR>
321 : : inline bool
322 : : operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
323 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
324 : : { return !(__x < __y); }
325 : :
326 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
327 : : // According to the resolution of DR179 not only the various comparison
328 : : // operators but also operator- must accept mixed iterator/const_iterator
329 : : // parameters.
330 : : template<typename _Tp, typename _Ref, typename _Ptr>
331 : : inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
332 : 3190484 : operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
333 : : const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
334 : : {
335 : : return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
336 : : (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
337 : : * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
338 : 3190484 : + (__y._M_last - __y._M_cur);
339 : : }
340 : :
341 : : template<typename _Tp, typename _RefL, typename _PtrL,
342 : : typename _RefR, typename _PtrR>
343 : : inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
344 : : operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
345 : : const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
346 : : {
347 : : return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
348 : : (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
349 : : * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
350 : : + (__y._M_last - __y._M_cur);
351 : : }
352 : :
353 : : template<typename _Tp, typename _Ref, typename _Ptr>
354 : : inline _Deque_iterator<_Tp, _Ref, _Ptr>
355 : : operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
356 : : { return __x + __n; }
357 : :
358 : : template<typename _Tp>
359 : : void
360 : : fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
361 : : const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
362 : :
363 : : template<typename _Tp>
364 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
365 : : copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
366 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
367 : : _Deque_iterator<_Tp, _Tp&, _Tp*>);
368 : :
369 : : template<typename _Tp>
370 : : inline _Deque_iterator<_Tp, _Tp&, _Tp*>
371 : : copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
372 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
373 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
374 : : { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
375 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
376 : : __result); }
377 : :
378 : : template<typename _Tp>
379 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
380 : : copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
381 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
382 : : _Deque_iterator<_Tp, _Tp&, _Tp*>);
383 : :
384 : : template<typename _Tp>
385 : : inline _Deque_iterator<_Tp, _Tp&, _Tp*>
386 : : copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
387 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
388 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
389 : : { return std::copy_backward(_Deque_iterator<_Tp,
390 : : const _Tp&, const _Tp*>(__first),
391 : : _Deque_iterator<_Tp,
392 : : const _Tp&, const _Tp*>(__last),
393 : : __result); }
394 : :
395 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
396 : : template<typename _Tp>
397 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
398 : : move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
399 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
400 : : _Deque_iterator<_Tp, _Tp&, _Tp*>);
401 : :
402 : : template<typename _Tp>
403 : : inline _Deque_iterator<_Tp, _Tp&, _Tp*>
404 : : move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
405 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
406 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
407 : : { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
408 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
409 : : __result); }
410 : :
411 : : template<typename _Tp>
412 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
413 : : move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
414 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
415 : : _Deque_iterator<_Tp, _Tp&, _Tp*>);
416 : :
417 : : template<typename _Tp>
418 : : inline _Deque_iterator<_Tp, _Tp&, _Tp*>
419 : : move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
420 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
421 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
422 : : { return std::move_backward(_Deque_iterator<_Tp,
423 : : const _Tp&, const _Tp*>(__first),
424 : : _Deque_iterator<_Tp,
425 : : const _Tp&, const _Tp*>(__last),
426 : : __result); }
427 : : #endif
428 : :
429 : : /**
430 : : * Deque base class. This class provides the unified face for %deque's
431 : : * allocation. This class's constructor and destructor allocate and
432 : : * deallocate (but do not initialize) storage. This makes %exception
433 : : * safety easier.
434 : : *
435 : : * Nothing in this class ever constructs or destroys an actual Tp element.
436 : : * (Deque handles that itself.) Only/All memory management is performed
437 : : * here.
438 : : */
439 : : template<typename _Tp, typename _Alloc>
440 : : class _Deque_base
441 : : {
442 : : public:
443 : : typedef _Alloc allocator_type;
444 : :
445 : : allocator_type
446 : : get_allocator() const _GLIBCXX_NOEXCEPT
447 : : { return allocator_type(_M_get_Tp_allocator()); }
448 : :
449 : : typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
450 : : typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
451 : :
452 : 1494391 : _Deque_base()
453 : 1494391 : : _M_impl()
454 [ + - ][ + - ]: 1494391 : { _M_initialize_map(0); }
[ # # ]
455 : :
456 : : _Deque_base(size_t __num_elements)
457 : : : _M_impl()
458 : : { _M_initialize_map(__num_elements); }
459 : :
460 : 1595398 : _Deque_base(const allocator_type& __a, size_t __num_elements)
461 : 1595398 : : _M_impl(__a)
462 [ + - ][ + - ]: 1595398 : { _M_initialize_map(__num_elements); }
[ # # ][ + - ]
463 : :
464 : : _Deque_base(const allocator_type& __a)
465 : : : _M_impl(__a)
466 : : { }
467 : :
468 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
469 : : _Deque_base(_Deque_base&& __x)
470 : : : _M_impl(std::move(__x._M_get_Tp_allocator()))
471 : : {
472 : : _M_initialize_map(0);
473 : : if (__x._M_impl._M_map)
474 : : {
475 : : std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
476 : : std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
477 : : std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
478 : : std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
479 : : }
480 : : }
481 : : #endif
482 : :
483 : : ~_Deque_base();
484 : :
485 : : protected:
486 : : //This struct encapsulates the implementation of the std::deque
487 : : //standard container and at the same time makes use of the EBO
488 : : //for empty allocators.
489 : : typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
490 : :
491 : : typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
492 : :
493 : 3086135 : struct _Deque_impl
494 : : : public _Tp_alloc_type
495 : : {
496 : : _Tp** _M_map;
497 : : size_t _M_map_size;
498 : : iterator _M_start;
499 : : iterator _M_finish;
500 : :
501 : 1494391 : _Deque_impl()
502 : : : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
503 : 1494391 : _M_start(), _M_finish()
504 : : { }
505 : :
506 : 1595398 : _Deque_impl(const _Tp_alloc_type& __a)
507 : : : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
508 : 1595398 : _M_start(), _M_finish()
509 : : { }
510 : :
511 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
512 : : _Deque_impl(_Tp_alloc_type&& __a)
513 : : : _Tp_alloc_type(std::move(__a)), _M_map(0), _M_map_size(0),
514 : : _M_start(), _M_finish()
515 : : { }
516 : : #endif
517 : : };
518 : :
519 : : _Tp_alloc_type&
520 : 4681533 : _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
521 : 4681533 : { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
522 : :
523 : : const _Tp_alloc_type&
524 : 7670315 : _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
525 : 7670315 : { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
526 : :
527 : : _Map_alloc_type
528 : 6175924 : _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
529 : 6175924 : { return _Map_alloc_type(_M_get_Tp_allocator()); }
530 : :
531 : : _Tp*
532 : 3089789 : _M_allocate_node()
533 : : {
534 : 3089789 : return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
535 : : }
536 : :
537 : : void
538 : 3086135 : _M_deallocate_node(_Tp* __p)
539 : : {
540 : 3086135 : _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
541 : 3086135 : }
542 : :
543 : : _Tp**
544 : 3089789 : _M_allocate_map(size_t __n)
545 [ + - ][ + - ]: 3089789 : { return _M_get_map_allocator().allocate(__n); }
[ + - ][ # # ]
546 : :
547 : : void
548 : 3086135 : _M_deallocate_map(_Tp** __p, size_t __n)
549 : 3086135 : { _M_get_map_allocator().deallocate(__p, __n); }
550 : :
551 : : protected:
552 : : void _M_initialize_map(size_t);
553 : : void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
554 : : void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
555 : : enum { _S_initial_map_size = 8 };
556 : :
557 : : _Deque_impl _M_impl;
558 : : };
559 : :
560 : : template<typename _Tp, typename _Alloc>
561 : 3086135 : _Deque_base<_Tp, _Alloc>::
562 : : ~_Deque_base()
563 : : {
564 [ + - ][ + - ]: 3086135 : if (this->_M_impl._M_map)
[ + - ][ # # ]
565 : : {
566 [ + - ][ + - ]: 3086135 : _M_destroy_nodes(this->_M_impl._M_start._M_node,
[ + - ][ # # ]
567 : : this->_M_impl._M_finish._M_node + 1);
568 [ + - ][ + - ]: 3086135 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
[ + - ][ # # ]
569 : : }
570 : 3086135 : }
571 : :
572 : : /**
573 : : * @brief Layout storage.
574 : : * @param __num_elements The count of T's for which to allocate space
575 : : * at first.
576 : : * @return Nothing.
577 : : *
578 : : * The initial underlying memory layout is a bit complicated...
579 : : */
580 : : template<typename _Tp, typename _Alloc>
581 : : void
582 : 3089789 : _Deque_base<_Tp, _Alloc>::
583 : : _M_initialize_map(size_t __num_elements)
584 : : {
585 : : const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
586 : 3089789 : + 1);
587 : :
588 : 3089789 : this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
589 : : size_t(__num_nodes + 2));
590 : 3089789 : this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
591 : :
592 : : // For "small" maps (needing less than _M_map_size nodes), allocation
593 : : // starts in the middle elements and grows outwards. So nstart may be
594 : : // the beginning of _M_map, but for small maps it may be as far in as
595 : : // _M_map+3.
596 : :
597 : : _Tp** __nstart = (this->_M_impl._M_map
598 : 3089789 : + (this->_M_impl._M_map_size - __num_nodes) / 2);
599 : 3089789 : _Tp** __nfinish = __nstart + __num_nodes;
600 : :
601 : : __try
602 [ + - + - : 3089789 : { _M_create_nodes(__nstart, __nfinish); }
+ - # # ]
603 : : __catch(...)
604 : : {
605 [ # # # # : : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
# # # # ]
606 : : this->_M_impl._M_map = 0;
607 : : this->_M_impl._M_map_size = 0;
608 : : __throw_exception_again;
609 : : }
610 : :
611 : 3089789 : this->_M_impl._M_start._M_set_node(__nstart);
612 : 3089789 : this->_M_impl._M_finish._M_set_node(__nfinish - 1);
613 : 3089789 : this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
614 : 3089789 : this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
615 : : + __num_elements
616 : : % __deque_buf_size(sizeof(_Tp)));
617 : 3089789 : }
618 : :
619 : : template<typename _Tp, typename _Alloc>
620 : : void
621 : 3089789 : _Deque_base<_Tp, _Alloc>::
622 : : _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
623 : : {
624 : : _Tp** __cur;
625 : : __try
626 : : {
627 [ + + ][ + + ]: 6179578 : for (__cur = __nstart; __cur < __nfinish; ++__cur)
[ + + ][ # # ]
628 [ + - ][ + - ]: 3089789 : *__cur = this->_M_allocate_node();
[ + - ][ # # ]
629 : : }
630 : : __catch(...)
631 : : {
632 [ # # # # : : _M_destroy_nodes(__nstart, __cur);
# # # # ]
633 : : __throw_exception_again;
634 : : }
635 : 3089789 : }
636 : :
637 : : template<typename _Tp, typename _Alloc>
638 : : void
639 : 3086135 : _Deque_base<_Tp, _Alloc>::
640 : : _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
641 : : {
642 [ + + ][ + + ]: 6172270 : for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
[ + + ][ # # ]
643 : 3086135 : _M_deallocate_node(*__n);
644 : 3086135 : }
645 : :
646 : : /**
647 : : * @brief A standard container using fixed-size memory allocation and
648 : : * constant-time manipulation of elements at either end.
649 : : *
650 : : * @ingroup sequences
651 : : *
652 : : * Meets the requirements of a <a href="tables.html#65">container</a>, a
653 : : * <a href="tables.html#66">reversible container</a>, and a
654 : : * <a href="tables.html#67">sequence</a>, including the
655 : : * <a href="tables.html#68">optional sequence requirements</a>.
656 : : *
657 : : * In previous HP/SGI versions of deque, there was an extra template
658 : : * parameter so users could control the node size. This extension turned
659 : : * out to violate the C++ standard (it can be detected using template
660 : : * template parameters), and it was removed.
661 : : *
662 : : * Here's how a deque<Tp> manages memory. Each deque has 4 members:
663 : : *
664 : : * - Tp** _M_map
665 : : * - size_t _M_map_size
666 : : * - iterator _M_start, _M_finish
667 : : *
668 : : * map_size is at least 8. %map is an array of map_size
669 : : * pointers-to-@a nodes. (The name %map has nothing to do with the
670 : : * std::map class, and @b nodes should not be confused with
671 : : * std::list's usage of @a node.)
672 : : *
673 : : * A @a node has no specific type name as such, but it is referred
674 : : * to as @a node in this file. It is a simple array-of-Tp. If Tp
675 : : * is very large, there will be one Tp element per node (i.e., an
676 : : * @a array of one). For non-huge Tp's, node size is inversely
677 : : * related to Tp size: the larger the Tp, the fewer Tp's will fit
678 : : * in a node. The goal here is to keep the total size of a node
679 : : * relatively small and constant over different Tp's, to improve
680 : : * allocator efficiency.
681 : : *
682 : : * Not every pointer in the %map array will point to a node. If
683 : : * the initial number of elements in the deque is small, the
684 : : * /middle/ %map pointers will be valid, and the ones at the edges
685 : : * will be unused. This same situation will arise as the %map
686 : : * grows: available %map pointers, if any, will be on the ends. As
687 : : * new nodes are created, only a subset of the %map's pointers need
688 : : * to be copied @a outward.
689 : : *
690 : : * Class invariants:
691 : : * - For any nonsingular iterator i:
692 : : * - i.node points to a member of the %map array. (Yes, you read that
693 : : * correctly: i.node does not actually point to a node.) The member of
694 : : * the %map array is what actually points to the node.
695 : : * - i.first == *(i.node) (This points to the node (first Tp element).)
696 : : * - i.last == i.first + node_size
697 : : * - i.cur is a pointer in the range [i.first, i.last). NOTE:
698 : : * the implication of this is that i.cur is always a dereferenceable
699 : : * pointer, even if i is a past-the-end iterator.
700 : : * - Start and Finish are always nonsingular iterators. NOTE: this
701 : : * means that an empty deque must have one node, a deque with <N
702 : : * elements (where N is the node buffer size) must have one node, a
703 : : * deque with N through (2N-1) elements must have two nodes, etc.
704 : : * - For every node other than start.node and finish.node, every
705 : : * element in the node is an initialized object. If start.node ==
706 : : * finish.node, then [start.cur, finish.cur) are initialized
707 : : * objects, and the elements outside that range are uninitialized
708 : : * storage. Otherwise, [start.cur, start.last) and [finish.first,
709 : : * finish.cur) are initialized objects, and [start.first, start.cur)
710 : : * and [finish.cur, finish.last) are uninitialized storage.
711 : : * - [%map, %map + map_size) is a valid, non-empty range.
712 : : * - [start.node, finish.node] is a valid range contained within
713 : : * [%map, %map + map_size).
714 : : * - A pointer in the range [%map, %map + map_size) points to an allocated
715 : : * node if and only if the pointer is in the range
716 : : * [start.node, finish.node].
717 : : *
718 : : * Here's the magic: nothing in deque is @b aware of the discontiguous
719 : : * storage!
720 : : *
721 : : * The memory setup and layout occurs in the parent, _Base, and the iterator
722 : : * class is entirely responsible for @a leaping from one node to the next.
723 : : * All the implementation routines for deque itself work only through the
724 : : * start and finish iterators. This keeps the routines simple and sane,
725 : : * and we can use other standard algorithms as well.
726 : : */
727 : : template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
728 : : class deque : protected _Deque_base<_Tp, _Alloc>
729 : : {
730 : : // concept requirements
731 : : typedef typename _Alloc::value_type _Alloc_value_type;
732 : : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
733 : : __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
734 : :
735 : : typedef _Deque_base<_Tp, _Alloc> _Base;
736 : : typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
737 : :
738 : : public:
739 : : typedef _Tp value_type;
740 : : typedef typename _Tp_alloc_type::pointer pointer;
741 : : typedef typename _Tp_alloc_type::const_pointer const_pointer;
742 : : typedef typename _Tp_alloc_type::reference reference;
743 : : typedef typename _Tp_alloc_type::const_reference const_reference;
744 : : typedef typename _Base::iterator iterator;
745 : : typedef typename _Base::const_iterator const_iterator;
746 : : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
747 : : typedef std::reverse_iterator<iterator> reverse_iterator;
748 : : typedef size_t size_type;
749 : : typedef ptrdiff_t difference_type;
750 : : typedef _Alloc allocator_type;
751 : :
752 : : protected:
753 : : typedef pointer* _Map_pointer;
754 : :
755 : 0 : static size_t _S_buffer_size()
756 : 0 : { return __deque_buf_size(sizeof(_Tp)); }
757 : :
758 : : // Functions controlling memory layout, and nothing else.
759 : : using _Base::_M_initialize_map;
760 : : using _Base::_M_create_nodes;
761 : : using _Base::_M_destroy_nodes;
762 : : using _Base::_M_allocate_node;
763 : : using _Base::_M_deallocate_node;
764 : : using _Base::_M_allocate_map;
765 : : using _Base::_M_deallocate_map;
766 : : using _Base::_M_get_Tp_allocator;
767 : :
768 : : /**
769 : : * A total of four data members accumulated down the hierarchy.
770 : : * May be accessed via _M_impl.*
771 : : */
772 : : using _Base::_M_impl;
773 : :
774 : : public:
775 : : // [23.2.1.1] construct/copy/destroy
776 : : // (assign() and get_allocator() are also listed in this section)
777 : : /**
778 : : * @brief Default constructor creates no elements.
779 : : */
780 : 1494391 : deque()
781 : 1494391 : : _Base() { }
782 : :
783 : : /**
784 : : * @brief Creates a %deque with no elements.
785 : : * @param __a An allocator object.
786 : : */
787 : : explicit
788 : : deque(const allocator_type& __a)
789 : : : _Base(__a, 0) { }
790 : :
791 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
792 : : /**
793 : : * @brief Creates a %deque with default constructed elements.
794 : : * @param __n The number of elements to initially create.
795 : : *
796 : : * This constructor fills the %deque with @a n default
797 : : * constructed elements.
798 : : */
799 : : explicit
800 : : deque(size_type __n)
801 : : : _Base(__n)
802 : : { _M_default_initialize(); }
803 : :
804 : : /**
805 : : * @brief Creates a %deque with copies of an exemplar element.
806 : : * @param __n The number of elements to initially create.
807 : : * @param __value An element to copy.
808 : : * @param __a An allocator.
809 : : *
810 : : * This constructor fills the %deque with @a __n copies of @a __value.
811 : : */
812 : : deque(size_type __n, const value_type& __value,
813 : : const allocator_type& __a = allocator_type())
814 : : : _Base(__a, __n)
815 : : { _M_fill_initialize(__value); }
816 : : #else
817 : : /**
818 : : * @brief Creates a %deque with copies of an exemplar element.
819 : : * @param __n The number of elements to initially create.
820 : : * @param __value An element to copy.
821 : : * @param __a An allocator.
822 : : *
823 : : * This constructor fills the %deque with @a __n copies of @a __value.
824 : : */
825 : : explicit
826 : 101007 : deque(size_type __n, const value_type& __value = value_type(),
827 : : const allocator_type& __a = allocator_type())
828 : 101007 : : _Base(__a, __n)
829 [ + - ]: 101007 : { _M_fill_initialize(__value); }
830 : : #endif
831 : :
832 : : /**
833 : : * @brief %Deque copy constructor.
834 : : * @param __x A %deque of identical element and allocator types.
835 : : *
836 : : * The newly-created %deque uses a copy of the allocation object used
837 : : * by @a __x.
838 : : */
839 : 1494391 : deque(const deque& __x)
840 : 1494391 : : _Base(__x._M_get_Tp_allocator(), __x.size())
841 [ + - ][ + - ]: 1494391 : { std::__uninitialized_copy_a(__x.begin(), __x.end(),
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ]
842 : : this->_M_impl._M_start,
843 : : _M_get_Tp_allocator()); }
844 : :
845 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
846 : : /**
847 : : * @brief %Deque move constructor.
848 : : * @param __x A %deque of identical element and allocator types.
849 : : *
850 : : * The newly-created %deque contains the exact contents of @a __x.
851 : : * The contents of @a __x are a valid, but unspecified %deque.
852 : : */
853 : : deque(deque&& __x)
854 : : : _Base(std::move(__x)) { }
855 : :
856 : : /**
857 : : * @brief Builds a %deque from an initializer list.
858 : : * @param __l An initializer_list.
859 : : * @param __a An allocator object.
860 : : *
861 : : * Create a %deque consisting of copies of the elements in the
862 : : * initializer_list @a __l.
863 : : *
864 : : * This will call the element type's copy constructor N times
865 : : * (where N is __l.size()) and do no memory reallocation.
866 : : */
867 : : deque(initializer_list<value_type> __l,
868 : : const allocator_type& __a = allocator_type())
869 : : : _Base(__a)
870 : : {
871 : : _M_range_initialize(__l.begin(), __l.end(),
872 : : random_access_iterator_tag());
873 : : }
874 : : #endif
875 : :
876 : : /**
877 : : * @brief Builds a %deque from a range.
878 : : * @param __first An input iterator.
879 : : * @param __last An input iterator.
880 : : * @param __a An allocator object.
881 : : *
882 : : * Create a %deque consisting of copies of the elements from [__first,
883 : : * __last).
884 : : *
885 : : * If the iterators are forward, bidirectional, or random-access, then
886 : : * this will call the elements' copy constructor N times (where N is
887 : : * distance(__first,__last)) and do no memory reallocation. But if only
888 : : * input iterators are used, then this will do at most 2N calls to the
889 : : * copy constructor, and logN memory reallocations.
890 : : */
891 : : template<typename _InputIterator>
892 : : deque(_InputIterator __first, _InputIterator __last,
893 : : const allocator_type& __a = allocator_type())
894 : : : _Base(__a)
895 : : {
896 : : // Check whether it's an integral type. If so, it's not an iterator.
897 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
898 : : _M_initialize_dispatch(__first, __last, _Integral());
899 : : }
900 : :
901 : : /**
902 : : * The dtor only erases the elements, and note that if the elements
903 : : * themselves are pointers, the pointed-to memory is not touched in any
904 : : * way. Managing the pointer is the user's responsibility.
905 : : */
906 : 3086135 : ~deque() _GLIBCXX_NOEXCEPT
907 [ + - ][ + - ]: 3086135 : { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ # # ]
[ # # ][ # # ]
908 : :
909 : : /**
910 : : * @brief %Deque assignment operator.
911 : : * @param __x A %deque of identical element and allocator types.
912 : : *
913 : : * All the elements of @a x are copied, but unlike the copy constructor,
914 : : * the allocator object is not copied.
915 : : */
916 : : deque&
917 : : operator=(const deque& __x);
918 : :
919 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
920 : : /**
921 : : * @brief %Deque move assignment operator.
922 : : * @param __x A %deque of identical element and allocator types.
923 : : *
924 : : * The contents of @a __x are moved into this deque (without copying).
925 : : * @a __x is a valid, but unspecified %deque.
926 : : */
927 : : deque&
928 : : operator=(deque&& __x)
929 : : {
930 : : // NB: DR 1204.
931 : : // NB: DR 675.
932 : : this->clear();
933 : : this->swap(__x);
934 : : return *this;
935 : : }
936 : :
937 : : /**
938 : : * @brief Assigns an initializer list to a %deque.
939 : : * @param __l An initializer_list.
940 : : *
941 : : * This function fills a %deque with copies of the elements in the
942 : : * initializer_list @a __l.
943 : : *
944 : : * Note that the assignment completely changes the %deque and that the
945 : : * resulting %deque's size is the same as the number of elements
946 : : * assigned. Old data may be lost.
947 : : */
948 : : deque&
949 : : operator=(initializer_list<value_type> __l)
950 : : {
951 : : this->assign(__l.begin(), __l.end());
952 : : return *this;
953 : : }
954 : : #endif
955 : :
956 : : /**
957 : : * @brief Assigns a given value to a %deque.
958 : : * @param __n Number of elements to be assigned.
959 : : * @param __val Value to be assigned.
960 : : *
961 : : * This function fills a %deque with @a n copies of the given
962 : : * value. Note that the assignment completely changes the
963 : : * %deque and that the resulting %deque's size is the same as
964 : : * the number of elements assigned. Old data may be lost.
965 : : */
966 : : void
967 : : assign(size_type __n, const value_type& __val)
968 : : { _M_fill_assign(__n, __val); }
969 : :
970 : : /**
971 : : * @brief Assigns a range to a %deque.
972 : : * @param __first An input iterator.
973 : : * @param __last An input iterator.
974 : : *
975 : : * This function fills a %deque with copies of the elements in the
976 : : * range [__first,__last).
977 : : *
978 : : * Note that the assignment completely changes the %deque and that the
979 : : * resulting %deque's size is the same as the number of elements
980 : : * assigned. Old data may be lost.
981 : : */
982 : : template<typename _InputIterator>
983 : : void
984 : : assign(_InputIterator __first, _InputIterator __last)
985 : : {
986 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
987 : : _M_assign_dispatch(__first, __last, _Integral());
988 : : }
989 : :
990 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
991 : : /**
992 : : * @brief Assigns an initializer list to a %deque.
993 : : * @param __l An initializer_list.
994 : : *
995 : : * This function fills a %deque with copies of the elements in the
996 : : * initializer_list @a __l.
997 : : *
998 : : * Note that the assignment completely changes the %deque and that the
999 : : * resulting %deque's size is the same as the number of elements
1000 : : * assigned. Old data may be lost.
1001 : : */
1002 : : void
1003 : : assign(initializer_list<value_type> __l)
1004 : : { this->assign(__l.begin(), __l.end()); }
1005 : : #endif
1006 : :
1007 : : /// Get a copy of the memory allocation object.
1008 : : allocator_type
1009 : : get_allocator() const _GLIBCXX_NOEXCEPT
1010 : : { return _Base::get_allocator(); }
1011 : :
1012 : : // iterators
1013 : : /**
1014 : : * Returns a read/write iterator that points to the first element in the
1015 : : * %deque. Iteration is done in ordinary element order.
1016 : : */
1017 : : iterator
1018 : 3187142 : begin() _GLIBCXX_NOEXCEPT
1019 : 3187142 : { return this->_M_impl._M_start; }
1020 : :
1021 : : /**
1022 : : * Returns a read-only (constant) iterator that points to the first
1023 : : * element in the %deque. Iteration is done in ordinary element order.
1024 : : */
1025 : : const_iterator
1026 : 1494391 : begin() const _GLIBCXX_NOEXCEPT
1027 : 1494391 : { return this->_M_impl._M_start; }
1028 : :
1029 : : /**
1030 : : * Returns a read/write iterator that points one past the last
1031 : : * element in the %deque. Iteration is done in ordinary
1032 : : * element order.
1033 : : */
1034 : : iterator
1035 : 43944186 : end() _GLIBCXX_NOEXCEPT
1036 : 43944186 : { return this->_M_impl._M_finish; }
1037 : :
1038 : : /**
1039 : : * Returns a read-only (constant) iterator that points one past
1040 : : * the last element in the %deque. Iteration is done in
1041 : : * ordinary element order.
1042 : : */
1043 : : const_iterator
1044 : 1494391 : end() const _GLIBCXX_NOEXCEPT
1045 : 1494391 : { return this->_M_impl._M_finish; }
1046 : :
1047 : : /**
1048 : : * Returns a read/write reverse iterator that points to the
1049 : : * last element in the %deque. Iteration is done in reverse
1050 : : * element order.
1051 : : */
1052 : : reverse_iterator
1053 : : rbegin() _GLIBCXX_NOEXCEPT
1054 : : { return reverse_iterator(this->_M_impl._M_finish); }
1055 : :
1056 : : /**
1057 : : * Returns a read-only (constant) reverse iterator that points
1058 : : * to the last element in the %deque. Iteration is done in
1059 : : * reverse element order.
1060 : : */
1061 : : const_reverse_iterator
1062 : : rbegin() const _GLIBCXX_NOEXCEPT
1063 : : { return const_reverse_iterator(this->_M_impl._M_finish); }
1064 : :
1065 : : /**
1066 : : * Returns a read/write reverse iterator that points to one
1067 : : * before the first element in the %deque. Iteration is done
1068 : : * in reverse element order.
1069 : : */
1070 : : reverse_iterator
1071 : : rend() _GLIBCXX_NOEXCEPT
1072 : : { return reverse_iterator(this->_M_impl._M_start); }
1073 : :
1074 : : /**
1075 : : * Returns a read-only (constant) reverse iterator that points
1076 : : * to one before the first element in the %deque. Iteration is
1077 : : * done in reverse element order.
1078 : : */
1079 : : const_reverse_iterator
1080 : : rend() const _GLIBCXX_NOEXCEPT
1081 : : { return const_reverse_iterator(this->_M_impl._M_start); }
1082 : :
1083 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1084 : : /**
1085 : : * Returns a read-only (constant) iterator that points to the first
1086 : : * element in the %deque. Iteration is done in ordinary element order.
1087 : : */
1088 : : const_iterator
1089 : : cbegin() const noexcept
1090 : : { return this->_M_impl._M_start; }
1091 : :
1092 : : /**
1093 : : * Returns a read-only (constant) iterator that points one past
1094 : : * the last element in the %deque. Iteration is done in
1095 : : * ordinary element order.
1096 : : */
1097 : : const_iterator
1098 : : cend() const noexcept
1099 : : { return this->_M_impl._M_finish; }
1100 : :
1101 : : /**
1102 : : * Returns a read-only (constant) reverse iterator that points
1103 : : * to the last element in the %deque. Iteration is done in
1104 : : * reverse element order.
1105 : : */
1106 : : const_reverse_iterator
1107 : : crbegin() const noexcept
1108 : : { return const_reverse_iterator(this->_M_impl._M_finish); }
1109 : :
1110 : : /**
1111 : : * Returns a read-only (constant) reverse iterator that points
1112 : : * to one before the first element in the %deque. Iteration is
1113 : : * done in reverse element order.
1114 : : */
1115 : : const_reverse_iterator
1116 : : crend() const noexcept
1117 : : { return const_reverse_iterator(this->_M_impl._M_start); }
1118 : : #endif
1119 : :
1120 : : // [23.2.1.2] capacity
1121 : : /** Returns the number of elements in the %deque. */
1122 : : size_type
1123 : 1696093 : size() const _GLIBCXX_NOEXCEPT
1124 : 1696093 : { return this->_M_impl._M_finish - this->_M_impl._M_start; }
1125 : :
1126 : : /** Returns the size() of the largest possible %deque. */
1127 : : size_type
1128 : : max_size() const _GLIBCXX_NOEXCEPT
1129 : : { return _M_get_Tp_allocator().max_size(); }
1130 : :
1131 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1132 : : /**
1133 : : * @brief Resizes the %deque to the specified number of elements.
1134 : : * @param __new_size Number of elements the %deque should contain.
1135 : : *
1136 : : * This function will %resize the %deque to the specified
1137 : : * number of elements. If the number is smaller than the
1138 : : * %deque's current size the %deque is truncated, otherwise
1139 : : * default constructed elements are appended.
1140 : : */
1141 : : void
1142 : : resize(size_type __new_size)
1143 : : {
1144 : : const size_type __len = size();
1145 : : if (__new_size > __len)
1146 : : _M_default_append(__new_size - __len);
1147 : : else if (__new_size < __len)
1148 : : _M_erase_at_end(this->_M_impl._M_start
1149 : : + difference_type(__new_size));
1150 : : }
1151 : :
1152 : : /**
1153 : : * @brief Resizes the %deque to the specified number of elements.
1154 : : * @param __new_size Number of elements the %deque should contain.
1155 : : * @param __x Data with which new elements should be populated.
1156 : : *
1157 : : * This function will %resize the %deque to the specified
1158 : : * number of elements. If the number is smaller than the
1159 : : * %deque's current size the %deque is truncated, otherwise the
1160 : : * %deque is extended and new elements are populated with given
1161 : : * data.
1162 : : */
1163 : : void
1164 : : resize(size_type __new_size, const value_type& __x)
1165 : : {
1166 : : const size_type __len = size();
1167 : : if (__new_size > __len)
1168 : : insert(this->_M_impl._M_finish, __new_size - __len, __x);
1169 : : else if (__new_size < __len)
1170 : : _M_erase_at_end(this->_M_impl._M_start
1171 : : + difference_type(__new_size));
1172 : : }
1173 : : #else
1174 : : /**
1175 : : * @brief Resizes the %deque to the specified number of elements.
1176 : : * @param __new_size Number of elements the %deque should contain.
1177 : : * @param __x Data with which new elements should be populated.
1178 : : *
1179 : : * This function will %resize the %deque to the specified
1180 : : * number of elements. If the number is smaller than the
1181 : : * %deque's current size the %deque is truncated, otherwise the
1182 : : * %deque is extended and new elements are populated with given
1183 : : * data.
1184 : : */
1185 : : void
1186 : : resize(size_type __new_size, value_type __x = value_type())
1187 : : {
1188 : : const size_type __len = size();
1189 : : if (__new_size > __len)
1190 : : insert(this->_M_impl._M_finish, __new_size - __len, __x);
1191 : : else if (__new_size < __len)
1192 : : _M_erase_at_end(this->_M_impl._M_start
1193 : : + difference_type(__new_size));
1194 : : }
1195 : : #endif
1196 : :
1197 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1198 : : /** A non-binding request to reduce memory use. */
1199 : : void
1200 : : shrink_to_fit()
1201 : : { _M_shrink_to_fit(); }
1202 : : #endif
1203 : :
1204 : : /**
1205 : : * Returns true if the %deque is empty. (Thus begin() would
1206 : : * equal end().)
1207 : : */
1208 : : bool
1209 : 41759638 : empty() const _GLIBCXX_NOEXCEPT
1210 : 41759638 : { return this->_M_impl._M_finish == this->_M_impl._M_start; }
1211 : :
1212 : : // element access
1213 : : /**
1214 : : * @brief Subscript access to the data contained in the %deque.
1215 : : * @param __n The index of the element for which data should be
1216 : : * accessed.
1217 : : * @return Read/write reference to data.
1218 : : *
1219 : : * This operator allows for easy, array-style, data access.
1220 : : * Note that data access with this operator is unchecked and
1221 : : * out_of_range lookups are not defined. (For checked lookups
1222 : : * see at().)
1223 : : */
1224 : : reference
1225 : : operator[](size_type __n)
1226 : : { return this->_M_impl._M_start[difference_type(__n)]; }
1227 : :
1228 : : /**
1229 : : * @brief Subscript access to the data contained in the %deque.
1230 : : * @param __n The index of the element for which data should be
1231 : : * accessed.
1232 : : * @return Read-only (constant) reference to data.
1233 : : *
1234 : : * This operator allows for easy, array-style, data access.
1235 : : * Note that data access with this operator is unchecked and
1236 : : * out_of_range lookups are not defined. (For checked lookups
1237 : : * see at().)
1238 : : */
1239 : : const_reference
1240 : : operator[](size_type __n) const
1241 : : { return this->_M_impl._M_start[difference_type(__n)]; }
1242 : :
1243 : : protected:
1244 : : /// Safety check used only from at().
1245 : : void
1246 : : _M_range_check(size_type __n) const
1247 : : {
1248 : : if (__n >= this->size())
1249 : : __throw_out_of_range(__N("deque::_M_range_check"));
1250 : : }
1251 : :
1252 : : public:
1253 : : /**
1254 : : * @brief Provides access to the data contained in the %deque.
1255 : : * @param __n The index of the element for which data should be
1256 : : * accessed.
1257 : : * @return Read/write reference to data.
1258 : : * @throw std::out_of_range If @a __n is an invalid index.
1259 : : *
1260 : : * This function provides for safer data access. The parameter
1261 : : * is first checked that it is in the range of the deque. The
1262 : : * function throws out_of_range if the check fails.
1263 : : */
1264 : : reference
1265 : : at(size_type __n)
1266 : : {
1267 : : _M_range_check(__n);
1268 : : return (*this)[__n];
1269 : : }
1270 : :
1271 : : /**
1272 : : * @brief Provides access to the data contained in the %deque.
1273 : : * @param __n The index of the element for which data should be
1274 : : * accessed.
1275 : : * @return Read-only (constant) reference to data.
1276 : : * @throw std::out_of_range If @a __n is an invalid index.
1277 : : *
1278 : : * This function provides for safer data access. The parameter is first
1279 : : * checked that it is in the range of the deque. The function throws
1280 : : * out_of_range if the check fails.
1281 : : */
1282 : : const_reference
1283 : : at(size_type __n) const
1284 : : {
1285 : : _M_range_check(__n);
1286 : : return (*this)[__n];
1287 : : }
1288 : :
1289 : : /**
1290 : : * Returns a read/write reference to the data at the first
1291 : : * element of the %deque.
1292 : : */
1293 : : reference
1294 : 101007 : front()
1295 : 101007 : { return *begin(); }
1296 : :
1297 : : /**
1298 : : * Returns a read-only (constant) reference to the data at the first
1299 : : * element of the %deque.
1300 : : */
1301 : : const_reference
1302 : : front() const
1303 : : { return *begin(); }
1304 : :
1305 : : /**
1306 : : * Returns a read/write reference to the data at the last element of the
1307 : : * %deque.
1308 : : */
1309 : : reference
1310 : 40858051 : back()
1311 : : {
1312 [ + - ][ + - ]: 40858051 : iterator __tmp = end();
[ + - ]
1313 [ + - ][ + - ]: 40858051 : --__tmp;
[ + - ]
1314 : 40858051 : return *__tmp;
1315 : : }
1316 : :
1317 : : /**
1318 : : * Returns a read-only (constant) reference to the data at the last
1319 : : * element of the %deque.
1320 : : */
1321 : : const_reference
1322 : : back() const
1323 : : {
1324 : : const_iterator __tmp = end();
1325 : : --__tmp;
1326 : : return *__tmp;
1327 : : }
1328 : :
1329 : : // [23.2.1.2] modifiers
1330 : : /**
1331 : : * @brief Add data to the front of the %deque.
1332 : : * @param __x Data to be added.
1333 : : *
1334 : : * This is a typical stack operation. The function creates an
1335 : : * element at the front of the %deque and assigns the given
1336 : : * data to it. Due to the nature of a %deque this operation
1337 : : * can be done in constant time.
1338 : : */
1339 : : void
1340 : : push_front(const value_type& __x)
1341 : : {
1342 : : if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1343 : : {
1344 : : this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
1345 : : --this->_M_impl._M_start._M_cur;
1346 : : }
1347 : : else
1348 : : _M_push_front_aux(__x);
1349 : : }
1350 : :
1351 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1352 : : void
1353 : : push_front(value_type&& __x)
1354 : : { emplace_front(std::move(__x)); }
1355 : :
1356 : : template<typename... _Args>
1357 : : void
1358 : : emplace_front(_Args&&... __args);
1359 : : #endif
1360 : :
1361 : : /**
1362 : : * @brief Add data to the end of the %deque.
1363 : : * @param __x Data to be added.
1364 : : *
1365 : : * This is a typical stack operation. The function creates an
1366 : : * element at the end of the %deque and assigns the given data
1367 : : * to it. Due to the nature of a %deque this operation can be
1368 : : * done in constant time.
1369 : : */
1370 : : void
1371 : 41473260 : push_back(const value_type& __x)
1372 : : {
1373 [ + - ][ + - ]: 41473260 : if (this->_M_impl._M_finish._M_cur
[ + - ][ # # ]
1374 : : != this->_M_impl._M_finish._M_last - 1)
1375 : : {
1376 : 41473260 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
1377 : 41473260 : ++this->_M_impl._M_finish._M_cur;
1378 : : }
1379 : : else
1380 : 0 : _M_push_back_aux(__x);
1381 : 41473260 : }
1382 : :
1383 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1384 : : void
1385 : : push_back(value_type&& __x)
1386 : : { emplace_back(std::move(__x)); }
1387 : :
1388 : : template<typename... _Args>
1389 : : void
1390 : : emplace_back(_Args&&... __args);
1391 : : #endif
1392 : :
1393 : : /**
1394 : : * @brief Removes first element.
1395 : : *
1396 : : * This is a typical stack operation. It shrinks the %deque by one.
1397 : : *
1398 : : * Note that no data is returned, and if the first element's data is
1399 : : * needed, it should be retrieved before pop_front() is called.
1400 : : */
1401 : : void
1402 : 21938 : pop_front()
1403 : : {
1404 [ + - ]: 21938 : if (this->_M_impl._M_start._M_cur
1405 : : != this->_M_impl._M_start._M_last - 1)
1406 : : {
1407 : 21938 : this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
1408 : 21938 : ++this->_M_impl._M_start._M_cur;
1409 : : }
1410 : : else
1411 : 0 : _M_pop_front_aux();
1412 : 21938 : }
1413 : :
1414 : : /**
1415 : : * @brief Removes last element.
1416 : : *
1417 : : * This is a typical stack operation. It shrinks the %deque by one.
1418 : : *
1419 : : * Note that no data is returned, and if the last element's data is
1420 : : * needed, it should be retrieved before pop_back() is called.
1421 : : */
1422 : : void
1423 : 41473245 : pop_back()
1424 : : {
1425 [ + - ][ + - ]: 41473245 : if (this->_M_impl._M_finish._M_cur
[ + - ]
1426 : : != this->_M_impl._M_finish._M_first)
1427 : : {
1428 : 41473245 : --this->_M_impl._M_finish._M_cur;
1429 : 41473245 : this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
1430 : : }
1431 : : else
1432 : 0 : _M_pop_back_aux();
1433 : 41473245 : }
1434 : :
1435 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1436 : : /**
1437 : : * @brief Inserts an object in %deque before specified iterator.
1438 : : * @param __position An iterator into the %deque.
1439 : : * @param __args Arguments.
1440 : : * @return An iterator that points to the inserted data.
1441 : : *
1442 : : * This function will insert an object of type T constructed
1443 : : * with T(std::forward<Args>(args)...) before the specified location.
1444 : : */
1445 : : template<typename... _Args>
1446 : : iterator
1447 : : emplace(iterator __position, _Args&&... __args);
1448 : : #endif
1449 : :
1450 : : /**
1451 : : * @brief Inserts given value into %deque before specified iterator.
1452 : : * @param __position An iterator into the %deque.
1453 : : * @param __x Data to be inserted.
1454 : : * @return An iterator that points to the inserted data.
1455 : : *
1456 : : * This function will insert a copy of the given value before the
1457 : : * specified location.
1458 : : */
1459 : : iterator
1460 : : insert(iterator __position, const value_type& __x);
1461 : :
1462 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1463 : : /**
1464 : : * @brief Inserts given rvalue into %deque before specified iterator.
1465 : : * @param __position An iterator into the %deque.
1466 : : * @param __x Data to be inserted.
1467 : : * @return An iterator that points to the inserted data.
1468 : : *
1469 : : * This function will insert a copy of the given rvalue before the
1470 : : * specified location.
1471 : : */
1472 : : iterator
1473 : : insert(iterator __position, value_type&& __x)
1474 : : { return emplace(__position, std::move(__x)); }
1475 : :
1476 : : /**
1477 : : * @brief Inserts an initializer list into the %deque.
1478 : : * @param __p An iterator into the %deque.
1479 : : * @param __l An initializer_list.
1480 : : *
1481 : : * This function will insert copies of the data in the
1482 : : * initializer_list @a __l into the %deque before the location
1483 : : * specified by @a __p. This is known as <em>list insert</em>.
1484 : : */
1485 : : void
1486 : : insert(iterator __p, initializer_list<value_type> __l)
1487 : : { this->insert(__p, __l.begin(), __l.end()); }
1488 : : #endif
1489 : :
1490 : : /**
1491 : : * @brief Inserts a number of copies of given data into the %deque.
1492 : : * @param __position An iterator into the %deque.
1493 : : * @param __n Number of elements to be inserted.
1494 : : * @param __x Data to be inserted.
1495 : : *
1496 : : * This function will insert a specified number of copies of the given
1497 : : * data before the location specified by @a __position.
1498 : : */
1499 : : void
1500 : : insert(iterator __position, size_type __n, const value_type& __x)
1501 : : { _M_fill_insert(__position, __n, __x); }
1502 : :
1503 : : /**
1504 : : * @brief Inserts a range into the %deque.
1505 : : * @param __position An iterator into the %deque.
1506 : : * @param __first An input iterator.
1507 : : * @param __last An input iterator.
1508 : : *
1509 : : * This function will insert copies of the data in the range
1510 : : * [__first,__last) into the %deque before the location specified
1511 : : * by @a __position. This is known as <em>range insert</em>.
1512 : : */
1513 : : template<typename _InputIterator>
1514 : : void
1515 : : insert(iterator __position, _InputIterator __first,
1516 : : _InputIterator __last)
1517 : : {
1518 : : // Check whether it's an integral type. If so, it's not an iterator.
1519 : : typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1520 : : _M_insert_dispatch(__position, __first, __last, _Integral());
1521 : : }
1522 : :
1523 : : /**
1524 : : * @brief Remove element at given position.
1525 : : * @param __position Iterator pointing to element to be erased.
1526 : : * @return An iterator pointing to the next element (or end()).
1527 : : *
1528 : : * This function will erase the element at the given position and thus
1529 : : * shorten the %deque by one.
1530 : : *
1531 : : * The user is cautioned that
1532 : : * this function only erases the element, and that if the element is
1533 : : * itself a pointer, the pointed-to memory is not touched in any way.
1534 : : * Managing the pointer is the user's responsibility.
1535 : : */
1536 : : iterator
1537 : : erase(iterator __position);
1538 : :
1539 : : /**
1540 : : * @brief Remove a range of elements.
1541 : : * @param __first Iterator pointing to the first element to be erased.
1542 : : * @param __last Iterator pointing to one past the last element to be
1543 : : * erased.
1544 : : * @return An iterator pointing to the element pointed to by @a last
1545 : : * prior to erasing (or end()).
1546 : : *
1547 : : * This function will erase the elements in the range
1548 : : * [__first,__last) and shorten the %deque accordingly.
1549 : : *
1550 : : * The user is cautioned that
1551 : : * this function only erases the elements, and that if the elements
1552 : : * themselves are pointers, the pointed-to memory is not touched in any
1553 : : * way. Managing the pointer is the user's responsibility.
1554 : : */
1555 : : iterator
1556 : : erase(iterator __first, iterator __last);
1557 : :
1558 : : /**
1559 : : * @brief Swaps data with another %deque.
1560 : : * @param __x A %deque of the same element and allocator types.
1561 : : *
1562 : : * This exchanges the elements between two deques in constant time.
1563 : : * (Four pointers, so it should be quite fast.)
1564 : : * Note that the global std::swap() function is specialized such that
1565 : : * std::swap(d1,d2) will feed to this function.
1566 : : */
1567 : : void
1568 : : swap(deque& __x)
1569 : : {
1570 : : std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1571 : : std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1572 : : std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
1573 : : std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
1574 : :
1575 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1576 : : // 431. Swapping containers with unequal allocators.
1577 : : std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
1578 : : __x._M_get_Tp_allocator());
1579 : : }
1580 : :
1581 : : /**
1582 : : * Erases all the elements. Note that this function only erases the
1583 : : * elements, and that if the elements themselves are pointers, the
1584 : : * pointed-to memory is not touched in any way. Managing the pointer is
1585 : : * the user's responsibility.
1586 : : */
1587 : : void
1588 : : clear() _GLIBCXX_NOEXCEPT
1589 : : { _M_erase_at_end(begin()); }
1590 : :
1591 : : protected:
1592 : : // Internal constructor functions follow.
1593 : :
1594 : : // called by the range constructor to implement [23.1.1]/9
1595 : :
1596 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1597 : : // 438. Ambiguity in the "do the right thing" clause
1598 : : template<typename _Integer>
1599 : : void
1600 : : _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1601 : : {
1602 : : _M_initialize_map(static_cast<size_type>(__n));
1603 : : _M_fill_initialize(__x);
1604 : : }
1605 : :
1606 : : // called by the range constructor to implement [23.1.1]/9
1607 : : template<typename _InputIterator>
1608 : : void
1609 : : _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1610 : : __false_type)
1611 : : {
1612 : : typedef typename std::iterator_traits<_InputIterator>::
1613 : : iterator_category _IterCategory;
1614 : : _M_range_initialize(__first, __last, _IterCategory());
1615 : : }
1616 : :
1617 : : // called by the second initialize_dispatch above
1618 : : //@{
1619 : : /**
1620 : : * @brief Fills the deque with whatever is in [first,last).
1621 : : * @param __first An input iterator.
1622 : : * @param __last An input iterator.
1623 : : * @return Nothing.
1624 : : *
1625 : : * If the iterators are actually forward iterators (or better), then the
1626 : : * memory layout can be done all at once. Else we move forward using
1627 : : * push_back on each value from the iterator.
1628 : : */
1629 : : template<typename _InputIterator>
1630 : : void
1631 : : _M_range_initialize(_InputIterator __first, _InputIterator __last,
1632 : : std::input_iterator_tag);
1633 : :
1634 : : // called by the second initialize_dispatch above
1635 : : template<typename _ForwardIterator>
1636 : : void
1637 : : _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1638 : : std::forward_iterator_tag);
1639 : : //@}
1640 : :
1641 : : /**
1642 : : * @brief Fills the %deque with copies of value.
1643 : : * @param __value Initial value.
1644 : : * @return Nothing.
1645 : : * @pre _M_start and _M_finish have already been initialized,
1646 : : * but none of the %deque's elements have yet been constructed.
1647 : : *
1648 : : * This function is called only when the user provides an explicit size
1649 : : * (with or without an explicit exemplar value).
1650 : : */
1651 : : void
1652 : : _M_fill_initialize(const value_type& __value);
1653 : :
1654 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1655 : : // called by deque(n).
1656 : : void
1657 : : _M_default_initialize();
1658 : : #endif
1659 : :
1660 : : // Internal assign functions follow. The *_aux functions do the actual
1661 : : // assignment work for the range versions.
1662 : :
1663 : : // called by the range assign to implement [23.1.1]/9
1664 : :
1665 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1666 : : // 438. Ambiguity in the "do the right thing" clause
1667 : : template<typename _Integer>
1668 : : void
1669 : : _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1670 : : { _M_fill_assign(__n, __val); }
1671 : :
1672 : : // called by the range assign to implement [23.1.1]/9
1673 : : template<typename _InputIterator>
1674 : : void
1675 : : _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1676 : : __false_type)
1677 : : {
1678 : : typedef typename std::iterator_traits<_InputIterator>::
1679 : : iterator_category _IterCategory;
1680 : : _M_assign_aux(__first, __last, _IterCategory());
1681 : : }
1682 : :
1683 : : // called by the second assign_dispatch above
1684 : : template<typename _InputIterator>
1685 : : void
1686 : : _M_assign_aux(_InputIterator __first, _InputIterator __last,
1687 : : std::input_iterator_tag);
1688 : :
1689 : : // called by the second assign_dispatch above
1690 : : template<typename _ForwardIterator>
1691 : : void
1692 : : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1693 : : std::forward_iterator_tag)
1694 : : {
1695 : : const size_type __len = std::distance(__first, __last);
1696 : : if (__len > size())
1697 : : {
1698 : : _ForwardIterator __mid = __first;
1699 : : std::advance(__mid, size());
1700 : : std::copy(__first, __mid, begin());
1701 : : insert(end(), __mid, __last);
1702 : : }
1703 : : else
1704 : : _M_erase_at_end(std::copy(__first, __last, begin()));
1705 : : }
1706 : :
1707 : : // Called by assign(n,t), and the range assign when it turns out
1708 : : // to be the same thing.
1709 : : void
1710 : : _M_fill_assign(size_type __n, const value_type& __val)
1711 : : {
1712 : : if (__n > size())
1713 : : {
1714 : : std::fill(begin(), end(), __val);
1715 : : insert(end(), __n - size(), __val);
1716 : : }
1717 : : else
1718 : : {
1719 : : _M_erase_at_end(begin() + difference_type(__n));
1720 : : std::fill(begin(), end(), __val);
1721 : : }
1722 : : }
1723 : :
1724 : : //@{
1725 : : /// Helper functions for push_* and pop_*.
1726 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
1727 : : void _M_push_back_aux(const value_type&);
1728 : :
1729 : : void _M_push_front_aux(const value_type&);
1730 : : #else
1731 : : template<typename... _Args>
1732 : : void _M_push_back_aux(_Args&&... __args);
1733 : :
1734 : : template<typename... _Args>
1735 : : void _M_push_front_aux(_Args&&... __args);
1736 : : #endif
1737 : :
1738 : : void _M_pop_back_aux();
1739 : :
1740 : : void _M_pop_front_aux();
1741 : : //@}
1742 : :
1743 : : // Internal insert functions follow. The *_aux functions do the actual
1744 : : // insertion work when all shortcuts fail.
1745 : :
1746 : : // called by the range insert to implement [23.1.1]/9
1747 : :
1748 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1749 : : // 438. Ambiguity in the "do the right thing" clause
1750 : : template<typename _Integer>
1751 : : void
1752 : : _M_insert_dispatch(iterator __pos,
1753 : : _Integer __n, _Integer __x, __true_type)
1754 : : { _M_fill_insert(__pos, __n, __x); }
1755 : :
1756 : : // called by the range insert to implement [23.1.1]/9
1757 : : template<typename _InputIterator>
1758 : : void
1759 : : _M_insert_dispatch(iterator __pos,
1760 : : _InputIterator __first, _InputIterator __last,
1761 : : __false_type)
1762 : : {
1763 : : typedef typename std::iterator_traits<_InputIterator>::
1764 : : iterator_category _IterCategory;
1765 : : _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1766 : : }
1767 : :
1768 : : // called by the second insert_dispatch above
1769 : : template<typename _InputIterator>
1770 : : void
1771 : : _M_range_insert_aux(iterator __pos, _InputIterator __first,
1772 : : _InputIterator __last, std::input_iterator_tag);
1773 : :
1774 : : // called by the second insert_dispatch above
1775 : : template<typename _ForwardIterator>
1776 : : void
1777 : : _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1778 : : _ForwardIterator __last, std::forward_iterator_tag);
1779 : :
1780 : : // Called by insert(p,n,x), and the range insert when it turns out to be
1781 : : // the same thing. Can use fill functions in optimal situations,
1782 : : // otherwise passes off to insert_aux(p,n,x).
1783 : : void
1784 : : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1785 : :
1786 : : // called by insert(p,x)
1787 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
1788 : : iterator
1789 : : _M_insert_aux(iterator __pos, const value_type& __x);
1790 : : #else
1791 : : template<typename... _Args>
1792 : : iterator
1793 : : _M_insert_aux(iterator __pos, _Args&&... __args);
1794 : : #endif
1795 : :
1796 : : // called by insert(p,n,x) via fill_insert
1797 : : void
1798 : : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1799 : :
1800 : : // called by range_insert_aux for forward iterators
1801 : : template<typename _ForwardIterator>
1802 : : void
1803 : : _M_insert_aux(iterator __pos,
1804 : : _ForwardIterator __first, _ForwardIterator __last,
1805 : : size_type __n);
1806 : :
1807 : :
1808 : : // Internal erase functions follow.
1809 : :
1810 : : void
1811 : : _M_destroy_data_aux(iterator __first, iterator __last);
1812 : :
1813 : : // Called by ~deque().
1814 : : // NB: Doesn't deallocate the nodes.
1815 : : template<typename _Alloc1>
1816 : : void
1817 : : _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
1818 : : { _M_destroy_data_aux(__first, __last); }
1819 : :
1820 : : void
1821 : 3086135 : _M_destroy_data(iterator __first, iterator __last,
1822 : : const std::allocator<_Tp>&)
1823 : : {
1824 : : if (!__has_trivial_destructor(value_type))
1825 : : _M_destroy_data_aux(__first, __last);
1826 : 3086135 : }
1827 : :
1828 : : // Called by erase(q1, q2).
1829 : : void
1830 : : _M_erase_at_begin(iterator __pos)
1831 : : {
1832 : : _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
1833 : : _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
1834 : : this->_M_impl._M_start = __pos;
1835 : : }
1836 : :
1837 : : // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
1838 : : // _M_fill_assign, operator=.
1839 : : void
1840 : : _M_erase_at_end(iterator __pos)
1841 : : {
1842 : : _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
1843 : : _M_destroy_nodes(__pos._M_node + 1,
1844 : : this->_M_impl._M_finish._M_node + 1);
1845 : : this->_M_impl._M_finish = __pos;
1846 : : }
1847 : :
1848 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1849 : : // Called by resize(sz).
1850 : : void
1851 : : _M_default_append(size_type __n);
1852 : :
1853 : : bool
1854 : : _M_shrink_to_fit();
1855 : : #endif
1856 : :
1857 : : //@{
1858 : : /// Memory-handling helpers for the previous internal insert functions.
1859 : : iterator
1860 : : _M_reserve_elements_at_front(size_type __n)
1861 : : {
1862 : : const size_type __vacancies = this->_M_impl._M_start._M_cur
1863 : : - this->_M_impl._M_start._M_first;
1864 : : if (__n > __vacancies)
1865 : : _M_new_elements_at_front(__n - __vacancies);
1866 : : return this->_M_impl._M_start - difference_type(__n);
1867 : : }
1868 : :
1869 : : iterator
1870 : : _M_reserve_elements_at_back(size_type __n)
1871 : : {
1872 : : const size_type __vacancies = (this->_M_impl._M_finish._M_last
1873 : : - this->_M_impl._M_finish._M_cur) - 1;
1874 : : if (__n > __vacancies)
1875 : : _M_new_elements_at_back(__n - __vacancies);
1876 : : return this->_M_impl._M_finish + difference_type(__n);
1877 : : }
1878 : :
1879 : : void
1880 : : _M_new_elements_at_front(size_type __new_elements);
1881 : :
1882 : : void
1883 : : _M_new_elements_at_back(size_type __new_elements);
1884 : : //@}
1885 : :
1886 : :
1887 : : //@{
1888 : : /**
1889 : : * @brief Memory-handling helpers for the major %map.
1890 : : *
1891 : : * Makes sure the _M_map has space for new nodes. Does not
1892 : : * actually add the nodes. Can invalidate _M_map pointers.
1893 : : * (And consequently, %deque iterators.)
1894 : : */
1895 : : void
1896 : 0 : _M_reserve_map_at_back(size_type __nodes_to_add = 1)
1897 : : {
1898 [ # # ][ # # ]: 0 : if (__nodes_to_add + 1 > this->_M_impl._M_map_size
[ # # ][ # # ]
1899 : : - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
1900 : 0 : _M_reallocate_map(__nodes_to_add, false);
1901 : 0 : }
1902 : :
1903 : : void
1904 : : _M_reserve_map_at_front(size_type __nodes_to_add = 1)
1905 : : {
1906 : : if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
1907 : : - this->_M_impl._M_map))
1908 : : _M_reallocate_map(__nodes_to_add, true);
1909 : : }
1910 : :
1911 : : void
1912 : : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1913 : : //@}
1914 : : };
1915 : :
1916 : :
1917 : : /**
1918 : : * @brief Deque equality comparison.
1919 : : * @param __x A %deque.
1920 : : * @param __y A %deque of the same type as @a __x.
1921 : : * @return True iff the size and elements of the deques are equal.
1922 : : *
1923 : : * This is an equivalence relation. It is linear in the size of the
1924 : : * deques. Deques are considered equivalent if their sizes are equal,
1925 : : * and if corresponding elements compare equal.
1926 : : */
1927 : : template<typename _Tp, typename _Alloc>
1928 : : inline bool
1929 : : operator==(const deque<_Tp, _Alloc>& __x,
1930 : : const deque<_Tp, _Alloc>& __y)
1931 : : { return __x.size() == __y.size()
1932 : : && std::equal(__x.begin(), __x.end(), __y.begin()); }
1933 : :
1934 : : /**
1935 : : * @brief Deque ordering relation.
1936 : : * @param __x A %deque.
1937 : : * @param __y A %deque of the same type as @a __x.
1938 : : * @return True iff @a x is lexicographically less than @a __y.
1939 : : *
1940 : : * This is a total ordering relation. It is linear in the size of the
1941 : : * deques. The elements must be comparable with @c <.
1942 : : *
1943 : : * See std::lexicographical_compare() for how the determination is made.
1944 : : */
1945 : : template<typename _Tp, typename _Alloc>
1946 : : inline bool
1947 : : operator<(const deque<_Tp, _Alloc>& __x,
1948 : : const deque<_Tp, _Alloc>& __y)
1949 : : { return std::lexicographical_compare(__x.begin(), __x.end(),
1950 : : __y.begin(), __y.end()); }
1951 : :
1952 : : /// Based on operator==
1953 : : template<typename _Tp, typename _Alloc>
1954 : : inline bool
1955 : : operator!=(const deque<_Tp, _Alloc>& __x,
1956 : : const deque<_Tp, _Alloc>& __y)
1957 : : { return !(__x == __y); }
1958 : :
1959 : : /// Based on operator<
1960 : : template<typename _Tp, typename _Alloc>
1961 : : inline bool
1962 : : operator>(const deque<_Tp, _Alloc>& __x,
1963 : : const deque<_Tp, _Alloc>& __y)
1964 : : { return __y < __x; }
1965 : :
1966 : : /// Based on operator<
1967 : : template<typename _Tp, typename _Alloc>
1968 : : inline bool
1969 : : operator<=(const deque<_Tp, _Alloc>& __x,
1970 : : const deque<_Tp, _Alloc>& __y)
1971 : : { return !(__y < __x); }
1972 : :
1973 : : /// Based on operator<
1974 : : template<typename _Tp, typename _Alloc>
1975 : : inline bool
1976 : : operator>=(const deque<_Tp, _Alloc>& __x,
1977 : : const deque<_Tp, _Alloc>& __y)
1978 : : { return !(__x < __y); }
1979 : :
1980 : : /// See std::deque::swap().
1981 : : template<typename _Tp, typename _Alloc>
1982 : : inline void
1983 : : swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
1984 : : { __x.swap(__y); }
1985 : :
1986 : : #undef _GLIBCXX_DEQUE_BUF_SIZE
1987 : :
1988 : : _GLIBCXX_END_NAMESPACE_CONTAINER
1989 : : } // namespace std
1990 : :
1991 : : #endif /* _STL_DEQUE_H */
|
