197403Sobrien// List implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996,1997 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_list.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien */ 6197403Sobrien 62132720Skan#ifndef _LIST_H 63132720Skan#define _LIST_H 1 6497403Sobrien 6597403Sobrien#include <bits/concept_check.h> 6697403Sobrien 67169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 68169691Skan 69117397Skan // Supporting structures are split into common and templated types; the 70117397Skan // latter publicly inherits from the former in an effort to reduce code 71117397Skan // duplication. This results in some "needless" static_cast'ing later on, 72117397Skan // but it's all safe downcasting. 73132720Skan 74117397Skan /// @if maint Common part of a node in the %list. @endif 7597403Sobrien struct _List_node_base 7697403Sobrien { 77117397Skan _List_node_base* _M_next; ///< Self-explanatory 78117397Skan _List_node_base* _M_prev; ///< Self-explanatory 79132720Skan 80132720Skan static void 81132720Skan swap(_List_node_base& __x, _List_node_base& __y); 82132720Skan 83132720Skan void 84132720Skan transfer(_List_node_base * const __first, 85132720Skan _List_node_base * const __last); 86132720Skan 87132720Skan void 88132720Skan reverse(); 89132720Skan 90132720Skan void 91132720Skan hook(_List_node_base * const __position); 92132720Skan 93132720Skan void 94132720Skan unhook(); 9597403Sobrien }; 96132720Skan 97117397Skan /// @if maint An actual node in the %list. @endif 9897403Sobrien template<typename _Tp> 9997403Sobrien struct _List_node : public _List_node_base 100132720Skan { 101132720Skan _Tp _M_data; ///< User's data. 102132720Skan }; 103132720Skan 104117397Skan /** 105117397Skan * @brief A list::iterator. 106117397Skan * 107117397Skan * @if maint 108117397Skan * All the functions are op overloads. 109117397Skan * @endif 110117397Skan */ 111132720Skan template<typename _Tp> 112132720Skan struct _List_iterator 11397403Sobrien { 114169691Skan typedef _List_iterator<_Tp> _Self; 115169691Skan typedef _List_node<_Tp> _Node; 116132720Skan 117169691Skan typedef ptrdiff_t difference_type; 118169691Skan typedef std::bidirectional_iterator_tag iterator_category; 119169691Skan typedef _Tp value_type; 120169691Skan typedef _Tp* pointer; 121169691Skan typedef _Tp& reference; 122132720Skan 123146897Skan _List_iterator() 124146897Skan : _M_node() { } 125132720Skan 126169691Skan explicit 127132720Skan _List_iterator(_List_node_base* __x) 128132720Skan : _M_node(__x) { } 129132720Skan 130132720Skan // Must downcast from List_node_base to _List_node to get to _M_data. 131132720Skan reference 132132720Skan operator*() const 133132720Skan { return static_cast<_Node*>(_M_node)->_M_data; } 134132720Skan 135132720Skan pointer 136132720Skan operator->() const 137132720Skan { return &static_cast<_Node*>(_M_node)->_M_data; } 138132720Skan 139132720Skan _Self& 140132720Skan operator++() 141132720Skan { 142132720Skan _M_node = _M_node->_M_next; 143132720Skan return *this; 144132720Skan } 145132720Skan 146132720Skan _Self 147132720Skan operator++(int) 148132720Skan { 149132720Skan _Self __tmp = *this; 150132720Skan _M_node = _M_node->_M_next; 151132720Skan return __tmp; 152132720Skan } 153132720Skan 154132720Skan _Self& 155132720Skan operator--() 156132720Skan { 157132720Skan _M_node = _M_node->_M_prev; 158132720Skan return *this; 159132720Skan } 160132720Skan 161132720Skan _Self 162132720Skan operator--(int) 163132720Skan { 164132720Skan _Self __tmp = *this; 165132720Skan _M_node = _M_node->_M_prev; 166132720Skan return __tmp; 167132720Skan } 168132720Skan 169132720Skan bool 170132720Skan operator==(const _Self& __x) const 171132720Skan { return _M_node == __x._M_node; } 172132720Skan 173132720Skan bool 174132720Skan operator!=(const _Self& __x) const 175132720Skan { return _M_node != __x._M_node; } 176132720Skan 177132720Skan // The only member points to the %list element. 178132720Skan _List_node_base* _M_node; 179132720Skan }; 180132720Skan 181117397Skan /** 182132720Skan * @brief A list::const_iterator. 183132720Skan * 184117397Skan * @if maint 185132720Skan * All the functions are op overloads. 186117397Skan * @endif 187117397Skan */ 188132720Skan template<typename _Tp> 189132720Skan struct _List_const_iterator 190132720Skan { 191169691Skan typedef _List_const_iterator<_Tp> _Self; 192169691Skan typedef const _List_node<_Tp> _Node; 193169691Skan typedef _List_iterator<_Tp> iterator; 194132720Skan 195169691Skan typedef ptrdiff_t difference_type; 196169691Skan typedef std::bidirectional_iterator_tag iterator_category; 197169691Skan typedef _Tp value_type; 198169691Skan typedef const _Tp* pointer; 199169691Skan typedef const _Tp& reference; 200132720Skan 201146897Skan _List_const_iterator() 202146897Skan : _M_node() { } 203132720Skan 204169691Skan explicit 205132720Skan _List_const_iterator(const _List_node_base* __x) 206132720Skan : _M_node(__x) { } 207132720Skan 208132720Skan _List_const_iterator(const iterator& __x) 209132720Skan : _M_node(__x._M_node) { } 210132720Skan 211132720Skan // Must downcast from List_node_base to _List_node to get to 212132720Skan // _M_data. 213132720Skan reference 214132720Skan operator*() const 215132720Skan { return static_cast<_Node*>(_M_node)->_M_data; } 216132720Skan 217132720Skan pointer 218132720Skan operator->() const 219132720Skan { return &static_cast<_Node*>(_M_node)->_M_data; } 220132720Skan 221132720Skan _Self& 222132720Skan operator++() 223132720Skan { 224132720Skan _M_node = _M_node->_M_next; 225132720Skan return *this; 226132720Skan } 227132720Skan 228132720Skan _Self 229132720Skan operator++(int) 230132720Skan { 231132720Skan _Self __tmp = *this; 232132720Skan _M_node = _M_node->_M_next; 233132720Skan return __tmp; 234132720Skan } 235132720Skan 236132720Skan _Self& 237132720Skan operator--() 238132720Skan { 239132720Skan _M_node = _M_node->_M_prev; 240132720Skan return *this; 241132720Skan } 242132720Skan 243132720Skan _Self 244132720Skan operator--(int) 245132720Skan { 246132720Skan _Self __tmp = *this; 247132720Skan _M_node = _M_node->_M_prev; 248132720Skan return __tmp; 249132720Skan } 250132720Skan 251132720Skan bool 252132720Skan operator==(const _Self& __x) const 253132720Skan { return _M_node == __x._M_node; } 254132720Skan 255132720Skan bool 256132720Skan operator!=(const _Self& __x) const 257132720Skan { return _M_node != __x._M_node; } 258132720Skan 259132720Skan // The only member points to the %list element. 260132720Skan const _List_node_base* _M_node; 261132720Skan }; 262132720Skan 263132720Skan template<typename _Val> 264132720Skan inline bool 265132720Skan operator==(const _List_iterator<_Val>& __x, 266132720Skan const _List_const_iterator<_Val>& __y) 267132720Skan { return __x._M_node == __y._M_node; } 268132720Skan 269132720Skan template<typename _Val> 270132720Skan inline bool 271132720Skan operator!=(const _List_iterator<_Val>& __x, 272132720Skan const _List_const_iterator<_Val>& __y) 273132720Skan { return __x._M_node != __y._M_node; } 274132720Skan 275132720Skan 276117397Skan /** 277117397Skan * @if maint 278117397Skan * See bits/stl_deque.h's _Deque_base for an explanation. 279117397Skan * @endif 280117397Skan */ 281132720Skan template<typename _Tp, typename _Alloc> 282117397Skan class _List_base 283132720Skan { 284132720Skan protected: 285132720Skan // NOTA BENE 286132720Skan // The stored instance is not actually of "allocator_type"'s 287132720Skan // type. Instead we rebind the type to 288132720Skan // Allocator<List_node<Tp>>, which according to [20.1.5]/4 289132720Skan // should probably be the same. List_node<Tp> is not the same 290132720Skan // size as Tp (it's two pointers larger), and specializations on 291132720Skan // Tp may go unused because List_node<Tp> is being bound 292132720Skan // instead. 293132720Skan // 294132720Skan // We put this to the test in the constructors and in 295132720Skan // get_allocator, where we use conversions between 296169691Skan // allocator_type and _Node_alloc_type. The conversion is 297132720Skan // required by table 32 in [20.1.5]. 298132720Skan typedef typename _Alloc::template rebind<_List_node<_Tp> >::other 299169691Skan _Node_alloc_type; 300132720Skan 301169691Skan typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; 302132720Skan 303132720Skan struct _List_impl 304169691Skan : public _Node_alloc_type 305169691Skan { 306132720Skan _List_node_base _M_node; 307169691Skan 308236829Spfg _List_impl() 309236829Spfg : _Node_alloc_type(), _M_node() 310236829Spfg { } 311236829Spfg 312169691Skan _List_impl(const _Node_alloc_type& __a) 313169691Skan : _Node_alloc_type(__a), _M_node() 314132720Skan { } 315132720Skan }; 316132720Skan 317132720Skan _List_impl _M_impl; 318132720Skan 319132720Skan _List_node<_Tp>* 320132720Skan _M_get_node() 321169691Skan { return _M_impl._Node_alloc_type::allocate(1); } 322132720Skan 323132720Skan void 324132720Skan _M_put_node(_List_node<_Tp>* __p) 325169691Skan { _M_impl._Node_alloc_type::deallocate(__p, 1); } 326132720Skan 327117397Skan public: 328132720Skan typedef _Alloc allocator_type; 329132720Skan 330169691Skan _Node_alloc_type& 331169691Skan _M_get_Node_allocator() 332169691Skan { return *static_cast<_Node_alloc_type*>(&this->_M_impl); } 333169691Skan 334169691Skan const _Node_alloc_type& 335169691Skan _M_get_Node_allocator() const 336169691Skan { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); } 337169691Skan 338169691Skan _Tp_alloc_type 339169691Skan _M_get_Tp_allocator() const 340169691Skan { return _Tp_alloc_type(_M_get_Node_allocator()); } 341169691Skan 342132720Skan allocator_type 343132720Skan get_allocator() const 344169691Skan { return allocator_type(_M_get_Node_allocator()); } 345132720Skan 346236829Spfg _List_base() 347236829Spfg : _M_impl() 348236829Spfg { _M_init(); } 349236829Spfg 350132720Skan _List_base(const allocator_type& __a) 351169691Skan : _M_impl(__a) 352132720Skan { _M_init(); } 353132720Skan 354132720Skan // This is what actually destroys the list. 355132720Skan ~_List_base() 356132720Skan { _M_clear(); } 357132720Skan 358132720Skan void 359132720Skan _M_clear(); 360132720Skan 361132720Skan void 362132720Skan _M_init() 363132720Skan { 364132720Skan this->_M_impl._M_node._M_next = &this->_M_impl._M_node; 365132720Skan this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; 366132720Skan } 367132720Skan }; 368132720Skan 36997403Sobrien /** 370132720Skan * @brief A standard container with linear time access to elements, 371132720Skan * and fixed time insertion/deletion at any point in the sequence. 372117397Skan * 37397403Sobrien * @ingroup Containers 37497403Sobrien * @ingroup Sequences 37597403Sobrien * 37697403Sobrien * Meets the requirements of a <a href="tables.html#65">container</a>, a 37797403Sobrien * <a href="tables.html#66">reversible container</a>, and a 37897403Sobrien * <a href="tables.html#67">sequence</a>, including the 37997403Sobrien * <a href="tables.html#68">optional sequence requirements</a> with the 38097403Sobrien * %exception of @c at and @c operator[]. 38197403Sobrien * 382132720Skan * This is a @e doubly @e linked %list. Traversal up and down the 383132720Skan * %list requires linear time, but adding and removing elements (or 384132720Skan * @e nodes) is done in constant time, regardless of where the 385132720Skan * change takes place. Unlike std::vector and std::deque, 386132720Skan * random-access iterators are not provided, so subscripting ( @c 387132720Skan * [] ) access is not allowed. For algorithms which only need 388132720Skan * sequential access, this lack makes no difference. 38997403Sobrien * 390132720Skan * Also unlike the other standard containers, std::list provides 391132720Skan * specialized algorithms %unique to linked lists, such as 392132720Skan * splicing, sorting, and in-place reversal. 393117397Skan * 394117397Skan * @if maint 395117397Skan * A couple points on memory allocation for list<Tp>: 396117397Skan * 397132720Skan * First, we never actually allocate a Tp, we allocate 398132720Skan * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure 399132720Skan * that after elements from %list<X,Alloc1> are spliced into 400132720Skan * %list<X,Alloc2>, destroying the memory of the second %list is a 401132720Skan * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. 402117397Skan * 403117397Skan * Second, a %list conceptually represented as 404117397Skan * @code 405117397Skan * A <---> B <---> C <---> D 406117397Skan * @endcode 407132720Skan * is actually circular; a link exists between A and D. The %list 408132720Skan * class holds (as its only data member) a private list::iterator 409132720Skan * pointing to @e D, not to @e A! To get to the head of the %list, 410132720Skan * we start at the tail and move forward by one. When this member 411132720Skan * iterator's next/previous pointers refer to itself, the %list is 412132720Skan * %empty. @endif 41397403Sobrien */ 414169691Skan template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 41597403Sobrien class list : protected _List_base<_Tp, _Alloc> 41697403Sobrien { 417132720Skan // concept requirements 418169691Skan typedef typename _Alloc::value_type _Alloc_value_type; 419132720Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 420169691Skan __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) 421132720Skan 422169691Skan typedef _List_base<_Tp, _Alloc> _Base; 423169691Skan typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; 424132720Skan 425132720Skan public: 426132720Skan typedef _Tp value_type; 427169691Skan typedef typename _Tp_alloc_type::pointer pointer; 428169691Skan typedef typename _Tp_alloc_type::const_pointer const_pointer; 429169691Skan typedef typename _Tp_alloc_type::reference reference; 430169691Skan typedef typename _Tp_alloc_type::const_reference const_reference; 431132720Skan typedef _List_iterator<_Tp> iterator; 432132720Skan typedef _List_const_iterator<_Tp> const_iterator; 433132720Skan typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 434132720Skan typedef std::reverse_iterator<iterator> reverse_iterator; 435132720Skan typedef size_t size_type; 436132720Skan typedef ptrdiff_t difference_type; 437169691Skan typedef _Alloc allocator_type; 438132720Skan 439132720Skan protected: 440132720Skan // Note that pointers-to-_Node's can be ctor-converted to 441132720Skan // iterator types. 442169691Skan typedef _List_node<_Tp> _Node; 443132720Skan 444132720Skan using _Base::_M_impl; 445132720Skan using _Base::_M_put_node; 446132720Skan using _Base::_M_get_node; 447169691Skan using _Base::_M_get_Tp_allocator; 448169691Skan using _Base::_M_get_Node_allocator; 449132720Skan 450132720Skan /** 451132720Skan * @if maint 452132720Skan * @param x An instance of user data. 453132720Skan * 454132720Skan * Allocates space for a new node and constructs a copy of @a x in it. 455132720Skan * @endif 456132720Skan */ 457132720Skan _Node* 458132720Skan _M_create_node(const value_type& __x) 45997403Sobrien { 460132720Skan _Node* __p = this->_M_get_node(); 461132720Skan try 462132720Skan { 463169691Skan _M_get_Tp_allocator().construct(&__p->_M_data, __x); 464132720Skan } 465132720Skan catch(...) 466132720Skan { 467132720Skan _M_put_node(__p); 468132720Skan __throw_exception_again; 469132720Skan } 470132720Skan return __p; 47197403Sobrien } 472132720Skan 473132720Skan public: 474132720Skan // [23.2.2.1] construct/copy/destroy 475132720Skan // (assign() and get_allocator() are also listed in this section) 476132720Skan /** 477132720Skan * @brief Default constructor creates no elements. 478132720Skan */ 479236829Spfg list() 480236829Spfg : _Base() { } 481236829Spfg 482132720Skan explicit 483236829Spfg list(const allocator_type& __a) 484132720Skan : _Base(__a) { } 485132720Skan 486132720Skan /** 487132720Skan * @brief Create a %list with copies of an exemplar element. 488132720Skan * @param n The number of elements to initially create. 489132720Skan * @param value An element to copy. 490132720Skan * 491132720Skan * This constructor fills the %list with @a n copies of @a value. 492132720Skan */ 493169691Skan explicit 494169691Skan list(size_type __n, const value_type& __value = value_type(), 495132720Skan const allocator_type& __a = allocator_type()) 49697403Sobrien : _Base(__a) 497169691Skan { _M_fill_initialize(__n, __value); } 498132720Skan 499132720Skan /** 500132720Skan * @brief %List copy constructor. 501132720Skan * @param x A %list of identical element and allocator types. 502132720Skan * 503132720Skan * The newly-created %list uses a copy of the allocation object used 504132720Skan * by @a x. 505132720Skan */ 506132720Skan list(const list& __x) 507169691Skan : _Base(__x._M_get_Node_allocator()) 508169691Skan { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } 509132720Skan 510132720Skan /** 511132720Skan * @brief Builds a %list from a range. 512132720Skan * @param first An input iterator. 513132720Skan * @param last An input iterator. 514132720Skan * 515132720Skan * Create a %list consisting of copies of the elements from 516132720Skan * [@a first,@a last). This is linear in N (where N is 517132720Skan * distance(@a first,@a last)). 518132720Skan */ 519132720Skan template<typename _InputIterator> 520132720Skan list(_InputIterator __first, _InputIterator __last, 521132720Skan const allocator_type& __a = allocator_type()) 522132720Skan : _Base(__a) 523169691Skan { 524169691Skan // Check whether it's an integral type. If so, it's not an iterator. 525169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 526169691Skan _M_initialize_dispatch(__first, __last, _Integral()); 527169691Skan } 528132720Skan 529132720Skan /** 530132720Skan * No explicit dtor needed as the _Base dtor takes care of 531132720Skan * things. The _Base dtor only erases the elements, and note 532132720Skan * that if the elements themselves are pointers, the pointed-to 533132720Skan * memory is not touched in any way. Managing the pointer is 534132720Skan * the user's responsibilty. 535132720Skan */ 536132720Skan 537132720Skan /** 538132720Skan * @brief %List assignment operator. 539132720Skan * @param x A %list of identical element and allocator types. 540132720Skan * 541132720Skan * All the elements of @a x are copied, but unlike the copy 542132720Skan * constructor, the allocator object is not copied. 543132720Skan */ 544132720Skan list& 545132720Skan operator=(const list& __x); 546132720Skan 547132720Skan /** 548132720Skan * @brief Assigns a given value to a %list. 549132720Skan * @param n Number of elements to be assigned. 550132720Skan * @param val Value to be assigned. 551132720Skan * 552132720Skan * This function fills a %list with @a n copies of the given 553132720Skan * value. Note that the assignment completely changes the %list 554132720Skan * and that the resulting %list's size is the same as the number 555132720Skan * of elements assigned. Old data may be lost. 556132720Skan */ 55797403Sobrien void 558132720Skan assign(size_type __n, const value_type& __val) 559132720Skan { _M_fill_assign(__n, __val); } 560132720Skan 561132720Skan /** 562132720Skan * @brief Assigns a range to a %list. 563132720Skan * @param first An input iterator. 564132720Skan * @param last An input iterator. 565132720Skan * 566132720Skan * This function fills a %list with copies of the elements in the 567132720Skan * range [@a first,@a last). 568132720Skan * 569132720Skan * Note that the assignment completely changes the %list and 570132720Skan * that the resulting %list's size is the same as the number of 571132720Skan * elements assigned. Old data may be lost. 572132720Skan */ 573132720Skan template<typename _InputIterator> 574132720Skan void 575132720Skan assign(_InputIterator __first, _InputIterator __last) 576132720Skan { 577132720Skan // Check whether it's an integral type. If so, it's not an iterator. 578169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 579132720Skan _M_assign_dispatch(__first, __last, _Integral()); 580132720Skan } 581132720Skan 582132720Skan /// Get a copy of the memory allocation object. 583132720Skan allocator_type 584132720Skan get_allocator() const 585132720Skan { return _Base::get_allocator(); } 586132720Skan 587132720Skan // iterators 588132720Skan /** 589132720Skan * Returns a read/write iterator that points to the first element in the 590132720Skan * %list. Iteration is done in ordinary element order. 591132720Skan */ 592132720Skan iterator 593132720Skan begin() 594169691Skan { return iterator(this->_M_impl._M_node._M_next); } 595132720Skan 596132720Skan /** 597132720Skan * Returns a read-only (constant) iterator that points to the 598132720Skan * first element in the %list. Iteration is done in ordinary 599132720Skan * element order. 600132720Skan */ 601132720Skan const_iterator 602132720Skan begin() const 603169691Skan { return const_iterator(this->_M_impl._M_node._M_next); } 604132720Skan 605132720Skan /** 606132720Skan * Returns a read/write iterator that points one past the last 607132720Skan * element in the %list. Iteration is done in ordinary element 608132720Skan * order. 609132720Skan */ 610132720Skan iterator 611169691Skan end() 612169691Skan { return iterator(&this->_M_impl._M_node); } 613132720Skan 614132720Skan /** 615132720Skan * Returns a read-only (constant) iterator that points one past 616132720Skan * the last element in the %list. Iteration is done in ordinary 617132720Skan * element order. 618132720Skan */ 619132720Skan const_iterator 620132720Skan end() const 621169691Skan { return const_iterator(&this->_M_impl._M_node); } 622132720Skan 623132720Skan /** 624132720Skan * Returns a read/write reverse iterator that points to the last 625132720Skan * element in the %list. Iteration is done in reverse element 626132720Skan * order. 627132720Skan */ 628132720Skan reverse_iterator 629132720Skan rbegin() 630132720Skan { return reverse_iterator(end()); } 631132720Skan 632132720Skan /** 633132720Skan * Returns a read-only (constant) reverse iterator that points to 634132720Skan * the last element in the %list. Iteration is done in reverse 635132720Skan * element order. 636132720Skan */ 637132720Skan const_reverse_iterator 638132720Skan rbegin() const 639132720Skan { return const_reverse_iterator(end()); } 640132720Skan 641132720Skan /** 642132720Skan * Returns a read/write reverse iterator that points to one 643132720Skan * before the first element in the %list. Iteration is done in 644132720Skan * reverse element order. 645132720Skan */ 646132720Skan reverse_iterator 647132720Skan rend() 648132720Skan { return reverse_iterator(begin()); } 649132720Skan 650132720Skan /** 651132720Skan * Returns a read-only (constant) reverse iterator that points to one 652132720Skan * before the first element in the %list. Iteration is done in reverse 653132720Skan * element order. 654132720Skan */ 655132720Skan const_reverse_iterator 656132720Skan rend() const 657132720Skan { return const_reverse_iterator(begin()); } 658132720Skan 659132720Skan // [23.2.2.2] capacity 660132720Skan /** 661132720Skan * Returns true if the %list is empty. (Thus begin() would equal 662132720Skan * end().) 663132720Skan */ 664132720Skan bool 665132720Skan empty() const 666132720Skan { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } 667132720Skan 668132720Skan /** Returns the number of elements in the %list. */ 669132720Skan size_type 670132720Skan size() const 671132720Skan { return std::distance(begin(), end()); } 672132720Skan 673132720Skan /** Returns the size() of the largest possible %list. */ 674132720Skan size_type 675132720Skan max_size() const 676169691Skan { return _M_get_Tp_allocator().max_size(); } 677132720Skan 678132720Skan /** 679132720Skan * @brief Resizes the %list to the specified number of elements. 680132720Skan * @param new_size Number of elements the %list should contain. 681132720Skan * @param x Data with which new elements should be populated. 682132720Skan * 683132720Skan * This function will %resize the %list to the specified number 684132720Skan * of elements. If the number is smaller than the %list's 685132720Skan * current size the %list is truncated, otherwise the %list is 686132720Skan * extended and new elements are populated with given data. 687132720Skan */ 688132720Skan void 689169691Skan resize(size_type __new_size, value_type __x = value_type()); 690132720Skan 691132720Skan // element access 692132720Skan /** 693132720Skan * Returns a read/write reference to the data at the first 694132720Skan * element of the %list. 695132720Skan */ 696132720Skan reference 697132720Skan front() 698132720Skan { return *begin(); } 699132720Skan 700132720Skan /** 701132720Skan * Returns a read-only (constant) reference to the data at the first 702132720Skan * element of the %list. 703132720Skan */ 704132720Skan const_reference 705132720Skan front() const 706132720Skan { return *begin(); } 707132720Skan 708132720Skan /** 709132720Skan * Returns a read/write reference to the data at the last element 710132720Skan * of the %list. 711132720Skan */ 712132720Skan reference 713132720Skan back() 714169691Skan { 715169691Skan iterator __tmp = end(); 716169691Skan --__tmp; 717169691Skan return *__tmp; 718169691Skan } 719132720Skan 720132720Skan /** 721132720Skan * Returns a read-only (constant) reference to the data at the last 722132720Skan * element of the %list. 723132720Skan */ 724132720Skan const_reference 725132720Skan back() const 726169691Skan { 727169691Skan const_iterator __tmp = end(); 728169691Skan --__tmp; 729169691Skan return *__tmp; 730169691Skan } 731132720Skan 732132720Skan // [23.2.2.3] modifiers 733132720Skan /** 734132720Skan * @brief Add data to the front of the %list. 735132720Skan * @param x Data to be added. 736132720Skan * 737132720Skan * This is a typical stack operation. The function creates an 738132720Skan * element at the front of the %list and assigns the given data 739132720Skan * to it. Due to the nature of a %list this operation can be 740132720Skan * done in constant time, and does not invalidate iterators and 741132720Skan * references. 742132720Skan */ 743132720Skan void 744132720Skan push_front(const value_type& __x) 745132720Skan { this->_M_insert(begin(), __x); } 746132720Skan 747132720Skan /** 748132720Skan * @brief Removes first element. 749132720Skan * 750132720Skan * This is a typical stack operation. It shrinks the %list by 751132720Skan * one. Due to the nature of a %list this operation can be done 752132720Skan * in constant time, and only invalidates iterators/references to 753132720Skan * the element being removed. 754132720Skan * 755132720Skan * Note that no data is returned, and if the first element's data 756132720Skan * is needed, it should be retrieved before pop_front() is 757132720Skan * called. 758132720Skan */ 759132720Skan void 760132720Skan pop_front() 761132720Skan { this->_M_erase(begin()); } 762132720Skan 763132720Skan /** 764132720Skan * @brief Add data to the end of the %list. 765132720Skan * @param x Data to be added. 766132720Skan * 767132720Skan * This is a typical stack operation. The function creates an 768132720Skan * element at the end of the %list and assigns the given data to 769132720Skan * it. Due to the nature of a %list this operation can be done 770132720Skan * in constant time, and does not invalidate iterators and 771132720Skan * references. 772132720Skan */ 773132720Skan void 774132720Skan push_back(const value_type& __x) 775132720Skan { this->_M_insert(end(), __x); } 776132720Skan 777132720Skan /** 778132720Skan * @brief Removes last element. 779132720Skan * 780132720Skan * This is a typical stack operation. It shrinks the %list by 781132720Skan * one. Due to the nature of a %list this operation can be done 782132720Skan * in constant time, and only invalidates iterators/references to 783132720Skan * the element being removed. 784132720Skan * 785132720Skan * Note that no data is returned, and if the last element's data 786132720Skan * is needed, it should be retrieved before pop_back() is called. 787132720Skan */ 788132720Skan void 789132720Skan pop_back() 790169691Skan { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } 791132720Skan 792132720Skan /** 793132720Skan * @brief Inserts given value into %list before specified iterator. 794132720Skan * @param position An iterator into the %list. 795132720Skan * @param x Data to be inserted. 796132720Skan * @return An iterator that points to the inserted data. 797132720Skan * 798132720Skan * This function will insert a copy of the given value before 799132720Skan * the specified location. Due to the nature of a %list this 800132720Skan * operation can be done in constant time, and does not 801132720Skan * invalidate iterators and references. 802132720Skan */ 803132720Skan iterator 804132720Skan insert(iterator __position, const value_type& __x); 805132720Skan 806132720Skan /** 807132720Skan * @brief Inserts a number of copies of given data into the %list. 808132720Skan * @param position An iterator into the %list. 809132720Skan * @param n Number of elements to be inserted. 810132720Skan * @param x Data to be inserted. 811132720Skan * 812132720Skan * This function will insert a specified number of copies of the 813132720Skan * given data before the location specified by @a position. 814132720Skan * 815169691Skan * This operation is linear in the number of elements inserted and 816169691Skan * does not invalidate iterators and references. 817132720Skan */ 818132720Skan void 819132720Skan insert(iterator __position, size_type __n, const value_type& __x) 820169691Skan { 821169691Skan list __tmp(__n, __x, _M_get_Node_allocator()); 822169691Skan splice(__position, __tmp); 823169691Skan } 824132720Skan 825132720Skan /** 826132720Skan * @brief Inserts a range into the %list. 827132720Skan * @param position An iterator into the %list. 828132720Skan * @param first An input iterator. 829132720Skan * @param last An input iterator. 830132720Skan * 831132720Skan * This function will insert copies of the data in the range [@a 832132720Skan * first,@a last) into the %list before the location specified by 833132720Skan * @a position. 834132720Skan * 835169691Skan * This operation is linear in the number of elements inserted and 836169691Skan * does not invalidate iterators and references. 837132720Skan */ 838132720Skan template<typename _InputIterator> 839132720Skan void 840132720Skan insert(iterator __position, _InputIterator __first, 841132720Skan _InputIterator __last) 842132720Skan { 843169691Skan list __tmp(__first, __last, _M_get_Node_allocator()); 844169691Skan splice(__position, __tmp); 845132720Skan } 846132720Skan 847132720Skan /** 848132720Skan * @brief Remove element at given position. 849132720Skan * @param position Iterator pointing to element to be erased. 850132720Skan * @return An iterator pointing to the next element (or end()). 851132720Skan * 852132720Skan * This function will erase the element at the given position and thus 853132720Skan * shorten the %list by one. 854132720Skan * 855132720Skan * Due to the nature of a %list this operation can be done in 856132720Skan * constant time, and only invalidates iterators/references to 857132720Skan * the element being removed. The user is also cautioned that 858132720Skan * this function only erases the element, and that if the element 859132720Skan * is itself a pointer, the pointed-to memory is not touched in 860132720Skan * any way. Managing the pointer is the user's responsibilty. 861132720Skan */ 862132720Skan iterator 863132720Skan erase(iterator __position); 864132720Skan 865132720Skan /** 866132720Skan * @brief Remove a range of elements. 867132720Skan * @param first Iterator pointing to the first element to be erased. 868132720Skan * @param last Iterator pointing to one past the last element to be 869132720Skan * erased. 870132720Skan * @return An iterator pointing to the element pointed to by @a last 871132720Skan * prior to erasing (or end()). 872132720Skan * 873132720Skan * This function will erase the elements in the range @a 874132720Skan * [first,last) and shorten the %list accordingly. 875132720Skan * 876169691Skan * This operation is linear time in the size of the range and only 877169691Skan * invalidates iterators/references to the element being removed. 878169691Skan * The user is also cautioned that this function only erases the 879169691Skan * elements, and that if the elements themselves are pointers, the 880169691Skan * pointed-to memory is not touched in any way. Managing the pointer 881169691Skan * is the user's responsibilty. 882132720Skan */ 883132720Skan iterator 884132720Skan erase(iterator __first, iterator __last) 88597403Sobrien { 886132720Skan while (__first != __last) 887132720Skan __first = erase(__first); 888132720Skan return __last; 88997403Sobrien } 890132720Skan 891132720Skan /** 892132720Skan * @brief Swaps data with another %list. 893132720Skan * @param x A %list of the same element and allocator types. 894132720Skan * 895132720Skan * This exchanges the elements between two lists in constant 896132720Skan * time. Note that the global std::swap() function is 897132720Skan * specialized such that std::swap(l1,l2) will feed to this 898132720Skan * function. 899132720Skan */ 90097403Sobrien void 901132720Skan swap(list& __x) 902169691Skan { 903169691Skan _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); 904132720Skan 905169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 906169691Skan // 431. Swapping containers with unequal allocators. 907169691Skan std::__alloc_swap<typename _Base::_Node_alloc_type>:: 908169691Skan _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); 909169691Skan } 910169691Skan 911132720Skan /** 912132720Skan * Erases all the elements. Note that this function only erases 913132720Skan * the elements, and that if the elements themselves are 914132720Skan * pointers, the pointed-to memory is not touched in any way. 915132720Skan * Managing the pointer is the user's responsibilty. 916132720Skan */ 917132720Skan void 918132720Skan clear() 91997403Sobrien { 920132720Skan _Base::_M_clear(); 921132720Skan _Base::_M_init(); 92297403Sobrien } 923132720Skan 924132720Skan // [23.2.2.4] list operations 925132720Skan /** 926132720Skan * @brief Insert contents of another %list. 927132720Skan * @param position Iterator referencing the element to insert before. 928132720Skan * @param x Source list. 929132720Skan * 930132720Skan * The elements of @a x are inserted in constant time in front of 931132720Skan * the element referenced by @a position. @a x becomes an empty 932132720Skan * list. 933169691Skan * 934169691Skan * Requires this != @a x. 935132720Skan */ 93697403Sobrien void 937132720Skan splice(iterator __position, list& __x) 938132720Skan { 939132720Skan if (!__x.empty()) 940169691Skan { 941169691Skan _M_check_equal_allocators(__x); 942169691Skan 943169691Skan this->_M_transfer(__position, __x.begin(), __x.end()); 944169691Skan } 945132720Skan } 946132720Skan 947132720Skan /** 948132720Skan * @brief Insert element from another %list. 949132720Skan * @param position Iterator referencing the element to insert before. 950132720Skan * @param x Source list. 951132720Skan * @param i Iterator referencing the element to move. 952132720Skan * 953132720Skan * Removes the element in list @a x referenced by @a i and 954132720Skan * inserts it into the current list before @a position. 955132720Skan */ 956132720Skan void 957169691Skan splice(iterator __position, list& __x, iterator __i) 958132720Skan { 959132720Skan iterator __j = __i; 960132720Skan ++__j; 961132720Skan if (__position == __i || __position == __j) 962132720Skan return; 963169691Skan 964169691Skan if (this != &__x) 965169691Skan _M_check_equal_allocators(__x); 966169691Skan 967132720Skan this->_M_transfer(__position, __i, __j); 968132720Skan } 969132720Skan 970132720Skan /** 971132720Skan * @brief Insert range from another %list. 972132720Skan * @param position Iterator referencing the element to insert before. 973132720Skan * @param x Source list. 974132720Skan * @param first Iterator referencing the start of range in x. 975132720Skan * @param last Iterator referencing the end of range in x. 976132720Skan * 977132720Skan * Removes elements in the range [first,last) and inserts them 978132720Skan * before @a position in constant time. 979132720Skan * 980132720Skan * Undefined if @a position is in [first,last). 981132720Skan */ 982132720Skan void 983169691Skan splice(iterator __position, list& __x, iterator __first, iterator __last) 984132720Skan { 985132720Skan if (__first != __last) 986169691Skan { 987169691Skan if (this != &__x) 988169691Skan _M_check_equal_allocators(__x); 989169691Skan 990169691Skan this->_M_transfer(__position, __first, __last); 991169691Skan } 992132720Skan } 993132720Skan 994132720Skan /** 995132720Skan * @brief Remove all elements equal to value. 996132720Skan * @param value The value to remove. 997132720Skan * 998132720Skan * Removes every element in the list equal to @a value. 999132720Skan * Remaining elements stay in list order. Note that this 1000132720Skan * function only erases the elements, and that if the elements 1001132720Skan * themselves are pointers, the pointed-to memory is not 1002132720Skan * touched in any way. Managing the pointer is the user's 1003132720Skan * responsibilty. 1004132720Skan */ 1005132720Skan void 1006132720Skan remove(const _Tp& __value); 1007132720Skan 1008132720Skan /** 1009132720Skan * @brief Remove all elements satisfying a predicate. 1010132720Skan * @param Predicate Unary predicate function or object. 1011132720Skan * 1012132720Skan * Removes every element in the list for which the predicate 1013132720Skan * returns true. Remaining elements stay in list order. Note 1014132720Skan * that this function only erases the elements, and that if the 1015132720Skan * elements themselves are pointers, the pointed-to memory is 1016132720Skan * not touched in any way. Managing the pointer is the user's 1017132720Skan * responsibilty. 1018132720Skan */ 1019132720Skan template<typename _Predicate> 1020169691Skan void 1021169691Skan remove_if(_Predicate); 1022132720Skan 1023132720Skan /** 1024132720Skan * @brief Remove consecutive duplicate elements. 1025132720Skan * 1026132720Skan * For each consecutive set of elements with the same value, 1027132720Skan * remove all but the first one. Remaining elements stay in 1028132720Skan * list order. Note that this function only erases the 1029132720Skan * elements, and that if the elements themselves are pointers, 1030132720Skan * the pointed-to memory is not touched in any way. Managing 1031132720Skan * the pointer is the user's responsibilty. 1032132720Skan */ 103397403Sobrien void 1034132720Skan unique(); 1035132720Skan 1036132720Skan /** 1037132720Skan * @brief Remove consecutive elements satisfying a predicate. 1038132720Skan * @param BinaryPredicate Binary predicate function or object. 1039132720Skan * 1040132720Skan * For each consecutive set of elements [first,last) that 1041132720Skan * satisfy predicate(first,i) where i is an iterator in 1042132720Skan * [first,last), remove all but the first one. Remaining 1043132720Skan * elements stay in list order. Note that this function only 1044132720Skan * erases the elements, and that if the elements themselves are 1045132720Skan * pointers, the pointed-to memory is not touched in any way. 1046132720Skan * Managing the pointer is the user's responsibilty. 1047132720Skan */ 1048132720Skan template<typename _BinaryPredicate> 1049132720Skan void 1050132720Skan unique(_BinaryPredicate); 1051132720Skan 1052132720Skan /** 1053132720Skan * @brief Merge sorted lists. 1054132720Skan * @param x Sorted list to merge. 1055132720Skan * 1056132720Skan * Assumes that both @a x and this list are sorted according to 1057132720Skan * operator<(). Merges elements of @a x into this list in 1058132720Skan * sorted order, leaving @a x empty when complete. Elements in 1059132720Skan * this list precede elements in @a x that are equal. 1060132720Skan */ 106197403Sobrien void 1062132720Skan merge(list& __x); 1063132720Skan 1064132720Skan /** 1065132720Skan * @brief Merge sorted lists according to comparison function. 1066132720Skan * @param x Sorted list to merge. 1067132720Skan * @param StrictWeakOrdering Comparison function definining 1068132720Skan * sort order. 1069132720Skan * 1070132720Skan * Assumes that both @a x and this list are sorted according to 1071132720Skan * StrictWeakOrdering. Merges elements of @a x into this list 1072132720Skan * in sorted order, leaving @a x empty when complete. Elements 1073132720Skan * in this list precede elements in @a x that are equivalent 1074132720Skan * according to StrictWeakOrdering(). 1075132720Skan */ 1076132720Skan template<typename _StrictWeakOrdering> 1077132720Skan void 1078132720Skan merge(list&, _StrictWeakOrdering); 1079132720Skan 1080132720Skan /** 1081132720Skan * @brief Reverse the elements in list. 1082132720Skan * 1083132720Skan * Reverse the order of elements in the list in linear time. 1084132720Skan */ 108597403Sobrien void 1086132720Skan reverse() 1087132720Skan { this->_M_impl._M_node.reverse(); } 1088132720Skan 1089132720Skan /** 1090132720Skan * @brief Sort the elements. 1091132720Skan * 1092132720Skan * Sorts the elements of this list in NlogN time. Equivalent 1093132720Skan * elements remain in list order. 1094132720Skan */ 109597403Sobrien void 1096132720Skan sort(); 1097132720Skan 1098132720Skan /** 1099132720Skan * @brief Sort the elements according to comparison function. 1100132720Skan * 1101132720Skan * Sorts the elements of this list in NlogN time. Equivalent 1102132720Skan * elements remain in list order. 1103132720Skan */ 1104132720Skan template<typename _StrictWeakOrdering> 1105132720Skan void 1106132720Skan sort(_StrictWeakOrdering); 1107132720Skan 1108132720Skan protected: 1109169691Skan // Internal constructor functions follow. 1110132720Skan 1111169691Skan // Called by the range constructor to implement [23.1.1]/9 1112132720Skan template<typename _Integer> 1113132720Skan void 1114169691Skan _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 1115132720Skan { 1116169691Skan _M_fill_initialize(static_cast<size_type>(__n), 1117169691Skan static_cast<value_type>(__x)); 1118132720Skan } 1119132720Skan 1120169691Skan // Called by the range constructor to implement [23.1.1]/9 1121132720Skan template<typename _InputIterator> 1122132720Skan void 1123169691Skan _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1124169691Skan __false_type) 1125169691Skan { 1126169691Skan for (; __first != __last; ++__first) 1127169691Skan push_back(*__first); 1128169691Skan } 1129132720Skan 1130169691Skan // Called by list(n,v,a), and the range constructor when it turns out 1131132720Skan // to be the same thing. 1132132720Skan void 1133169691Skan _M_fill_initialize(size_type __n, const value_type& __x) 1134169691Skan { 1135169691Skan for (; __n > 0; --__n) 1136169691Skan push_back(__x); 1137169691Skan } 1138132720Skan 1139132720Skan 1140169691Skan // Internal assign functions follow. 1141132720Skan 1142169691Skan // Called by the range assign to implement [23.1.1]/9 1143132720Skan template<typename _Integer> 1144132720Skan void 1145169691Skan _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1146132720Skan { 1147169691Skan _M_fill_assign(static_cast<size_type>(__n), 1148169691Skan static_cast<value_type>(__val)); 1149132720Skan } 1150132720Skan 1151169691Skan // Called by the range assign to implement [23.1.1]/9 1152132720Skan template<typename _InputIterator> 1153132720Skan void 1154169691Skan _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1155169691Skan __false_type); 1156132720Skan 1157169691Skan // Called by assign(n,t), and the range assign when it turns out 1158132720Skan // to be the same thing. 1159132720Skan void 1160169691Skan _M_fill_assign(size_type __n, const value_type& __val); 1161132720Skan 1162132720Skan 1163132720Skan // Moves the elements from [first,last) before position. 116497403Sobrien void 1165132720Skan _M_transfer(iterator __position, iterator __first, iterator __last) 1166169691Skan { __position._M_node->transfer(__first._M_node, __last._M_node); } 1167132720Skan 1168132720Skan // Inserts new element at position given and with value given. 116997403Sobrien void 1170132720Skan _M_insert(iterator __position, const value_type& __x) 117197403Sobrien { 1172132720Skan _Node* __tmp = _M_create_node(__x); 1173132720Skan __tmp->hook(__position._M_node); 117497403Sobrien } 1175132720Skan 1176132720Skan // Erases element at position given. 117797403Sobrien void 1178132720Skan _M_erase(iterator __position) 117997403Sobrien { 1180132720Skan __position._M_node->unhook(); 1181132720Skan _Node* __n = static_cast<_Node*>(__position._M_node); 1182169691Skan _M_get_Tp_allocator().destroy(&__n->_M_data); 1183132720Skan _M_put_node(__n); 118497403Sobrien } 1185169691Skan 1186169691Skan // To implement the splice (and merge) bits of N1599. 1187169691Skan void 1188169691Skan _M_check_equal_allocators(list& __x) 1189169691Skan { 1190169691Skan if (_M_get_Node_allocator() != __x._M_get_Node_allocator()) 1191169691Skan __throw_runtime_error(__N("list::_M_check_equal_allocators")); 1192169691Skan } 1193132720Skan }; 1194132720Skan 1195117397Skan /** 1196117397Skan * @brief List equality comparison. 1197117397Skan * @param x A %list. 1198117397Skan * @param y A %list of the same type as @a x. 1199117397Skan * @return True iff the size and elements of the lists are equal. 1200117397Skan * 1201132720Skan * This is an equivalence relation. It is linear in the size of 1202132720Skan * the lists. Lists are considered equivalent if their sizes are 1203132720Skan * equal, and if corresponding elements compare equal. 1204117397Skan */ 120597403Sobrien template<typename _Tp, typename _Alloc> 1206132720Skan inline bool 1207169691Skan operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 120897403Sobrien { 1209169691Skan typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; 121097403Sobrien const_iterator __end1 = __x.end(); 121197403Sobrien const_iterator __end2 = __y.end(); 1212132720Skan 121397403Sobrien const_iterator __i1 = __x.begin(); 121497403Sobrien const_iterator __i2 = __y.begin(); 1215132720Skan while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 1216132720Skan { 1217132720Skan ++__i1; 1218132720Skan ++__i2; 1219132720Skan } 122097403Sobrien return __i1 == __end1 && __i2 == __end2; 122197403Sobrien } 1222132720Skan 1223117397Skan /** 1224117397Skan * @brief List ordering relation. 1225117397Skan * @param x A %list. 1226117397Skan * @param y A %list of the same type as @a x. 1227132720Skan * @return True iff @a x is lexicographically less than @a y. 1228117397Skan * 1229117397Skan * This is a total ordering relation. It is linear in the size of the 1230117397Skan * lists. The elements must be comparable with @c <. 1231117397Skan * 1232132720Skan * See std::lexicographical_compare() for how the determination is made. 1233117397Skan */ 123497403Sobrien template<typename _Tp, typename _Alloc> 123597403Sobrien inline bool 1236169691Skan operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 1237132720Skan { return std::lexicographical_compare(__x.begin(), __x.end(), 1238132720Skan __y.begin(), __y.end()); } 1239132720Skan 1240117397Skan /// Based on operator== 124197403Sobrien template<typename _Tp, typename _Alloc> 124297403Sobrien inline bool 1243169691Skan operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 124497403Sobrien { return !(__x == __y); } 1245132720Skan 1246117397Skan /// Based on operator< 124797403Sobrien template<typename _Tp, typename _Alloc> 124897403Sobrien inline bool 1249169691Skan operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 125097403Sobrien { return __y < __x; } 1251132720Skan 1252117397Skan /// Based on operator< 125397403Sobrien template<typename _Tp, typename _Alloc> 125497403Sobrien inline bool 1255169691Skan operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 125697403Sobrien { return !(__y < __x); } 1257132720Skan 1258117397Skan /// Based on operator< 125997403Sobrien template<typename _Tp, typename _Alloc> 126097403Sobrien inline bool 1261169691Skan operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 126297403Sobrien { return !(__x < __y); } 1263132720Skan 1264117397Skan /// See std::list::swap(). 126597403Sobrien template<typename _Tp, typename _Alloc> 1266117397Skan inline void 126797403Sobrien swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 126897403Sobrien { __x.swap(__y); } 126997403Sobrien 1270169691Skan_GLIBCXX_END_NESTED_NAMESPACE 1271169691Skan 1272132720Skan#endif /* _LIST_H */ 1273132720Skan 1274