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