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