libstdc++
|
00001 // Deque implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1997 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file stl_deque.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _STL_DEQUE_H 00058 #define _STL_DEQUE_H 1 00059 00060 #include <bits/concept_check.h> 00061 #include <bits/stl_iterator_base_types.h> 00062 #include <bits/stl_iterator_base_funcs.h> 00063 #include <initializer_list> 00064 00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00066 00067 /** 00068 * @brief This function controls the size of memory nodes. 00069 * @param size The size of an element. 00070 * @return The number (not byte size) of elements per node. 00071 * 00072 * This function started off as a compiler kludge from SGI, but seems to 00073 * be a useful wrapper around a repeated constant expression. The '512' is 00074 * tunable (and no other code needs to change), but no investigation has 00075 * been done since inheriting the SGI code. 00076 */ 00077 inline size_t 00078 __deque_buf_size(size_t __size) 00079 { return __size < 512 ? size_t(512 / __size) : size_t(1); } 00080 00081 00082 /** 00083 * @brief A deque::iterator. 00084 * 00085 * Quite a bit of intelligence here. Much of the functionality of 00086 * deque is actually passed off to this class. A deque holds two 00087 * of these internally, marking its valid range. Access to 00088 * elements is done as offsets of either of those two, relying on 00089 * operator overloading in this class. 00090 * 00091 * All the functions are op overloads except for _M_set_node. 00092 */ 00093 template<typename _Tp, typename _Ref, typename _Ptr> 00094 struct _Deque_iterator 00095 { 00096 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 00097 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 00098 00099 static size_t _S_buffer_size() 00100 { return __deque_buf_size(sizeof(_Tp)); } 00101 00102 typedef std::random_access_iterator_tag iterator_category; 00103 typedef _Tp value_type; 00104 typedef _Ptr pointer; 00105 typedef _Ref reference; 00106 typedef size_t size_type; 00107 typedef ptrdiff_t difference_type; 00108 typedef _Tp** _Map_pointer; 00109 typedef _Deque_iterator _Self; 00110 00111 _Tp* _M_cur; 00112 _Tp* _M_first; 00113 _Tp* _M_last; 00114 _Map_pointer _M_node; 00115 00116 _Deque_iterator(_Tp* __x, _Map_pointer __y) 00117 : _M_cur(__x), _M_first(*__y), 00118 _M_last(*__y + _S_buffer_size()), _M_node(__y) { } 00119 00120 _Deque_iterator() 00121 : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { } 00122 00123 _Deque_iterator(const iterator& __x) 00124 : _M_cur(__x._M_cur), _M_first(__x._M_first), 00125 _M_last(__x._M_last), _M_node(__x._M_node) { } 00126 00127 reference 00128 operator*() const 00129 { return *_M_cur; } 00130 00131 pointer 00132 operator->() const 00133 { return _M_cur; } 00134 00135 _Self& 00136 operator++() 00137 { 00138 ++_M_cur; 00139 if (_M_cur == _M_last) 00140 { 00141 _M_set_node(_M_node + 1); 00142 _M_cur = _M_first; 00143 } 00144 return *this; 00145 } 00146 00147 _Self 00148 operator++(int) 00149 { 00150 _Self __tmp = *this; 00151 ++*this; 00152 return __tmp; 00153 } 00154 00155 _Self& 00156 operator--() 00157 { 00158 if (_M_cur == _M_first) 00159 { 00160 _M_set_node(_M_node - 1); 00161 _M_cur = _M_last; 00162 } 00163 --_M_cur; 00164 return *this; 00165 } 00166 00167 _Self 00168 operator--(int) 00169 { 00170 _Self __tmp = *this; 00171 --*this; 00172 return __tmp; 00173 } 00174 00175 _Self& 00176 operator+=(difference_type __n) 00177 { 00178 const difference_type __offset = __n + (_M_cur - _M_first); 00179 if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) 00180 _M_cur += __n; 00181 else 00182 { 00183 const difference_type __node_offset = 00184 __offset > 0 ? __offset / difference_type(_S_buffer_size()) 00185 : -difference_type((-__offset - 1) 00186 / _S_buffer_size()) - 1; 00187 _M_set_node(_M_node + __node_offset); 00188 _M_cur = _M_first + (__offset - __node_offset 00189 * difference_type(_S_buffer_size())); 00190 } 00191 return *this; 00192 } 00193 00194 _Self 00195 operator+(difference_type __n) const 00196 { 00197 _Self __tmp = *this; 00198 return __tmp += __n; 00199 } 00200 00201 _Self& 00202 operator-=(difference_type __n) 00203 { return *this += -__n; } 00204 00205 _Self 00206 operator-(difference_type __n) const 00207 { 00208 _Self __tmp = *this; 00209 return __tmp -= __n; 00210 } 00211 00212 reference 00213 operator[](difference_type __n) const 00214 { return *(*this + __n); } 00215 00216 /** 00217 * Prepares to traverse new_node. Sets everything except 00218 * _M_cur, which should therefore be set by the caller 00219 * immediately afterwards, based on _M_first and _M_last. 00220 */ 00221 void 00222 _M_set_node(_Map_pointer __new_node) 00223 { 00224 _M_node = __new_node; 00225 _M_first = *__new_node; 00226 _M_last = _M_first + difference_type(_S_buffer_size()); 00227 } 00228 }; 00229 00230 // Note: we also provide overloads whose operands are of the same type in 00231 // order to avoid ambiguous overload resolution when std::rel_ops operators 00232 // are in scope (for additional details, see libstdc++/3628) 00233 template<typename _Tp, typename _Ref, typename _Ptr> 00234 inline bool 00235 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00236 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00237 { return __x._M_cur == __y._M_cur; } 00238 00239 template<typename _Tp, typename _RefL, typename _PtrL, 00240 typename _RefR, typename _PtrR> 00241 inline bool 00242 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00243 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00244 { return __x._M_cur == __y._M_cur; } 00245 00246 template<typename _Tp, typename _Ref, typename _Ptr> 00247 inline bool 00248 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00249 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00250 { return !(__x == __y); } 00251 00252 template<typename _Tp, typename _RefL, typename _PtrL, 00253 typename _RefR, typename _PtrR> 00254 inline bool 00255 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00256 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00257 { return !(__x == __y); } 00258 00259 template<typename _Tp, typename _Ref, typename _Ptr> 00260 inline bool 00261 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00262 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00263 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) 00264 : (__x._M_node < __y._M_node); } 00265 00266 template<typename _Tp, typename _RefL, typename _PtrL, 00267 typename _RefR, typename _PtrR> 00268 inline bool 00269 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00270 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00271 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) 00272 : (__x._M_node < __y._M_node); } 00273 00274 template<typename _Tp, typename _Ref, typename _Ptr> 00275 inline bool 00276 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00277 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00278 { return __y < __x; } 00279 00280 template<typename _Tp, typename _RefL, typename _PtrL, 00281 typename _RefR, typename _PtrR> 00282 inline bool 00283 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00284 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00285 { return __y < __x; } 00286 00287 template<typename _Tp, typename _Ref, typename _Ptr> 00288 inline bool 00289 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00290 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00291 { return !(__y < __x); } 00292 00293 template<typename _Tp, typename _RefL, typename _PtrL, 00294 typename _RefR, typename _PtrR> 00295 inline bool 00296 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00298 { return !(__y < __x); } 00299 00300 template<typename _Tp, typename _Ref, typename _Ptr> 00301 inline bool 00302 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00303 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00304 { return !(__x < __y); } 00305 00306 template<typename _Tp, typename _RefL, typename _PtrL, 00307 typename _RefR, typename _PtrR> 00308 inline bool 00309 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00310 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00311 { return !(__x < __y); } 00312 00313 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00314 // According to the resolution of DR179 not only the various comparison 00315 // operators but also operator- must accept mixed iterator/const_iterator 00316 // parameters. 00317 template<typename _Tp, typename _Ref, typename _Ptr> 00318 inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type 00319 operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, 00320 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) 00321 { 00322 return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type 00323 (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size()) 00324 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) 00325 + (__y._M_last - __y._M_cur); 00326 } 00327 00328 template<typename _Tp, typename _RefL, typename _PtrL, 00329 typename _RefR, typename _PtrR> 00330 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 00331 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, 00332 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) 00333 { 00334 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type 00335 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) 00336 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) 00337 + (__y._M_last - __y._M_cur); 00338 } 00339 00340 template<typename _Tp, typename _Ref, typename _Ptr> 00341 inline _Deque_iterator<_Tp, _Ref, _Ptr> 00342 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) 00343 { return __x + __n; } 00344 00345 template<typename _Tp> 00346 void 00347 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 00348 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value); 00349 00350 /** 00351 * Deque base class. This class provides the unified face for %deque's 00352 * allocation. This class's constructor and destructor allocate and 00353 * deallocate (but do not initialize) storage. This makes %exception 00354 * safety easier. 00355 * 00356 * Nothing in this class ever constructs or destroys an actual Tp element. 00357 * (Deque handles that itself.) Only/All memory management is performed 00358 * here. 00359 */ 00360 template<typename _Tp, typename _Alloc> 00361 class _Deque_base 00362 { 00363 public: 00364 typedef _Alloc allocator_type; 00365 00366 allocator_type 00367 get_allocator() const 00368 { return allocator_type(_M_get_Tp_allocator()); } 00369 00370 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; 00371 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 00372 00373 _Deque_base() 00374 : _M_impl() 00375 { _M_initialize_map(0); } 00376 00377 _Deque_base(const allocator_type& __a, size_t __num_elements) 00378 : _M_impl(__a) 00379 { _M_initialize_map(__num_elements); } 00380 00381 _Deque_base(const allocator_type& __a) 00382 : _M_impl(__a) 00383 { } 00384 00385 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00386 _Deque_base(_Deque_base&& __x) 00387 : _M_impl(__x._M_get_Tp_allocator()) 00388 { 00389 _M_initialize_map(0); 00390 if (__x._M_impl._M_map) 00391 { 00392 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00393 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00394 std::swap(this->_M_impl._M_map, __x._M_impl._M_map); 00395 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); 00396 } 00397 } 00398 #endif 00399 00400 ~_Deque_base(); 00401 00402 protected: 00403 //This struct encapsulates the implementation of the std::deque 00404 //standard container and at the same time makes use of the EBO 00405 //for empty allocators. 00406 typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; 00407 00408 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 00409 00410 struct _Deque_impl 00411 : public _Tp_alloc_type 00412 { 00413 _Tp** _M_map; 00414 size_t _M_map_size; 00415 iterator _M_start; 00416 iterator _M_finish; 00417 00418 _Deque_impl() 00419 : _Tp_alloc_type(), _M_map(0), _M_map_size(0), 00420 _M_start(), _M_finish() 00421 { } 00422 00423 _Deque_impl(const _Tp_alloc_type& __a) 00424 : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), 00425 _M_start(), _M_finish() 00426 { } 00427 }; 00428 00429 _Tp_alloc_type& 00430 _M_get_Tp_allocator() 00431 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); } 00432 00433 const _Tp_alloc_type& 00434 _M_get_Tp_allocator() const 00435 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } 00436 00437 _Map_alloc_type 00438 _M_get_map_allocator() const 00439 { return _Map_alloc_type(_M_get_Tp_allocator()); } 00440 00441 _Tp* 00442 _M_allocate_node() 00443 { 00444 return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); 00445 } 00446 00447 void 00448 _M_deallocate_node(_Tp* __p) 00449 { 00450 _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); 00451 } 00452 00453 _Tp** 00454 _M_allocate_map(size_t __n) 00455 { return _M_get_map_allocator().allocate(__n); } 00456 00457 void 00458 _M_deallocate_map(_Tp** __p, size_t __n) 00459 { _M_get_map_allocator().deallocate(__p, __n); } 00460 00461 protected: 00462 void _M_initialize_map(size_t); 00463 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); 00464 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); 00465 enum { _S_initial_map_size = 8 }; 00466 00467 _Deque_impl _M_impl; 00468 }; 00469 00470 template<typename _Tp, typename _Alloc> 00471 _Deque_base<_Tp, _Alloc>:: 00472 ~_Deque_base() 00473 { 00474 if (this->_M_impl._M_map) 00475 { 00476 _M_destroy_nodes(this->_M_impl._M_start._M_node, 00477 this->_M_impl._M_finish._M_node + 1); 00478 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00479 } 00480 } 00481 00482 /** 00483 * @brief Layout storage. 00484 * @param num_elements The count of T's for which to allocate space 00485 * at first. 00486 * @return Nothing. 00487 * 00488 * The initial underlying memory layout is a bit complicated... 00489 */ 00490 template<typename _Tp, typename _Alloc> 00491 void 00492 _Deque_base<_Tp, _Alloc>:: 00493 _M_initialize_map(size_t __num_elements) 00494 { 00495 const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp)) 00496 + 1); 00497 00498 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size, 00499 size_t(__num_nodes + 2)); 00500 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size); 00501 00502 // For "small" maps (needing less than _M_map_size nodes), allocation 00503 // starts in the middle elements and grows outwards. So nstart may be 00504 // the beginning of _M_map, but for small maps it may be as far in as 00505 // _M_map+3. 00506 00507 _Tp** __nstart = (this->_M_impl._M_map 00508 + (this->_M_impl._M_map_size - __num_nodes) / 2); 00509 _Tp** __nfinish = __nstart + __num_nodes; 00510 00511 __try 00512 { _M_create_nodes(__nstart, __nfinish); } 00513 __catch(...) 00514 { 00515 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00516 this->_M_impl._M_map = 0; 00517 this->_M_impl._M_map_size = 0; 00518 __throw_exception_again; 00519 } 00520 00521 this->_M_impl._M_start._M_set_node(__nstart); 00522 this->_M_impl._M_finish._M_set_node(__nfinish - 1); 00523 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first; 00524 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first 00525 + __num_elements 00526 % __deque_buf_size(sizeof(_Tp))); 00527 } 00528 00529 template<typename _Tp, typename _Alloc> 00530 void 00531 _Deque_base<_Tp, _Alloc>:: 00532 _M_create_nodes(_Tp** __nstart, _Tp** __nfinish) 00533 { 00534 _Tp** __cur; 00535 __try 00536 { 00537 for (__cur = __nstart; __cur < __nfinish; ++__cur) 00538 *__cur = this->_M_allocate_node(); 00539 } 00540 __catch(...) 00541 { 00542 _M_destroy_nodes(__nstart, __cur); 00543 __throw_exception_again; 00544 } 00545 } 00546 00547 template<typename _Tp, typename _Alloc> 00548 void 00549 _Deque_base<_Tp, _Alloc>:: 00550 _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) 00551 { 00552 for (_Tp** __n = __nstart; __n < __nfinish; ++__n) 00553 _M_deallocate_node(*__n); 00554 } 00555 00556 /** 00557 * @brief A standard container using fixed-size memory allocation and 00558 * constant-time manipulation of elements at either end. 00559 * 00560 * @ingroup sequences 00561 * 00562 * Meets the requirements of a <a href="tables.html#65">container</a>, a 00563 * <a href="tables.html#66">reversible container</a>, and a 00564 * <a href="tables.html#67">sequence</a>, including the 00565 * <a href="tables.html#68">optional sequence requirements</a>. 00566 * 00567 * In previous HP/SGI versions of deque, there was an extra template 00568 * parameter so users could control the node size. This extension turned 00569 * out to violate the C++ standard (it can be detected using template 00570 * template parameters), and it was removed. 00571 * 00572 * Here's how a deque<Tp> manages memory. Each deque has 4 members: 00573 * 00574 * - Tp** _M_map 00575 * - size_t _M_map_size 00576 * - iterator _M_start, _M_finish 00577 * 00578 * map_size is at least 8. %map is an array of map_size 00579 * pointers-to-"nodes". (The name %map has nothing to do with the 00580 * std::map class, and "nodes" should not be confused with 00581 * std::list's usage of "node".) 00582 * 00583 * A "node" has no specific type name as such, but it is referred 00584 * to as "node" in this file. It is a simple array-of-Tp. If Tp 00585 * is very large, there will be one Tp element per node (i.e., an 00586 * "array" of one). For non-huge Tp's, node size is inversely 00587 * related to Tp size: the larger the Tp, the fewer Tp's will fit 00588 * in a node. The goal here is to keep the total size of a node 00589 * relatively small and constant over different Tp's, to improve 00590 * allocator efficiency. 00591 * 00592 * Not every pointer in the %map array will point to a node. If 00593 * the initial number of elements in the deque is small, the 00594 * /middle/ %map pointers will be valid, and the ones at the edges 00595 * will be unused. This same situation will arise as the %map 00596 * grows: available %map pointers, if any, will be on the ends. As 00597 * new nodes are created, only a subset of the %map's pointers need 00598 * to be copied "outward". 00599 * 00600 * Class invariants: 00601 * - For any nonsingular iterator i: 00602 * - i.node points to a member of the %map array. (Yes, you read that 00603 * correctly: i.node does not actually point to a node.) The member of 00604 * the %map array is what actually points to the node. 00605 * - i.first == *(i.node) (This points to the node (first Tp element).) 00606 * - i.last == i.first + node_size 00607 * - i.cur is a pointer in the range [i.first, i.last). NOTE: 00608 * the implication of this is that i.cur is always a dereferenceable 00609 * pointer, even if i is a past-the-end iterator. 00610 * - Start and Finish are always nonsingular iterators. NOTE: this 00611 * means that an empty deque must have one node, a deque with <N 00612 * elements (where N is the node buffer size) must have one node, a 00613 * deque with N through (2N-1) elements must have two nodes, etc. 00614 * - For every node other than start.node and finish.node, every 00615 * element in the node is an initialized object. If start.node == 00616 * finish.node, then [start.cur, finish.cur) are initialized 00617 * objects, and the elements outside that range are uninitialized 00618 * storage. Otherwise, [start.cur, start.last) and [finish.first, 00619 * finish.cur) are initialized objects, and [start.first, start.cur) 00620 * and [finish.cur, finish.last) are uninitialized storage. 00621 * - [%map, %map + map_size) is a valid, non-empty range. 00622 * - [start.node, finish.node] is a valid range contained within 00623 * [%map, %map + map_size). 00624 * - A pointer in the range [%map, %map + map_size) points to an allocated 00625 * node if and only if the pointer is in the range 00626 * [start.node, finish.node]. 00627 * 00628 * Here's the magic: nothing in deque is "aware" of the discontiguous 00629 * storage! 00630 * 00631 * The memory setup and layout occurs in the parent, _Base, and the iterator 00632 * class is entirely responsible for "leaping" from one node to the next. 00633 * All the implementation routines for deque itself work only through the 00634 * start and finish iterators. This keeps the routines simple and sane, 00635 * and we can use other standard algorithms as well. 00636 */ 00637 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 00638 class deque : protected _Deque_base<_Tp, _Alloc> 00639 { 00640 // concept requirements 00641 typedef typename _Alloc::value_type _Alloc_value_type; 00642 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00643 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 00644 00645 typedef _Deque_base<_Tp, _Alloc> _Base; 00646 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 00647 00648 public: 00649 typedef _Tp value_type; 00650 typedef typename _Tp_alloc_type::pointer pointer; 00651 typedef typename _Tp_alloc_type::const_pointer const_pointer; 00652 typedef typename _Tp_alloc_type::reference reference; 00653 typedef typename _Tp_alloc_type::const_reference const_reference; 00654 typedef typename _Base::iterator iterator; 00655 typedef typename _Base::const_iterator const_iterator; 00656 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00657 typedef std::reverse_iterator<iterator> reverse_iterator; 00658 typedef size_t size_type; 00659 typedef ptrdiff_t difference_type; 00660 typedef _Alloc allocator_type; 00661 00662 protected: 00663 typedef pointer* _Map_pointer; 00664 00665 static size_t _S_buffer_size() 00666 { return __deque_buf_size(sizeof(_Tp)); } 00667 00668 // Functions controlling memory layout, and nothing else. 00669 using _Base::_M_initialize_map; 00670 using _Base::_M_create_nodes; 00671 using _Base::_M_destroy_nodes; 00672 using _Base::_M_allocate_node; 00673 using _Base::_M_deallocate_node; 00674 using _Base::_M_allocate_map; 00675 using _Base::_M_deallocate_map; 00676 using _Base::_M_get_Tp_allocator; 00677 00678 /** 00679 * A total of four data members accumulated down the hierarchy. 00680 * May be accessed via _M_impl.* 00681 */ 00682 using _Base::_M_impl; 00683 00684 public: 00685 // [23.2.1.1] construct/copy/destroy 00686 // (assign() and get_allocator() are also listed in this section) 00687 /** 00688 * @brief Default constructor creates no elements. 00689 */ 00690 deque() 00691 : _Base() { } 00692 00693 /** 00694 * @brief Creates a %deque with no elements. 00695 * @param a An allocator object. 00696 */ 00697 explicit 00698 deque(const allocator_type& __a) 00699 : _Base(__a, 0) { } 00700 00701 /** 00702 * @brief Creates a %deque with copies of an exemplar element. 00703 * @param n The number of elements to initially create. 00704 * @param value An element to copy. 00705 * @param a An allocator. 00706 * 00707 * This constructor fills the %deque with @a n copies of @a value. 00708 */ 00709 explicit 00710 deque(size_type __n, const value_type& __value = value_type(), 00711 const allocator_type& __a = allocator_type()) 00712 : _Base(__a, __n) 00713 { _M_fill_initialize(__value); } 00714 00715 /** 00716 * @brief %Deque copy constructor. 00717 * @param x A %deque of identical element and allocator types. 00718 * 00719 * The newly-created %deque uses a copy of the allocation object used 00720 * by @a x. 00721 */ 00722 deque(const deque& __x) 00723 : _Base(__x._M_get_Tp_allocator(), __x.size()) 00724 { std::__uninitialized_copy_a(__x.begin(), __x.end(), 00725 this->_M_impl._M_start, 00726 _M_get_Tp_allocator()); } 00727 00728 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00729 /** 00730 * @brief %Deque move constructor. 00731 * @param x A %deque of identical element and allocator types. 00732 * 00733 * The newly-created %deque contains the exact contents of @a x. 00734 * The contents of @a x are a valid, but unspecified %deque. 00735 */ 00736 deque(deque&& __x) 00737 : _Base(std::forward<_Base>(__x)) { } 00738 00739 /** 00740 * @brief Builds a %deque from an initializer list. 00741 * @param l An initializer_list. 00742 * @param a An allocator object. 00743 * 00744 * Create a %deque consisting of copies of the elements in the 00745 * initializer_list @a l. 00746 * 00747 * This will call the element type's copy constructor N times 00748 * (where N is l.size()) and do no memory reallocation. 00749 */ 00750 deque(initializer_list<value_type> __l, 00751 const allocator_type& __a = allocator_type()) 00752 : _Base(__a) 00753 { 00754 _M_range_initialize(__l.begin(), __l.end(), 00755 random_access_iterator_tag()); 00756 } 00757 #endif 00758 00759 /** 00760 * @brief Builds a %deque from a range. 00761 * @param first An input iterator. 00762 * @param last An input iterator. 00763 * @param a An allocator object. 00764 * 00765 * Create a %deque consisting of copies of the elements from [first, 00766 * last). 00767 * 00768 * If the iterators are forward, bidirectional, or random-access, then 00769 * this will call the elements' copy constructor N times (where N is 00770 * distance(first,last)) and do no memory reallocation. But if only 00771 * input iterators are used, then this will do at most 2N calls to the 00772 * copy constructor, and logN memory reallocations. 00773 */ 00774 template<typename _InputIterator> 00775 deque(_InputIterator __first, _InputIterator __last, 00776 const allocator_type& __a = allocator_type()) 00777 : _Base(__a) 00778 { 00779 // Check whether it's an integral type. If so, it's not an iterator. 00780 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00781 _M_initialize_dispatch(__first, __last, _Integral()); 00782 } 00783 00784 /** 00785 * The dtor only erases the elements, and note that if the elements 00786 * themselves are pointers, the pointed-to memory is not touched in any 00787 * way. Managing the pointer is the user's responsibility. 00788 */ 00789 ~deque() 00790 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); } 00791 00792 /** 00793 * @brief %Deque assignment operator. 00794 * @param x A %deque of identical element and allocator types. 00795 * 00796 * All the elements of @a x are copied, but unlike the copy constructor, 00797 * the allocator object is not copied. 00798 */ 00799 deque& 00800 operator=(const deque& __x); 00801 00802 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00803 /** 00804 * @brief %Deque move assignment operator. 00805 * @param x A %deque of identical element and allocator types. 00806 * 00807 * The contents of @a x are moved into this deque (without copying). 00808 * @a x is a valid, but unspecified %deque. 00809 */ 00810 deque& 00811 operator=(deque&& __x) 00812 { 00813 // NB: DR 675. 00814 this->clear(); 00815 this->swap(__x); 00816 return *this; 00817 } 00818 00819 /** 00820 * @brief Assigns an initializer list to a %deque. 00821 * @param l An initializer_list. 00822 * 00823 * This function fills a %deque with copies of the elements in the 00824 * initializer_list @a l. 00825 * 00826 * Note that the assignment completely changes the %deque and that the 00827 * resulting %deque's size is the same as the number of elements 00828 * assigned. Old data may be lost. 00829 */ 00830 deque& 00831 operator=(initializer_list<value_type> __l) 00832 { 00833 this->assign(__l.begin(), __l.end()); 00834 return *this; 00835 } 00836 #endif 00837 00838 /** 00839 * @brief Assigns a given value to a %deque. 00840 * @param n Number of elements to be assigned. 00841 * @param val Value to be assigned. 00842 * 00843 * This function fills a %deque with @a n copies of the given 00844 * value. Note that the assignment completely changes the 00845 * %deque and that the resulting %deque's size is the same as 00846 * the number of elements assigned. Old data may be lost. 00847 */ 00848 void 00849 assign(size_type __n, const value_type& __val) 00850 { _M_fill_assign(__n, __val); } 00851 00852 /** 00853 * @brief Assigns a range to a %deque. 00854 * @param first An input iterator. 00855 * @param last An input iterator. 00856 * 00857 * This function fills a %deque with copies of the elements in the 00858 * range [first,last). 00859 * 00860 * Note that the assignment completely changes the %deque and that the 00861 * resulting %deque's size is the same as the number of elements 00862 * assigned. Old data may be lost. 00863 */ 00864 template<typename _InputIterator> 00865 void 00866 assign(_InputIterator __first, _InputIterator __last) 00867 { 00868 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00869 _M_assign_dispatch(__first, __last, _Integral()); 00870 } 00871 00872 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00873 /** 00874 * @brief Assigns an initializer list to a %deque. 00875 * @param l An initializer_list. 00876 * 00877 * This function fills a %deque with copies of the elements in the 00878 * initializer_list @a l. 00879 * 00880 * Note that the assignment completely changes the %deque and that the 00881 * resulting %deque's size is the same as the number of elements 00882 * assigned. Old data may be lost. 00883 */ 00884 void 00885 assign(initializer_list<value_type> __l) 00886 { this->assign(__l.begin(), __l.end()); } 00887 #endif 00888 00889 /// Get a copy of the memory allocation object. 00890 allocator_type 00891 get_allocator() const 00892 { return _Base::get_allocator(); } 00893 00894 // iterators 00895 /** 00896 * Returns a read/write iterator that points to the first element in the 00897 * %deque. Iteration is done in ordinary element order. 00898 */ 00899 iterator 00900 begin() 00901 { return this->_M_impl._M_start; } 00902 00903 /** 00904 * Returns a read-only (constant) iterator that points to the first 00905 * element in the %deque. Iteration is done in ordinary element order. 00906 */ 00907 const_iterator 00908 begin() const 00909 { return this->_M_impl._M_start; } 00910 00911 /** 00912 * Returns a read/write iterator that points one past the last 00913 * element in the %deque. Iteration is done in ordinary 00914 * element order. 00915 */ 00916 iterator 00917 end() 00918 { return this->_M_impl._M_finish; } 00919 00920 /** 00921 * Returns a read-only (constant) iterator that points one past 00922 * the last element in the %deque. Iteration is done in 00923 * ordinary element order. 00924 */ 00925 const_iterator 00926 end() const 00927 { return this->_M_impl._M_finish; } 00928 00929 /** 00930 * Returns a read/write reverse iterator that points to the 00931 * last element in the %deque. Iteration is done in reverse 00932 * element order. 00933 */ 00934 reverse_iterator 00935 rbegin() 00936 { return reverse_iterator(this->_M_impl._M_finish); } 00937 00938 /** 00939 * Returns a read-only (constant) reverse iterator that points 00940 * to the last element in the %deque. Iteration is done in 00941 * reverse element order. 00942 */ 00943 const_reverse_iterator 00944 rbegin() const 00945 { return const_reverse_iterator(this->_M_impl._M_finish); } 00946 00947 /** 00948 * Returns a read/write reverse iterator that points to one 00949 * before the first element in the %deque. Iteration is done 00950 * in reverse element order. 00951 */ 00952 reverse_iterator 00953 rend() 00954 { return reverse_iterator(this->_M_impl._M_start); } 00955 00956 /** 00957 * Returns a read-only (constant) reverse iterator that points 00958 * to one before the first element in the %deque. Iteration is 00959 * done in reverse element order. 00960 */ 00961 const_reverse_iterator 00962 rend() const 00963 { return const_reverse_iterator(this->_M_impl._M_start); } 00964 00965 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00966 /** 00967 * Returns a read-only (constant) iterator that points to the first 00968 * element in the %deque. Iteration is done in ordinary element order. 00969 */ 00970 const_iterator 00971 cbegin() const 00972 { return this->_M_impl._M_start; } 00973 00974 /** 00975 * Returns a read-only (constant) iterator that points one past 00976 * the last element in the %deque. Iteration is done in 00977 * ordinary element order. 00978 */ 00979 const_iterator 00980 cend() const 00981 { return this->_M_impl._M_finish; } 00982 00983 /** 00984 * Returns a read-only (constant) reverse iterator that points 00985 * to the last element in the %deque. Iteration is done in 00986 * reverse element order. 00987 */ 00988 const_reverse_iterator 00989 crbegin() const 00990 { return const_reverse_iterator(this->_M_impl._M_finish); } 00991 00992 /** 00993 * Returns a read-only (constant) reverse iterator that points 00994 * to one before the first element in the %deque. Iteration is 00995 * done in reverse element order. 00996 */ 00997 const_reverse_iterator 00998 crend() const 00999 { return const_reverse_iterator(this->_M_impl._M_start); } 01000 #endif 01001 01002 // [23.2.1.2] capacity 01003 /** Returns the number of elements in the %deque. */ 01004 size_type 01005 size() const 01006 { return this->_M_impl._M_finish - this->_M_impl._M_start; } 01007 01008 /** Returns the size() of the largest possible %deque. */ 01009 size_type 01010 max_size() const 01011 { return _M_get_Tp_allocator().max_size(); } 01012 01013 /** 01014 * @brief Resizes the %deque to the specified number of elements. 01015 * @param new_size Number of elements the %deque should contain. 01016 * @param x Data with which new elements should be populated. 01017 * 01018 * This function will %resize the %deque to the specified 01019 * number of elements. If the number is smaller than the 01020 * %deque's current size the %deque is truncated, otherwise the 01021 * %deque is extended and new elements are populated with given 01022 * data. 01023 */ 01024 void 01025 resize(size_type __new_size, value_type __x = value_type()) 01026 { 01027 const size_type __len = size(); 01028 if (__new_size < __len) 01029 _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size)); 01030 else 01031 insert(this->_M_impl._M_finish, __new_size - __len, __x); 01032 } 01033 01034 /** 01035 * Returns true if the %deque is empty. (Thus begin() would 01036 * equal end().) 01037 */ 01038 bool 01039 empty() const 01040 { return this->_M_impl._M_finish == this->_M_impl._M_start; } 01041 01042 // element access 01043 /** 01044 * @brief Subscript access to the data contained in the %deque. 01045 * @param n The index of the element for which data should be 01046 * accessed. 01047 * @return Read/write reference to data. 01048 * 01049 * This operator allows for easy, array-style, data access. 01050 * Note that data access with this operator is unchecked and 01051 * out_of_range lookups are not defined. (For checked lookups 01052 * see at().) 01053 */ 01054 reference 01055 operator[](size_type __n) 01056 { return this->_M_impl._M_start[difference_type(__n)]; } 01057 01058 /** 01059 * @brief Subscript access to the data contained in the %deque. 01060 * @param n The index of the element for which data should be 01061 * accessed. 01062 * @return Read-only (constant) reference to data. 01063 * 01064 * This operator allows for easy, array-style, data access. 01065 * Note that data access with this operator is unchecked and 01066 * out_of_range lookups are not defined. (For checked lookups 01067 * see at().) 01068 */ 01069 const_reference 01070 operator[](size_type __n) const 01071 { return this->_M_impl._M_start[difference_type(__n)]; } 01072 01073 protected: 01074 /// Safety check used only from at(). 01075 void 01076 _M_range_check(size_type __n) const 01077 { 01078 if (__n >= this->size()) 01079 __throw_out_of_range(__N("deque::_M_range_check")); 01080 } 01081 01082 public: 01083 /** 01084 * @brief Provides access to the data contained in the %deque. 01085 * @param n The index of the element for which data should be 01086 * accessed. 01087 * @return Read/write reference to data. 01088 * @throw std::out_of_range If @a n is an invalid index. 01089 * 01090 * This function provides for safer data access. The parameter 01091 * is first checked that it is in the range of the deque. The 01092 * function throws out_of_range if the check fails. 01093 */ 01094 reference 01095 at(size_type __n) 01096 { 01097 _M_range_check(__n); 01098 return (*this)[__n]; 01099 } 01100 01101 /** 01102 * @brief Provides access to the data contained in the %deque. 01103 * @param n The index of the element for which data should be 01104 * accessed. 01105 * @return Read-only (constant) reference to data. 01106 * @throw std::out_of_range If @a n is an invalid index. 01107 * 01108 * This function provides for safer data access. The parameter is first 01109 * checked that it is in the range of the deque. The function throws 01110 * out_of_range if the check fails. 01111 */ 01112 const_reference 01113 at(size_type __n) const 01114 { 01115 _M_range_check(__n); 01116 return (*this)[__n]; 01117 } 01118 01119 /** 01120 * Returns a read/write reference to the data at the first 01121 * element of the %deque. 01122 */ 01123 reference 01124 front() 01125 { return *begin(); } 01126 01127 /** 01128 * Returns a read-only (constant) reference to the data at the first 01129 * element of the %deque. 01130 */ 01131 const_reference 01132 front() const 01133 { return *begin(); } 01134 01135 /** 01136 * Returns a read/write reference to the data at the last element of the 01137 * %deque. 01138 */ 01139 reference 01140 back() 01141 { 01142 iterator __tmp = end(); 01143 --__tmp; 01144 return *__tmp; 01145 } 01146 01147 /** 01148 * Returns a read-only (constant) reference to the data at the last 01149 * element of the %deque. 01150 */ 01151 const_reference 01152 back() const 01153 { 01154 const_iterator __tmp = end(); 01155 --__tmp; 01156 return *__tmp; 01157 } 01158 01159 // [23.2.1.2] modifiers 01160 /** 01161 * @brief Add data to the front of the %deque. 01162 * @param x Data to be added. 01163 * 01164 * This is a typical stack operation. The function creates an 01165 * element at the front of the %deque and assigns the given 01166 * data to it. Due to the nature of a %deque this operation 01167 * can be done in constant time. 01168 */ 01169 void 01170 push_front(const value_type& __x) 01171 { 01172 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 01173 { 01174 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x); 01175 --this->_M_impl._M_start._M_cur; 01176 } 01177 else 01178 _M_push_front_aux(__x); 01179 } 01180 01181 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01182 void 01183 push_front(value_type&& __x) 01184 { emplace_front(std::move(__x)); } 01185 01186 template<typename... _Args> 01187 void 01188 emplace_front(_Args&&... __args); 01189 #endif 01190 01191 /** 01192 * @brief Add data to the end of the %deque. 01193 * @param x Data to be added. 01194 * 01195 * This is a typical stack operation. The function creates an 01196 * element at the end of the %deque and assigns the given data 01197 * to it. Due to the nature of a %deque this operation can be 01198 * done in constant time. 01199 */ 01200 void 01201 push_back(const value_type& __x) 01202 { 01203 if (this->_M_impl._M_finish._M_cur 01204 != this->_M_impl._M_finish._M_last - 1) 01205 { 01206 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x); 01207 ++this->_M_impl._M_finish._M_cur; 01208 } 01209 else 01210 _M_push_back_aux(__x); 01211 } 01212 01213 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01214 void 01215 push_back(value_type&& __x) 01216 { emplace_back(std::move(__x)); } 01217 01218 template<typename... _Args> 01219 void 01220 emplace_back(_Args&&... __args); 01221 #endif 01222 01223 /** 01224 * @brief Removes first element. 01225 * 01226 * This is a typical stack operation. It shrinks the %deque by one. 01227 * 01228 * Note that no data is returned, and if the first element's data is 01229 * needed, it should be retrieved before pop_front() is called. 01230 */ 01231 void 01232 pop_front() 01233 { 01234 if (this->_M_impl._M_start._M_cur 01235 != this->_M_impl._M_start._M_last - 1) 01236 { 01237 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 01238 ++this->_M_impl._M_start._M_cur; 01239 } 01240 else 01241 _M_pop_front_aux(); 01242 } 01243 01244 /** 01245 * @brief Removes last element. 01246 * 01247 * This is a typical stack operation. It shrinks the %deque by one. 01248 * 01249 * Note that no data is returned, and if the last element's data is 01250 * needed, it should be retrieved before pop_back() is called. 01251 */ 01252 void 01253 pop_back() 01254 { 01255 if (this->_M_impl._M_finish._M_cur 01256 != this->_M_impl._M_finish._M_first) 01257 { 01258 --this->_M_impl._M_finish._M_cur; 01259 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 01260 } 01261 else 01262 _M_pop_back_aux(); 01263 } 01264 01265 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01266 /** 01267 * @brief Inserts an object in %deque before specified iterator. 01268 * @param position An iterator into the %deque. 01269 * @param args Arguments. 01270 * @return An iterator that points to the inserted data. 01271 * 01272 * This function will insert an object of type T constructed 01273 * with T(std::forward<Args>(args)...) before the specified location. 01274 */ 01275 template<typename... _Args> 01276 iterator 01277 emplace(iterator __position, _Args&&... __args); 01278 #endif 01279 01280 /** 01281 * @brief Inserts given value into %deque before specified iterator. 01282 * @param position An iterator into the %deque. 01283 * @param x Data to be inserted. 01284 * @return An iterator that points to the inserted data. 01285 * 01286 * This function will insert a copy of the given value before the 01287 * specified location. 01288 */ 01289 iterator 01290 insert(iterator __position, const value_type& __x); 01291 01292 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01293 /** 01294 * @brief Inserts given rvalue into %deque before specified iterator. 01295 * @param position An iterator into the %deque. 01296 * @param x Data to be inserted. 01297 * @return An iterator that points to the inserted data. 01298 * 01299 * This function will insert a copy of the given rvalue before the 01300 * specified location. 01301 */ 01302 iterator 01303 insert(iterator __position, value_type&& __x) 01304 { return emplace(__position, std::move(__x)); } 01305 01306 /** 01307 * @brief Inserts an initializer list into the %deque. 01308 * @param p An iterator into the %deque. 01309 * @param l An initializer_list. 01310 * 01311 * This function will insert copies of the data in the 01312 * initializer_list @a l into the %deque before the location 01313 * specified by @a p. This is known as "list insert." 01314 */ 01315 void 01316 insert(iterator __p, initializer_list<value_type> __l) 01317 { this->insert(__p, __l.begin(), __l.end()); } 01318 #endif 01319 01320 /** 01321 * @brief Inserts a number of copies of given data into the %deque. 01322 * @param position An iterator into the %deque. 01323 * @param n Number of elements to be inserted. 01324 * @param x Data to be inserted. 01325 * 01326 * This function will insert a specified number of copies of the given 01327 * data before the location specified by @a position. 01328 */ 01329 void 01330 insert(iterator __position, size_type __n, const value_type& __x) 01331 { _M_fill_insert(__position, __n, __x); } 01332 01333 /** 01334 * @brief Inserts a range into the %deque. 01335 * @param position An iterator into the %deque. 01336 * @param first An input iterator. 01337 * @param last An input iterator. 01338 * 01339 * This function will insert copies of the data in the range 01340 * [first,last) into the %deque before the location specified 01341 * by @a pos. This is known as "range insert." 01342 */ 01343 template<typename _InputIterator> 01344 void 01345 insert(iterator __position, _InputIterator __first, 01346 _InputIterator __last) 01347 { 01348 // Check whether it's an integral type. If so, it's not an iterator. 01349 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 01350 _M_insert_dispatch(__position, __first, __last, _Integral()); 01351 } 01352 01353 /** 01354 * @brief Remove element at given position. 01355 * @param position Iterator pointing to element to be erased. 01356 * @return An iterator pointing to the next element (or end()). 01357 * 01358 * This function will erase the element at the given position and thus 01359 * shorten the %deque by one. 01360 * 01361 * The user is cautioned that 01362 * this function only erases the element, and that if the element is 01363 * itself a pointer, the pointed-to memory is not touched in any way. 01364 * Managing the pointer is the user's responsibility. 01365 */ 01366 iterator 01367 erase(iterator __position); 01368 01369 /** 01370 * @brief Remove a range of elements. 01371 * @param first Iterator pointing to the first element to be erased. 01372 * @param last Iterator pointing to one past the last element to be 01373 * erased. 01374 * @return An iterator pointing to the element pointed to by @a last 01375 * prior to erasing (or end()). 01376 * 01377 * This function will erase the elements in the range [first,last) and 01378 * shorten the %deque accordingly. 01379 * 01380 * The user is cautioned that 01381 * this function only erases the elements, and that if the elements 01382 * themselves are pointers, the pointed-to memory is not touched in any 01383 * way. Managing the pointer is the user's responsibility. 01384 */ 01385 iterator 01386 erase(iterator __first, iterator __last); 01387 01388 /** 01389 * @brief Swaps data with another %deque. 01390 * @param x A %deque of the same element and allocator types. 01391 * 01392 * This exchanges the elements between two deques in constant time. 01393 * (Four pointers, so it should be quite fast.) 01394 * Note that the global std::swap() function is specialized such that 01395 * std::swap(d1,d2) will feed to this function. 01396 */ 01397 void 01398 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01399 swap(deque&& __x) 01400 #else 01401 swap(deque& __x) 01402 #endif 01403 { 01404 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 01405 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 01406 std::swap(this->_M_impl._M_map, __x._M_impl._M_map); 01407 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size); 01408 01409 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01410 // 431. Swapping containers with unequal allocators. 01411 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(), 01412 __x._M_get_Tp_allocator()); 01413 } 01414 01415 /** 01416 * Erases all the elements. Note that this function only erases the 01417 * elements, and that if the elements themselves are pointers, the 01418 * pointed-to memory is not touched in any way. Managing the pointer is 01419 * the user's responsibility. 01420 */ 01421 void 01422 clear() 01423 { _M_erase_at_end(begin()); } 01424 01425 protected: 01426 // Internal constructor functions follow. 01427 01428 // called by the range constructor to implement [23.1.1]/9 01429 01430 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01431 // 438. Ambiguity in the "do the right thing" clause 01432 template<typename _Integer> 01433 void 01434 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01435 { 01436 _M_initialize_map(static_cast<size_type>(__n)); 01437 _M_fill_initialize(__x); 01438 } 01439 01440 // called by the range constructor to implement [23.1.1]/9 01441 template<typename _InputIterator> 01442 void 01443 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01444 __false_type) 01445 { 01446 typedef typename std::iterator_traits<_InputIterator>:: 01447 iterator_category _IterCategory; 01448 _M_range_initialize(__first, __last, _IterCategory()); 01449 } 01450 01451 // called by the second initialize_dispatch above 01452 //@{ 01453 /** 01454 * @brief Fills the deque with whatever is in [first,last). 01455 * @param first An input iterator. 01456 * @param last An input iterator. 01457 * @return Nothing. 01458 * 01459 * If the iterators are actually forward iterators (or better), then the 01460 * memory layout can be done all at once. Else we move forward using 01461 * push_back on each value from the iterator. 01462 */ 01463 template<typename _InputIterator> 01464 void 01465 _M_range_initialize(_InputIterator __first, _InputIterator __last, 01466 std::input_iterator_tag); 01467 01468 // called by the second initialize_dispatch above 01469 template<typename _ForwardIterator> 01470 void 01471 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 01472 std::forward_iterator_tag); 01473 //@} 01474 01475 /** 01476 * @brief Fills the %deque with copies of value. 01477 * @param value Initial value. 01478 * @return Nothing. 01479 * @pre _M_start and _M_finish have already been initialized, 01480 * but none of the %deque's elements have yet been constructed. 01481 * 01482 * This function is called only when the user provides an explicit size 01483 * (with or without an explicit exemplar value). 01484 */ 01485 void 01486 _M_fill_initialize(const value_type& __value); 01487 01488 // Internal assign functions follow. The *_aux functions do the actual 01489 // assignment work for the range versions. 01490 01491 // called by the range assign to implement [23.1.1]/9 01492 01493 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01494 // 438. Ambiguity in the "do the right thing" clause 01495 template<typename _Integer> 01496 void 01497 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01498 { _M_fill_assign(__n, __val); } 01499 01500 // called by the range assign to implement [23.1.1]/9 01501 template<typename _InputIterator> 01502 void 01503 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01504 __false_type) 01505 { 01506 typedef typename std::iterator_traits<_InputIterator>:: 01507 iterator_category _IterCategory; 01508 _M_assign_aux(__first, __last, _IterCategory()); 01509 } 01510 01511 // called by the second assign_dispatch above 01512 template<typename _InputIterator> 01513 void 01514 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01515 std::input_iterator_tag); 01516 01517 // called by the second assign_dispatch above 01518 template<typename _ForwardIterator> 01519 void 01520 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01521 std::forward_iterator_tag) 01522 { 01523 const size_type __len = std::distance(__first, __last); 01524 if (__len > size()) 01525 { 01526 _ForwardIterator __mid = __first; 01527 std::advance(__mid, size()); 01528 std::copy(__first, __mid, begin()); 01529 insert(end(), __mid, __last); 01530 } 01531 else 01532 _M_erase_at_end(std::copy(__first, __last, begin())); 01533 } 01534 01535 // Called by assign(n,t), and the range assign when it turns out 01536 // to be the same thing. 01537 void 01538 _M_fill_assign(size_type __n, const value_type& __val) 01539 { 01540 if (__n > size()) 01541 { 01542 std::fill(begin(), end(), __val); 01543 insert(end(), __n - size(), __val); 01544 } 01545 else 01546 { 01547 _M_erase_at_end(begin() + difference_type(__n)); 01548 std::fill(begin(), end(), __val); 01549 } 01550 } 01551 01552 //@{ 01553 /// Helper functions for push_* and pop_*. 01554 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 01555 void _M_push_back_aux(const value_type&); 01556 01557 void _M_push_front_aux(const value_type&); 01558 #else 01559 template<typename... _Args> 01560 void _M_push_back_aux(_Args&&... __args); 01561 01562 template<typename... _Args> 01563 void _M_push_front_aux(_Args&&... __args); 01564 #endif 01565 01566 void _M_pop_back_aux(); 01567 01568 void _M_pop_front_aux(); 01569 //@} 01570 01571 // Internal insert functions follow. The *_aux functions do the actual 01572 // insertion work when all shortcuts fail. 01573 01574 // called by the range insert to implement [23.1.1]/9 01575 01576 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01577 // 438. Ambiguity in the "do the right thing" clause 01578 template<typename _Integer> 01579 void 01580 _M_insert_dispatch(iterator __pos, 01581 _Integer __n, _Integer __x, __true_type) 01582 { _M_fill_insert(__pos, __n, __x); } 01583 01584 // called by the range insert to implement [23.1.1]/9 01585 template<typename _InputIterator> 01586 void 01587 _M_insert_dispatch(iterator __pos, 01588 _InputIterator __first, _InputIterator __last, 01589 __false_type) 01590 { 01591 typedef typename std::iterator_traits<_InputIterator>:: 01592 iterator_category _IterCategory; 01593 _M_range_insert_aux(__pos, __first, __last, _IterCategory()); 01594 } 01595 01596 // called by the second insert_dispatch above 01597 template<typename _InputIterator> 01598 void 01599 _M_range_insert_aux(iterator __pos, _InputIterator __first, 01600 _InputIterator __last, std::input_iterator_tag); 01601 01602 // called by the second insert_dispatch above 01603 template<typename _ForwardIterator> 01604 void 01605 _M_range_insert_aux(iterator __pos, _ForwardIterator __first, 01606 _ForwardIterator __last, std::forward_iterator_tag); 01607 01608 // Called by insert(p,n,x), and the range insert when it turns out to be 01609 // the same thing. Can use fill functions in optimal situations, 01610 // otherwise passes off to insert_aux(p,n,x). 01611 void 01612 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); 01613 01614 // called by insert(p,x) 01615 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 01616 iterator 01617 _M_insert_aux(iterator __pos, const value_type& __x); 01618 #else 01619 template<typename... _Args> 01620 iterator 01621 _M_insert_aux(iterator __pos, _Args&&... __args); 01622 #endif 01623 01624 // called by insert(p,n,x) via fill_insert 01625 void 01626 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); 01627 01628 // called by range_insert_aux for forward iterators 01629 template<typename _ForwardIterator> 01630 void 01631 _M_insert_aux(iterator __pos, 01632 _ForwardIterator __first, _ForwardIterator __last, 01633 size_type __n); 01634 01635 01636 // Internal erase functions follow. 01637 01638 void 01639 _M_destroy_data_aux(iterator __first, iterator __last); 01640 01641 // Called by ~deque(). 01642 // NB: Doesn't deallocate the nodes. 01643 template<typename _Alloc1> 01644 void 01645 _M_destroy_data(iterator __first, iterator __last, const _Alloc1&) 01646 { _M_destroy_data_aux(__first, __last); } 01647 01648 void 01649 _M_destroy_data(iterator __first, iterator __last, 01650 const std::allocator<_Tp>&) 01651 { 01652 if (!__has_trivial_destructor(value_type)) 01653 _M_destroy_data_aux(__first, __last); 01654 } 01655 01656 // Called by erase(q1, q2). 01657 void 01658 _M_erase_at_begin(iterator __pos) 01659 { 01660 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator()); 01661 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node); 01662 this->_M_impl._M_start = __pos; 01663 } 01664 01665 // Called by erase(q1, q2), resize(), clear(), _M_assign_aux, 01666 // _M_fill_assign, operator=. 01667 void 01668 _M_erase_at_end(iterator __pos) 01669 { 01670 _M_destroy_data(__pos, end(), _M_get_Tp_allocator()); 01671 _M_destroy_nodes(__pos._M_node + 1, 01672 this->_M_impl._M_finish._M_node + 1); 01673 this->_M_impl._M_finish = __pos; 01674 } 01675 01676 //@{ 01677 /// Memory-handling helpers for the previous internal insert functions. 01678 iterator 01679 _M_reserve_elements_at_front(size_type __n) 01680 { 01681 const size_type __vacancies = this->_M_impl._M_start._M_cur 01682 - this->_M_impl._M_start._M_first; 01683 if (__n > __vacancies) 01684 _M_new_elements_at_front(__n - __vacancies); 01685 return this->_M_impl._M_start - difference_type(__n); 01686 } 01687 01688 iterator 01689 _M_reserve_elements_at_back(size_type __n) 01690 { 01691 const size_type __vacancies = (this->_M_impl._M_finish._M_last 01692 - this->_M_impl._M_finish._M_cur) - 1; 01693 if (__n > __vacancies) 01694 _M_new_elements_at_back(__n - __vacancies); 01695 return this->_M_impl._M_finish + difference_type(__n); 01696 } 01697 01698 void 01699 _M_new_elements_at_front(size_type __new_elements); 01700 01701 void 01702 _M_new_elements_at_back(size_type __new_elements); 01703 //@} 01704 01705 01706 //@{ 01707 /** 01708 * @brief Memory-handling helpers for the major %map. 01709 * 01710 * Makes sure the _M_map has space for new nodes. Does not 01711 * actually add the nodes. Can invalidate _M_map pointers. 01712 * (And consequently, %deque iterators.) 01713 */ 01714 void 01715 _M_reserve_map_at_back(size_type __nodes_to_add = 1) 01716 { 01717 if (__nodes_to_add + 1 > this->_M_impl._M_map_size 01718 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map)) 01719 _M_reallocate_map(__nodes_to_add, false); 01720 } 01721 01722 void 01723 _M_reserve_map_at_front(size_type __nodes_to_add = 1) 01724 { 01725 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node 01726 - this->_M_impl._M_map)) 01727 _M_reallocate_map(__nodes_to_add, true); 01728 } 01729 01730 void 01731 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); 01732 //@} 01733 }; 01734 01735 01736 /** 01737 * @brief Deque equality comparison. 01738 * @param x A %deque. 01739 * @param y A %deque of the same type as @a x. 01740 * @return True iff the size and elements of the deques are equal. 01741 * 01742 * This is an equivalence relation. It is linear in the size of the 01743 * deques. Deques are considered equivalent if their sizes are equal, 01744 * and if corresponding elements compare equal. 01745 */ 01746 template<typename _Tp, typename _Alloc> 01747 inline bool 01748 operator==(const deque<_Tp, _Alloc>& __x, 01749 const deque<_Tp, _Alloc>& __y) 01750 { return __x.size() == __y.size() 01751 && std::equal(__x.begin(), __x.end(), __y.begin()); } 01752 01753 /** 01754 * @brief Deque ordering relation. 01755 * @param x A %deque. 01756 * @param y A %deque of the same type as @a x. 01757 * @return True iff @a x is lexicographically less than @a y. 01758 * 01759 * This is a total ordering relation. It is linear in the size of the 01760 * deques. The elements must be comparable with @c <. 01761 * 01762 * See std::lexicographical_compare() for how the determination is made. 01763 */ 01764 template<typename _Tp, typename _Alloc> 01765 inline bool 01766 operator<(const deque<_Tp, _Alloc>& __x, 01767 const deque<_Tp, _Alloc>& __y) 01768 { return std::lexicographical_compare(__x.begin(), __x.end(), 01769 __y.begin(), __y.end()); } 01770 01771 /// Based on operator== 01772 template<typename _Tp, typename _Alloc> 01773 inline bool 01774 operator!=(const deque<_Tp, _Alloc>& __x, 01775 const deque<_Tp, _Alloc>& __y) 01776 { return !(__x == __y); } 01777 01778 /// Based on operator< 01779 template<typename _Tp, typename _Alloc> 01780 inline bool 01781 operator>(const deque<_Tp, _Alloc>& __x, 01782 const deque<_Tp, _Alloc>& __y) 01783 { return __y < __x; } 01784 01785 /// Based on operator< 01786 template<typename _Tp, typename _Alloc> 01787 inline bool 01788 operator<=(const deque<_Tp, _Alloc>& __x, 01789 const deque<_Tp, _Alloc>& __y) 01790 { return !(__y < __x); } 01791 01792 /// Based on operator< 01793 template<typename _Tp, typename _Alloc> 01794 inline bool 01795 operator>=(const deque<_Tp, _Alloc>& __x, 01796 const deque<_Tp, _Alloc>& __y) 01797 { return !(__x < __y); } 01798 01799 /// See std::deque::swap(). 01800 template<typename _Tp, typename _Alloc> 01801 inline void 01802 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) 01803 { __x.swap(__y); } 01804 01805 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01806 template<typename _Tp, typename _Alloc> 01807 inline void 01808 swap(deque<_Tp,_Alloc>&& __x, deque<_Tp,_Alloc>& __y) 01809 { __x.swap(__y); } 01810 01811 template<typename _Tp, typename _Alloc> 01812 inline void 01813 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>&& __y) 01814 { __x.swap(__y); } 01815 #endif 01816 01817 _GLIBCXX_END_NESTED_NAMESPACE 01818 01819 #endif /* _STL_DEQUE_H */