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