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