[1166] | 1 | // Singly-linked list implementation -*- C++ -*-
|
---|
| 2 |
|
---|
| 3 | // Copyright (C) 2001-2021 Free Software Foundation, Inc.
|
---|
| 4 | //
|
---|
| 5 | // This file is part of the GNU ISO C++ Library. This library is free
|
---|
| 6 | // software; you can redistribute it and/or modify it under the
|
---|
| 7 | // terms of the GNU General Public License as published by the
|
---|
| 8 | // Free Software Foundation; either version 3, or (at your option)
|
---|
| 9 | // any later version.
|
---|
| 10 |
|
---|
| 11 | // This library is distributed in the hope that it will be useful,
|
---|
| 12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 14 | // GNU General Public License for more details.
|
---|
| 15 |
|
---|
| 16 | // Under Section 7 of GPL version 3, you are granted additional
|
---|
| 17 | // permissions described in the GCC Runtime Library Exception, version
|
---|
| 18 | // 3.1, as published by the Free Software Foundation.
|
---|
| 19 |
|
---|
| 20 | // You should have received a copy of the GNU General Public License and
|
---|
| 21 | // a copy of the GCC Runtime Library Exception along with this program;
|
---|
| 22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
---|
| 23 | // <http://www.gnu.org/licenses/>.
|
---|
| 24 |
|
---|
| 25 | /*
|
---|
| 26 | * Copyright (c) 1997
|
---|
| 27 | * Silicon Graphics Computer Systems, Inc.
|
---|
| 28 | *
|
---|
| 29 | * Permission to use, copy, modify, distribute and sell this software
|
---|
| 30 | * and its documentation for any purpose is hereby granted without fee,
|
---|
| 31 | * provided that the above copyright notice appear in all copies and
|
---|
| 32 | * that both that copyright notice and this permission notice appear
|
---|
| 33 | * in supporting documentation. Silicon Graphics makes no
|
---|
| 34 | * representations about the suitability of this software for any
|
---|
| 35 | * purpose. It is provided "as is" without express or implied warranty.
|
---|
| 36 | *
|
---|
| 37 | */
|
---|
| 38 |
|
---|
| 39 | /** @file ext/slist
|
---|
| 40 | * This file is a GNU extension to the Standard C++ Library (possibly
|
---|
| 41 | * containing extensions from the HP/SGI STL subset).
|
---|
| 42 | */
|
---|
| 43 |
|
---|
| 44 | #ifndef _SLIST
|
---|
| 45 | #define _SLIST 1
|
---|
| 46 |
|
---|
| 47 | #include <algorithm>
|
---|
| 48 | #include <bits/allocator.h>
|
---|
| 49 | #include <bits/stl_construct.h>
|
---|
| 50 | #include <bits/stl_uninitialized.h>
|
---|
| 51 | #include <bits/concept_check.h>
|
---|
| 52 | #include <ext/alloc_traits.h>
|
---|
| 53 |
|
---|
| 54 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
|
---|
| 55 | {
|
---|
| 56 | _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
---|
| 57 |
|
---|
| 58 | struct _Slist_node_base
|
---|
| 59 | {
|
---|
| 60 | _Slist_node_base* _M_next;
|
---|
| 61 | };
|
---|
| 62 |
|
---|
| 63 | inline _Slist_node_base*
|
---|
| 64 | __slist_make_link(_Slist_node_base* __prev_node,
|
---|
| 65 | _Slist_node_base* __new_node)
|
---|
| 66 | {
|
---|
| 67 | __new_node->_M_next = __prev_node->_M_next;
|
---|
| 68 | __prev_node->_M_next = __new_node;
|
---|
| 69 | return __new_node;
|
---|
| 70 | }
|
---|
| 71 |
|
---|
| 72 | inline _Slist_node_base*
|
---|
| 73 | __slist_previous(_Slist_node_base* __head,
|
---|
| 74 | const _Slist_node_base* __node)
|
---|
| 75 | {
|
---|
| 76 | while (__head && __head->_M_next != __node)
|
---|
| 77 | __head = __head->_M_next;
|
---|
| 78 | return __head;
|
---|
| 79 | }
|
---|
| 80 |
|
---|
| 81 | inline const _Slist_node_base*
|
---|
| 82 | __slist_previous(const _Slist_node_base* __head,
|
---|
| 83 | const _Slist_node_base* __node)
|
---|
| 84 | {
|
---|
| 85 | while (__head && __head->_M_next != __node)
|
---|
| 86 | __head = __head->_M_next;
|
---|
| 87 | return __head;
|
---|
| 88 | }
|
---|
| 89 |
|
---|
| 90 | inline void
|
---|
| 91 | __slist_splice_after(_Slist_node_base* __pos,
|
---|
| 92 | _Slist_node_base* __before_first,
|
---|
| 93 | _Slist_node_base* __before_last)
|
---|
| 94 | {
|
---|
| 95 | if (__pos != __before_first && __pos != __before_last)
|
---|
| 96 | {
|
---|
| 97 | _Slist_node_base* __first = __before_first->_M_next;
|
---|
| 98 | _Slist_node_base* __after = __pos->_M_next;
|
---|
| 99 | __before_first->_M_next = __before_last->_M_next;
|
---|
| 100 | __pos->_M_next = __first;
|
---|
| 101 | __before_last->_M_next = __after;
|
---|
| 102 | }
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | inline void
|
---|
| 106 | __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
|
---|
| 107 | {
|
---|
| 108 | _Slist_node_base* __before_last = __slist_previous(__head, 0);
|
---|
| 109 | if (__before_last != __head)
|
---|
| 110 | {
|
---|
| 111 | _Slist_node_base* __after = __pos->_M_next;
|
---|
| 112 | __pos->_M_next = __head->_M_next;
|
---|
| 113 | __head->_M_next = 0;
|
---|
| 114 | __before_last->_M_next = __after;
|
---|
| 115 | }
|
---|
| 116 | }
|
---|
| 117 |
|
---|
| 118 | inline _Slist_node_base*
|
---|
| 119 | __slist_reverse(_Slist_node_base* __node)
|
---|
| 120 | {
|
---|
| 121 | _Slist_node_base* __result = __node;
|
---|
| 122 | __node = __node->_M_next;
|
---|
| 123 | __result->_M_next = 0;
|
---|
| 124 | while(__node)
|
---|
| 125 | {
|
---|
| 126 | _Slist_node_base* __next = __node->_M_next;
|
---|
| 127 | __node->_M_next = __result;
|
---|
| 128 | __result = __node;
|
---|
| 129 | __node = __next;
|
---|
| 130 | }
|
---|
| 131 | return __result;
|
---|
| 132 | }
|
---|
| 133 |
|
---|
| 134 | inline std::size_t
|
---|
| 135 | __slist_size(_Slist_node_base* __node)
|
---|
| 136 | {
|
---|
| 137 | std::size_t __result = 0;
|
---|
| 138 | for (; __node != 0; __node = __node->_M_next)
|
---|
| 139 | ++__result;
|
---|
| 140 | return __result;
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 | template <class _Tp>
|
---|
| 144 | struct _Slist_node : public _Slist_node_base
|
---|
| 145 | {
|
---|
| 146 | _Tp _M_data;
|
---|
| 147 | };
|
---|
| 148 |
|
---|
| 149 | struct _Slist_iterator_base
|
---|
| 150 | {
|
---|
| 151 | typedef std::size_t size_type;
|
---|
| 152 | typedef std::ptrdiff_t difference_type;
|
---|
| 153 | typedef std::forward_iterator_tag iterator_category;
|
---|
| 154 |
|
---|
| 155 | _Slist_node_base* _M_node;
|
---|
| 156 |
|
---|
| 157 | _Slist_iterator_base(_Slist_node_base* __x)
|
---|
| 158 | : _M_node(__x) {}
|
---|
| 159 |
|
---|
| 160 | void
|
---|
| 161 | _M_incr()
|
---|
| 162 | { _M_node = _M_node->_M_next; }
|
---|
| 163 |
|
---|
| 164 | bool
|
---|
| 165 | operator==(const _Slist_iterator_base& __x) const
|
---|
| 166 | { return _M_node == __x._M_node; }
|
---|
| 167 |
|
---|
| 168 | bool
|
---|
| 169 | operator!=(const _Slist_iterator_base& __x) const
|
---|
| 170 | { return _M_node != __x._M_node; }
|
---|
| 171 | };
|
---|
| 172 |
|
---|
| 173 | template <class _Tp, class _Ref, class _Ptr>
|
---|
| 174 | struct _Slist_iterator : public _Slist_iterator_base
|
---|
| 175 | {
|
---|
| 176 | typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;
|
---|
| 177 | typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
|
---|
| 178 | typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self;
|
---|
| 179 |
|
---|
| 180 | typedef _Tp value_type;
|
---|
| 181 | typedef _Ptr pointer;
|
---|
| 182 | typedef _Ref reference;
|
---|
| 183 | typedef _Slist_node<_Tp> _Node;
|
---|
| 184 |
|
---|
| 185 | explicit
|
---|
| 186 | _Slist_iterator(_Node* __x)
|
---|
| 187 | : _Slist_iterator_base(__x) {}
|
---|
| 188 |
|
---|
| 189 | _Slist_iterator()
|
---|
| 190 | : _Slist_iterator_base(0) {}
|
---|
| 191 |
|
---|
| 192 | _Slist_iterator(const iterator& __x)
|
---|
| 193 | : _Slist_iterator_base(__x._M_node) {}
|
---|
| 194 |
|
---|
| 195 | reference
|
---|
| 196 | operator*() const
|
---|
| 197 | { return ((_Node*) _M_node)->_M_data; }
|
---|
| 198 |
|
---|
| 199 | pointer
|
---|
| 200 | operator->() const
|
---|
| 201 | { return &(operator*()); }
|
---|
| 202 |
|
---|
| 203 | _Self&
|
---|
| 204 | operator++()
|
---|
| 205 | {
|
---|
| 206 | _M_incr();
|
---|
| 207 | return *this;
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 | _Self
|
---|
| 211 | operator++(int)
|
---|
| 212 | {
|
---|
| 213 | _Self __tmp = *this;
|
---|
| 214 | _M_incr();
|
---|
| 215 | return __tmp;
|
---|
| 216 | }
|
---|
| 217 | };
|
---|
| 218 |
|
---|
| 219 | template <class _Tp, class _Alloc>
|
---|
| 220 | struct _Slist_base
|
---|
| 221 | : public __alloc_traits<_Alloc>::template rebind<_Slist_node<_Tp> >::other
|
---|
| 222 | {
|
---|
| 223 | typedef typename __alloc_traits<_Alloc>::template
|
---|
| 224 | rebind<_Slist_node<_Tp> >::other _Node_alloc;
|
---|
| 225 | typedef _Alloc allocator_type;
|
---|
| 226 |
|
---|
| 227 | allocator_type
|
---|
| 228 | get_allocator() const
|
---|
| 229 | { return *static_cast<const _Node_alloc*>(this); }
|
---|
| 230 |
|
---|
| 231 | _Slist_base(const allocator_type& __a)
|
---|
| 232 | : _Node_alloc(__a)
|
---|
| 233 | { this->_M_head._M_next = 0; }
|
---|
| 234 |
|
---|
| 235 | ~_Slist_base()
|
---|
| 236 | { _M_erase_after(&this->_M_head, 0); }
|
---|
| 237 |
|
---|
| 238 | protected:
|
---|
| 239 | _Slist_node_base _M_head;
|
---|
| 240 |
|
---|
| 241 | _Slist_node<_Tp>*
|
---|
| 242 | _M_get_node()
|
---|
| 243 | { return _Node_alloc::allocate(1); }
|
---|
| 244 |
|
---|
| 245 | void
|
---|
| 246 | _M_put_node(_Slist_node<_Tp>* __p)
|
---|
| 247 | { _Node_alloc::deallocate(__p, 1); }
|
---|
| 248 |
|
---|
| 249 | protected:
|
---|
| 250 | _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
|
---|
| 251 | {
|
---|
| 252 | _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
|
---|
| 253 | _Slist_node_base* __next_next = __next->_M_next;
|
---|
| 254 | __pos->_M_next = __next_next;
|
---|
| 255 | allocator_type __a = get_allocator();
|
---|
| 256 | __alloc_traits<allocator_type>::destroy(__a, &__next->_M_data);
|
---|
| 257 | _M_put_node(__next);
|
---|
| 258 | return __next_next;
|
---|
| 259 | }
|
---|
| 260 | _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
|
---|
| 261 | };
|
---|
| 262 |
|
---|
| 263 | template <class _Tp, class _Alloc>
|
---|
| 264 | _Slist_node_base*
|
---|
| 265 | _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
|
---|
| 266 | _Slist_node_base* __last_node)
|
---|
| 267 | {
|
---|
| 268 | _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
|
---|
| 269 | while (__cur != __last_node)
|
---|
| 270 | {
|
---|
| 271 | _Slist_node<_Tp>* __tmp = __cur;
|
---|
| 272 | __cur = (_Slist_node<_Tp>*) __cur->_M_next;
|
---|
| 273 | allocator_type __a = get_allocator();
|
---|
| 274 | __alloc_traits<allocator_type>::destroy(__a, &__tmp->_M_data);
|
---|
| 275 | _M_put_node(__tmp);
|
---|
| 276 | }
|
---|
| 277 | __before_first->_M_next = __last_node;
|
---|
| 278 | return __last_node;
|
---|
| 279 | }
|
---|
| 280 |
|
---|
| 281 | /**
|
---|
| 282 | * This is an SGI extension.
|
---|
| 283 | * @ingroup SGIextensions
|
---|
| 284 | * @doctodo
|
---|
| 285 | */
|
---|
| 286 | template <class _Tp, class _Alloc = std::allocator<_Tp> >
|
---|
| 287 | class slist : private _Slist_base<_Tp,_Alloc>
|
---|
| 288 | {
|
---|
| 289 | // concept requirements
|
---|
| 290 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
|
---|
| 291 |
|
---|
| 292 | private:
|
---|
| 293 | typedef _Slist_base<_Tp,_Alloc> _Base;
|
---|
| 294 |
|
---|
| 295 | public:
|
---|
| 296 | typedef _Tp value_type;
|
---|
| 297 | typedef value_type* pointer;
|
---|
| 298 | typedef const value_type* const_pointer;
|
---|
| 299 | typedef value_type& reference;
|
---|
| 300 | typedef const value_type& const_reference;
|
---|
| 301 | typedef std::size_t size_type;
|
---|
| 302 | typedef std::ptrdiff_t difference_type;
|
---|
| 303 |
|
---|
| 304 | typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;
|
---|
| 305 | typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
|
---|
| 306 |
|
---|
| 307 | typedef typename _Base::allocator_type allocator_type;
|
---|
| 308 |
|
---|
| 309 | allocator_type
|
---|
| 310 | get_allocator() const
|
---|
| 311 | { return _Base::get_allocator(); }
|
---|
| 312 |
|
---|
| 313 | private:
|
---|
| 314 | typedef _Slist_node<_Tp> _Node;
|
---|
| 315 | typedef _Slist_node_base _Node_base;
|
---|
| 316 | typedef _Slist_iterator_base _Iterator_base;
|
---|
| 317 |
|
---|
| 318 | _Node*
|
---|
| 319 | _M_create_node(const value_type& __x)
|
---|
| 320 | {
|
---|
| 321 | _Node* __node = this->_M_get_node();
|
---|
| 322 | __try
|
---|
| 323 | {
|
---|
| 324 | allocator_type __a = get_allocator();
|
---|
| 325 | __alloc_traits<allocator_type>::construct(__a, &__node->_M_data,
|
---|
| 326 | __x);
|
---|
| 327 | __node->_M_next = 0;
|
---|
| 328 | }
|
---|
| 329 | __catch(...)
|
---|
| 330 | {
|
---|
| 331 | this->_M_put_node(__node);
|
---|
| 332 | __throw_exception_again;
|
---|
| 333 | }
|
---|
| 334 | return __node;
|
---|
| 335 | }
|
---|
| 336 |
|
---|
| 337 | _Node*
|
---|
| 338 | _M_create_node()
|
---|
| 339 | {
|
---|
| 340 | _Node* __node = this->_M_get_node();
|
---|
| 341 | __try
|
---|
| 342 | {
|
---|
| 343 | allocator_type __a = get_allocator();
|
---|
| 344 | __alloc_traits<allocator_type>::construct(__a, &__node->_M_data,
|
---|
| 345 | value_type());
|
---|
| 346 | __node->_M_next = 0;
|
---|
| 347 | }
|
---|
| 348 | __catch(...)
|
---|
| 349 | {
|
---|
| 350 | this->_M_put_node(__node);
|
---|
| 351 | __throw_exception_again;
|
---|
| 352 | }
|
---|
| 353 | return __node;
|
---|
| 354 | }
|
---|
| 355 |
|
---|
| 356 | public:
|
---|
| 357 | explicit
|
---|
| 358 | slist(const allocator_type& __a = allocator_type())
|
---|
| 359 | : _Base(__a) {}
|
---|
| 360 |
|
---|
| 361 | slist(size_type __n, const value_type& __x,
|
---|
| 362 | const allocator_type& __a = allocator_type())
|
---|
| 363 | : _Base(__a)
|
---|
| 364 | { _M_insert_after_fill(&this->_M_head, __n, __x); }
|
---|
| 365 |
|
---|
| 366 | explicit
|
---|
| 367 | slist(size_type __n)
|
---|
| 368 | : _Base(allocator_type())
|
---|
| 369 | { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
|
---|
| 370 |
|
---|
| 371 | // We don't need any dispatching tricks here, because
|
---|
| 372 | // _M_insert_after_range already does them.
|
---|
| 373 | template <class _InputIterator>
|
---|
| 374 | slist(_InputIterator __first, _InputIterator __last,
|
---|
| 375 | const allocator_type& __a = allocator_type())
|
---|
| 376 | : _Base(__a)
|
---|
| 377 | { _M_insert_after_range(&this->_M_head, __first, __last); }
|
---|
| 378 |
|
---|
| 379 | slist(const slist& __x)
|
---|
| 380 | : _Base(__x.get_allocator())
|
---|
| 381 | { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
|
---|
| 382 |
|
---|
| 383 | slist&
|
---|
| 384 | operator= (const slist& __x);
|
---|
| 385 |
|
---|
| 386 | ~slist() {}
|
---|
| 387 |
|
---|
| 388 | public:
|
---|
| 389 | // assign(), a generalized assignment member function. Two
|
---|
| 390 | // versions: one that takes a count, and one that takes a range.
|
---|
| 391 | // The range version is a member template, so we dispatch on whether
|
---|
| 392 | // or not the type is an integer.
|
---|
| 393 |
|
---|
| 394 | void
|
---|
| 395 | assign(size_type __n, const _Tp& __val)
|
---|
| 396 | { _M_fill_assign(__n, __val); }
|
---|
| 397 |
|
---|
| 398 | void
|
---|
| 399 | _M_fill_assign(size_type __n, const _Tp& __val);
|
---|
| 400 |
|
---|
| 401 | template <class _InputIterator>
|
---|
| 402 | void
|
---|
| 403 | assign(_InputIterator __first, _InputIterator __last)
|
---|
| 404 | {
|
---|
| 405 | typedef typename std::__is_integer<_InputIterator>::__type _Integral;
|
---|
| 406 | _M_assign_dispatch(__first, __last, _Integral());
|
---|
| 407 | }
|
---|
| 408 |
|
---|
| 409 | template <class _Integer>
|
---|
| 410 | void
|
---|
| 411 | _M_assign_dispatch(_Integer __n, _Integer __val, std::__true_type)
|
---|
| 412 | { _M_fill_assign((size_type) __n, (_Tp) __val); }
|
---|
| 413 |
|
---|
| 414 | template <class _InputIterator>
|
---|
| 415 | void
|
---|
| 416 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
|
---|
| 417 | std::__false_type);
|
---|
| 418 |
|
---|
| 419 | public:
|
---|
| 420 |
|
---|
| 421 | iterator
|
---|
| 422 | begin()
|
---|
| 423 | { return iterator((_Node*)this->_M_head._M_next); }
|
---|
| 424 |
|
---|
| 425 | const_iterator
|
---|
| 426 | begin() const
|
---|
| 427 | { return const_iterator((_Node*)this->_M_head._M_next);}
|
---|
| 428 |
|
---|
| 429 | iterator
|
---|
| 430 | end()
|
---|
| 431 | { return iterator(0); }
|
---|
| 432 |
|
---|
| 433 | const_iterator
|
---|
| 434 | end() const
|
---|
| 435 | { return const_iterator(0); }
|
---|
| 436 |
|
---|
| 437 | // Experimental new feature: before_begin() returns a
|
---|
| 438 | // non-dereferenceable iterator that, when incremented, yields
|
---|
| 439 | // begin(). This iterator may be used as the argument to
|
---|
| 440 | // insert_after, erase_after, etc. Note that even for an empty
|
---|
| 441 | // slist, before_begin() is not the same iterator as end(). It
|
---|
| 442 | // is always necessary to increment before_begin() at least once to
|
---|
| 443 | // obtain end().
|
---|
| 444 | iterator
|
---|
| 445 | before_begin()
|
---|
| 446 | { return iterator((_Node*) &this->_M_head); }
|
---|
| 447 |
|
---|
| 448 | const_iterator
|
---|
| 449 | before_begin() const
|
---|
| 450 | { return const_iterator((_Node*) &this->_M_head); }
|
---|
| 451 |
|
---|
| 452 | size_type
|
---|
| 453 | size() const
|
---|
| 454 | { return __slist_size(this->_M_head._M_next); }
|
---|
| 455 |
|
---|
| 456 | size_type
|
---|
| 457 | max_size() const
|
---|
| 458 | { return size_type(-1); }
|
---|
| 459 |
|
---|
| 460 | _GLIBCXX_NODISCARD bool
|
---|
| 461 | empty() const
|
---|
| 462 | { return this->_M_head._M_next == 0; }
|
---|
| 463 |
|
---|
| 464 | void
|
---|
| 465 | swap(slist& __x)
|
---|
| 466 | { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
|
---|
| 467 |
|
---|
| 468 | public:
|
---|
| 469 |
|
---|
| 470 | reference
|
---|
| 471 | front()
|
---|
| 472 | { return ((_Node*) this->_M_head._M_next)->_M_data; }
|
---|
| 473 |
|
---|
| 474 | const_reference
|
---|
| 475 | front() const
|
---|
| 476 | { return ((_Node*) this->_M_head._M_next)->_M_data; }
|
---|
| 477 |
|
---|
| 478 | void
|
---|
| 479 | push_front(const value_type& __x)
|
---|
| 480 | { __slist_make_link(&this->_M_head, _M_create_node(__x)); }
|
---|
| 481 |
|
---|
| 482 | void
|
---|
| 483 | push_front()
|
---|
| 484 | { __slist_make_link(&this->_M_head, _M_create_node()); }
|
---|
| 485 |
|
---|
| 486 | void
|
---|
| 487 | pop_front()
|
---|
| 488 | {
|
---|
| 489 | _Node* __node = (_Node*) this->_M_head._M_next;
|
---|
| 490 | this->_M_head._M_next = __node->_M_next;
|
---|
| 491 | allocator_type __a = get_allocator();
|
---|
| 492 | __alloc_traits<allocator_type>::destroy(__a, &__node->_M_data);
|
---|
| 493 | this->_M_put_node(__node);
|
---|
| 494 | }
|
---|
| 495 |
|
---|
| 496 | iterator
|
---|
| 497 | previous(const_iterator __pos)
|
---|
| 498 | { return iterator((_Node*) __slist_previous(&this->_M_head,
|
---|
| 499 | __pos._M_node)); }
|
---|
| 500 |
|
---|
| 501 | const_iterator
|
---|
| 502 | previous(const_iterator __pos) const
|
---|
| 503 | { return const_iterator((_Node*) __slist_previous(&this->_M_head,
|
---|
| 504 | __pos._M_node)); }
|
---|
| 505 |
|
---|
| 506 | private:
|
---|
| 507 | _Node*
|
---|
| 508 | _M_insert_after(_Node_base* __pos, const value_type& __x)
|
---|
| 509 | { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); }
|
---|
| 510 |
|
---|
| 511 | _Node*
|
---|
| 512 | _M_insert_after(_Node_base* __pos)
|
---|
| 513 | { return (_Node*) (__slist_make_link(__pos, _M_create_node())); }
|
---|
| 514 |
|
---|
| 515 | void
|
---|
| 516 | _M_insert_after_fill(_Node_base* __pos,
|
---|
| 517 | size_type __n, const value_type& __x)
|
---|
| 518 | {
|
---|
| 519 | for (size_type __i = 0; __i < __n; ++__i)
|
---|
| 520 | __pos = __slist_make_link(__pos, _M_create_node(__x));
|
---|
| 521 | }
|
---|
| 522 |
|
---|
| 523 | // Check whether it's an integral type. If so, it's not an iterator.
|
---|
| 524 | template <class _InIterator>
|
---|
| 525 | void
|
---|
| 526 | _M_insert_after_range(_Node_base* __pos,
|
---|
| 527 | _InIterator __first, _InIterator __last)
|
---|
| 528 | {
|
---|
| 529 | typedef typename std::__is_integer<_InIterator>::__type _Integral;
|
---|
| 530 | _M_insert_after_range(__pos, __first, __last, _Integral());
|
---|
| 531 | }
|
---|
| 532 |
|
---|
| 533 | template <class _Integer>
|
---|
| 534 | void
|
---|
| 535 | _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
|
---|
| 536 | std::__true_type)
|
---|
| 537 | { _M_insert_after_fill(__pos, __n, __x); }
|
---|
| 538 |
|
---|
| 539 | template <class _InIterator>
|
---|
| 540 | void
|
---|
| 541 | _M_insert_after_range(_Node_base* __pos,
|
---|
| 542 | _InIterator __first, _InIterator __last,
|
---|
| 543 | std::__false_type)
|
---|
| 544 | {
|
---|
| 545 | while (__first != __last)
|
---|
| 546 | {
|
---|
| 547 | __pos = __slist_make_link(__pos, _M_create_node(*__first));
|
---|
| 548 | ++__first;
|
---|
| 549 | }
|
---|
| 550 | }
|
---|
| 551 |
|
---|
| 552 | public:
|
---|
| 553 | iterator
|
---|
| 554 | insert_after(iterator __pos, const value_type& __x)
|
---|
| 555 | { return iterator(_M_insert_after(__pos._M_node, __x)); }
|
---|
| 556 |
|
---|
| 557 | iterator
|
---|
| 558 | insert_after(iterator __pos)
|
---|
| 559 | { return insert_after(__pos, value_type()); }
|
---|
| 560 |
|
---|
| 561 | void
|
---|
| 562 | insert_after(iterator __pos, size_type __n, const value_type& __x)
|
---|
| 563 | { _M_insert_after_fill(__pos._M_node, __n, __x); }
|
---|
| 564 |
|
---|
| 565 | // We don't need any dispatching tricks here, because
|
---|
| 566 | // _M_insert_after_range already does them.
|
---|
| 567 | template <class _InIterator>
|
---|
| 568 | void
|
---|
| 569 | insert_after(iterator __pos, _InIterator __first, _InIterator __last)
|
---|
| 570 | { _M_insert_after_range(__pos._M_node, __first, __last); }
|
---|
| 571 |
|
---|
| 572 | iterator
|
---|
| 573 | insert(iterator __pos, const value_type& __x)
|
---|
| 574 | { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
|
---|
| 575 | __pos._M_node),
|
---|
| 576 | __x)); }
|
---|
| 577 |
|
---|
| 578 | iterator
|
---|
| 579 | insert(iterator __pos)
|
---|
| 580 | { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
|
---|
| 581 | __pos._M_node),
|
---|
| 582 | value_type())); }
|
---|
| 583 |
|
---|
| 584 | void
|
---|
| 585 | insert(iterator __pos, size_type __n, const value_type& __x)
|
---|
| 586 | { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
|
---|
| 587 | __n, __x); }
|
---|
| 588 |
|
---|
| 589 | // We don't need any dispatching tricks here, because
|
---|
| 590 | // _M_insert_after_range already does them.
|
---|
| 591 | template <class _InIterator>
|
---|
| 592 | void
|
---|
| 593 | insert(iterator __pos, _InIterator __first, _InIterator __last)
|
---|
| 594 | { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),
|
---|
| 595 | __first, __last); }
|
---|
| 596 |
|
---|
| 597 | public:
|
---|
| 598 | iterator
|
---|
| 599 | erase_after(iterator __pos)
|
---|
| 600 | { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }
|
---|
| 601 |
|
---|
| 602 | iterator
|
---|
| 603 | erase_after(iterator __before_first, iterator __last)
|
---|
| 604 | {
|
---|
| 605 | return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
|
---|
| 606 | __last._M_node));
|
---|
| 607 | }
|
---|
| 608 |
|
---|
| 609 | iterator
|
---|
| 610 | erase(iterator __pos)
|
---|
| 611 | {
|
---|
| 612 | return iterator((_Node*) this->_M_erase_after
|
---|
| 613 | (__slist_previous(&this->_M_head, __pos._M_node)));
|
---|
| 614 | }
|
---|
| 615 |
|
---|
| 616 | iterator
|
---|
| 617 | erase(iterator __first, iterator __last)
|
---|
| 618 | {
|
---|
| 619 | return iterator((_Node*) this->_M_erase_after
|
---|
| 620 | (__slist_previous(&this->_M_head, __first._M_node),
|
---|
| 621 | __last._M_node));
|
---|
| 622 | }
|
---|
| 623 |
|
---|
| 624 | void
|
---|
| 625 | resize(size_type new_size, const _Tp& __x);
|
---|
| 626 |
|
---|
| 627 | void
|
---|
| 628 | resize(size_type new_size)
|
---|
| 629 | { resize(new_size, _Tp()); }
|
---|
| 630 |
|
---|
| 631 | void
|
---|
| 632 | clear()
|
---|
| 633 | { this->_M_erase_after(&this->_M_head, 0); }
|
---|
| 634 |
|
---|
| 635 | public:
|
---|
| 636 | // Moves the range [__before_first + 1, __before_last + 1) to *this,
|
---|
| 637 | // inserting it immediately after __pos. This is constant time.
|
---|
| 638 | void
|
---|
| 639 | splice_after(iterator __pos,
|
---|
| 640 | iterator __before_first, iterator __before_last)
|
---|
| 641 | {
|
---|
| 642 | if (__before_first != __before_last)
|
---|
| 643 | __slist_splice_after(__pos._M_node, __before_first._M_node,
|
---|
| 644 | __before_last._M_node);
|
---|
| 645 | }
|
---|
| 646 |
|
---|
| 647 | // Moves the element that follows __prev to *this, inserting it
|
---|
| 648 | // immediately after __pos. This is constant time.
|
---|
| 649 | void
|
---|
| 650 | splice_after(iterator __pos, iterator __prev)
|
---|
| 651 | { __slist_splice_after(__pos._M_node,
|
---|
| 652 | __prev._M_node, __prev._M_node->_M_next); }
|
---|
| 653 |
|
---|
| 654 | // Removes all of the elements from the list __x to *this, inserting
|
---|
| 655 | // them immediately after __pos. __x must not be *this. Complexity:
|
---|
| 656 | // linear in __x.size().
|
---|
| 657 | void
|
---|
| 658 | splice_after(iterator __pos, slist& __x)
|
---|
| 659 | { __slist_splice_after(__pos._M_node, &__x._M_head); }
|
---|
| 660 |
|
---|
| 661 | // Linear in distance(begin(), __pos), and linear in __x.size().
|
---|
| 662 | void
|
---|
| 663 | splice(iterator __pos, slist& __x)
|
---|
| 664 | {
|
---|
| 665 | if (__x._M_head._M_next)
|
---|
| 666 | __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
|
---|
| 667 | &__x._M_head,
|
---|
| 668 | __slist_previous(&__x._M_head, 0)); }
|
---|
| 669 |
|
---|
| 670 | // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
|
---|
| 671 | void
|
---|
| 672 | splice(iterator __pos, slist& __x, iterator __i)
|
---|
| 673 | { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
|
---|
| 674 | __slist_previous(&__x._M_head, __i._M_node),
|
---|
| 675 | __i._M_node); }
|
---|
| 676 |
|
---|
| 677 | // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
|
---|
| 678 | // and in distance(__first, __last).
|
---|
| 679 | void
|
---|
| 680 | splice(iterator __pos, slist& __x, iterator __first, iterator __last)
|
---|
| 681 | {
|
---|
| 682 | if (__first != __last)
|
---|
| 683 | __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
|
---|
| 684 | __slist_previous(&__x._M_head, __first._M_node),
|
---|
| 685 | __slist_previous(__first._M_node,
|
---|
| 686 | __last._M_node));
|
---|
| 687 | }
|
---|
| 688 |
|
---|
| 689 | public:
|
---|
| 690 | void
|
---|
| 691 | reverse()
|
---|
| 692 | {
|
---|
| 693 | if (this->_M_head._M_next)
|
---|
| 694 | this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
|
---|
| 695 | }
|
---|
| 696 |
|
---|
| 697 | void
|
---|
| 698 | remove(const _Tp& __val);
|
---|
| 699 |
|
---|
| 700 | void
|
---|
| 701 | unique();
|
---|
| 702 |
|
---|
| 703 | void
|
---|
| 704 | merge(slist& __x);
|
---|
| 705 |
|
---|
| 706 | void
|
---|
| 707 | sort();
|
---|
| 708 |
|
---|
| 709 | template <class _Predicate>
|
---|
| 710 | void
|
---|
| 711 | remove_if(_Predicate __pred);
|
---|
| 712 |
|
---|
| 713 | template <class _BinaryPredicate>
|
---|
| 714 | void
|
---|
| 715 | unique(_BinaryPredicate __pred);
|
---|
| 716 |
|
---|
| 717 | template <class _StrictWeakOrdering>
|
---|
| 718 | void
|
---|
| 719 | merge(slist&, _StrictWeakOrdering);
|
---|
| 720 |
|
---|
| 721 | template <class _StrictWeakOrdering>
|
---|
| 722 | void
|
---|
| 723 | sort(_StrictWeakOrdering __comp);
|
---|
| 724 | };
|
---|
| 725 |
|
---|
| 726 | template <class _Tp, class _Alloc>
|
---|
| 727 | slist<_Tp, _Alloc>&
|
---|
| 728 | slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x)
|
---|
| 729 | {
|
---|
| 730 | if (&__x != this)
|
---|
| 731 | {
|
---|
| 732 | _Node_base* __p1 = &this->_M_head;
|
---|
| 733 | _Node* __n1 = (_Node*) this->_M_head._M_next;
|
---|
| 734 | const _Node* __n2 = (const _Node*) __x._M_head._M_next;
|
---|
| 735 | while (__n1 && __n2)
|
---|
| 736 | {
|
---|
| 737 | __n1->_M_data = __n2->_M_data;
|
---|
| 738 | __p1 = __n1;
|
---|
| 739 | __n1 = (_Node*) __n1->_M_next;
|
---|
| 740 | __n2 = (const _Node*) __n2->_M_next;
|
---|
| 741 | }
|
---|
| 742 | if (__n2 == 0)
|
---|
| 743 | this->_M_erase_after(__p1, 0);
|
---|
| 744 | else
|
---|
| 745 | _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
|
---|
| 746 | const_iterator(0));
|
---|
| 747 | }
|
---|
| 748 | return *this;
|
---|
| 749 | }
|
---|
| 750 |
|
---|
| 751 | template <class _Tp, class _Alloc>
|
---|
| 752 | void
|
---|
| 753 | slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val)
|
---|
| 754 | {
|
---|
| 755 | _Node_base* __prev = &this->_M_head;
|
---|
| 756 | _Node* __node = (_Node*) this->_M_head._M_next;
|
---|
| 757 | for (; __node != 0 && __n > 0; --__n)
|
---|
| 758 | {
|
---|
| 759 | __node->_M_data = __val;
|
---|
| 760 | __prev = __node;
|
---|
| 761 | __node = (_Node*) __node->_M_next;
|
---|
| 762 | }
|
---|
| 763 | if (__n > 0)
|
---|
| 764 | _M_insert_after_fill(__prev, __n, __val);
|
---|
| 765 | else
|
---|
| 766 | this->_M_erase_after(__prev, 0);
|
---|
| 767 | }
|
---|
| 768 |
|
---|
| 769 | template <class _Tp, class _Alloc>
|
---|
| 770 | template <class _InputIterator>
|
---|
| 771 | void
|
---|
| 772 | slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first,
|
---|
| 773 | _InputIterator __last,
|
---|
| 774 | std::__false_type)
|
---|
| 775 | {
|
---|
| 776 | _Node_base* __prev = &this->_M_head;
|
---|
| 777 | _Node* __node = (_Node*) this->_M_head._M_next;
|
---|
| 778 | while (__node != 0 && __first != __last)
|
---|
| 779 | {
|
---|
| 780 | __node->_M_data = *__first;
|
---|
| 781 | __prev = __node;
|
---|
| 782 | __node = (_Node*) __node->_M_next;
|
---|
| 783 | ++__first;
|
---|
| 784 | }
|
---|
| 785 | if (__first != __last)
|
---|
| 786 | _M_insert_after_range(__prev, __first, __last);
|
---|
| 787 | else
|
---|
| 788 | this->_M_erase_after(__prev, 0);
|
---|
| 789 | }
|
---|
| 790 |
|
---|
| 791 | template <class _Tp, class _Alloc>
|
---|
| 792 | inline bool
|
---|
| 793 | operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 794 | {
|
---|
| 795 | typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
|
---|
| 796 | const_iterator __end1 = _SL1.end();
|
---|
| 797 | const_iterator __end2 = _SL2.end();
|
---|
| 798 |
|
---|
| 799 | const_iterator __i1 = _SL1.begin();
|
---|
| 800 | const_iterator __i2 = _SL2.begin();
|
---|
| 801 | while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
|
---|
| 802 | {
|
---|
| 803 | ++__i1;
|
---|
| 804 | ++__i2;
|
---|
| 805 | }
|
---|
| 806 | return __i1 == __end1 && __i2 == __end2;
|
---|
| 807 | }
|
---|
| 808 |
|
---|
| 809 |
|
---|
| 810 | template <class _Tp, class _Alloc>
|
---|
| 811 | inline bool
|
---|
| 812 | operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 813 | { return std::lexicographical_compare(_SL1.begin(), _SL1.end(),
|
---|
| 814 | _SL2.begin(), _SL2.end()); }
|
---|
| 815 |
|
---|
| 816 | template <class _Tp, class _Alloc>
|
---|
| 817 | inline bool
|
---|
| 818 | operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 819 | { return !(_SL1 == _SL2); }
|
---|
| 820 |
|
---|
| 821 | template <class _Tp, class _Alloc>
|
---|
| 822 | inline bool
|
---|
| 823 | operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 824 | { return _SL2 < _SL1; }
|
---|
| 825 |
|
---|
| 826 | template <class _Tp, class _Alloc>
|
---|
| 827 | inline bool
|
---|
| 828 | operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 829 | { return !(_SL2 < _SL1); }
|
---|
| 830 |
|
---|
| 831 | template <class _Tp, class _Alloc>
|
---|
| 832 | inline bool
|
---|
| 833 | operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2)
|
---|
| 834 | { return !(_SL1 < _SL2); }
|
---|
| 835 |
|
---|
| 836 | template <class _Tp, class _Alloc>
|
---|
| 837 | inline void
|
---|
| 838 | swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y)
|
---|
| 839 | { __x.swap(__y); }
|
---|
| 840 |
|
---|
| 841 | template <class _Tp, class _Alloc>
|
---|
| 842 | void
|
---|
| 843 | slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x)
|
---|
| 844 | {
|
---|
| 845 | _Node_base* __cur = &this->_M_head;
|
---|
| 846 | while (__cur->_M_next != 0 && __len > 0)
|
---|
| 847 | {
|
---|
| 848 | --__len;
|
---|
| 849 | __cur = __cur->_M_next;
|
---|
| 850 | }
|
---|
| 851 | if (__cur->_M_next)
|
---|
| 852 | this->_M_erase_after(__cur, 0);
|
---|
| 853 | else
|
---|
| 854 | _M_insert_after_fill(__cur, __len, __x);
|
---|
| 855 | }
|
---|
| 856 |
|
---|
| 857 | template <class _Tp, class _Alloc>
|
---|
| 858 | void
|
---|
| 859 | slist<_Tp, _Alloc>::remove(const _Tp& __val)
|
---|
| 860 | {
|
---|
| 861 | _Node_base* __cur = &this->_M_head;
|
---|
| 862 | while (__cur && __cur->_M_next)
|
---|
| 863 | {
|
---|
| 864 | if (((_Node*) __cur->_M_next)->_M_data == __val)
|
---|
| 865 | this->_M_erase_after(__cur);
|
---|
| 866 | else
|
---|
| 867 | __cur = __cur->_M_next;
|
---|
| 868 | }
|
---|
| 869 | }
|
---|
| 870 |
|
---|
| 871 | template <class _Tp, class _Alloc>
|
---|
| 872 | void
|
---|
| 873 | slist<_Tp, _Alloc>::unique()
|
---|
| 874 | {
|
---|
| 875 | _Node_base* __cur = this->_M_head._M_next;
|
---|
| 876 | if (__cur)
|
---|
| 877 | {
|
---|
| 878 | while (__cur->_M_next)
|
---|
| 879 | {
|
---|
| 880 | if (((_Node*)__cur)->_M_data
|
---|
| 881 | == ((_Node*)(__cur->_M_next))->_M_data)
|
---|
| 882 | this->_M_erase_after(__cur);
|
---|
| 883 | else
|
---|
| 884 | __cur = __cur->_M_next;
|
---|
| 885 | }
|
---|
| 886 | }
|
---|
| 887 | }
|
---|
| 888 |
|
---|
| 889 | template <class _Tp, class _Alloc>
|
---|
| 890 | void
|
---|
| 891 | slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x)
|
---|
| 892 | {
|
---|
| 893 | _Node_base* __n1 = &this->_M_head;
|
---|
| 894 | while (__n1->_M_next && __x._M_head._M_next)
|
---|
| 895 | {
|
---|
| 896 | if (((_Node*) __x._M_head._M_next)->_M_data
|
---|
| 897 | < ((_Node*) __n1->_M_next)->_M_data)
|
---|
| 898 | __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
|
---|
| 899 | __n1 = __n1->_M_next;
|
---|
| 900 | }
|
---|
| 901 | if (__x._M_head._M_next)
|
---|
| 902 | {
|
---|
| 903 | __n1->_M_next = __x._M_head._M_next;
|
---|
| 904 | __x._M_head._M_next = 0;
|
---|
| 905 | }
|
---|
| 906 | }
|
---|
| 907 |
|
---|
| 908 | template <class _Tp, class _Alloc>
|
---|
| 909 | void
|
---|
| 910 | slist<_Tp, _Alloc>::sort()
|
---|
| 911 | {
|
---|
| 912 | if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
|
---|
| 913 | {
|
---|
| 914 | slist __carry;
|
---|
| 915 | slist __counter[64];
|
---|
| 916 | int __fill = 0;
|
---|
| 917 | while (!empty())
|
---|
| 918 | {
|
---|
| 919 | __slist_splice_after(&__carry._M_head,
|
---|
| 920 | &this->_M_head, this->_M_head._M_next);
|
---|
| 921 | int __i = 0;
|
---|
| 922 | while (__i < __fill && !__counter[__i].empty())
|
---|
| 923 | {
|
---|
| 924 | __counter[__i].merge(__carry);
|
---|
| 925 | __carry.swap(__counter[__i]);
|
---|
| 926 | ++__i;
|
---|
| 927 | }
|
---|
| 928 | __carry.swap(__counter[__i]);
|
---|
| 929 | if (__i == __fill)
|
---|
| 930 | ++__fill;
|
---|
| 931 | }
|
---|
| 932 |
|
---|
| 933 | for (int __i = 1; __i < __fill; ++__i)
|
---|
| 934 | __counter[__i].merge(__counter[__i-1]);
|
---|
| 935 | this->swap(__counter[__fill-1]);
|
---|
| 936 | }
|
---|
| 937 | }
|
---|
| 938 |
|
---|
| 939 | template <class _Tp, class _Alloc>
|
---|
| 940 | template <class _Predicate>
|
---|
| 941 | void slist<_Tp, _Alloc>::remove_if(_Predicate __pred)
|
---|
| 942 | {
|
---|
| 943 | _Node_base* __cur = &this->_M_head;
|
---|
| 944 | while (__cur->_M_next)
|
---|
| 945 | {
|
---|
| 946 | if (__pred(((_Node*) __cur->_M_next)->_M_data))
|
---|
| 947 | this->_M_erase_after(__cur);
|
---|
| 948 | else
|
---|
| 949 | __cur = __cur->_M_next;
|
---|
| 950 | }
|
---|
| 951 | }
|
---|
| 952 |
|
---|
| 953 | template <class _Tp, class _Alloc>
|
---|
| 954 | template <class _BinaryPredicate>
|
---|
| 955 | void
|
---|
| 956 | slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred)
|
---|
| 957 | {
|
---|
| 958 | _Node* __cur = (_Node*) this->_M_head._M_next;
|
---|
| 959 | if (__cur)
|
---|
| 960 | {
|
---|
| 961 | while (__cur->_M_next)
|
---|
| 962 | {
|
---|
| 963 | if (__pred(((_Node*)__cur)->_M_data,
|
---|
| 964 | ((_Node*)(__cur->_M_next))->_M_data))
|
---|
| 965 | this->_M_erase_after(__cur);
|
---|
| 966 | else
|
---|
| 967 | __cur = (_Node*) __cur->_M_next;
|
---|
| 968 | }
|
---|
| 969 | }
|
---|
| 970 | }
|
---|
| 971 |
|
---|
| 972 | template <class _Tp, class _Alloc>
|
---|
| 973 | template <class _StrictWeakOrdering>
|
---|
| 974 | void
|
---|
| 975 | slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x,
|
---|
| 976 | _StrictWeakOrdering __comp)
|
---|
| 977 | {
|
---|
| 978 | _Node_base* __n1 = &this->_M_head;
|
---|
| 979 | while (__n1->_M_next && __x._M_head._M_next)
|
---|
| 980 | {
|
---|
| 981 | if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
|
---|
| 982 | ((_Node*) __n1->_M_next)->_M_data))
|
---|
| 983 | __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
|
---|
| 984 | __n1 = __n1->_M_next;
|
---|
| 985 | }
|
---|
| 986 | if (__x._M_head._M_next)
|
---|
| 987 | {
|
---|
| 988 | __n1->_M_next = __x._M_head._M_next;
|
---|
| 989 | __x._M_head._M_next = 0;
|
---|
| 990 | }
|
---|
| 991 | }
|
---|
| 992 |
|
---|
| 993 | template <class _Tp, class _Alloc>
|
---|
| 994 | template <class _StrictWeakOrdering>
|
---|
| 995 | void
|
---|
| 996 | slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
|
---|
| 997 | {
|
---|
| 998 | if (this->_M_head._M_next && this->_M_head._M_next->_M_next)
|
---|
| 999 | {
|
---|
| 1000 | slist __carry;
|
---|
| 1001 | slist __counter[64];
|
---|
| 1002 | int __fill = 0;
|
---|
| 1003 | while (!empty())
|
---|
| 1004 | {
|
---|
| 1005 | __slist_splice_after(&__carry._M_head,
|
---|
| 1006 | &this->_M_head, this->_M_head._M_next);
|
---|
| 1007 | int __i = 0;
|
---|
| 1008 | while (__i < __fill && !__counter[__i].empty())
|
---|
| 1009 | {
|
---|
| 1010 | __counter[__i].merge(__carry, __comp);
|
---|
| 1011 | __carry.swap(__counter[__i]);
|
---|
| 1012 | ++__i;
|
---|
| 1013 | }
|
---|
| 1014 | __carry.swap(__counter[__i]);
|
---|
| 1015 | if (__i == __fill)
|
---|
| 1016 | ++__fill;
|
---|
| 1017 | }
|
---|
| 1018 |
|
---|
| 1019 | for (int __i = 1; __i < __fill; ++__i)
|
---|
| 1020 | __counter[__i].merge(__counter[__i-1], __comp);
|
---|
| 1021 | this->swap(__counter[__fill-1]);
|
---|
| 1022 | }
|
---|
| 1023 | }
|
---|
| 1024 |
|
---|
| 1025 | _GLIBCXX_END_NAMESPACE_VERSION
|
---|
| 1026 | } // namespace
|
---|
| 1027 |
|
---|
| 1028 | namespace std _GLIBCXX_VISIBILITY(default)
|
---|
| 1029 | {
|
---|
| 1030 | _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
---|
| 1031 |
|
---|
| 1032 | // Specialization of insert_iterator so that insertions will be constant
|
---|
| 1033 | // time rather than linear time.
|
---|
| 1034 | template <class _Tp, class _Alloc>
|
---|
| 1035 | class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> >
|
---|
| 1036 | {
|
---|
| 1037 | protected:
|
---|
| 1038 | typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;
|
---|
| 1039 | _Container* container;
|
---|
| 1040 | typename _Container::iterator iter;
|
---|
| 1041 |
|
---|
| 1042 | public:
|
---|
| 1043 | typedef _Container container_type;
|
---|
| 1044 | typedef output_iterator_tag iterator_category;
|
---|
| 1045 | typedef void value_type;
|
---|
| 1046 | typedef void difference_type;
|
---|
| 1047 | typedef void pointer;
|
---|
| 1048 | typedef void reference;
|
---|
| 1049 |
|
---|
| 1050 | insert_iterator(_Container& __x, typename _Container::iterator __i)
|
---|
| 1051 | : container(&__x)
|
---|
| 1052 | {
|
---|
| 1053 | if (__i == __x.begin())
|
---|
| 1054 | iter = __x.before_begin();
|
---|
| 1055 | else
|
---|
| 1056 | iter = __x.previous(__i);
|
---|
| 1057 | }
|
---|
| 1058 |
|
---|
| 1059 | insert_iterator<_Container>&
|
---|
| 1060 | operator=(const typename _Container::value_type& __value)
|
---|
| 1061 | {
|
---|
| 1062 | iter = container->insert_after(iter, __value);
|
---|
| 1063 | return *this;
|
---|
| 1064 | }
|
---|
| 1065 |
|
---|
| 1066 | insert_iterator<_Container>&
|
---|
| 1067 | operator*()
|
---|
| 1068 | { return *this; }
|
---|
| 1069 |
|
---|
| 1070 | insert_iterator<_Container>&
|
---|
| 1071 | operator++()
|
---|
| 1072 | { return *this; }
|
---|
| 1073 |
|
---|
| 1074 | insert_iterator<_Container>&
|
---|
| 1075 | operator++(int)
|
---|
| 1076 | { return *this; }
|
---|
| 1077 | };
|
---|
| 1078 |
|
---|
| 1079 | _GLIBCXX_END_NAMESPACE_VERSION
|
---|
| 1080 | } // namespace
|
---|
| 1081 |
|
---|
| 1082 | #endif
|
---|