diff options
Diffstat (limited to 'rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html')
| -rw-r--r-- | rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html | 1533 |
1 files changed, 0 insertions, 1533 deletions
diff --git a/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html b/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html deleted file mode 100644 index 9827a27..0000000 --- a/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html +++ /dev/null @@ -1,1533 +0,0 @@ -<!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_tree.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_tree.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%">295</td> - </tr> - <tr> - <td class="headerItem" width="20%">Code covered:</td> - <td class="headerValue" width="20%">94.2 %</td> - <td width="20%"></td> - <td class="headerItem" width="20%">Executed lines:</td> - <td class="headerValue" width="20%">278</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> : // RB tree implementation -*- C++ -*- -<span class="lineNum"> 2 </span> : -<span class="lineNum"> 3 </span> : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 -<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) 1996,1997 -<span class="lineNum"> 34 </span> : * Silicon Graphics Computer Systems, Inc. -<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. Silicon Graphics 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) 1994 -<span class="lineNum"> 46 </span> : * Hewlett-Packard Company -<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. Hewlett-Packard Company 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> : */ -<span class="lineNum"> 58 </span> : -<span class="lineNum"> 59 </span> : /** @file stl_tree.h -<span class="lineNum"> 60 </span> : * This is an internal header file, included by other library headers. -<span class="lineNum"> 61 </span> : * You should not attempt to use it directly. -<span class="lineNum"> 62 </span> : */ -<span class="lineNum"> 63 </span> : -<span class="lineNum"> 64 </span> : #ifndef _STL_TREE_H -<span class="lineNum"> 65 </span> : #define _STL_TREE_H 1 -<span class="lineNum"> 66 </span> : -<span class="lineNum"> 67 </span> : #include <bits/stl_algobase.h> -<span class="lineNum"> 68 </span> : #include <bits/allocator.h> -<span class="lineNum"> 69 </span> : #include <bits/stl_function.h> -<span class="lineNum"> 70 </span> : #include <bits/cpp_type_traits.h> -<span class="lineNum"> 71 </span> : -<span class="lineNum"> 72 </span> : _GLIBCXX_BEGIN_NAMESPACE(std) -<span class="lineNum"> 73 </span> : -<span class="lineNum"> 74 </span> : // Red-black tree class, designed for use in implementing STL -<span class="lineNum"> 75 </span> : // associative containers (set, multiset, map, and multimap). The -<span class="lineNum"> 76 </span> : // insertion and deletion algorithms are based on those in Cormen, -<span class="lineNum"> 77 </span> : // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, -<span class="lineNum"> 78 </span> : // 1990), except that -<span class="lineNum"> 79 </span> : // -<span class="lineNum"> 80 </span> : // (1) the header cell is maintained with links not only to the root -<span class="lineNum"> 81 </span> : // but also to the leftmost node of the tree, to enable constant -<span class="lineNum"> 82 </span> : // time begin(), and to the rightmost node of the tree, to enable -<span class="lineNum"> 83 </span> : // linear time performance when used with the generic set algorithms -<span class="lineNum"> 84 </span> : // (set_union, etc.) -<span class="lineNum"> 85 </span> : // -<span class="lineNum"> 86 </span> : // (2) when a node being deleted has two children its successor node -<span class="lineNum"> 87 </span> : // is relinked into its place, rather than copied, so that the only -<span class="lineNum"> 88 </span> : // iterators invalidated are those referring to the deleted node. -<span class="lineNum"> 89 </span> : -<span class="lineNum"> 90 </span> : enum _Rb_tree_color { _S_red = false, _S_black = true }; -<span class="lineNum"> 91 </span> : -<span class="lineNum"> 92 </span> : struct _Rb_tree_node_base -<span class="lineNum"> 93 </span> : { -<span class="lineNum"> 94 </span> : typedef _Rb_tree_node_base* _Base_ptr; -<span class="lineNum"> 95 </span> : typedef const _Rb_tree_node_base* _Const_Base_ptr; -<span class="lineNum"> 96 </span> : -<span class="lineNum"> 97 </span> : _Rb_tree_color _M_color; -<span class="lineNum"> 98 </span> : _Base_ptr _M_parent; -<span class="lineNum"> 99 </span> : _Base_ptr _M_left; -<span class="lineNum"> 100 </span> : _Base_ptr _M_right; -<span class="lineNum"> 101 </span> : -<span class="lineNum"> 102 </span> : static _Base_ptr -<span class="lineNum"> 103 </span><span class="lineCov"> 880633 : _S_minimum(_Base_ptr __x)</span> -<span class="lineNum"> 104 </span> : { -<span class="lineNum"> 105 </span><span class="lineCov"> 880633 : while (__x->_M_left != 0) __x = __x->_M_left;</span> -<span class="lineNum"> 106 </span><span class="lineCov"> 880633 : return __x;</span> -<span class="lineNum"> 107 </span> : } -<span class="lineNum"> 108 </span> : -<span class="lineNum"> 109 </span> : static _Const_Base_ptr -<span class="lineNum"> 110 </span> : _S_minimum(_Const_Base_ptr __x) -<span class="lineNum"> 111 </span> : { -<span class="lineNum"> 112 </span> : while (__x->_M_left != 0) __x = __x->_M_left; -<span class="lineNum"> 113 </span> : return __x; -<span class="lineNum"> 114 </span> : } -<span class="lineNum"> 115 </span> : -<span class="lineNum"> 116 </span> : static _Base_ptr -<span class="lineNum"> 117 </span><span class="lineCov"> 880633 : _S_maximum(_Base_ptr __x)</span> -<span class="lineNum"> 118 </span> : { -<span class="lineNum"> 119 </span><span class="lineCov"> 880633 : while (__x->_M_right != 0) __x = __x->_M_right;</span> -<span class="lineNum"> 120 </span><span class="lineCov"> 880633 : return __x;</span> -<span class="lineNum"> 121 </span> : } -<span class="lineNum"> 122 </span> : -<span class="lineNum"> 123 </span> : static _Const_Base_ptr -<span class="lineNum"> 124 </span> : _S_maximum(_Const_Base_ptr __x) -<span class="lineNum"> 125 </span> : { -<span class="lineNum"> 126 </span> : while (__x->_M_right != 0) __x = __x->_M_right; -<span class="lineNum"> 127 </span> : return __x; -<span class="lineNum"> 128 </span> : } -<span class="lineNum"> 129 </span> : }; -<span class="lineNum"> 130 </span> : -<span class="lineNum"> 131 </span> : template<typename _Val> -<span class="lineNum"> 132 </span> : struct _Rb_tree_node : public _Rb_tree_node_base -<span class="lineNum"> 133 </span> : { -<span class="lineNum"> 134 </span> : typedef _Rb_tree_node<_Val>* _Link_type; -<span class="lineNum"> 135 </span> : _Val _M_value_field; -<span class="lineNum"> 136 </span> : }; -<span class="lineNum"> 137 </span> : -<span class="lineNum"> 138 </span> : _Rb_tree_node_base* -<span class="lineNum"> 139 </span> : _Rb_tree_increment(_Rb_tree_node_base* __x); -<span class="lineNum"> 140 </span> : -<span class="lineNum"> 141 </span> : const _Rb_tree_node_base* -<span class="lineNum"> 142 </span> : _Rb_tree_increment(const _Rb_tree_node_base* __x); -<span class="lineNum"> 143 </span> : -<span class="lineNum"> 144 </span> : _Rb_tree_node_base* -<span class="lineNum"> 145 </span> : _Rb_tree_decrement(_Rb_tree_node_base* __x); -<span class="lineNum"> 146 </span> : -<span class="lineNum"> 147 </span> : const _Rb_tree_node_base* -<span class="lineNum"> 148 </span> : _Rb_tree_decrement(const _Rb_tree_node_base* __x); -<span class="lineNum"> 149 </span> : -<span class="lineNum"> 150 </span> : template<typename _Tp> -<span class="lineNum"> 151 </span> : struct _Rb_tree_iterator -<span class="lineNum"> 152 </span> : { -<span class="lineNum"> 153 </span> : typedef _Tp value_type; -<span class="lineNum"> 154 </span> : typedef _Tp& reference; -<span class="lineNum"> 155 </span> : typedef _Tp* pointer; -<span class="lineNum"> 156 </span> : -<span class="lineNum"> 157 </span> : typedef bidirectional_iterator_tag iterator_category; -<span class="lineNum"> 158 </span> : typedef ptrdiff_t difference_type; -<span class="lineNum"> 159 </span> : -<span class="lineNum"> 160 </span> : typedef _Rb_tree_iterator<_Tp> _Self; -<span class="lineNum"> 161 </span> : typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; -<span class="lineNum"> 162 </span> : typedef _Rb_tree_node<_Tp>* _Link_type; -<span class="lineNum"> 163 </span> : -<span class="lineNum"> 164 </span> : _Rb_tree_iterator() -<span class="lineNum"> 165 </span> : : _M_node() { } -<span class="lineNum"> 166 </span> : -<span class="lineNum"> 167 </span> : explicit -<span class="lineNum"> 168 </span><span class="lineCov"> 4550329 : _Rb_tree_iterator(_Link_type __x)</span> -<span class="lineNum"> 169 </span><span class="lineCov"> 4550329 : : _M_node(__x) { }</span> -<span class="lineNum"> 170 </span> : -<span class="lineNum"> 171 </span> : reference -<span class="lineNum"> 172 </span><span class="lineCov"> 9593 : operator*() const</span> -<span class="lineNum"> 173 </span><span class="lineCov"> 9593 : { return static_cast<_Link_type>(_M_node)->_M_value_field; }</span> -<span class="lineNum"> 174 </span> : -<span class="lineNum"> 175 </span> : pointer -<span class="lineNum"> 176 </span><span class="lineCov"> 32985 : operator->() const</span> -<span class="lineNum"> 177 </span><span class="lineCov"> 32985 : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }</span> -<span class="lineNum"> 178 </span> : -<span class="lineNum"> 179 </span> : _Self& -<span class="lineNum"> 180 </span> : operator++() -<span class="lineNum"> 181 </span> : { -<span class="lineNum"> 182 </span> : _M_node = _Rb_tree_increment(_M_node); -<span class="lineNum"> 183 </span> : return *this; -<span class="lineNum"> 184 </span> : } -<span class="lineNum"> 185 </span> : -<span class="lineNum"> 186 </span> : _Self -<span class="lineNum"> 187 </span><span class="lineCov"> 658 : operator++(int)</span> -<span class="lineNum"> 188 </span> : { -<span class="lineNum"> 189 </span><span class="lineCov"> 658 : _Self __tmp = *this;</span> -<span class="lineNum"> 190 </span><span class="lineCov"> 658 : _M_node = _Rb_tree_increment(_M_node);</span> -<span class="lineNum"> 191 </span> : return __tmp; -<span class="lineNum"> 192 </span> : } -<span class="lineNum"> 193 </span> : -<span class="lineNum"> 194 </span> : _Self& -<span class="lineNum"> 195 </span><span class="lineCov"> 83333 : operator--()</span> -<span class="lineNum"> 196 </span> : { -<span class="lineNum"> 197 </span><span class="lineCov"> 83333 : _M_node = _Rb_tree_decrement(_M_node);</span> -<span class="lineNum"> 198 </span><span class="lineCov"> 83333 : return *this;</span> -<span class="lineNum"> 199 </span> : } -<span class="lineNum"> 200 </span> : -<span class="lineNum"> 201 </span> : _Self -<span class="lineNum"> 202 </span> : operator--(int) -<span class="lineNum"> 203 </span> : { -<span class="lineNum"> 204 </span> : _Self __tmp = *this; -<span class="lineNum"> 205 </span> : _M_node = _Rb_tree_decrement(_M_node); -<span class="lineNum"> 206 </span> : return __tmp; -<span class="lineNum"> 207 </span> : } -<span class="lineNum"> 208 </span> : -<span class="lineNum"> 209 </span> : bool -<span class="lineNum"> 210 </span><span class="lineCov"> 638793 : operator==(const _Self& __x) const</span> -<span class="lineNum"> 211 </span><span class="lineCov"> 638793 : { return _M_node == __x._M_node; }</span> -<span class="lineNum"> 212 </span> : -<span class="lineNum"> 213 </span> : bool -<span class="lineNum"> 214 </span><span class="lineCov"> 749 : operator!=(const _Self& __x) const</span> -<span class="lineNum"> 215 </span><span class="lineCov"> 749 : { return _M_node != __x._M_node; }</span> -<span class="lineNum"> 216 </span> : -<span class="lineNum"> 217 </span> : _Base_ptr _M_node; -<span class="lineNum"> 218 </span> : }; -<span class="lineNum"> 219 </span> : -<span class="lineNum"> 220 </span> : template<typename _Tp> -<span class="lineNum"> 221 </span> : struct _Rb_tree_const_iterator -<span class="lineNum"> 222 </span> : { -<span class="lineNum"> 223 </span> : typedef _Tp value_type; -<span class="lineNum"> 224 </span> : typedef const _Tp& reference; -<span class="lineNum"> 225 </span> : typedef const _Tp* pointer; -<span class="lineNum"> 226 </span> : -<span class="lineNum"> 227 </span> : typedef _Rb_tree_iterator<_Tp> iterator; -<span class="lineNum"> 228 </span> : -<span class="lineNum"> 229 </span> : typedef bidirectional_iterator_tag iterator_category; -<span class="lineNum"> 230 </span> : typedef ptrdiff_t difference_type; -<span class="lineNum"> 231 </span> : -<span class="lineNum"> 232 </span> : typedef _Rb_tree_const_iterator<_Tp> _Self; -<span class="lineNum"> 233 </span> : typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; -<span class="lineNum"> 234 </span> : typedef const _Rb_tree_node<_Tp>* _Link_type; -<span class="lineNum"> 235 </span> : -<span class="lineNum"> 236 </span> : _Rb_tree_const_iterator() -<span class="lineNum"> 237 </span> : : _M_node() { } -<span class="lineNum"> 238 </span> : -<span class="lineNum"> 239 </span> : explicit -<span class="lineNum"> 240 </span><span class="lineCov"> 2494703 : _Rb_tree_const_iterator(_Link_type __x)</span> -<span class="lineNum"> 241 </span><span class="lineCov"> 2494703 : : _M_node(__x) { }</span> -<span class="lineNum"> 242 </span> : -<span class="lineNum"> 243 </span><span class="lineCov"> 1643427 : _Rb_tree_const_iterator(const iterator& __it)</span> -<span class="lineNum"> 244 </span><span class="lineCov"> 1643427 : : _M_node(__it._M_node) { }</span> -<span class="lineNum"> 245 </span> : -<span class="lineNum"> 246 </span> : reference -<span class="lineNum"> 247 </span><span class="lineCov"> 1553025 : operator*() const</span> -<span class="lineNum"> 248 </span><span class="lineCov"> 1553025 : { return static_cast<_Link_type>(_M_node)->_M_value_field; }</span> -<span class="lineNum"> 249 </span> : -<span class="lineNum"> 250 </span> : pointer -<span class="lineNum"> 251 </span><span class="lineCov"> 817027 : operator->() const</span> -<span class="lineNum"> 252 </span><span class="lineCov"> 817027 : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }</span> -<span class="lineNum"> 253 </span> : -<span class="lineNum"> 254 </span> : _Self& -<span class="lineNum"> 255 </span><span class="lineCov"> 1717591 : operator++()</span> -<span class="lineNum"> 256 </span> : { -<span class="lineNum"> 257 </span><span class="lineCov"> 1717591 : _M_node = _Rb_tree_increment(_M_node);</span> -<span class="lineNum"> 258 </span><span class="lineCov"> 1717591 : return *this;</span> -<span class="lineNum"> 259 </span> : } -<span class="lineNum"> 260 </span> : -<span class="lineNum"> 261 </span> : _Self -<span class="lineNum"> 262 </span><span class="lineCov"> 9048 : operator++(int)</span> -<span class="lineNum"> 263 </span> : { -<span class="lineNum"> 264 </span><span class="lineCov"> 9048 : _Self __tmp = *this;</span> -<span class="lineNum"> 265 </span><span class="lineCov"> 9048 : _M_node = _Rb_tree_increment(_M_node);</span> -<span class="lineNum"> 266 </span> : return __tmp; -<span class="lineNum"> 267 </span> : } -<span class="lineNum"> 268 </span> : -<span class="lineNum"> 269 </span> : _Self& -<span class="lineNum"> 270 </span><span class="lineCov"> 2000 : operator--()</span> -<span class="lineNum"> 271 </span> : { -<span class="lineNum"> 272 </span><span class="lineCov"> 2000 : _M_node = _Rb_tree_decrement(_M_node);</span> -<span class="lineNum"> 273 </span><span class="lineCov"> 2000 : return *this;</span> -<span class="lineNum"> 274 </span> : } -<span class="lineNum"> 275 </span> : -<span class="lineNum"> 276 </span> : _Self -<span class="lineNum"> 277 </span> : operator--(int) -<span class="lineNum"> 278 </span> : { -<span class="lineNum"> 279 </span> : _Self __tmp = *this; -<span class="lineNum"> 280 </span> : _M_node = _Rb_tree_decrement(_M_node); -<span class="lineNum"> 281 </span> : return __tmp; -<span class="lineNum"> 282 </span> : } -<span class="lineNum"> 283 </span> : -<span class="lineNum"> 284 </span> : bool -<span class="lineNum"> 285 </span><span class="lineCov"> 177758 : operator==(const _Self& __x) const</span> -<span class="lineNum"> 286 </span><span class="lineCov"> 177758 : { return _M_node == __x._M_node; }</span> -<span class="lineNum"> 287 </span> : -<span class="lineNum"> 288 </span> : bool -<span class="lineNum"> 289 </span><span class="lineCov"> 2095612 : operator!=(const _Self& __x) const</span> -<span class="lineNum"> 290 </span><span class="lineCov"> 2095612 : { return _M_node != __x._M_node; }</span> -<span class="lineNum"> 291 </span> : -<span class="lineNum"> 292 </span> : _Base_ptr _M_node; -<span class="lineNum"> 293 </span> : }; -<span class="lineNum"> 294 </span> : -<span class="lineNum"> 295 </span> : template<typename _Val> -<span class="lineNum"> 296 </span> : inline bool -<span class="lineNum"> 297 </span> : operator==(const _Rb_tree_iterator<_Val>& __x, -<span class="lineNum"> 298 </span> : const _Rb_tree_const_iterator<_Val>& __y) -<span class="lineNum"> 299 </span> : { return __x._M_node == __y._M_node; } -<span class="lineNum"> 300 </span> : -<span class="lineNum"> 301 </span> : template<typename _Val> -<span class="lineNum"> 302 </span> : inline bool -<span class="lineNum"> 303 </span> : operator!=(const _Rb_tree_iterator<_Val>& __x, -<span class="lineNum"> 304 </span> : const _Rb_tree_const_iterator<_Val>& __y) -<span class="lineNum"> 305 </span> : { return __x._M_node != __y._M_node; } -<span class="lineNum"> 306 </span> : -<span class="lineNum"> 307 </span> : void -<span class="lineNum"> 308 </span> : _Rb_tree_insert_and_rebalance(const bool __insert_left, -<span class="lineNum"> 309 </span> : _Rb_tree_node_base* __x, -<span class="lineNum"> 310 </span> : _Rb_tree_node_base* __p, -<span class="lineNum"> 311 </span> : _Rb_tree_node_base& __header); -<span class="lineNum"> 312 </span> : -<span class="lineNum"> 313 </span> : _Rb_tree_node_base* -<span class="lineNum"> 314 </span> : _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, -<span class="lineNum"> 315 </span> : _Rb_tree_node_base& __header); -<span class="lineNum"> 316 </span> : -<span class="lineNum"> 317 </span> : -<span class="lineNum"> 318 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 319 </span> : typename _Compare, typename _Alloc = allocator<_Val> > -<span class="lineNum"> 320 </span> : class _Rb_tree -<span class="lineNum"> 321 </span> : { -<span class="lineNum"> 322 </span> : typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other -<span class="lineNum"> 323 </span> : _Node_allocator; -<span class="lineNum"> 324 </span> : -<span class="lineNum"> 325 </span> : protected: -<span class="lineNum"> 326 </span> : typedef _Rb_tree_node_base* _Base_ptr; -<span class="lineNum"> 327 </span> : typedef const _Rb_tree_node_base* _Const_Base_ptr; -<span class="lineNum"> 328 </span> : -<span class="lineNum"> 329 </span> : public: -<span class="lineNum"> 330 </span> : typedef _Key key_type; -<span class="lineNum"> 331 </span> : typedef _Val value_type; -<span class="lineNum"> 332 </span> : typedef value_type* pointer; -<span class="lineNum"> 333 </span> : typedef const value_type* const_pointer; -<span class="lineNum"> 334 </span> : typedef value_type& reference; -<span class="lineNum"> 335 </span> : typedef const value_type& const_reference; -<span class="lineNum"> 336 </span> : typedef _Rb_tree_node<_Val>* _Link_type; -<span class="lineNum"> 337 </span> : typedef const _Rb_tree_node<_Val>* _Const_Link_type; -<span class="lineNum"> 338 </span> : typedef size_t size_type; -<span class="lineNum"> 339 </span> : typedef ptrdiff_t difference_type; -<span class="lineNum"> 340 </span> : typedef _Alloc allocator_type; -<span class="lineNum"> 341 </span> : -<span class="lineNum"> 342 </span> : _Node_allocator& -<span class="lineNum"> 343 </span> : _M_get_Node_allocator() -<span class="lineNum"> 344 </span> : { return *static_cast<_Node_allocator*>(&this->_M_impl); } -<span class="lineNum"> 345 </span> : -<span class="lineNum"> 346 </span> : const _Node_allocator& -<span class="lineNum"> 347 </span><span class="lineCov"> 12223942 : _M_get_Node_allocator() const</span> -<span class="lineNum"> 348 </span><span class="lineCov"> 12223942 : { return *static_cast<const _Node_allocator*>(&this->_M_impl); }</span> -<span class="lineNum"> 349 </span> : -<span class="lineNum"> 350 </span> : allocator_type -<span class="lineNum"> 351 </span><span class="lineCov"> 11289346 : get_allocator() const</span> -<span class="lineNum"> 352 </span><span class="lineCov"> 11289346 : { return allocator_type(_M_get_Node_allocator()); }</span> -<span class="lineNum"> 353 </span> : -<span class="lineNum"> 354 </span> : protected: -<span class="lineNum"> 355 </span> : _Link_type -<span class="lineNum"> 356 </span><span class="lineCov"> 5644688 : _M_get_node()</span> -<span class="lineNum"> 357 </span><span class="lineCov"> 5644688 : { return _M_impl._Node_allocator::allocate(1); }</span> -<span class="lineNum"> 358 </span> : -<span class="lineNum"> 359 </span> : void -<span class="lineNum"> 360 </span><span class="lineCov"> 5644658 : _M_put_node(_Link_type __p)</span> -<span class="lineNum"> 361 </span><span class="lineCov"> 5644658 : { _M_impl._Node_allocator::deallocate(__p, 1); }</span> -<span class="lineNum"> 362 </span> : -<span class="lineNum"> 363 </span> : _Link_type -<span class="lineNum"> 364 </span><span class="lineCov"> 5644688 : _M_create_node(const value_type& __x)</span> -<span class="lineNum"> 365 </span> : { -<span class="lineNum"> 366 </span><span class="lineCov"> 5644688 : _Link_type __tmp = _M_get_node();</span> -<span class="lineNum"> 367 </span> : try -<span class="lineNum"> 368 </span><span class="lineCov"> 5644688 : { get_allocator().construct(&__tmp->_M_value_field, __x); }</span> -<span class="lineNum"> 369 </span><span class="lineNoCov"> 0 : catch(...)</span> -<span class="lineNum"> 370 </span> : { -<span class="lineNum"> 371 </span><span class="lineNoCov"> 0 : _M_put_node(__tmp);</span> -<span class="lineNum"> 372 </span><span class="lineNoCov"> 0 : __throw_exception_again;</span> -<span class="lineNum"> 373 </span> : } -<span class="lineNum"> 374 </span><span class="lineCov"> 5644688 : return __tmp;</span> -<span class="lineNum"> 375 </span> : } -<span class="lineNum"> 376 </span> : -<span class="lineNum"> 377 </span> : _Link_type -<span class="lineNum"> 378 </span><span class="lineCov"> 3573982 : _M_clone_node(_Const_Link_type __x)</span> -<span class="lineNum"> 379 </span> : { -<span class="lineNum"> 380 </span><span class="lineCov"> 3573982 : _Link_type __tmp = _M_create_node(__x->_M_value_field);</span> -<span class="lineNum"> 381 </span><span class="lineCov"> 3573982 : __tmp->_M_color = __x->_M_color;</span> -<span class="lineNum"> 382 </span><span class="lineCov"> 3573982 : __tmp->_M_left = 0;</span> -<span class="lineNum"> 383 </span><span class="lineCov"> 3573982 : __tmp->_M_right = 0;</span> -<span class="lineNum"> 384 </span><span class="lineCov"> 3573982 : return __tmp;</span> -<span class="lineNum"> 385 </span> : } -<span class="lineNum"> 386 </span> : -<span class="lineNum"> 387 </span> : void -<span class="lineNum"> 388 </span><span class="lineCov"> 5644658 : _M_destroy_node(_Link_type __p)</span> -<span class="lineNum"> 389 </span> : { -<span class="lineNum"> 390 </span><span class="lineCov"> 5644658 : get_allocator().destroy(&__p->_M_value_field);</span> -<span class="lineNum"> 391 </span><span class="lineCov"> 5644658 : _M_put_node(__p);</span> -<span class="lineNum"> 392 </span><span class="lineCov"> 5644658 : }</span> -<span class="lineNum"> 393 </span> : -<span class="lineNum"> 394 </span> : protected: -<span class="lineNum"> 395 </span> : template<typename _Key_compare, -<span class="lineNum"> 396 </span> : bool _Is_pod_comparator = __is_pod(_Key_compare)> -<span class="lineNum"> 397 </span> : struct _Rb_tree_impl : public _Node_allocator -<span class="lineNum"> 398 </span><span class="lineCov"> 1320929 : {</span> -<span class="lineNum"> 399 </span> : _Key_compare _M_key_compare; -<span class="lineNum"> 400 </span> : _Rb_tree_node_base _M_header; -<span class="lineNum"> 401 </span> : size_type _M_node_count; // Keeps track of size of tree. -<span class="lineNum"> 402 </span> : -<span class="lineNum"> 403 </span><span class="lineCov"> 280599 : _Rb_tree_impl()</span> -<span class="lineNum"> 404 </span> : : _Node_allocator(), _M_key_compare(), _M_header(), -<span class="lineNum"> 405 </span><span class="lineCov"> 280599 : _M_node_count(0)</span> -<span class="lineNum"> 406 </span><span class="lineCov"> 280599 : { _M_initialize(); }</span> -<span class="lineNum"> 407 </span> : -<span class="lineNum"> 408 </span><span class="lineCov"> 934596 : _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)</span> -<span class="lineNum"> 409 </span> : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), -<span class="lineNum"> 410 </span><span class="lineCov"> 934596 : _M_node_count(0)</span> -<span class="lineNum"> 411 </span><span class="lineCov"> 934596 : { _M_initialize(); }</span> -<span class="lineNum"> 412 </span> : -<span class="lineNum"> 413 </span> : private: -<span class="lineNum"> 414 </span> : void -<span class="lineNum"> 415 </span><span class="lineCov"> 1215195 : _M_initialize()</span> -<span class="lineNum"> 416 </span> : { -<span class="lineNum"> 417 </span><span class="lineCov"> 1215195 : this->_M_header._M_color = _S_red;</span> -<span class="lineNum"> 418 </span><span class="lineCov"> 1215195 : this->_M_header._M_parent = 0;</span> -<span class="lineNum"> 419 </span><span class="lineCov"> 1215195 : this->_M_header._M_left = &this->_M_header;</span> -<span class="lineNum"> 420 </span><span class="lineCov"> 1215195 : this->_M_header._M_right = &this->_M_header;</span> -<span class="lineNum"> 421 </span><span class="lineCov"> 1215195 : } </span> -<span class="lineNum"> 422 </span> : }; -<span class="lineNum"> 423 </span> : -<span class="lineNum"> 424 </span> : _Rb_tree_impl<_Compare> _M_impl; -<span class="lineNum"> 425 </span> : -<span class="lineNum"> 426 </span> : protected: -<span class="lineNum"> 427 </span> : _Base_ptr& -<span class="lineNum"> 428 </span><span class="lineCov"> 2729891 : _M_root()</span> -<span class="lineNum"> 429 </span><span class="lineCov"> 2729891 : { return this->_M_impl._M_header._M_parent; }</span> -<span class="lineNum"> 430 </span> : -<span class="lineNum"> 431 </span> : _Const_Base_ptr -<span class="lineNum"> 432 </span><span class="lineCov"> 934693 : _M_root() const</span> -<span class="lineNum"> 433 </span><span class="lineCov"> 934693 : { return this->_M_impl._M_header._M_parent; }</span> -<span class="lineNum"> 434 </span> : -<span class="lineNum"> 435 </span> : _Base_ptr& -<span class="lineNum"> 436 </span><span class="lineCov"> 970809 : _M_leftmost()</span> -<span class="lineNum"> 437 </span><span class="lineCov"> 970809 : { return this->_M_impl._M_header._M_left; }</span> -<span class="lineNum"> 438 </span> : -<span class="lineNum"> 439 </span> : _Const_Base_ptr -<span class="lineNum"> 440 </span> : _M_leftmost() const -<span class="lineNum"> 441 </span> : { return this->_M_impl._M_header._M_left; } -<span class="lineNum"> 442 </span> : -<span class="lineNum"> 443 </span> : _Base_ptr& -<span class="lineNum"> 444 </span><span class="lineCov"> 2012568 : _M_rightmost()</span> -<span class="lineNum"> 445 </span><span class="lineCov"> 2012568 : { return this->_M_impl._M_header._M_right; }</span> -<span class="lineNum"> 446 </span> : -<span class="lineNum"> 447 </span> : _Const_Base_ptr -<span class="lineNum"> 448 </span> : _M_rightmost() const -<span class="lineNum"> 449 </span> : { return this->_M_impl._M_header._M_right; } -<span class="lineNum"> 450 </span> : -<span class="lineNum"> 451 </span> : _Link_type -<span class="lineNum"> 452 </span><span class="lineCov"> 3119123 : _M_begin()</span> -<span class="lineNum"> 453 </span><span class="lineCov"> 3119123 : { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }</span> -<span class="lineNum"> 454 </span> : -<span class="lineNum"> 455 </span> : _Const_Link_type -<span class="lineNum"> 456 </span><span class="lineCov"> 884565 : _M_begin() const</span> -<span class="lineNum"> 457 </span> : { -<span class="lineNum"> 458 </span> : return static_cast<_Const_Link_type> -<span class="lineNum"> 459 </span><span class="lineCov"> 884565 : (this->_M_impl._M_header._M_parent);</span> -<span class="lineNum"> 460 </span> : } -<span class="lineNum"> 461 </span> : -<span class="lineNum"> 462 </span> : _Link_type -<span class="lineNum"> 463 </span><span class="lineCov"> 5489610 : _M_end()</span> -<span class="lineNum"> 464 </span><span class="lineCov"> 5489610 : { return static_cast<_Link_type>(&this->_M_impl._M_header); }</span> -<span class="lineNum"> 465 </span> : -<span class="lineNum"> 466 </span> : _Const_Link_type -<span class="lineNum"> 467 </span><span class="lineCov"> 3932 : _M_end() const</span> -<span class="lineNum"> 468 </span><span class="lineCov"> 3932 : { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }</span> -<span class="lineNum"> 469 </span> : -<span class="lineNum"> 470 </span> : static const_reference -<span class="lineNum"> 471 </span><span class="lineCov"> 7342455 : _S_value(_Const_Link_type __x)</span> -<span class="lineNum"> 472 </span><span class="lineCov"> 7342455 : { return __x->_M_value_field; }</span> -<span class="lineNum"> 473 </span> : -<span class="lineNum"> 474 </span> : static const _Key& -<span class="lineNum"> 475 </span><span class="lineCov"> 7342455 : _S_key(_Const_Link_type __x)</span> -<span class="lineNum"> 476 </span><span class="lineCov"> 7342455 : { return _KeyOfValue()(_S_value(__x)); }</span> -<span class="lineNum"> 477 </span> : -<span class="lineNum"> 478 </span> : static _Link_type -<span class="lineNum"> 479 </span><span class="lineCov"> 6468290 : _S_left(_Base_ptr __x)</span> -<span class="lineNum"> 480 </span><span class="lineCov"> 6468290 : { return static_cast<_Link_type>(__x->_M_left); }</span> -<span class="lineNum"> 481 </span> : -<span class="lineNum"> 482 </span> : static _Const_Link_type -<span class="lineNum"> 483 </span><span class="lineCov"> 3579867 : _S_left(_Const_Base_ptr __x)</span> -<span class="lineNum"> 484 </span><span class="lineCov"> 3579867 : { return static_cast<_Const_Link_type>(__x->_M_left); }</span> -<span class="lineNum"> 485 </span> : -<span class="lineNum"> 486 </span> : static _Link_type -<span class="lineNum"> 487 </span><span class="lineCov"> 12155056 : _S_right(_Base_ptr __x)</span> -<span class="lineNum"> 488 </span><span class="lineCov"> 12155056 : { return static_cast<_Link_type>(__x->_M_right); }</span> -<span class="lineNum"> 489 </span> : -<span class="lineNum"> 490 </span> : static _Const_Link_type -<span class="lineNum"> 491 </span><span class="lineCov"> 1503831 : _S_right(_Const_Base_ptr __x)</span> -<span class="lineNum"> 492 </span><span class="lineCov"> 1503831 : { return static_cast<_Const_Link_type>(__x->_M_right); }</span> -<span class="lineNum"> 493 </span> : -<span class="lineNum"> 494 </span> : static const_reference -<span class="lineNum"> 495 </span><span class="lineCov"> 3381491 : _S_value(_Const_Base_ptr __x)</span> -<span class="lineNum"> 496 </span><span class="lineCov"> 3381491 : { return static_cast<_Const_Link_type>(__x)->_M_value_field; }</span> -<span class="lineNum"> 497 </span> : -<span class="lineNum"> 498 </span> : static const _Key& -<span class="lineNum"> 499 </span><span class="lineCov"> 3381491 : _S_key(_Const_Base_ptr __x)</span> -<span class="lineNum"> 500 </span><span class="lineCov"> 3381491 : { return _KeyOfValue()(_S_value(__x)); }</span> -<span class="lineNum"> 501 </span> : -<span class="lineNum"> 502 </span> : static _Base_ptr -<span class="lineNum"> 503 </span><span class="lineCov"> 880633 : _S_minimum(_Base_ptr __x)</span> -<span class="lineNum"> 504 </span><span class="lineCov"> 880633 : { return _Rb_tree_node_base::_S_minimum(__x); }</span> -<span class="lineNum"> 505 </span> : -<span class="lineNum"> 506 </span> : static _Const_Base_ptr -<span class="lineNum"> 507 </span> : _S_minimum(_Const_Base_ptr __x) -<span class="lineNum"> 508 </span> : { return _Rb_tree_node_base::_S_minimum(__x); } -<span class="lineNum"> 509 </span> : -<span class="lineNum"> 510 </span> : static _Base_ptr -<span class="lineNum"> 511 </span><span class="lineCov"> 880633 : _S_maximum(_Base_ptr __x)</span> -<span class="lineNum"> 512 </span><span class="lineCov"> 880633 : { return _Rb_tree_node_base::_S_maximum(__x); }</span> -<span class="lineNum"> 513 </span> : -<span class="lineNum"> 514 </span> : static _Const_Base_ptr -<span class="lineNum"> 515 </span> : _S_maximum(_Const_Base_ptr __x) -<span class="lineNum"> 516 </span> : { return _Rb_tree_node_base::_S_maximum(__x); } -<span class="lineNum"> 517 </span> : -<span class="lineNum"> 518 </span> : public: -<span class="lineNum"> 519 </span> : typedef _Rb_tree_iterator<value_type> iterator; -<span class="lineNum"> 520 </span> : typedef _Rb_tree_const_iterator<value_type> const_iterator; -<span class="lineNum"> 521 </span> : -<span class="lineNum"> 522 </span> : typedef std::reverse_iterator<iterator> reverse_iterator; -<span class="lineNum"> 523 </span> : typedef std::reverse_iterator<const_iterator> const_reverse_iterator; -<span class="lineNum"> 524 </span> : -<span class="lineNum"> 525 </span> : private: -<span class="lineNum"> 526 </span> : iterator -<span class="lineNum"> 527 </span> : _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, -<span class="lineNum"> 528 </span> : const value_type& __v); -<span class="lineNum"> 529 </span> : -<span class="lineNum"> 530 </span> : // _GLIBCXX_RESOLVE_LIB_DEFECTS -<span class="lineNum"> 531 </span> : // 233. Insertion hints in associative containers. -<span class="lineNum"> 532 </span> : iterator -<span class="lineNum"> 533 </span> : _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); -<span class="lineNum"> 534 </span> : -<span class="lineNum"> 535 </span> : iterator -<span class="lineNum"> 536 </span> : _M_insert_equal_lower(const value_type& __x); -<span class="lineNum"> 537 </span> : -<span class="lineNum"> 538 </span> : _Link_type -<span class="lineNum"> 539 </span> : _M_copy(_Const_Link_type __x, _Link_type __p); -<span class="lineNum"> 540 </span> : -<span class="lineNum"> 541 </span> : void -<span class="lineNum"> 542 </span> : _M_erase(_Link_type __x); -<span class="lineNum"> 543 </span> : -<span class="lineNum"> 544 </span> : iterator -<span class="lineNum"> 545 </span> : _M_lower_bound(_Link_type __x, _Link_type __y, -<span class="lineNum"> 546 </span> : const _Key& __k); -<span class="lineNum"> 547 </span> : -<span class="lineNum"> 548 </span> : const_iterator -<span class="lineNum"> 549 </span> : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, -<span class="lineNum"> 550 </span> : const _Key& __k) const; -<span class="lineNum"> 551 </span> : -<span class="lineNum"> 552 </span> : iterator -<span class="lineNum"> 553 </span> : _M_upper_bound(_Link_type __x, _Link_type __y, -<span class="lineNum"> 554 </span> : const _Key& __k); -<span class="lineNum"> 555 </span> : -<span class="lineNum"> 556 </span> : const_iterator -<span class="lineNum"> 557 </span> : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, -<span class="lineNum"> 558 </span> : const _Key& __k) const; -<span class="lineNum"> 559 </span> : -<span class="lineNum"> 560 </span> : public: -<span class="lineNum"> 561 </span> : // allocation/deallocation -<span class="lineNum"> 562 </span><span class="lineCov"> 280599 : _Rb_tree() { }</span> -<span class="lineNum"> 563 </span> : -<span class="lineNum"> 564 </span> : _Rb_tree(const _Compare& __comp, -<span class="lineNum"> 565 </span> : const allocator_type& __a = allocator_type()) -<span class="lineNum"> 566 </span> : : _M_impl(__comp, __a) { } -<span class="lineNum"> 567 </span> : -<span class="lineNum"> 568 </span><span class="lineCov"> 934596 : _Rb_tree(const _Rb_tree& __x)</span> -<span class="lineNum"> 569 </span><span class="lineCov"> 934596 : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())</span> -<span class="lineNum"> 570 </span> : { -<span class="lineNum"> 571 </span><span class="lineCov"> 934596 : if (__x._M_root() != 0)</span> -<span class="lineNum"> 572 </span> : { -<span class="lineNum"> 573 </span><span class="lineCov"> 880580 : _M_root() = _M_copy(__x._M_begin(), _M_end());</span> -<span class="lineNum"> 574 </span><span class="lineCov"> 880580 : _M_leftmost() = _S_minimum(_M_root());</span> -<span class="lineNum"> 575 </span><span class="lineCov"> 880580 : _M_rightmost() = _S_maximum(_M_root());</span> -<span class="lineNum"> 576 </span><span class="lineCov"> 880580 : _M_impl._M_node_count = __x._M_impl._M_node_count;</span> -<span class="lineNum"> 577 </span> : } -<span class="lineNum"> 578 </span><span class="lineCov"> 934596 : }</span> -<span class="lineNum"> 579 </span> : -<span class="lineNum"> 580 </span> : #ifdef __GXX_EXPERIMENTAL_CXX0X__ -<span class="lineNum"> 581 </span> : _Rb_tree(_Rb_tree&& __x); -<span class="lineNum"> 582 </span> : #endif -<span class="lineNum"> 583 </span> : -<span class="lineNum"> 584 </span><span class="lineCov"> 1320929 : ~_Rb_tree()</span> -<span class="lineNum"> 585 </span><span class="lineCov"> 1320929 : { _M_erase(_M_begin()); }</span> -<span class="lineNum"> 586 </span> : -<span class="lineNum"> 587 </span> : _Rb_tree& -<span class="lineNum"> 588 </span> : operator=(const _Rb_tree& __x); -<span class="lineNum"> 589 </span> : -<span class="lineNum"> 590 </span> : // Accessors. -<span class="lineNum"> 591 </span> : _Compare -<span class="lineNum"> 592 </span><span class="lineCov"> 3296 : key_comp() const</span> -<span class="lineNum"> 593 </span><span class="lineCov"> 3296 : { return _M_impl._M_key_compare; }</span> -<span class="lineNum"> 594 </span> : -<span class="lineNum"> 595 </span> : iterator -<span class="lineNum"> 596 </span><span class="lineCov"> 538878 : begin()</span> -<span class="lineNum"> 597 </span> : { -<span class="lineNum"> 598 </span> : return iterator(static_cast<_Link_type> -<span class="lineNum"> 599 </span><span class="lineCov"> 538878 : (this->_M_impl._M_header._M_left));</span> -<span class="lineNum"> 600 </span> : } -<span class="lineNum"> 601 </span> : -<span class="lineNum"> 602 </span> : const_iterator -<span class="lineNum"> 603 </span><span class="lineCov"> 468185 : begin() const</span> -<span class="lineNum"> 604 </span> : { -<span class="lineNum"> 605 </span> : return const_iterator(static_cast<_Const_Link_type> -<span class="lineNum"> 606 </span><span class="lineCov"> 468185 : (this->_M_impl._M_header._M_left));</span> -<span class="lineNum"> 607 </span> : } -<span class="lineNum"> 608 </span> : -<span class="lineNum"> 609 </span> : iterator -<span class="lineNum"> 610 </span><span class="lineCov"> 230534 : end()</span> -<span class="lineNum"> 611 </span><span class="lineCov"> 230534 : { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }</span> -<span class="lineNum"> 612 </span> : -<span class="lineNum"> 613 </span> : const_iterator -<span class="lineNum"> 614 </span><span class="lineCov"> 2022586 : end() const</span> -<span class="lineNum"> 615 </span> : { -<span class="lineNum"> 616 </span> : return const_iterator(static_cast<_Const_Link_type> -<span class="lineNum"> 617 </span><span class="lineCov"> 2022586 : (&this->_M_impl._M_header));</span> -<span class="lineNum"> 618 </span> : } -<span class="lineNum"> 619 </span> : -<span class="lineNum"> 620 </span> : reverse_iterator -<span class="lineNum"> 621 </span> : rbegin() -<span class="lineNum"> 622 </span> : { return reverse_iterator(end()); } -<span class="lineNum"> 623 </span> : -<span class="lineNum"> 624 </span> : const_reverse_iterator -<span class="lineNum"> 625 </span><span class="lineCov"> 32 : rbegin() const</span> -<span class="lineNum"> 626 </span><span class="lineCov"> 32 : { return const_reverse_iterator(end()); }</span> -<span class="lineNum"> 627 </span> : -<span class="lineNum"> 628 </span> : reverse_iterator -<span class="lineNum"> 629 </span> : rend() -<span class="lineNum"> 630 </span> : { return reverse_iterator(begin()); } -<span class="lineNum"> 631 </span> : -<span class="lineNum"> 632 </span> : const_reverse_iterator -<span class="lineNum"> 633 </span> : rend() const -<span class="lineNum"> 634 </span> : { return const_reverse_iterator(begin()); } -<span class="lineNum"> 635 </span> : -<span class="lineNum"> 636 </span> : bool -<span class="lineNum"> 637 </span><span class="lineCov"> 342325 : empty() const</span> -<span class="lineNum"> 638 </span><span class="lineCov"> 342325 : { return _M_impl._M_node_count == 0; }</span> -<span class="lineNum"> 639 </span> : -<span class="lineNum"> 640 </span> : size_type -<span class="lineNum"> 641 </span><span class="lineCov"> 734435 : size() const</span> -<span class="lineNum"> 642 </span><span class="lineCov"> 734435 : { return _M_impl._M_node_count; }</span> -<span class="lineNum"> 643 </span> : -<span class="lineNum"> 644 </span> : size_type -<span class="lineNum"> 645 </span> : max_size() const -<span class="lineNum"> 646 </span> : { return get_allocator().max_size(); } -<span class="lineNum"> 647 </span> : -<span class="lineNum"> 648 </span> : void -<span class="lineNum"> 649 </span> : #ifdef __GXX_EXPERIMENTAL_CXX0X__ -<span class="lineNum"> 650 </span> : swap(_Rb_tree&& __t); -<span class="lineNum"> 651 </span> : #else -<span class="lineNum"> 652 </span> : swap(_Rb_tree& __t); -<span class="lineNum"> 653 </span> : #endif -<span class="lineNum"> 654 </span> : -<span class="lineNum"> 655 </span> : // Insert/erase. -<span class="lineNum"> 656 </span> : pair<iterator, bool> -<span class="lineNum"> 657 </span> : _M_insert_unique(const value_type& __x); -<span class="lineNum"> 658 </span> : -<span class="lineNum"> 659 </span> : iterator -<span class="lineNum"> 660 </span> : _M_insert_equal(const value_type& __x); -<span class="lineNum"> 661 </span> : -<span class="lineNum"> 662 </span> : iterator -<span class="lineNum"> 663 </span> : _M_insert_unique_(const_iterator __position, const value_type& __x); -<span class="lineNum"> 664 </span> : -<span class="lineNum"> 665 </span> : iterator -<span class="lineNum"> 666 </span> : _M_insert_equal_(const_iterator __position, const value_type& __x); -<span class="lineNum"> 667 </span> : -<span class="lineNum"> 668 </span> : template<typename _InputIterator> -<span class="lineNum"> 669 </span> : void -<span class="lineNum"> 670 </span> : _M_insert_unique(_InputIterator __first, _InputIterator __last); -<span class="lineNum"> 671 </span> : -<span class="lineNum"> 672 </span> : template<typename _InputIterator> -<span class="lineNum"> 673 </span> : void -<span class="lineNum"> 674 </span> : _M_insert_equal(_InputIterator __first, _InputIterator __last); -<span class="lineNum"> 675 </span> : -<span class="lineNum"> 676 </span> : void -<span class="lineNum"> 677 </span> : erase(iterator __position); -<span class="lineNum"> 678 </span> : -<span class="lineNum"> 679 </span> : void -<span class="lineNum"> 680 </span> : erase(const_iterator __position); -<span class="lineNum"> 681 </span> : -<span class="lineNum"> 682 </span> : size_type -<span class="lineNum"> 683 </span> : erase(const key_type& __x); -<span class="lineNum"> 684 </span> : -<span class="lineNum"> 685 </span> : void -<span class="lineNum"> 686 </span> : erase(iterator __first, iterator __last); -<span class="lineNum"> 687 </span> : -<span class="lineNum"> 688 </span> : void -<span class="lineNum"> 689 </span> : erase(const_iterator __first, const_iterator __last); -<span class="lineNum"> 690 </span> : -<span class="lineNum"> 691 </span> : void -<span class="lineNum"> 692 </span> : erase(const key_type* __first, const key_type* __last); -<span class="lineNum"> 693 </span> : -<span class="lineNum"> 694 </span> : void -<span class="lineNum"> 695 </span><span class="lineCov"> 87992 : clear()</span> -<span class="lineNum"> 696 </span> : { -<span class="lineNum"> 697 </span><span class="lineCov"> 87992 : _M_erase(_M_begin());</span> -<span class="lineNum"> 698 </span><span class="lineCov"> 87992 : _M_leftmost() = _M_end();</span> -<span class="lineNum"> 699 </span><span class="lineCov"> 87992 : _M_root() = 0;</span> -<span class="lineNum"> 700 </span><span class="lineCov"> 87992 : _M_rightmost() = _M_end();</span> -<span class="lineNum"> 701 </span><span class="lineCov"> 87992 : _M_impl._M_node_count = 0;</span> -<span class="lineNum"> 702 </span><span class="lineCov"> 87992 : }</span> -<span class="lineNum"> 703 </span> : -<span class="lineNum"> 704 </span> : // Set operations. -<span class="lineNum"> 705 </span> : iterator -<span class="lineNum"> 706 </span> : find(const key_type& __k); -<span class="lineNum"> 707 </span> : -<span class="lineNum"> 708 </span> : const_iterator -<span class="lineNum"> 709 </span> : find(const key_type& __k) const; -<span class="lineNum"> 710 </span> : -<span class="lineNum"> 711 </span> : size_type -<span class="lineNum"> 712 </span> : count(const key_type& __k) const; -<span class="lineNum"> 713 </span> : -<span class="lineNum"> 714 </span> : iterator -<span class="lineNum"> 715 </span><span class="lineCov"> 6297 : lower_bound(const key_type& __k)</span> -<span class="lineNum"> 716 </span><span class="lineCov"> 6297 : { return _M_lower_bound(_M_begin(), _M_end(), __k); }</span> -<span class="lineNum"> 717 </span> : -<span class="lineNum"> 718 </span> : const_iterator -<span class="lineNum"> 719 </span> : lower_bound(const key_type& __k) const -<span class="lineNum"> 720 </span> : { return _M_lower_bound(_M_begin(), _M_end(), __k); } -<span class="lineNum"> 721 </span> : -<span class="lineNum"> 722 </span> : iterator -<span class="lineNum"> 723 </span> : upper_bound(const key_type& __k) -<span class="lineNum"> 724 </span> : { return _M_upper_bound(_M_begin(), _M_end(), __k); } -<span class="lineNum"> 725 </span> : -<span class="lineNum"> 726 </span> : const_iterator -<span class="lineNum"> 727 </span> : upper_bound(const key_type& __k) const -<span class="lineNum"> 728 </span> : { return _M_upper_bound(_M_begin(), _M_end(), __k); } -<span class="lineNum"> 729 </span> : -<span class="lineNum"> 730 </span> : pair<iterator, iterator> -<span class="lineNum"> 731 </span> : equal_range(const key_type& __k); -<span class="lineNum"> 732 </span> : -<span class="lineNum"> 733 </span> : pair<const_iterator, const_iterator> -<span class="lineNum"> 734 </span> : equal_range(const key_type& __k) const; -<span class="lineNum"> 735 </span> : -<span class="lineNum"> 736 </span> : // Debugging. -<span class="lineNum"> 737 </span> : bool -<span class="lineNum"> 738 </span> : __rb_verify() const; -<span class="lineNum"> 739 </span> : }; -<span class="lineNum"> 740 </span> : -<span class="lineNum"> 741 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 742 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 743 </span> : inline bool -<span class="lineNum"> 744 </span> : operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 745 </span><span class="lineCov"> 4 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)</span> -<span class="lineNum"> 746 </span> : { -<span class="lineNum"> 747 </span> : return __x.size() == __y.size() -<span class="lineNum"> 748 </span><span class="lineCov"> 4 : && std::equal(__x.begin(), __x.end(), __y.begin());</span> -<span class="lineNum"> 749 </span> : } -<span class="lineNum"> 750 </span> : -<span class="lineNum"> 751 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 752 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 753 </span> : inline bool -<span class="lineNum"> 754 </span> : operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 755 </span> : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 756 </span> : { -<span class="lineNum"> 757 </span> : return std::lexicographical_compare(__x.begin(), __x.end(), -<span class="lineNum"> 758 </span> : __y.begin(), __y.end()); -<span class="lineNum"> 759 </span> : } -<span class="lineNum"> 760 </span> : -<span class="lineNum"> 761 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 762 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 763 </span> : inline bool -<span class="lineNum"> 764 </span> : operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 765 </span> : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 766 </span> : { return !(__x == __y); } -<span class="lineNum"> 767 </span> : -<span class="lineNum"> 768 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 769 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 770 </span> : inline bool -<span class="lineNum"> 771 </span> : operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 772 </span> : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 773 </span> : { return __y < __x; } -<span class="lineNum"> 774 </span> : -<span class="lineNum"> 775 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 776 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 777 </span> : inline bool -<span class="lineNum"> 778 </span> : operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 779 </span> : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 780 </span> : { return !(__y < __x); } -<span class="lineNum"> 781 </span> : -<span class="lineNum"> 782 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 783 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 784 </span> : inline bool -<span class="lineNum"> 785 </span> : operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 786 </span> : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 787 </span> : { return !(__x < __y); } -<span class="lineNum"> 788 </span> : -<span class="lineNum"> 789 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 790 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 791 </span> : inline void -<span class="lineNum"> 792 </span> : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, -<span class="lineNum"> 793 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) -<span class="lineNum"> 794 </span> : { __x.swap(__y); } -<span class="lineNum"> 795 </span> : -<span class="lineNum"> 796 </span> : #ifdef __GXX_EXPERIMENTAL_CXX0X__ -<span class="lineNum"> 797 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 798 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 799 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 800 </span> : _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) -<span class="lineNum"> 801 </span> : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) -<span class="lineNum"> 802 </span> : { -<span class="lineNum"> 803 </span> : if (__x._M_root() != 0) -<span class="lineNum"> 804 </span> : { -<span class="lineNum"> 805 </span> : _M_root() = __x._M_root(); -<span class="lineNum"> 806 </span> : _M_leftmost() = __x._M_leftmost(); -<span class="lineNum"> 807 </span> : _M_rightmost() = __x._M_rightmost(); -<span class="lineNum"> 808 </span> : _M_root()->_M_parent = _M_end(); -<span class="lineNum"> 809 </span> : -<span class="lineNum"> 810 </span> : __x._M_root() = 0; -<span class="lineNum"> 811 </span> : __x._M_leftmost() = __x._M_end(); -<span class="lineNum"> 812 </span> : __x._M_rightmost() = __x._M_end(); -<span class="lineNum"> 813 </span> : -<span class="lineNum"> 814 </span> : this->_M_impl._M_node_count = __x._M_impl._M_node_count; -<span class="lineNum"> 815 </span> : __x._M_impl._M_node_count = 0; -<span class="lineNum"> 816 </span> : } -<span class="lineNum"> 817 </span> : } -<span class="lineNum"> 818 </span> : #endif -<span class="lineNum"> 819 </span> : -<span class="lineNum"> 820 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 821 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 822 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& -<span class="lineNum"> 823 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 824 </span><span class="lineCov"> 97 : operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)</span> -<span class="lineNum"> 825 </span> : { -<span class="lineNum"> 826 </span><span class="lineCov"> 97 : if (this != &__x)</span> -<span class="lineNum"> 827 </span> : { -<span class="lineNum"> 828 </span> : // Note that _Key may be a constant type. -<span class="lineNum"> 829 </span><span class="lineCov"> 97 : clear();</span> -<span class="lineNum"> 830 </span><span class="lineCov"> 97 : _M_impl._M_key_compare = __x._M_impl._M_key_compare;</span> -<span class="lineNum"> 831 </span><span class="lineCov"> 97 : if (__x._M_root() != 0)</span> -<span class="lineNum"> 832 </span> : { -<span class="lineNum"> 833 </span><span class="lineCov"> 53 : _M_root() = _M_copy(__x._M_begin(), _M_end());</span> -<span class="lineNum"> 834 </span><span class="lineCov"> 53 : _M_leftmost() = _S_minimum(_M_root());</span> -<span class="lineNum"> 835 </span><span class="lineCov"> 53 : _M_rightmost() = _S_maximum(_M_root());</span> -<span class="lineNum"> 836 </span><span class="lineCov"> 53 : _M_impl._M_node_count = __x._M_impl._M_node_count;</span> -<span class="lineNum"> 837 </span> : } -<span class="lineNum"> 838 </span> : } -<span class="lineNum"> 839 </span><span class="lineCov"> 97 : return *this;</span> -<span class="lineNum"> 840 </span> : } -<span class="lineNum"> 841 </span> : -<span class="lineNum"> 842 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 843 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 844 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 845 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 846 </span><span class="lineCov"> 2070706 : _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)</span> -<span class="lineNum"> 847 </span> : { -<span class="lineNum"> 848 </span> : bool __insert_left = (__x != 0 || __p == _M_end() -<span class="lineNum"> 849 </span> : || _M_impl._M_key_compare(_KeyOfValue()(__v), -<span class="lineNum"> 850 </span><span class="lineCov"> 2070706 : _S_key(__p)));</span> -<span class="lineNum"> 851 </span> : -<span class="lineNum"> 852 </span><span class="lineCov"> 2070706 : _Link_type __z = _M_create_node(__v);</span> -<span class="lineNum"> 853 </span> : -<span class="lineNum"> 854 </span><span class="lineCov"> 2070706 : _Rb_tree_insert_and_rebalance(__insert_left, __z,</span> -<span class="lineNum"> 855 </span> : const_cast<_Base_ptr>(__p), -<span class="lineNum"> 856 </span> : this->_M_impl._M_header); -<span class="lineNum"> 857 </span><span class="lineCov"> 2070706 : ++_M_impl._M_node_count;</span> -<span class="lineNum"> 858 </span><span class="lineCov"> 2070706 : return iterator(__z);</span> -<span class="lineNum"> 859 </span> : } -<span class="lineNum"> 860 </span> : -<span class="lineNum"> 861 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 862 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 863 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 864 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 865 </span> : _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) -<span class="lineNum"> 866 </span> : { -<span class="lineNum"> 867 </span> : bool __insert_left = (__x != 0 || __p == _M_end() -<span class="lineNum"> 868 </span> : || !_M_impl._M_key_compare(_S_key(__p), -<span class="lineNum"> 869 </span> : _KeyOfValue()(__v))); -<span class="lineNum"> 870 </span> : -<span class="lineNum"> 871 </span> : _Link_type __z = _M_create_node(__v); -<span class="lineNum"> 872 </span> : -<span class="lineNum"> 873 </span> : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, -<span class="lineNum"> 874 </span> : this->_M_impl._M_header); -<span class="lineNum"> 875 </span> : ++_M_impl._M_node_count; -<span class="lineNum"> 876 </span> : return iterator(__z); -<span class="lineNum"> 877 </span> : } -<span class="lineNum"> 878 </span> : -<span class="lineNum"> 879 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 880 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 881 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 882 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 883 </span> : _M_insert_equal_lower(const _Val& __v) -<span class="lineNum"> 884 </span> : { -<span class="lineNum"> 885 </span> : _Link_type __x = _M_begin(); -<span class="lineNum"> 886 </span> : _Link_type __y = _M_end(); -<span class="lineNum"> 887 </span> : while (__x != 0) -<span class="lineNum"> 888 </span> : { -<span class="lineNum"> 889 </span> : __y = __x; -<span class="lineNum"> 890 </span> : __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? -<span class="lineNum"> 891 </span> : _S_left(__x) : _S_right(__x); -<span class="lineNum"> 892 </span> : } -<span class="lineNum"> 893 </span> : return _M_insert_lower(__x, __y, __v); -<span class="lineNum"> 894 </span> : } -<span class="lineNum"> 895 </span> : -<span class="lineNum"> 896 </span> : template<typename _Key, typename _Val, typename _KoV, -<span class="lineNum"> 897 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 898 </span> : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type -<span class="lineNum"> 899 </span> : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: -<span class="lineNum"> 900 </span><span class="lineCov"> 2381075 : _M_copy(_Const_Link_type __x, _Link_type __p)</span> -<span class="lineNum"> 901 </span> : { -<span class="lineNum"> 902 </span> : // Structural copy. __x and __p must be non-null. -<span class="lineNum"> 903 </span><span class="lineCov"> 2381075 : _Link_type __top = _M_clone_node(__x);</span> -<span class="lineNum"> 904 </span><span class="lineCov"> 2381075 : __top->_M_parent = __p;</span> -<span class="lineNum"> 905 </span> : -<span class="lineNum"> 906 </span> : try -<span class="lineNum"> 907 </span> : { -<span class="lineNum"> 908 </span><span class="lineCov"> 2381075 : if (__x->_M_right)</span> -<span class="lineNum"> 909 </span><span class="lineCov"> 1355924 : __top->_M_right = _M_copy(_S_right(__x), __top);</span> -<span class="lineNum"> 910 </span><span class="lineCov"> 2381075 : __p = __top;</span> -<span class="lineNum"> 911 </span><span class="lineCov"> 2381075 : __x = _S_left(__x);</span> -<span class="lineNum"> 912 </span> : -<span class="lineNum"> 913 </span><span class="lineCov"> 5955057 : while (__x != 0)</span> -<span class="lineNum"> 914 </span> : { -<span class="lineNum"> 915 </span><span class="lineCov"> 1192907 : _Link_type __y = _M_clone_node(__x);</span> -<span class="lineNum"> 916 </span><span class="lineCov"> 1192907 : __p->_M_left = __y;</span> -<span class="lineNum"> 917 </span><span class="lineCov"> 1192907 : __y->_M_parent = __p;</span> -<span class="lineNum"> 918 </span><span class="lineCov"> 1192907 : if (__x->_M_right)</span> -<span class="lineNum"> 919 </span><span class="lineCov"> 144518 : __y->_M_right = _M_copy(_S_right(__x), __y);</span> -<span class="lineNum"> 920 </span><span class="lineCov"> 1192907 : __p = __y;</span> -<span class="lineNum"> 921 </span><span class="lineCov"> 1192907 : __x = _S_left(__x);</span> -<span class="lineNum"> 922 </span> : } -<span class="lineNum"> 923 </span> : } -<span class="lineNum"> 924 </span><span class="lineNoCov"> 0 : catch(...)</span> -<span class="lineNum"> 925 </span> : { -<span class="lineNum"> 926 </span><span class="lineNoCov"> 0 : _M_erase(__top);</span> -<span class="lineNum"> 927 </span><span class="lineNoCov"> 0 : __throw_exception_again;</span> -<span class="lineNum"> 928 </span> : } -<span class="lineNum"> 929 </span><span class="lineCov"> 2381075 : return __top;</span> -<span class="lineNum"> 930 </span> : } -<span class="lineNum"> 931 </span> : -<span class="lineNum"> 932 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 933 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 934 </span> : void -<span class="lineNum"> 935 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 936 </span><span class="lineCov"> 7053477 : _M_erase(_Link_type __x)</span> -<span class="lineNum"> 937 </span> : { -<span class="lineNum"> 938 </span> : // Erase without rebalancing. -<span class="lineNum"> 939 </span><span class="lineCov"> 19751483 : while (__x != 0)</span> -<span class="lineNum"> 940 </span> : { -<span class="lineNum"> 941 </span><span class="lineCov"> 5644529 : _M_erase(_S_right(__x));</span> -<span class="lineNum"> 942 </span><span class="lineCov"> 5644529 : _Link_type __y = _S_left(__x);</span> -<span class="lineNum"> 943 </span><span class="lineCov"> 5644529 : _M_destroy_node(__x);</span> -<span class="lineNum"> 944 </span><span class="lineCov"> 5644529 : __x = __y;</span> -<span class="lineNum"> 945 </span> : } -<span class="lineNum"> 946 </span><span class="lineCov"> 7053477 : }</span> -<span class="lineNum"> 947 </span> : -<span class="lineNum"> 948 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 949 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 950 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 951 </span> : _Compare, _Alloc>::iterator -<span class="lineNum"> 952 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 953 </span> : _M_lower_bound(_Link_type __x, _Link_type __y, -<span class="lineNum"> 954 </span><span class="lineCov"> 56455 : const _Key& __k)</span> -<span class="lineNum"> 955 </span> : { -<span class="lineNum"> 956 </span><span class="lineCov"> 956283 : while (__x != 0)</span> -<span class="lineNum"> 957 </span><span class="lineCov"> 843373 : if (!_M_impl._M_key_compare(_S_key(__x), __k))</span> -<span class="lineNum"> 958 </span><span class="lineCov"> 159236 : __y = __x, __x = _S_left(__x);</span> -<span class="lineNum"> 959 </span> : else -<span class="lineNum"> 960 </span><span class="lineCov"> 684137 : __x = _S_right(__x);</span> -<span class="lineNum"> 961 </span><span class="lineCov"> 56455 : return iterator(__y);</span> -<span class="lineNum"> 962 </span> : } -<span class="lineNum"> 963 </span> : -<span class="lineNum"> 964 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 965 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 966 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 967 </span> : _Compare, _Alloc>::const_iterator -<span class="lineNum"> 968 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 969 </span> : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, -<span class="lineNum"> 970 </span><span class="lineCov"> 3932 : const _Key& __k) const</span> -<span class="lineNum"> 971 </span> : { -<span class="lineNum"> 972 </span><span class="lineCov"> 16029 : while (__x != 0)</span> -<span class="lineNum"> 973 </span><span class="lineCov"> 8165 : if (!_M_impl._M_key_compare(_S_key(__x), __k))</span> -<span class="lineNum"> 974 </span><span class="lineCov"> 5885 : __y = __x, __x = _S_left(__x);</span> -<span class="lineNum"> 975 </span> : else -<span class="lineNum"> 976 </span><span class="lineCov"> 2280 : __x = _S_right(__x);</span> -<span class="lineNum"> 977 </span><span class="lineCov"> 3932 : return const_iterator(__y);</span> -<span class="lineNum"> 978 </span> : } -<span class="lineNum"> 979 </span> : -<span class="lineNum"> 980 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 981 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 982 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 983 </span> : _Compare, _Alloc>::iterator -<span class="lineNum"> 984 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 985 </span> : _M_upper_bound(_Link_type __x, _Link_type __y, -<span class="lineNum"> 986 </span><span class="lineCov"> 2 : const _Key& __k)</span> -<span class="lineNum"> 987 </span> : { -<span class="lineNum"> 988 </span><span class="lineCov"> 4 : while (__x != 0)</span> -<span class="lineNum"> 989 </span><span class="lineNoCov"> 0 : if (_M_impl._M_key_compare(__k, _S_key(__x)))</span> -<span class="lineNum"> 990 </span><span class="lineNoCov"> 0 : __y = __x, __x = _S_left(__x);</span> -<span class="lineNum"> 991 </span> : else -<span class="lineNum"> 992 </span><span class="lineNoCov"> 0 : __x = _S_right(__x);</span> -<span class="lineNum"> 993 </span><span class="lineCov"> 2 : return iterator(__y);</span> -<span class="lineNum"> 994 </span> : } -<span class="lineNum"> 995 </span> : -<span class="lineNum"> 996 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 997 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 998 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 999 </span> : _Compare, _Alloc>::const_iterator -<span class="lineNum"> 1000 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1001 </span> : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, -<span class="lineNum"> 1002 </span> : const _Key& __k) const -<span class="lineNum"> 1003 </span> : { -<span class="lineNum"> 1004 </span> : while (__x != 0) -<span class="lineNum"> 1005 </span> : if (_M_impl._M_key_compare(__k, _S_key(__x))) -<span class="lineNum"> 1006 </span> : __y = __x, __x = _S_left(__x); -<span class="lineNum"> 1007 </span> : else -<span class="lineNum"> 1008 </span> : __x = _S_right(__x); -<span class="lineNum"> 1009 </span> : return const_iterator(__y); -<span class="lineNum"> 1010 </span> : } -<span class="lineNum"> 1011 </span> : -<span class="lineNum"> 1012 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1013 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1014 </span> : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1015 </span> : _Compare, _Alloc>::iterator, -<span class="lineNum"> 1016 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1017 </span> : _Compare, _Alloc>::iterator> -<span class="lineNum"> 1018 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1019 </span><span class="lineCov"> 9 : equal_range(const _Key& __k)</span> -<span class="lineNum"> 1020 </span> : { -<span class="lineNum"> 1021 </span><span class="lineCov"> 9 : _Link_type __x = _M_begin();</span> -<span class="lineNum"> 1022 </span><span class="lineCov"> 9 : _Link_type __y = _M_end();</span> -<span class="lineNum"> 1023 </span><span class="lineCov"> 20 : while (__x != 0)</span> -<span class="lineNum"> 1024 </span> : { -<span class="lineNum"> 1025 </span><span class="lineCov"> 4 : if (_M_impl._M_key_compare(_S_key(__x), __k))</span> -<span class="lineNum"> 1026 </span><span class="lineNoCov"> 0 : __x = _S_right(__x);</span> -<span class="lineNum"> 1027 </span><span class="lineCov"> 4 : else if (_M_impl._M_key_compare(__k, _S_key(__x)))</span> -<span class="lineNum"> 1028 </span><span class="lineCov"> 2 : __y = __x, __x = _S_left(__x);</span> -<span class="lineNum"> 1029 </span> : else -<span class="lineNum"> 1030 </span> : { -<span class="lineNum"> 1031 </span><span class="lineCov"> 2 : _Link_type __xu(__x), __yu(__y);</span> -<span class="lineNum"> 1032 </span><span class="lineCov"> 2 : __y = __x, __x = _S_left(__x);</span> -<span class="lineNum"> 1033 </span><span class="lineCov"> 2 : __xu = _S_right(__xu);</span> -<span class="lineNum"> 1034 </span> : return pair<iterator, -<span class="lineNum"> 1035 </span> : iterator>(_M_lower_bound(__x, __y, __k), -<span class="lineNum"> 1036 </span><span class="lineCov"> 2 : _M_upper_bound(__xu, __yu, __k));</span> -<span class="lineNum"> 1037 </span> : } -<span class="lineNum"> 1038 </span> : } -<span class="lineNum"> 1039 </span> : return pair<iterator, iterator>(iterator(__y), -<span class="lineNum"> 1040 </span><span class="lineCov"> 7 : iterator(__y));</span> -<span class="lineNum"> 1041 </span> : } -<span class="lineNum"> 1042 </span> : -<span class="lineNum"> 1043 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1044 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1045 </span> : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1046 </span> : _Compare, _Alloc>::const_iterator, -<span class="lineNum"> 1047 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1048 </span> : _Compare, _Alloc>::const_iterator> -<span class="lineNum"> 1049 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1050 </span> : equal_range(const _Key& __k) const -<span class="lineNum"> 1051 </span> : { -<span class="lineNum"> 1052 </span> : _Const_Link_type __x = _M_begin(); -<span class="lineNum"> 1053 </span> : _Const_Link_type __y = _M_end(); -<span class="lineNum"> 1054 </span> : while (__x != 0) -<span class="lineNum"> 1055 </span> : { -<span class="lineNum"> 1056 </span> : if (_M_impl._M_key_compare(_S_key(__x), __k)) -<span class="lineNum"> 1057 </span> : __x = _S_right(__x); -<span class="lineNum"> 1058 </span> : else if (_M_impl._M_key_compare(__k, _S_key(__x))) -<span class="lineNum"> 1059 </span> : __y = __x, __x = _S_left(__x); -<span class="lineNum"> 1060 </span> : else -<span class="lineNum"> 1061 </span> : { -<span class="lineNum"> 1062 </span> : _Const_Link_type __xu(__x), __yu(__y); -<span class="lineNum"> 1063 </span> : __y = __x, __x = _S_left(__x); -<span class="lineNum"> 1064 </span> : __xu = _S_right(__xu); -<span class="lineNum"> 1065 </span> : return pair<const_iterator, -<span class="lineNum"> 1066 </span> : const_iterator>(_M_lower_bound(__x, __y, __k), -<span class="lineNum"> 1067 </span> : _M_upper_bound(__xu, __yu, __k)); -<span class="lineNum"> 1068 </span> : } -<span class="lineNum"> 1069 </span> : } -<span class="lineNum"> 1070 </span> : return pair<const_iterator, const_iterator>(const_iterator(__y), -<span class="lineNum"> 1071 </span> : const_iterator(__y)); -<span class="lineNum"> 1072 </span> : } -<span class="lineNum"> 1073 </span> : -<span class="lineNum"> 1074 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1075 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1076 </span> : void -<span class="lineNum"> 1077 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1078 </span> : #ifdef __GXX_EXPERIMENTAL_CXX0X__ -<span class="lineNum"> 1079 </span> : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t) -<span class="lineNum"> 1080 </span> : #else -<span class="lineNum"> 1081 </span> : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) -<span class="lineNum"> 1082 </span> : #endif -<span class="lineNum"> 1083 </span> : { -<span class="lineNum"> 1084 </span> : if (_M_root() == 0) -<span class="lineNum"> 1085 </span> : { -<span class="lineNum"> 1086 </span> : if (__t._M_root() != 0) -<span class="lineNum"> 1087 </span> : { -<span class="lineNum"> 1088 </span> : _M_root() = __t._M_root(); -<span class="lineNum"> 1089 </span> : _M_leftmost() = __t._M_leftmost(); -<span class="lineNum"> 1090 </span> : _M_rightmost() = __t._M_rightmost(); -<span class="lineNum"> 1091 </span> : _M_root()->_M_parent = _M_end(); -<span class="lineNum"> 1092 </span> : -<span class="lineNum"> 1093 </span> : __t._M_root() = 0; -<span class="lineNum"> 1094 </span> : __t._M_leftmost() = __t._M_end(); -<span class="lineNum"> 1095 </span> : __t._M_rightmost() = __t._M_end(); -<span class="lineNum"> 1096 </span> : } -<span class="lineNum"> 1097 </span> : } -<span class="lineNum"> 1098 </span> : else if (__t._M_root() == 0) -<span class="lineNum"> 1099 </span> : { -<span class="lineNum"> 1100 </span> : __t._M_root() = _M_root(); -<span class="lineNum"> 1101 </span> : __t._M_leftmost() = _M_leftmost(); -<span class="lineNum"> 1102 </span> : __t._M_rightmost() = _M_rightmost(); -<span class="lineNum"> 1103 </span> : __t._M_root()->_M_parent = __t._M_end(); -<span class="lineNum"> 1104 </span> : -<span class="lineNum"> 1105 </span> : _M_root() = 0; -<span class="lineNum"> 1106 </span> : _M_leftmost() = _M_end(); -<span class="lineNum"> 1107 </span> : _M_rightmost() = _M_end(); -<span class="lineNum"> 1108 </span> : } -<span class="lineNum"> 1109 </span> : else -<span class="lineNum"> 1110 </span> : { -<span class="lineNum"> 1111 </span> : std::swap(_M_root(),__t._M_root()); -<span class="lineNum"> 1112 </span> : std::swap(_M_leftmost(),__t._M_leftmost()); -<span class="lineNum"> 1113 </span> : std::swap(_M_rightmost(),__t._M_rightmost()); -<span class="lineNum"> 1114 </span> : -<span class="lineNum"> 1115 </span> : _M_root()->_M_parent = _M_end(); -<span class="lineNum"> 1116 </span> : __t._M_root()->_M_parent = __t._M_end(); -<span class="lineNum"> 1117 </span> : } -<span class="lineNum"> 1118 </span> : // No need to swap header's color as it does not change. -<span class="lineNum"> 1119 </span> : std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); -<span class="lineNum"> 1120 </span> : std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); -<span class="lineNum"> 1121 </span> : -<span class="lineNum"> 1122 </span> : // _GLIBCXX_RESOLVE_LIB_DEFECTS -<span class="lineNum"> 1123 </span> : // 431. Swapping containers with unequal allocators. -<span class="lineNum"> 1124 </span> : std::__alloc_swap<_Node_allocator>:: -<span class="lineNum"> 1125 </span> : _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); -<span class="lineNum"> 1126 </span> : } -<span class="lineNum"> 1127 </span> : -<span class="lineNum"> 1128 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1129 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1130 </span> : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1131 </span> : _Compare, _Alloc>::iterator, bool> -<span class="lineNum"> 1132 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1133 </span><span class="lineCov"> 1653740 : _M_insert_unique(const _Val& __v)</span> -<span class="lineNum"> 1134 </span> : { -<span class="lineNum"> 1135 </span><span class="lineCov"> 1653740 : _Link_type __x = _M_begin();</span> -<span class="lineNum"> 1136 </span><span class="lineCov"> 1653740 : _Link_type __y = _M_end();</span> -<span class="lineNum"> 1137 </span><span class="lineCov"> 1653740 : bool __comp = true;</span> -<span class="lineNum"> 1138 </span><span class="lineCov"> 9798389 : while (__x != 0)</span> -<span class="lineNum"> 1139 </span> : { -<span class="lineNum"> 1140 </span><span class="lineCov"> 6490909 : __y = __x;</span> -<span class="lineNum"> 1141 </span><span class="lineCov"> 6490909 : __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));</span> -<span class="lineNum"> 1142 </span><span class="lineCov"> 6490909 : __x = __comp ? _S_left(__x) : _S_right(__x);</span> -<span class="lineNum"> 1143 </span> : } -<span class="lineNum"> 1144 </span><span class="lineCov"> 1653740 : iterator __j = iterator(__y);</span> -<span class="lineNum"> 1145 </span><span class="lineCov"> 1653740 : if (__comp)</span> -<span class="lineNum"> 1146 </span> : { -<span class="lineNum"> 1147 </span><span class="lineCov"> 536188 : if (__j == begin())</span> -<span class="lineNum"> 1148 </span><span class="lineCov"> 452855 : return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);</span> -<span class="lineNum"> 1149 </span> : else -<span class="lineNum"> 1150 </span><span class="lineCov"> 83333 : --__j;</span> -<span class="lineNum"> 1151 </span> : } -<span class="lineNum"> 1152 </span><span class="lineCov"> 1200885 : if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))</span> -<span class="lineNum"> 1153 </span><span class="lineCov"> 1095156 : return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);</span> -<span class="lineNum"> 1154 </span><span class="lineCov"> 105729 : return pair<iterator, bool>(__j, false);</span> -<span class="lineNum"> 1155 </span> : } -<span class="lineNum"> 1156 </span> : -<span class="lineNum"> 1157 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1158 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1159 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 1160 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1161 </span> : _M_insert_equal(const _Val& __v) -<span class="lineNum"> 1162 </span> : { -<span class="lineNum"> 1163 </span> : _Link_type __x = _M_begin(); -<span class="lineNum"> 1164 </span> : _Link_type __y = _M_end(); -<span class="lineNum"> 1165 </span> : while (__x != 0) -<span class="lineNum"> 1166 </span> : { -<span class="lineNum"> 1167 </span> : __y = __x; -<span class="lineNum"> 1168 </span> : __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? -<span class="lineNum"> 1169 </span> : _S_left(__x) : _S_right(__x); -<span class="lineNum"> 1170 </span> : } -<span class="lineNum"> 1171 </span> : return _M_insert_(__x, __y, __v); -<span class="lineNum"> 1172 </span> : } -<span class="lineNum"> 1173 </span> : -<span class="lineNum"> 1174 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1175 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1176 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 1177 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1178 </span><span class="lineCov"> 652700 : _M_insert_unique_(const_iterator __position, const _Val& __v)</span> -<span class="lineNum"> 1179 </span> : { -<span class="lineNum"> 1180 </span> : // end() -<span class="lineNum"> 1181 </span><span class="lineCov"> 652700 : if (__position._M_node == _M_end())</span> -<span class="lineNum"> 1182 </span> : { -<span class="lineNum"> 1183 </span><span class="lineCov"> 649758 : if (size() > 0</span> -<span class="lineNum"> 1184 </span> : && _M_impl._M_key_compare(_S_key(_M_rightmost()), -<span class="lineNum"> 1185 </span> : _KeyOfValue()(__v))) -<span class="lineNum"> 1186 </span><span class="lineCov"> 521501 : return _M_insert_(0, _M_rightmost(), __v);</span> -<span class="lineNum"> 1187 </span> : else -<span class="lineNum"> 1188 </span><span class="lineCov"> 128257 : return _M_insert_unique(__v).first;</span> -<span class="lineNum"> 1189 </span> : } -<span class="lineNum"> 1190 </span><span class="lineCov"> 2942 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),</span> -<span class="lineNum"> 1191 </span> : _S_key(__position._M_node))) -<span class="lineNum"> 1192 </span> : { -<span class="lineNum"> 1193 </span> : // First, try before... -<span class="lineNum"> 1194 </span><span class="lineCov"> 2040 : const_iterator __before = __position;</span> -<span class="lineNum"> 1195 </span><span class="lineCov"> 2040 : if (__position._M_node == _M_leftmost()) // begin()</span> -<span class="lineNum"> 1196 </span><span class="lineCov"> 72 : return _M_insert_(_M_leftmost(), _M_leftmost(), __v);</span> -<span class="lineNum"> 1197 </span><span class="lineCov"> 1968 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), </span> -<span class="lineNum"> 1198 </span> : _KeyOfValue()(__v))) -<span class="lineNum"> 1199 </span> : { -<span class="lineNum"> 1200 </span><span class="lineCov"> 1101 : if (_S_right(__before._M_node) == 0)</span> -<span class="lineNum"> 1201 </span><span class="lineCov"> 562 : return _M_insert_(0, __before._M_node, __v);</span> -<span class="lineNum"> 1202 </span> : else -<span class="lineNum"> 1203 </span> : return _M_insert_(__position._M_node, -<span class="lineNum"> 1204 </span><span class="lineCov"> 539 : __position._M_node, __v);</span> -<span class="lineNum"> 1205 </span> : } -<span class="lineNum"> 1206 </span> : else -<span class="lineNum"> 1207 </span><span class="lineCov"> 867 : return _M_insert_unique(__v).first;</span> -<span class="lineNum"> 1208 </span> : } -<span class="lineNum"> 1209 </span><span class="lineCov"> 902 : else if (_M_impl._M_key_compare(_S_key(__position._M_node),</span> -<span class="lineNum"> 1210 </span> : _KeyOfValue()(__v))) -<span class="lineNum"> 1211 </span> : { -<span class="lineNum"> 1212 </span> : // ... then try after. -<span class="lineNum"> 1213 </span><span class="lineCov"> 902 : const_iterator __after = __position;</span> -<span class="lineNum"> 1214 </span><span class="lineCov"> 902 : if (__position._M_node == _M_rightmost())</span> -<span class="lineNum"> 1215 </span><span class="lineCov"> 13 : return _M_insert_(0, _M_rightmost(), __v);</span> -<span class="lineNum"> 1216 </span><span class="lineCov"> 889 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),</span> -<span class="lineNum"> 1217 </span> : _S_key((++__after)._M_node))) -<span class="lineNum"> 1218 </span> : { -<span class="lineNum"> 1219 </span><span class="lineCov"> 8 : if (_S_right(__position._M_node) == 0)</span> -<span class="lineNum"> 1220 </span><span class="lineCov"> 4 : return _M_insert_(0, __position._M_node, __v);</span> -<span class="lineNum"> 1221 </span> : else -<span class="lineNum"> 1222 </span><span class="lineCov"> 4 : return _M_insert_(__after._M_node, __after._M_node, __v);</span> -<span class="lineNum"> 1223 </span> : } -<span class="lineNum"> 1224 </span> : else -<span class="lineNum"> 1225 </span><span class="lineCov"> 881 : return _M_insert_unique(__v).first;</span> -<span class="lineNum"> 1226 </span> : } -<span class="lineNum"> 1227 </span> : else -<span class="lineNum"> 1228 </span> : // Equivalent keys. -<span class="lineNum"> 1229 </span> : return iterator(static_cast<_Link_type> -<span class="lineNum"> 1230 </span><span class="lineNoCov"> 0 : (const_cast<_Base_ptr>(__position._M_node)));</span> -<span class="lineNum"> 1231 </span> : } -<span class="lineNum"> 1232 </span> : -<span class="lineNum"> 1233 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1234 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1235 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator -<span class="lineNum"> 1236 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1237 </span> : _M_insert_equal_(const_iterator __position, const _Val& __v) -<span class="lineNum"> 1238 </span> : { -<span class="lineNum"> 1239 </span> : // end() -<span class="lineNum"> 1240 </span> : if (__position._M_node == _M_end()) -<span class="lineNum"> 1241 </span> : { -<span class="lineNum"> 1242 </span> : if (size() > 0 -<span class="lineNum"> 1243 </span> : && !_M_impl._M_key_compare(_KeyOfValue()(__v), -<span class="lineNum"> 1244 </span> : _S_key(_M_rightmost()))) -<span class="lineNum"> 1245 </span> : return _M_insert_(0, _M_rightmost(), __v); -<span class="lineNum"> 1246 </span> : else -<span class="lineNum"> 1247 </span> : return _M_insert_equal(__v); -<span class="lineNum"> 1248 </span> : } -<span class="lineNum"> 1249 </span> : else if (!_M_impl._M_key_compare(_S_key(__position._M_node), -<span class="lineNum"> 1250 </span> : _KeyOfValue()(__v))) -<span class="lineNum"> 1251 </span> : { -<span class="lineNum"> 1252 </span> : // First, try before... -<span class="lineNum"> 1253 </span> : const_iterator __before = __position; -<span class="lineNum"> 1254 </span> : if (__position._M_node == _M_leftmost()) // begin() -<span class="lineNum"> 1255 </span> : return _M_insert_(_M_leftmost(), _M_leftmost(), __v); -<span class="lineNum"> 1256 </span> : else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), -<span class="lineNum"> 1257 </span> : _S_key((--__before)._M_node))) -<span class="lineNum"> 1258 </span> : { -<span class="lineNum"> 1259 </span> : if (_S_right(__before._M_node) == 0) -<span class="lineNum"> 1260 </span> : return _M_insert_(0, __before._M_node, __v); -<span class="lineNum"> 1261 </span> : else -<span class="lineNum"> 1262 </span> : return _M_insert_(__position._M_node, -<span class="lineNum"> 1263 </span> : __position._M_node, __v); -<span class="lineNum"> 1264 </span> : } -<span class="lineNum"> 1265 </span> : else -<span class="lineNum"> 1266 </span> : return _M_insert_equal(__v); -<span class="lineNum"> 1267 </span> : } -<span class="lineNum"> 1268 </span> : else -<span class="lineNum"> 1269 </span> : { -<span class="lineNum"> 1270 </span> : // ... then try after. -<span class="lineNum"> 1271 </span> : const_iterator __after = __position; -<span class="lineNum"> 1272 </span> : if (__position._M_node == _M_rightmost()) -<span class="lineNum"> 1273 </span> : return _M_insert_(0, _M_rightmost(), __v); -<span class="lineNum"> 1274 </span> : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), -<span class="lineNum"> 1275 </span> : _KeyOfValue()(__v))) -<span class="lineNum"> 1276 </span> : { -<span class="lineNum"> 1277 </span> : if (_S_right(__position._M_node) == 0) -<span class="lineNum"> 1278 </span> : return _M_insert_(0, __position._M_node, __v); -<span class="lineNum"> 1279 </span> : else -<span class="lineNum"> 1280 </span> : return _M_insert_(__after._M_node, __after._M_node, __v); -<span class="lineNum"> 1281 </span> : } -<span class="lineNum"> 1282 </span> : else -<span class="lineNum"> 1283 </span> : return _M_insert_equal_lower(__v); -<span class="lineNum"> 1284 </span> : } -<span class="lineNum"> 1285 </span> : } -<span class="lineNum"> 1286 </span> : -<span class="lineNum"> 1287 </span> : template<typename _Key, typename _Val, typename _KoV, -<span class="lineNum"> 1288 </span> : typename _Cmp, typename _Alloc> -<span class="lineNum"> 1289 </span> : template<class _II> -<span class="lineNum"> 1290 </span> : void -<span class="lineNum"> 1291 </span> : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: -<span class="lineNum"> 1292 </span> : _M_insert_unique(_II __first, _II __last) -<span class="lineNum"> 1293 </span> : { -<span class="lineNum"> 1294 </span> : for (; __first != __last; ++__first) -<span class="lineNum"> 1295 </span> : _M_insert_unique_(end(), *__first); -<span class="lineNum"> 1296 </span> : } -<span class="lineNum"> 1297 </span> : -<span class="lineNum"> 1298 </span> : template<typename _Key, typename _Val, typename _KoV, -<span class="lineNum"> 1299 </span> : typename _Cmp, typename _Alloc> -<span class="lineNum"> 1300 </span> : template<class _II> -<span class="lineNum"> 1301 </span> : void -<span class="lineNum"> 1302 </span> : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: -<span class="lineNum"> 1303 </span> : _M_insert_equal(_II __first, _II __last) -<span class="lineNum"> 1304 </span> : { -<span class="lineNum"> 1305 </span> : for (; __first != __last; ++__first) -<span class="lineNum"> 1306 </span> : _M_insert_equal_(end(), *__first); -<span class="lineNum"> 1307 </span> : } -<span class="lineNum"> 1308 </span> : -<span class="lineNum"> 1309 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1310 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1311 </span> : inline void -<span class="lineNum"> 1312 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1313 </span><span class="lineNoCov"> 0 : erase(iterator __position)</span> -<span class="lineNum"> 1314 </span> : { -<span class="lineNum"> 1315 </span> : _Link_type __y = -<span class="lineNum"> 1316 </span> : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase -<span class="lineNum"> 1317 </span> : (__position._M_node, -<span class="lineNum"> 1318 </span><span class="lineNoCov"> 0 : this->_M_impl._M_header));</span> -<span class="lineNum"> 1319 </span><span class="lineNoCov"> 0 : _M_destroy_node(__y);</span> -<span class="lineNum"> 1320 </span><span class="lineNoCov"> 0 : --_M_impl._M_node_count;</span> -<span class="lineNum"> 1321 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 1322 </span> : -<span class="lineNum"> 1323 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1324 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1325 </span> : inline void -<span class="lineNum"> 1326 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1327 </span><span class="lineCov"> 129 : erase(const_iterator __position)</span> -<span class="lineNum"> 1328 </span> : { -<span class="lineNum"> 1329 </span> : _Link_type __y = -<span class="lineNum"> 1330 </span> : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase -<span class="lineNum"> 1331 </span> : (const_cast<_Base_ptr>(__position._M_node), -<span class="lineNum"> 1332 </span><span class="lineCov"> 129 : this->_M_impl._M_header));</span> -<span class="lineNum"> 1333 </span><span class="lineCov"> 129 : _M_destroy_node(__y);</span> -<span class="lineNum"> 1334 </span><span class="lineCov"> 129 : --_M_impl._M_node_count;</span> -<span class="lineNum"> 1335 </span><span class="lineCov"> 129 : }</span> -<span class="lineNum"> 1336 </span> : -<span class="lineNum"> 1337 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1338 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1339 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type -<span class="lineNum"> 1340 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1341 </span><span class="lineCov"> 9 : erase(const _Key& __x)</span> -<span class="lineNum"> 1342 </span> : { -<span class="lineNum"> 1343 </span><span class="lineCov"> 9 : pair<iterator, iterator> __p = equal_range(__x);</span> -<span class="lineNum"> 1344 </span><span class="lineCov"> 9 : const size_type __old_size = size();</span> -<span class="lineNum"> 1345 </span><span class="lineCov"> 9 : erase(__p.first, __p.second);</span> -<span class="lineNum"> 1346 </span><span class="lineCov"> 9 : return __old_size - size();</span> -<span class="lineNum"> 1347 </span> : } -<span class="lineNum"> 1348 </span> : -<span class="lineNum"> 1349 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1350 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1351 </span> : void -<span class="lineNum"> 1352 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1353 </span><span class="lineCov"> 9 : erase(iterator __first, iterator __last)</span> -<span class="lineNum"> 1354 </span> : { -<span class="lineNum"> 1355 </span><span class="lineCov"> 9 : if (__first == begin() && __last == end())</span> -<span class="lineNum"> 1356 </span><span class="lineCov"> 7 : clear();</span> -<span class="lineNum"> 1357 </span> : else -<span class="lineNum"> 1358 </span><span class="lineCov"> 4 : while (__first != __last)</span> -<span class="lineNum"> 1359 </span><span class="lineNoCov"> 0 : erase(__first++);</span> -<span class="lineNum"> 1360 </span><span class="lineCov"> 9 : }</span> -<span class="lineNum"> 1361 </span> : -<span class="lineNum"> 1362 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1363 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1364 </span> : void -<span class="lineNum"> 1365 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1366 </span> : erase(const_iterator __first, const_iterator __last) -<span class="lineNum"> 1367 </span> : { -<span class="lineNum"> 1368 </span> : if (__first == begin() && __last == end()) -<span class="lineNum"> 1369 </span> : clear(); -<span class="lineNum"> 1370 </span> : else -<span class="lineNum"> 1371 </span> : while (__first != __last) -<span class="lineNum"> 1372 </span> : erase(__first++); -<span class="lineNum"> 1373 </span> : } -<span class="lineNum"> 1374 </span> : -<span class="lineNum"> 1375 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1376 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1377 </span> : void -<span class="lineNum"> 1378 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1379 </span> : erase(const _Key* __first, const _Key* __last) -<span class="lineNum"> 1380 </span> : { -<span class="lineNum"> 1381 </span> : while (__first != __last) -<span class="lineNum"> 1382 </span> : erase(*__first++); -<span class="lineNum"> 1383 </span> : } -<span class="lineNum"> 1384 </span> : -<span class="lineNum"> 1385 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1386 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1387 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1388 </span> : _Compare, _Alloc>::iterator -<span class="lineNum"> 1389 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1390 </span><span class="lineCov"> 50156 : find(const _Key& __k)</span> -<span class="lineNum"> 1391 </span> : { -<span class="lineNum"> 1392 </span><span class="lineCov"> 50156 : iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);</span> -<span class="lineNum"> 1393 </span> : return (__j == end() -<span class="lineNum"> 1394 </span> : || _M_impl._M_key_compare(__k, -<span class="lineNum"> 1395 </span><span class="lineCov"> 50156 : _S_key(__j._M_node))) ? end() : __j;</span> -<span class="lineNum"> 1396 </span> : } -<span class="lineNum"> 1397 </span> : -<span class="lineNum"> 1398 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1399 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1400 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, -<span class="lineNum"> 1401 </span> : _Compare, _Alloc>::const_iterator -<span class="lineNum"> 1402 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1403 </span><span class="lineCov"> 3932 : find(const _Key& __k) const</span> -<span class="lineNum"> 1404 </span> : { -<span class="lineNum"> 1405 </span><span class="lineCov"> 3932 : const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);</span> -<span class="lineNum"> 1406 </span> : return (__j == end() -<span class="lineNum"> 1407 </span> : || _M_impl._M_key_compare(__k, -<span class="lineNum"> 1408 </span><span class="lineCov"> 3932 : _S_key(__j._M_node))) ? end() : __j;</span> -<span class="lineNum"> 1409 </span> : } -<span class="lineNum"> 1410 </span> : -<span class="lineNum"> 1411 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1412 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1413 </span> : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type -<span class="lineNum"> 1414 </span> : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -<span class="lineNum"> 1415 </span> : count(const _Key& __k) const -<span class="lineNum"> 1416 </span> : { -<span class="lineNum"> 1417 </span> : pair<const_iterator, const_iterator> __p = equal_range(__k); -<span class="lineNum"> 1418 </span> : const size_type __n = std::distance(__p.first, __p.second); -<span class="lineNum"> 1419 </span> : return __n; -<span class="lineNum"> 1420 </span> : } -<span class="lineNum"> 1421 </span> : -<span class="lineNum"> 1422 </span> : unsigned int -<span class="lineNum"> 1423 </span> : _Rb_tree_black_count(const _Rb_tree_node_base* __node, -<span class="lineNum"> 1424 </span> : const _Rb_tree_node_base* __root); -<span class="lineNum"> 1425 </span> : -<span class="lineNum"> 1426 </span> : template<typename _Key, typename _Val, typename _KeyOfValue, -<span class="lineNum"> 1427 </span> : typename _Compare, typename _Alloc> -<span class="lineNum"> 1428 </span> : bool -<span class="lineNum"> 1429 </span> : _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const -<span class="lineNum"> 1430 </span> : { -<span class="lineNum"> 1431 </span> : if (_M_impl._M_node_count == 0 || begin() == end()) -<span class="lineNum"> 1432 </span> : return _M_impl._M_node_count == 0 && begin() == end() -<span class="lineNum"> 1433 </span> : && this->_M_impl._M_header._M_left == _M_end() -<span class="lineNum"> 1434 </span> : && this->_M_impl._M_header._M_right == _M_end(); -<span class="lineNum"> 1435 </span> : -<span class="lineNum"> 1436 </span> : unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); -<span class="lineNum"> 1437 </span> : for (const_iterator __it = begin(); __it != end(); ++__it) -<span class="lineNum"> 1438 </span> : { -<span class="lineNum"> 1439 </span> : _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); -<span class="lineNum"> 1440 </span> : _Const_Link_type __L = _S_left(__x); -<span class="lineNum"> 1441 </span> : _Const_Link_type __R = _S_right(__x); -<span class="lineNum"> 1442 </span> : -<span class="lineNum"> 1443 </span> : if (__x->_M_color == _S_red) -<span class="lineNum"> 1444 </span> : if ((__L && __L->_M_color == _S_red) -<span class="lineNum"> 1445 </span> : || (__R && __R->_M_color == _S_red)) -<span class="lineNum"> 1446 </span> : return false; -<span class="lineNum"> 1447 </span> : -<span class="lineNum"> 1448 </span> : if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) -<span class="lineNum"> 1449 </span> : return false; -<span class="lineNum"> 1450 </span> : if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) -<span class="lineNum"> 1451 </span> : return false; -<span class="lineNum"> 1452 </span> : -<span class="lineNum"> 1453 </span> : if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) -<span class="lineNum"> 1454 </span> : return false; -<span class="lineNum"> 1455 </span> : } -<span class="lineNum"> 1456 </span> : -<span class="lineNum"> 1457 </span> : if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) -<span class="lineNum"> 1458 </span> : return false; -<span class="lineNum"> 1459 </span> : if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) -<span class="lineNum"> 1460 </span> : return false; -<span class="lineNum"> 1461 </span> : return true; -<span class="lineNum"> 1462 </span> : } -<span class="lineNum"> 1463 </span> : -<span class="lineNum"> 1464 </span> : _GLIBCXX_END_NAMESPACE -<span class="lineNum"> 1465 </span> : -<span class="lineNum"> 1466 </span> : #endif -</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> |